akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b) {
  if (a < b) return gcd(b, a);
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K, maxn = 0;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    if (maxn < A[i]) maxn = A[i];
  }
  int g = A[0];
  for (int i = 1; i < N; i++)
    g = gcd(g, A[i]);
  if (K % g == 0 && maxn >= K)
    cout << "POSSIBLE" << '\n';
  else
    cout << "IMPOSSIBLE" << '\n';
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10,mod=1e9+7;
int n;
typedef long long ll;
ll a[maxn],b[62][2];
ll fpm(ll a,ll b){
    ll ret=1ll;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)ret=ret*a%mod;
    return ret;
}
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",a+i);
        for(int j=0;j<=60;++j){
            ++b[j][a[i]&1];
            a[i]>>=1;
        }
    }
    ll ans=0;
    for(int j=0;j<=60;++j){
        (ans+=b[j][0]*b[j][1]%mod*fpm(2,j)%mod)%=mod;
    }
    printf("%lld\n",ans);
}
int main(){
    solve();

    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll dp[1010][1010];
ll N, A, B, C, D;

const ll N_MAX = 1000005;

ll inv[N_MAX],fac[N_MAX],finv[N_MAX];
void make(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<N_MAX;i++){
        inv[i]=mod-inv[mod%i]*(mod/i)%mod;
        fac[i]=fac[i-1]*(ll) i%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

ll Combination(ll C, ll D){
    if(C<D||C<1) return 0;
    return fac[C]*(finv[D]*finv[C-D]%mod)%mod;
}

ll pows(ll x, ll k){
	if(k == 0) return 1;
	ll res = pows(x, k/2);
	if(k%2 == 0){
		return (res * res) % mod;
	}else{
		return res * res % mod * x % mod;
	}
}

ll rec(ll nok, ll val){
	if(dp[nok][val] >= 0) return dp[nok][val];
	if(val == B+1){
		if(nok == 0) return 1;
		else return 0;
	}
	ll res = 0;
	res += rec(nok, val+1);
	res %= mod;
	for(int i=C;i<=min((nok/val), D);i++){
		if(nok - val*i < 0) continue;
		ll tmp = rec(nok - val*i, val+1);
		tmp *= Combination(nok, nok - val*i);
		tmp %= mod;
		ll ue = fac[val*i];
		ll shita = modinv(fac[val], mod);
		shita = pows(shita, i);
		shita *= modinv(fac[i], mod);
		shita %= mod;
		ue *= shita;
		ue %= mod;
		tmp *= ue;
		tmp %= mod;
		res += tmp;
		res %= mod;
	}
	dp[nok][val] = res;
	return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> A >> B >> C >> D;
    make();

    REP(i, 1010)REP(j, 1010) dp[i][j] = -1;

    cout << rec(N, A) << endl;
    return 0;
}

Measured memory_bytes: 31744
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <stdio.h>
#include <string>
using namespace std;
#define ll long long
#define mod 1000000007;


int main() {
	int n, a[30], b[30], c[30], ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < n-1; i++) {
		cin >> c[i];
	}
	for (int i = 0; i < n; i++) {
		ans += b[a[i] - 1];
		if (i != 0 && a[i - 1] + 1 == a[i])ans += c[a[i-1] - 1];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  string s; cin >> s;
  cout << (s == "hi" || s == "hihi" || s == "hihihi" || s == "hihihihi" || s == "hihihihihi" ? "Yes" : "No") << endl;
  

  return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(){
	char ch;
	while((ch = getchar()) != EOF){
			if(ch >= 97 && ch <= 122)
				printf("%c",ch-32);
			else if(ch >= 65 && ch <= 90)
				printf("%c",ch+32);
			else
				printf("%c",ch);
	}
}



Measured memory_bytes: 2528
N = int(input())

def calc_digits_sum(n):
    return sum([int(i) for i in list(str(n))])

ans = float('inf')
for i in range(1, N):
    A = i
    B = N - i
    # print(A, B)
    a_sum = calc_digits_sum(A)
    b_sum = calc_digits_sum(B)
    # print(a_sum, b_sum)
    ans = min(ans, a_sum + b_sum)
    
print(ans)

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-

# 入力読み込み
nb_A = int(input())
A = list(map(int, input().split(" ")))

uniq_A = list(set(A))

if (nb_A - len(uniq_A)) % 2 == 1:
    print(len(uniq_A)-1)
else:
    print(len(uniq_A))

Measured memory_bytes: 14204
N = int(input())

C = []

for i in range(N):

    c = int(input())

    if len(C) == 0 or C[-1] != c-1:
        C.append(c-1)

lis = []
last = [-1] * (2 * (10**5))

for i in range(len(C)):

    if i == 0:
        lis.append(1)
    
    elif last[C[i]] == -1 or last[C[i]] == i-1:
        lis.append(lis[-1])

    else:
        lis.append(lis[-1]+lis[last[C[i]]])

    lis[-1] %= 10 ** 9 + 7
    last[C[i]] = i


print (lis[-1])


Measured memory_bytes: 73048
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct RMQ {
	using type = ll;
	static type id() { return LLONG_MIN; }
	static type op(const type& l, const type & r) { return max(l, r); }
};

template <typename M>
class SegmentTree {
	using T = typename M::type;
	const int n;
	vector<T> data;
	int size(int n) {
		int res;
		for (res = 1; res < n; res <<= 1);
		return res;
	}
public:
	SegmentTree(int n_) :
		n(size(n_)), data(n * 2, M::id()) {}
	void init(const vector<T>& data_) {
		for (int i = 0; i < (int)data_.size(); i++)
			data[i + n] = data_[i];
		for (int i = n - 1; i >= 0; i--)
			data[i] = M::op(data[i * 2], data[i * 2 + 1]);
	}
	void update(int p, T val) {
		p += n;
		data[p] = val;
		while (p >>= 1) data[p] = M::op(data[p * 2], data[p * 2 + 1]);
	}
	void add(int p, T val) {
		p += n;
		data[p] += val;
		while (p >>= 1) data[p] = M::op(data[p * 2], data[p * 2 + 1]);
	}
	T find(int l, int r) {
		l += n; r += n + 1;
		T res1 = M::id(), res2 = M::id();
		while (l < r) {
			if (l & 1) res1 = M::op(res1, data[l++]);
			if (r & 1) res2 = M::op(data[--r], res2);
			l >>= 1; r >>= 1;
		}
		return M::op(res1, res2);
	}
};

int main()
{
	int N;
	cin >> N;
	vector<ll> x(N), s(N), sum(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> s[i];
		sum[i] = s[i];
	}
	for (int i = 1; i < N; i++) {
		sum[i] += sum[i - 1];
	}
	for (int i = 0; i < N; i++) {
		sum[i] -= x[i];
	}
	SegmentTree<RMQ> st(N);
	st.init(sum);
	ll res = 0;
	for (int i = 0; i < N; i++) {
		res = max(res, s[i] + st.find(i, N - 1) - sum[i]);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 9088
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N,A,B,C;
vector<int> L(8);

int dfs(int depth,int a, int b, int c){
	if(depth == N){
		if(a==0 || b==0 || c==0)
			return 1e9;
		return abs(a-A)+abs(b-B)+abs(c-C);
	}
	int ans = 1e9;
	ans = min(ans, dfs(depth+1,a+L[depth],b,c)+(a >0 ? 10 : 0));
	ans = min(ans, dfs(depth+1,a,b+L[depth],c)+(b > 0 ? 10 : 0));
    ans = min(ans, dfs(depth+1,a,b,c+L[depth]) +(c > 0 ? 10 : 0));
    ans = min(ans, dfs(depth+1,a,b,c));
    return ans;
}

int main()
{	
	cin >> N >> A >> B >> C;

	for (int i = 0; i < N; i++)	{
		cin >> L[i];
	}
	cout << dfs(0,0,0,0) << endl;

	return 0;
}

Measured memory_bytes: 256
K, X = map(int, input().split())
MAX = 1000000
left = X - (K-1)
right = X + (K-1)

if left < -MAX:
    left = -MAX
    right = -MAX + (K-1)
elif right > MAX:
    right = MAX
    left = MAX - (K-1)

ret = range(left, right+1)
print(*ret)


Measured memory_bytes: 38384
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N, K = map(int, readline().split())
    H = list(map(int, readline().split()))
    H.sort()

    if N <= K:
        ans = 0
    else:
        ans = sum(H[:N - K])
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 105612
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

if __name__ == '__main__':
    a = [int(i) for i in input().split()]

    if a[0] >8 or a[1]>8:
        print(":(")
    else:
        print("Yay!")



Measured memory_bytes: 3828
#include <bits/stdc++.h>

using namespace std;

// void insertion(int a[], int n)
// {
//     for (int i = 1; i < n; i++)
//     {
//         int v = a[i];
//         int j = i - 1;
//         while (j >= 0 && a[j] > v)
//         {
//             a[j + 1] = a[j];
//             j--;
//         }
//         a[j + 1] = v;
//     }
// }
int a[1010];
int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; i++)
    {
        cout << a[i] << " ";
    }
    cout << a[n - 1];
    cout << endl;
    for (int i = 1; i < n; i++)
    {

        int v = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > v)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = v;
        for (int j = 0; j < n - 1; j++)
        {
            cout << a[j] << " ";
        }
        cout << a[n - 1];
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 3088
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
 
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
 
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
    
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
 
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
 
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
 
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
 
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
 
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
 
//
// # Examples
//
// # integers
// input! { n: usize, m: usize, ... }
//
// # array
// input! { n: usize, v: [i32; n], }
//
// # matrix
// input! { n: usize, m: usize, mat: [[]] }
//
// # string
// input! { s: chars }
//
// 3 4
// ####
// #..#
// .#.#
//
// input!{
//     h: usize,
//     w: usize,
//     board: [chars; h],
// }
 
// https://practice.contest.atcoder.jp/tasks/practice_1
fn main() {
    input! { n: i32, h: [i32;n] }
    let mut ans = 1;
    (1..n).fold(h[0], |mut acc, i| {
        let i = i as usize;
        if acc <= h[i] {
            ans += 1;
            acc = h[i];
        }
        acc
    });
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char p;
int k;
int num[105];
int tot=0;
ll f[105][4];

ll C(int n,int k){
	if (k<0 || k>n) return 0;
	ll s=1;
	for (int i=0;i<k;i++){
		s *= (n-i);
	}
	for (int i=1;i<=k;i++){
		s /= i;
	}
	return s;
}

ll pwr(int a,int x){
	ll s=1;
	for (int i=1;i<=x;i++){
		s *= a;
	}	
	return s;
}

int main(){
	while (p=getchar()){
		if (p=='\n') break;
		num[++tot]=(int)p-48;
	}
	cin >> k;
	f[0][0]=1;
	for (int i=1;i<=tot;i++){
		f[i][0]=1;
		for (int j=1;j<=k;j++){
			if (num[tot-i+1]==0){f[i][j]=f[i-1][j]; continue;}
			f[i][j] = C(i-1,j) * pwr(9,j); 
			f[i][j] += f[i-1][j-1];
			f[i][j] += ((num[tot-i+1]-1) * C(i-1,j-1) * pwr(9,j-1));
		}
	}
//	for (int i=0;i<=k;i++){
//		for (int j=0;j<=tot;j++){
//			cout << f[j][i] << ' ';
//		}
//		cout << endl;
//	}
	cout << f[tot][k];
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
 
using namespace std;

int main() {
    int N,M;

    cin >> N >> M;

    vector<int> H;

    for(int i = 0; i < N; i++){
        int h;
        cin >> h;

        H.push_back(h);
    }

    vector<vector<int>> A(N);

    for(int i = 0; i < M; i++){
        int a,b;
        cin >> a >> b;

        A[a-1].push_back(b-1);
        A[b-1].push_back(a-1);
    }

    int sum = 0;

    for(int i = 0; i < N; i++){
        bool f = true;
        for(int j = 0; j < A[i].size(); j++){
            if(H[i] <= H[A[i][j]]){
                f = false;
            }
        }

        if(f){
            sum++;
        }
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 8808
#include <stdio.h>

int main(void){
    int a,b;
    scanf("%d %d",&a,&b);

   if(a < b){
      printf("a < b\n");
   } else if(a > b){
      printf("a > b\n");
   } else {
      printf("a == b\n");
   }
  return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef long long ll;
typedef pair<int, int> pi;

int n;
vector<vector<pi> > adjList;
vector<int> vertex;

void dfs(int node, int parent, int flag){
    if (flag%2 == 0) vertex[node] = 1;
    else vertex[node] = 0;

    for (auto child : adjList[node]){
        if (child.first==parent) continue;
        dfs(child.first, node, flag+child.second);
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    adjList.assign(n, vector<pi>());
    vertex.resize(n);

    int u, v, w;
    for (int i=0;i<n-1;++i){
        cin>>u>>v>>w;
        u--; v--;
        adjList[u].push_back(make_pair(v, w));
        adjList[v].push_back(make_pair(u, w));
    }
    dfs(1, -1, 0);
    for (int i=0;i<n;++i) cout<<vertex[i]<<endl;

    return 0;
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = int_fast64_t;
using PAIR = pair<int, int>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 1e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<"\n";
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=0;--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

signed main() {
  INIT;
	VAR(int, n);
	int ans = 0, t = 1;
	FOR(i, 1, n + 1) {
		t *= 2;
		if (t > n) {
			ans = t / 2;
			break;
		}
	}
	OUT(ans)BR;
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rp(i,n) for(int i=0;i<n;i++)
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define lrp(i,n) for(long long i=0;i<n;i++)
#define lrep(i,m,n) for(long long i=m;i<=n;i++)
#define mrp(i,n) for(int i=n-1;i>=0;i--)
#define mrep(i,m,n) for(int i=m;i>=n;i--)
#define mlrp(i,n) for(long long i=n;i>=0;i--)
#define mlrep(i,m,n) for(long long i=m;i>=n;i--)
#define ll long long
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define abs(a,b) (a-b>0?a-b:b-a)

int main(){
    int n,m;
    cin >> n >> m;
    
    if(n==1){
        n=14;
    }
    if(m==1){
        m=14;
    }
    
    if(n==m){
        cout << "Draw" << endl;
    }else{
        cout << (n>m?"Alice":"Bob") << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main(void) {
    int N;
    cin >> N;
    vector<int> d(N);
    for(int i=0; i<N; i++) {
        cin >> d[i];
    }
    int answer = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<i; j++) {
            answer += d[i]*d[j];
        }
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

int main() {
	int N;
	cin >> N;

	string ans;
	for (int i = 1; i < 10; ++i) {
		if (0 < N / i && N / i < 10 && N % i == 0) {
			ans = "Yes";
			break;
		}
		else ans = "No";
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
// URL: https://atcoder.jp/contests/abc134/tasks/abc134_d

import std.algorithm, std.container, std.math, std.range, std.typecons, std.string;

version(unittest) {} else
void main()
{
  int n; io.getV(n);
  int[] a; io.getA(n, a);

  auto c = new int[](n);
  foreach_reverse (i; 0..n)
    c[i] = (c.indexed(iota(i, n, i+1)).sum + a[i]) % 2;

  io.put(c.count(1));
  io.put(c.enumerate.map!(e => e[1] ? e[0]+1 : 0).filter!"a".array);
}

auto io = IO();

struct IO
{
  import std.algorithm, std.conv, std.format, std.meta, std.range, std.stdio, std.traits;

  dchar[] buf;
  auto sp = (new dchar[](0)).splitter;
  int precision = 10;
  string delimiter = " ";

  void nextLine()
  {
    stdin.readln(buf);
    sp = buf.splitter;
  }

  auto get(T)(ref T v)
  {
    if (sp.empty) nextLine();
    v = sp.front.to!T;
    sp.popFront();
  }

  auto getV(T...)(ref T v)
  {
    foreach (ref w; v) get(w);
  }

  auto getA(T)(size_t n, ref T v)
  if (hasAssignableElements!T)
  {
    v = new T(n);
    foreach (ref w; v) get(w);
  }

  auto getC(T...)(size_t n, ref T v)
  if (allSatisfy!(hasAssignableElements, T))
  {
    foreach (ref w; v)
      w = new typeof(w)(n);
    foreach (i; 0..n)
      foreach (ref w; v) get(w[i]);
  }

  auto getM(T)(size_t r, size_t c, ref T v)
  if (hasAssignableElements!T && hasAssignableElements!(ElementType!T))
  {
    v = new T(r);
    foreach (ref w; v) getA(c, w);
  }

  auto putA(T)(T v)
  {
    static if (isInputRange!T && hasLength!T && !isSomeString!T) {
      foreach (i, w; v) {
	putA(w);
	if (i < v.length - 1) write(delimiter);
      }
    } else if (isFloatingPoint!T) {
      writef(format("%%.%df", precision), v);
    } else {
      write(v);
    }
  }

  auto put(T...)(T v)
  {
    foreach (i, w; v) {
      putA(w);
      if (i < v.length - 1) write(delimiter);
    }
    writeln;
  }

  auto putB(S, T)(bool c, S t, T f)
  {
    if (c)
      put(t);
    else
      put(f);
  }

  auto dbg(T...)(T v)
  {
    stderr.writeln(v);
  }
}


Measured memory_bytes: 6168
n,m = list(map(int,input().split()))
swi = []
for _ in range(m):
    k, *sss = list(map(int,input().split()))
    t = 0
    for s in sss:
        t += 1 << (s-1)
    swi.append(t)
ppp = list(map(int,input().split()))

ans = 0
for bit in range(1<<n):
    for s,p in zip(swi,ppp):
        t = bit&s
        c = bin(t).count("1") % 2
        if c != p:
            break
    else:
        ans += 1
print(ans)

Measured memory_bytes: 3064
#include <stdio.h>

int main(){
  int i,n,A[100],j,minj,count=0,tmp;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }

  for(i=0;i<=n-1;i++){
    minj=i;
    for(j=i;j<=n-1;j++){
      if(A[j]<A[minj])
	minj=j;
    }
    if(minj!=i){
    tmp=A[i];
    A[i]=A[minj];
    A[minj]=tmp;
    count++;
    }
  }
  for(i=0;i<n-1;i++)
    printf("%d ",A[i]);
  printf("%d\n%d\n",A[n-1],count);

  return 0;
}



Measured memory_bytes: 2144
#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

const int P = 1000000007;
ll inv[100010], fac[100010], facInv[100010];

void initFact(int n){
  inv[1] = 1;
  for (int i = 2; i <= n; ++i){
    inv[i] = P - (P / i) * inv[P % i] % P;
  }

  fac[0] = facInv[0] = 1;
  for (int i = 1; i <= n; ++i) {
    fac[i] = (fac[i - 1] * i) % P;
    facInv[i] = (facInv[i - 1] * inv[i]) % P;
  }
}

ll choose(int n, int k) {
  if (k > n) return 0;
  return (((fac[n] * facInv[k]) % P) * facInv[n - k]) % P;
}

int main(){
  int n;
  cin >> n;

  vector<int> v(n + 1, -1);
  int x, outside;
  for(int i = 0; i < n + 1; i++){
    cin >> x;
    if(v[x] != -1){
      outside = n - i + v[x];
    }
    else{
      v[x] = i;
    }
  }

  initFact(n + 1);

  ll ans;
  for(int i = 1; i <= n + 1; i++){
    ans = choose(n + 1, i) - choose(outside, i - 1);
    if(ans < 0) ans += P;
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;

typedef int64_t Int;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << endl; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << std::endl;
}

int main() {
    string s;
    cin >> s;
    vector<Int> a(s.size() + 1, 0);
    Int cnt = 0;
    for (Int i = 0; i < (Int)s.size(); i++) {
        if (s[i] == '<') {
            cnt++;
            a[i + 1] = cnt;
        } else {
            cnt = 0;
        }
    }
    cnt = 0;
    for (Int i = (Int)s.size() - 1; (Int)i >= 0; i--) {
        if (s[i] == '>') {
            cnt++;
            a[i] = max(a[i], cnt);
        } else {
            cnt = 0;
        }
    }
    print(accumulate(all(a), 0LL));
    return 0;
}

Measured memory_bytes: 4740
#include <bits/stdc++.h>

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main() {
  int k;
  string s;
  cin >> k >> s;
  string res;
  if (s.size() <= k) {
    res = s;
  } else {
    res = s.substr(0, k) + "...";
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 3608
#include <stdio.h>
#include <limits.h>

int main(void) {
    int n, a, i, mx, acc;

    while (scanf("%d", &n) == 1 && n) {
        for (i = 0, mx = INT_MIN, acc = 0; i < n; i++) {
            scanf("%d", &a);
            acc += a;
            if (mx < acc) mx = acc;
            if (acc < 0) acc = 0;
        }
        printf("%d\n", mx);
    }
    return 0;
}

Measured memory_bytes: 600
#include <stdio.h>

typedef struct dice{
  int men[6];
} Dice;
  
int main(void)
{
  Dice dice1, dice2, dice_memo;
  int ans = 0;
  int i, j, k, l;
  
  for(i = 0; i < 6; i++)
    scanf("%d", &dice1.men[i]);

  for(i = 0; i < 6; i++)
    scanf("%d", &dice2.men[i]);

  for(i = 0; i < 6; i++)
    dice_memo.men[i] = dice1.men[i];
  
    for(i = 0; i < 4; i++){
      for(j = 0; j < 4; j++){
	for(k = 0; k < 4; k++){
	  if(dice1.men[0] == dice2.men[0] && dice1.men[1] == dice2.men[1] && dice1.men[2] == dice2.men[2] && dice1.men[3] == dice2.men[3] && dice1.men[4] == dice2.men[4] && dice1.men[5] == dice2.men[5])
	    ans = 1;
	  
	  else{
	    dice_memo.men[0] = dice1.men[1];
	    dice_memo.men[1] = dice1.men[5];
	    dice_memo.men[5] = dice1.men[4];
	    dice_memo.men[4] = dice1.men[0];
	  }
	  
	  for(l = 0; l < 6; l++)
	    dice1.men[l] = dice_memo.men[l];
	}
	dice_memo.men[0] = dice1.men[3];
	dice_memo.men[3] = dice1.men[5];
	dice_memo.men[5] = dice1.men[2];
	dice_memo.men[2] = dice1.men[0];
	
	for(l = 0; l < 6; l++)
	  dice1.men[l] = dice_memo.men[l];
      }
      dice_memo.men[1] = dice1.men[2];
      dice_memo.men[2] = dice1.men[4];
      dice_memo.men[4] = dice1.men[3];
      dice_memo.men[3] = dice1.men[1];
      
      for(l = 0; l < 6; l++)
	dice1.men[l] = dice_memo.men[l];
    }

    
    if(ans)
      printf("Yes\n");
    else
      printf("No\n");
    
    return 0;
}

Measured memory_bytes: 580
using System;

namespace ABC095_A_Something_on_It
{
	internal class Program
	{
		public static void Main(string[] args)
		{
			string s = Console.ReadLine();

			int count = 0;
			
			for (int i = 0; i < 3; i++) {
				if (s.Substring(i, 1) == "o")
				{
					count++;
				}
			}
			
			Console.WriteLine(700 + count * 100);
		}
	}
}


Measured memory_bytes: 13140
object Main {
  def main(args:Array[String]) = {
    val sc = new java.util.Scanner(System.in)
    val a, b = sc.nextLong
    // 最大公約数
    val g = gcd(a, b)

    // 割っていく
    var result = 0
    var current_g = g
    for(v<- 2 to Math.sqrt(g).toInt+1 if current_g != 1 && current_g % v == 0) {
      while(current_g % v == 0) {
        // 割り切れるだけ割る
        current_g = current_g / v
      }
      result += 1
    }

    result = (g, current_g, result) match {
      case (1, _, _)             => 1 // 1なら1
      case (_, cg, v) if cg != 1 => v+2 // 割り切れない分があったなら+2
      case (_, _, v)             => v+1 // それ以外なら1を加算
    }
    println(result)
    
  }
  def gcd(a:Long, b:Long): Long = {
    var x = Math.max(a,b)
    var y = Math.min(a,b)
    var m = x % y
    while(m!=0) {
      x = y
      y = m
      m = x % y
    }
    return y
  }
}


Measured memory_bytes: 27600
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;


int main() {
  int n ,x, ans = 0;
  cin >> n >> x;
  int a[100] = {0};
  for(int i= 0; i< n; i++){
    cin >> a[i];
  }
  sort(a,a+100);
  for(int i = 100 - n; i < 99; i++){
    if(x >= a[i]){
        x -= a[i];
        ans ++;
    }else{
        break;
    }
  }
  if(x == a[99]) ans++;
  cout << ans;
}

Measured memory_bytes: 256
from collections import Counter


def getinputdata():
    # 配列初期化
    array_result = []

    data = input()

    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            array_temp = []

            if (data != ""):

                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:

        return array_result


arr_data = getinputdata()

n = int(arr_data[0][0])
m = int(arr_data[0][1])

arr = []

for i in range(1, 1 + m):
    arr.append(int(arr_data[i][0]))
    arr.append(int(arr_data[i][1]))

list01 = Counter(arr)


for i in range(1, 1 + n):
    print(list01[i])


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
int main(){
    char b;
    cin >> b;
    if(b=='A')cout << 'T' << endl;
    else if(b=='T')cout << 'A' << endl;
    else if(b=='C')cout << 'G' << endl;
    else if(b=='G')cout << 'C' << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;

/* next combination */
int next_combination(int sub) {
    int x = sub & -sub, y = sub + x;
    return (((sub & ~y) / x) >> 1) | y;
}

int main(){
    double t,x;cin >> t >> x;
    cout << double(t/x) << endl;
    return 0;
}

Measured memory_bytes: 3776
#include <stdio.h>

/*int fac(int x) {
    int y=1;
    for (int i=x; i>0; --i) {
        y *= i;
    }
    return y;
}
*/
int main() {
    int k;
    /*int n, fac1=1, fac2=1, fac3=1;*/
    scanf("%d", &k);

    /*
    fac1 = fac(n);
    fac2 = fac(k);
    fac3 = fac(n-k);
    */

    printf("%d\n", k*k*k);

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>


#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amax(T& a,T b){ a=max(a,b);}

int main(){
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	vector<pii> vp(n);
	rep(i, n) cin >>vp[i].first >>vp[i].second;
	sort(all(vp));
	VI x(n), l(n);
	rep(i, n){
		x[i]=vp[i].first; l[i]=vp[i].second;
	}
	vector<VI> dt(n, VI(2));
	rep(i, n) dt[i] = VI{vp[i].first+vp[i].second, i};
	sort(all(dt));
	//for(auto xl: dt){for(auto x :xl) cerr<<x<<":"; cerr<<", ";}
	
	int rg=0, zk=0;
	rep(i, n){
		int z= dt[i][1];
		if(i == 0){ rg = dt[i][0]; continue;}
		if(vp[z].first - vp[z].second < rg) zk++;
		else rg = dt[i][0];
	}
	cout << n - zk <<"\n";
	return 0;
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N, K;
    cin >> N >> K;
    vector<ll> H(N);
    for (int i = 0; i < N; i++) {
        cin >> H[i];
    }
    sort(H.begin(), H.end());
    ll sum = 0;
    for (int i = 0; i < N - K; i++) {
        sum += H[i];
    }
    cout << sum << "\n";
    return 0;
}


Measured memory_bytes: 1792
rec_dx, rec_dy, cir_x, cir_y, cir_r = [int(x) for x in input().split()]

cir_left = cir_x - cir_r
cir_right = cir_x + cir_r
cir_up = cir_y + cir_r
cir_down = cir_y - cir_r

if cir_left < 0:
    print("No")
elif cir_right > rec_dx:
    print("No")
elif cir_up > rec_dy:
    print("No")
elif cir_down < 0:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 5604
N, K = map(int, input().split())
dt = []
for i in range(N):
	t, d = map(int, input().split())
	dt.append((d, t))
dt.sort()
dt.reverse()
dic = {}
can_delete = []
dp = 0
x = 0
for i in range(K):
	d, t = dt[i]
	dp += d
	if t in dic:
		can_delete.append(d)
	else:
		dic[t] = d
		x += 1
can_delete.sort()
can_delete.reverse()
ans = dp + x * x
v = ans
for i in range(K, N):
	if len(can_delete) == 0:
		break
	d, t = dt[i]
	if t in dic:
		continue
	dic[t] = d
	x += 1
	v = v - can_delete.pop() + d + 2 * x - 1
	if v > ans:
		ans = v
print(ans)

Measured memory_bytes: 60120
#include <iostream>
    #include <vector>
    #include <algorithm>

    using namespace std;
     
    int main() {
      int n,k;
      cin >> n >> k;
      
      vector<int> v(n);

      for (int i=0;i<n;i++){
        cin >> v[i];
      }
      
      std::sort(v.begin(),v.end());
      
      vector<int> vc(n-k+1);
      for(int i=0;i<n-k+1;i++){
        vc[i] = v[i+k-1] - v[i];
      }
      
      int min = *std::min_element(vc.begin(), vc.end());
      cout << min << endl;

      return 0;
    }

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
#define li long long int
#define rep(i, to) for (li i = 0; i < ((li)(to)); i++)
typedef pair<li, li> PI;
 
 
vector<li> edge[2020];
li n, k;
 
inline li calc(li root, li parent, li lim) {
    stack<pair<PI, li>> stk;
    li cnt = 0;
    stk.push({{root, parent}, 0});
    while (!stk.empty()) {
        li now = stk.top().first.first;
        li from = stk.top().first.second;
        li now_d = stk.top().second;
        stk.pop();
        cnt++;
        if (now_d >= lim)continue;
        for (auto next : edge[now]) {
            if (next == from)continue;
            stk.push({{next, now}, now_d + 1});
        }
    }
    return cnt;
}
 
inline li solve_node() {
    li res = n;
    rep(i, n) {
        res = min(res, n - calc(i, -1, k / 2));
    }
    return res;
}
 
inline li solve_link() {
    li res = n;
    rep(i, n) {
        for (auto to : edge[i]) {
            res = min(res, n - calc(i, to, k / 2) - calc(to, i, k / 2));
        }
    }
    return res;
}
 
int main(void)
{
    cin >> n >> k;
    rep(i, n - 1) {
        li a, b;
        cin >> a >> b;
        a--;
        b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
 
    if (k % 2 == 0) {
        cout << solve_node() << endl;
    } else {
        cout << solve_link() << endl;
    }
 
 
    return 0;
}

Measured memory_bytes: 384
import numpy as np
N,X = list(map(int,input().split()))
x = np.array(list(map(int,input().split())))
#distance from point"X"
Xar = np.array([X]*N)
d = abs(x-Xar)
def EA(a,b):
    if a%b ==0:
        return b
    else:
        return EA(b,a%b)
if len(x)==1:
    ans = d[0]
else:
    ans = EA(d[0],d[1])
    for i in range(N):
        ans = EA(ans,d[i])
print(ans)

Measured memory_bytes: 23128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back()
#define ALL(a) (a).begin(),(a).end()

using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

#define INF 1e+9
#define MAX_V 100100

struct edge {
    int to;
    int cost;
};

// <最短距離, 頂点の番号>
using P = pair<int, int>;

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i=0; i<G[v].size(); ++i) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}
signed main(){
    int x,y; cin >> V >> x >> y;
    x--; y--;
    rep(i,V-1){
        G[i].pb({i+1,1});
        G[i+1].pb({i,1});
    }
    G[y].pb({x,1}); G[x].pb({y,1});
    
    vector<int> ans(V-1,0);
    rep(i,V){
        dijkstra(i);
        rep(j,V){
            if(d[j]==INF||d[j]==0) continue;
            ans[d[j]-1]++;
        }
    }
    rep(i,V-1) cout << ans[i]/2 << endl;
}


Measured memory_bytes: 2688
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

mod = 10**9 + 7

a.sort(reverse=True)
b.sort(reverse=True)

a.append(-1)
b.append(-1)

s = 0
t = 0
ans = 1
for i in range(n*m, 0, -1):
    if i == a[s] and i == b[t]:
        s += 1
        t += 1
    elif i == a[s]:
        s += 1
        ans *= t
        ans %= mod
    elif i == b[t]:
        t += 1
        ans *= s
        ans %= mod
    else:
        ans *= (s * t - (n * m - i))
        ans %= mod
print(ans)


Measured memory_bytes: 3188
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        d: i64,
        point: [(i64,i64); n],
    }

    let result = point.into_iter().filter(|(x,y)| x.pow(2) + y.pow(2) <= d.pow(2)).count();
    println!("{}", result);
}


Measured memory_bytes: 7800
import java.io.*;
import java.util.*;

class Main{
    public static void main(String[] args){
	BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
	String st;
	int a, b, n, s;
	try{
	    while((st=sc.readLine())!=null){
		String[] x = st.split(" ");
		a = Integer.valueOf(x[0]);
		b = Integer.valueOf(x[1]);
		n = Integer.valueOf(x[2]);
		s = 0;
		a%=b;
		for(int i=0; i<n; i++){
		    a*=10;
		    s+=(a/b);
		    a%=b;
		}
		System.out.println(s);
	    }
	}catch (Exception e){
	    System.out.println("Error");
	}
    }
}

Measured memory_bytes: 9720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string press[1010];
string state[1010];

char conv(int n){
	if(0 <= n && n <= 9) return '0' + n;
	n -= 10;
	return 'A' + n;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int N, M, Q;
	while(cin >> N >> M >> Q, N){
		state[0] = string(M, '0');
		for(int i = 1; i <= Q; i++){
			cin >> press[i] >> state[i];
		}

		string ans;
		for(int i = 0; i < M; i++){
			set<int> cand;
			for(int n = 0; n < N; n++){
				int cnt[2][2] = { 0 };
				for(int j = 1; j <= Q; j++){
					const string& pre = state[j - 1];
					int change = state[j][i] != state[j - 1][i];
					int p = press[j][n] == '1';
					cnt[change][p]++;
				}
				if(cnt[0][0] + cnt[1][1] == Q){
					cand.insert(n);
				}
			}
			if(cand.size() == 1){
				ans += conv(*cand.begin());
			}
			else{
				ans += '?';
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 4540
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void) 
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n, K;
  cin >> n >> K;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  ll ans = 0;
  for(ll i=40; i>=0; --i) {
    if(!(K&1LL<<i)) continue;
    ll x = 0;
    for(ll j=40; j>i; --j) {
      x |= K&1LL<<j;
    }
    for(ll j=i-1; j>=0; --j) {
      ll cnt0 = 0, cnt1 = 0;
      REP(k, n) {
        if(a[k]&1LL<<j) cnt1++;      
        else cnt0++;
      }
      if(cnt0 > cnt1) x |= 1LL<<j;
    }

    // cout << "i=" << i << " x=" << x << endl;
    ll ret = 0;
    REP(j, n) ret += a[j]^x;
    chmax(ans, ret);
  }

  ll ret = 0;
  REP(j, n) ret += a[j]^K;
  chmax(ans, ret);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h> 

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll N,C;
  cin>>N>>C;
  vector<ll>x(N),v(N);
  for(int i=0;i<N;i++)cin>>x[i]>>v[i];

  vector<ll>suml(N+1);
  suml[0]=0;
  for(int i=1;i<=N;i++)suml[i]=suml[i-1]+v[i-1];

  vector<ll>sumr(N+1);
  sumr[0]=0;
  for(int i=1;i<=N;i++)sumr[i]=sumr[i-1]+v[N-i];

  ll anslr=0;
  vector<ll>maxll=suml;
  for(int i=1;i<=N;i++)maxll[i]-=x[i-1];
  for(int i=1;i<=N;i++)maxll[i]=max(maxll[i],maxll[i-1]);

  vector<ll>maxrr=sumr;
  for(int i=1;i<=N;i++)maxrr[i]-=C-x[N-i];
  for(int i=1;i<=N;i++)maxrr[i]=max(maxrr[i],maxrr[i-1]);
  // right -> left
  ll ansrl=0;

  for(int i=0;i<=N;i++){
    if(i==0)ansrl=max(ansrl,maxrr[N]);
    else ansrl=max(ansrl,maxrr[N-i]+suml[i]-2*x[i-1]);
  }

  // left -> right
  for(int i=0;i<=N;i++){
    if(i==0)anslr=max(anslr,maxll[N]);
    else anslr=max(anslr,maxll[N-i]+sumr[i]-2*(C-x[N-i]));
  }
  cout<<max(ansrl,anslr)<<endl;
  return 0;
}


Measured memory_bytes: 4992
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int a=in.nextInt();
        int b=in.nextInt();
        int sum1=0,sum2=0,sum=0;
        a=a-1;b=b-1;
        sum1=(a*(a+1))/2;
        sum2=(b*(b+1))/2;
        sum=sum1+sum2;
        System.out.println(sum);
    }
}

Measured memory_bytes: 21844
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    int n;
    cin >> n;
    vvi edges(n);
    for (int i = 0; i < n - 1; ++i) {
        int p;
        cin >> p;
        p--;
        edges[i + 1].push_back(p);
        edges[p].push_back(i + 1);
    }
    vi x(n), y(n), z(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    bool ok                      = true;
    function<void(int, int)> dfs = [&](int c, int p) {
        int child = 0;
        for (auto &v : edges[c]) {
            if (v == p)
                continue;
            dfs(v, c);
            child++;
        }
        if (child == 0) {
            z[c] = x[c];
            y[c] = 0;
            return;
        }
        vvl dp(child + 1, vl(x[c] + 1, INF));
        dp[0][0] = 0;
        int idx  = 1;
        for (auto &v : edges[c]) {
            if (v == p)
                continue;
            for (int j = 0; j <= x[c]; ++j) {
                if (j >= x[v])
                    chmin(dp[idx][j], dp[idx - 1][j - x[v]] + y[v]);
                if (j >= y[v])
                    chmin(dp[idx][j], dp[idx - 1][j - y[v]] + x[v]);
            }
            idx++;
        }
        ll mini = INF;
        for (int i = 0; i <= x[c]; ++i) {
            chmin(mini, dp[child][i]);
        }
        if (mini == INF)
            ok = false;
        else
            y[c] = mini;
    };
    dfs(0, -1);
    if (ok)
        cout << "POSSIBLE"
             << "\n";
    else
        cout << "IMPOSSIBLE"
             << "\n";
    return 0;
}

Measured memory_bytes: 2384
#include <iostream>
#include <vector>

using namespace std;

class range {
private:
  struct Iterator {
    int val;
    int operator*() {return val;}
    bool operator!=(Iterator &itr) {return val < itr.val;}
    void operator++() {++val;}
  };
  Iterator i, n;
public:
  range(int n) : i({0}), n({n}) {}
  range(int i, int n) : i({i}), n({n}) {}
  Iterator &begin() {return i;}
  Iterator &end() {return n;}
};

template<class T> T at(vector<T> v, int i) {return v[(i % (int)v.size() + v.size()) % v.size()];}

int main() {
  while (true) {
    int n, m, p, q, r;
    cin >> n;
    if (n == 0) break; 
    cin >> m >> p >> q >> r;;
    --p;
    vector<pair<int, int>> dp[2];
    dp[0].emplace_back(1, n);
    for (int i : range(m)) {
      int x, y, sum = 0;
      cin >> x >> y;
      for (const auto &i : dp[0]) {
        int nsum = sum + i.second - i.first + 1;
        int xx = max(sum, y);
        int yy = min(nsum, n);
        if (xx < yy) dp[1].emplace_back(i.first + max(0, y - sum), i.second - max(0, nsum - n));
        sum = nsum;
      }
      sum = 0;
      for (const auto &i : dp[0]) {
        int nsum = sum + i.second - i.first + 1;
        int xx = max(sum, x);
        int yy = min(nsum, y);
        if (xx < yy) dp[1].emplace_back(i.first + max(0, x - sum), i.second - max(0, nsum - y));
        sum = nsum;
      }
      sum = 0;
      for (const auto &i : dp[0]) {
        int nsum = sum + i.second - i.first + 1;
        int xx = max(sum, 0);
        int yy = min(nsum, x);
        if (xx < yy) dp[1].emplace_back(i.first + max(0, 0 - sum), i.second - max(0, nsum - x));
        sum = nsum;
      }
      dp[0] = dp[1];
      dp[1].clear();
    }
    int sum = 0;
    int res = 0;
    for (const auto &i : dp[0]) {
      int nsum = sum + i.second - i.first + 1;
      int xx = max(sum, p);
      int yy = min(nsum, q);
      if (xx < yy) {
        int s = i.first + max(0, p - sum);
        int t = min(i.second - max(0, nsum - q), r);
        if (s <= r) res += t - s + 1;
      }
      sum = nsum;
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 1368