akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
#define rep(i,n) for(lint (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(lint (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(lint (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
#define all(x) (x).begin(),(x).end()
const lint MOD =1000000007;
const lint MAX = 1000000;
using Graph =vector<vector<lint>>;
typedef pair<lint,lint> P;
typedef map<lint,lint> M;
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
 
lint fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() 
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0;
 
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return 0;
        }
    }
 
    return 1;
}
   long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
    lint lcm(lint a,lint b){
        return a/__gcd(a,b)*b;
    }
     lint gcd(lint a,lint b){
        return __gcd(a,b);
    } 
    lint popcount(lint n){
        if(n==0)return 0;
        lint g=n;
        lint count=0;
        while(n){
            if(n%2)count++;
            n/=2;
        }
        return g%count;
    }

  int main(){
      lint n;
      string s;
      cin>>n>>s;
      lint count=0;
      rep(i,n){
          if(s[i]=='1')count++;
      }
      lint plus=0,minus=0;
      rep(i,n){
          if(s[i]=='1'){
          plus+=modpow(2,n-i-1,count+1);
          if(count!=1)minus+=modpow(2,n-i-1,count-1);
          }
      }
      plus%=(count+1);
      if(count!=1)minus%=(count-1);
      rep(i,n){
          lint x=0;
          if(s[i]=='0'){
            x=plus+modpow(2,n-i-1,count+1);
            x%=(count+1);
          }else if(count!=1){
              x=minus-modpow(2,n-i-1,count-1);
              x+=(count-1);
              x%=(count-1);
          }
          lint ans=1;
          if(count==1&&s[i]=='1')ans=0;
          while(x){
              ans++;
              x=popcount(x);
          }
          cout<<ans<<endl;
      }
      }
      

Measured memory_bytes: 3728
a,b,k = map(int,input().split())
for i in range(k):
    if i%2==0:
        if a%2 == 1:
            a-=1
        b+=a//2
        a-=a//2
    else:
        if b%2 == 1:
            b-=1
        a+=b//2
        b-=b//2
print(a,b)

Measured memory_bytes: 9136
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  string S;
  cin >> S;

  S[3] = '8';
  cout << S << endl;
}

Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int H, W, K;
queue<pair<int,int> >Q;
int d[5] = { 1,0,-1,0,1 };
int sx, sy;

int main() {
	ios::sync_with_stdio(false);
	cin >> H >> W >> K;
	vector<string> field(H + 2);
	vector<vector<int> >dp((H + 2), vector<int>(W + 2, INT_MAX));
	for (int i = 1; i <= H; i++) {
		cin >> field[i];
		field[i] = '0' + field[i];
		//cout << field[i] << endl;
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (field[i][j] == 'S') {
				dp[i][j] = 0;
				Q.push({ i,j });
				sy = i;
				sx = j;
			//	cout << i << " " << j << endl;
			}
		}
	}
	//cout << "hijiki";
	while (!Q.empty()) {
		int y = Q.front().first;
		int x = Q.front().second;
		for (int i = 0; i < 4; i++) {
			//cout << y + d[i] << " " << x + d[i + 1] << endl;
			if (field[y + d[i]][x + d[i + 1]] == '.') {
				if (dp[y + d[i]][x + d[i + 1]] > dp[y][x] + 1 && dp[y][x] + 1 <= K) {
					Q.push({ y + d[i],x + d[i + 1] });
					dp[y + d[i]][x + d[i + 1]] = dp[y][x] + 1;
				}
			}
		}
		Q.pop();
	}
	//cout << "hijiki";
	int ans = INT_MAX;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (dp[i][j] != INT_MAX) {
				int box = min({ abs(1 - i), abs(H - i), abs(1 - j), abs(W - j) });
				box = box / K + !!(box%K);
				ans = min(ans, 1 + box);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3456
n, a, b = map(int, input().split())

MOD = 1000000007

def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD 

mod_inv = lambda x: pow_mod(x, MOD - 2)

nCk = {0: 1}

for i in range(1, max(a,b) + 1):
  nCk[i] = nCk[i-1] * ((n-i+1) % MOD)
  nCk[i] %= MOD
  nCk[i] *= mod_inv(i)
  nCk[i] %= MOD

print((pow_mod(2, n) - 1 - nCk[a] - nCk[b]) % MOD)



Measured memory_bytes: 66396
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int H,N;
  cin>>H>>N;
  int sum=0;
  int A[N];
  for(int i=0;i<N;i++)
  {
    cin>>A[i];
    sum+=A[i];
  }
  if(sum>=H)
    cout<< "Yes";
  else
    cout<<"No";
}


Measured memory_bytes: 640
#include <stdio.h>
#include<string.h>
int main (void){
    char S[10],T[10],U[10];
    int A,B;
    scanf("%s %s",S,T);
    scanf("%d %d",&A,&B);
    scanf("%s",U);
    if(strcmp(S,U)==0){
        A--;
    }else{
        B--;
    }
    printf("%d %d\n",A,B);
    return 0;
}

Measured memory_bytes: 128
/*-------enazuma11----------------*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(v) v.begin(),v.end()
#define inc(a,n) sort(a,a+n)
#define dec(a,n) sort(a,a+n,greater<int>() )
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define F first
#define S second
#define M 1000000007
 
/* int x[]={-1,-1,0,1,1,1,0,-1};
int y[]={0,1,1,1,0,-1,-1,-1};
*/
/* int x[]={-1,0,1,0};
int y[]={0,1,0,-1};
*/

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t=1;
	//	cin>>t;
	while(t--){
		int k,x;
		cin>>k>>x;
		int c=0;
		vector<int> v;
		int cur=x-1;
		while(c<k-1){
			v.pb(cur);
			cur--;
			c++;
		}
		v.pb(x);
		cur=x+1;
		c=0;
		while(c<k-1){
			v.pb(cur);
			cur++;
			c++;
		}
		sort(all(v));
		for(auto i:v)
		cout<<i<<" ";
		
	}
	return 0;
}


Measured memory_bytes: 256
import java.io.{BufferedOutputStream, BufferedReader, InputStreamReader, PrintWriter}

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val out = new PrintWriter(new BufferedOutputStream(System.out))
    val s = in.readLine()

    out.println(
      if (s == "ABC") {
        "ARC"
      } else {
        "ABC"
      }
    )

    out.flush()
  }
}


Measured memory_bytes: 54580
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,i;
    cin>>n;
    int a[n],b[n],c[n],dp[n][3];
    for(i=0;i<n;i++){
    cin>>a[i]>>b[i]>>c[i];
    dp[i][0]=0;
    dp[i][1]=0;
    dp[i][2]=0;
    }
    
    dp[0][0]=a[0];
    dp[0][1]=b[0];
    dp[0][2]=c[0];
    for(i=1;i<n;i++){
    dp[i][0]+=a[i]+max(dp[i-1][1],dp[i-1][2]);
    dp[i][1]+=b[i]+max(dp[i-1][2],dp[i-1][0]);
    dp[i][2]+=c[i]+max(dp[i-1][0],dp[i-1][1]);
    }
    cout<<max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2])<<endl;
}

Measured memory_bytes: 2560
from collections import deque
h,w = map(int, input().split())
s = [list(input()) for _ in range(h)]

bom = deque()
for i in range(h):
  for j in range(w):
    if s[i][j] == "#": bom.append([i,j])
    else: s[i][j] = 0

while bom:
  x,y = bom.pop()
  for i,j in [(0,1), (1,0), (-1,0), (0,-1), (1,1), (1,-1), (-1,1), (-1,-1)]:
    new_h, new_w = x+i, y+j
    if new_h < 0 or new_h >= h or new_w < 0 or new_w >= w: continue
    if s[new_h][new_w] == "#": continue
    s[new_h][new_w] += 1
for v in s:
  print("".join(map(str, v)))

Measured memory_bytes: 3572
import collections
import copy
n=int(input())
l=['a']
c=[chr(i) for i in range(97, 97+26)]
for i in range(n-1):
  L=[]
  for j in range(len(l)):
    C=collections.Counter(l[j])
    for k in range(len(C.values())+1):
      L.append(l[j]+c[k])
  l=copy.copy(L)
l.sort()
for i in range(len(l)):
  print(l[i])

Measured memory_bytes: 14312
from queue import PriorityQueue
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


mod = 10**9+7


def prod(l):
    ret = 1
    for e in l:
        e %= mod
        ret = (ret*e) % mod

    return ret


def main():
    n, k = geta(int)
    a = list(geta(int))

    p, n, z = [], [], 0
    for ai in a:
        if ai > 0:
            p.append(ai)
        elif ai < 0:
            n.append(-ai)
        else:
            z += 1

    ans = 1
    p.sort()
    n.sort()


    if len(p) + len(n) < k:
        print(0)
        exit()
    elif len(p) + len(n) == k:
        if len(n) & 1 == 0:
            print(prod(p) * prod(n) % mod)
            exit()
        else:
            if z > 0:
                print(0)
                exit()
            else:
                print(-prod(p)*prod(n) % mod)
                exit()

    if k & 1 == 1:
        if len(p) == 0:
            if z > 0:
                print(0)
                exit()
            else:
                print(-prod(n[0:k]) % mod)
                exit()
        else:
            k -= 1
            ans = p.pop() % mod

    q = []

    n = n[::-1]
    for i in range(len(n)//2):
        q.append(n[2*i]*n[2*i+1])

    p = p[::-1]
    for i in range(len(p)//2):
        q.append(p[2*i]*p[2*i+1])

    q.sort(reverse=True)

    ans = ans * (prod(q[:k//2])) % mod

    print(ans % mod)


if __name__ == "__main__":
    main()


Measured memory_bytes: 119904
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 1000 + 5;

vector<int> v;
int n, m;

int main(){
    cin >> n >> m;
    int ans = 0;
    for (int i = 1; i * i <= m; i++){
        if (m % i) continue;
        v.push_back(i);
        if (i * i != m) v.push_back(m / i);
    }
    sort(v.begin(), v.end());
    int k = lower_bound(v.begin(), v.end(), n) - v.begin();
    cout << m / v[k];
    return 0;
}

Measured memory_bytes: 256
N, Q = map(int, input().split())
a = []
p = []
x = [0]*(N)
A = [0]*(N)

for i in range(N-1):
    t=list(map(int,input().split()))
    if t[0]>t[1]:
        swap = t[1]
        t[1] = t[0]
        t[0] =swap
    a.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=list(map(int,input().split()))
    p.append((int(t[0]),int(t[1])))

a =sorted(a, key=lambda x: x[0])
p =sorted(p, key=lambda x: x[0])

#print(a)
for i in range(Q):
    x[p[i][0]-1] += p[i][1]
for i in range(N):
    A[i] = x[i]
for i in range(N-1):
    La = a[i][0]-1
    Lb = a[i][1]-1

    A[Lb] = A[La]+x[Lb]

print(' '.join(map(str, A)))


Measured memory_bytes: 90156
#include <bits/stdc++.h>
#define int long long
#define f(i,n) for(int i=0;i<n;i++)
using namespace std;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int x[100000],y[100000],z[100000],n;
signed main(){
	cin>>n;
	int ans;
	f(i,n){
		cin>>x[i];
		if(i)y[i]=gcd(y[i-1],x[i]);
		else y[i]=x[i];
	}
	for(int i=n-1;i>=0;i--){
		if(i==n-1) z[i]=x[i];
		else z[i]=gcd(z[i+1],x[i]);
	}
	f(i,n){
		if(i==0) ans=z[i+1];
		else if(i==n-1) ans=max(ans,y[i-1]);
		else ans=max(ans,gcd(y[i-1],z[i+1]));
	}
	cout<<ans<<endl;
}


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

int N;
vector<int> p;
vector<vector<int>> c;
vector<int> a, a_inv;
vector<int> a_sub;
vector<int> is_confirm, is_leaf, is_progeny, progeny_count, candidate_v;

int do_confirm(){
	for(int i = N - 1; i >= 0; i--){
		int count = 0;
		for(int j = 0; j < c[i].size(); j++){
			count += is_confirm[c[i][j]];
		}
		if(count == c[i].size()){
			is_leaf[i] = 1;
			if(a[i] == i){
				is_confirm[i] = 1;
			}
		}
	}
	return is_confirm[0];
}

void dfs(int a_v){
	if(is_confirm[a_v] == 0){
		is_progeny[a_inv[a_v]] = 1;
		if(is_leaf[a_v] == 0){
			for(int i = 0; i < c[a_v].size(); i++){
				dfs(c[a_v][i]);
			}
		}
	}
}

int decide(){
	if(is_leaf[a[0]] == 1){
		return a[0];
	}
	for(int i = 0; i < N; i++){
		is_progeny[i] = 0;
		progeny_count[i] = 0;
	}
	dfs(a[0]);
	for(int i = N - 1; i > 0; i--){
		progeny_count[i] += is_progeny[i];
		progeny_count[p[i]] += progeny_count[i];
	}
/*	printf("is_progeny:");
	for(int i = 0; i < N; i++){
		printf("%d ", is_progeny[i]);
	}
	printf("\n");
	printf("progeny_count:");
	for(int i = 0; i < N; i++){
		printf("%d ", progeny_count[i]);
	}
	printf("\n");
*/	candidate_v.assign(0, -1);
	for(int i = 1; i < N; i++){
		if(is_progeny[i] == 1 && progeny_count[i] == 1){
			candidate_v.push_back(i);
		}
	}
//	return candidate_v[0];
	return candidate_v[rand() % candidate_v.size()];
}

void insersion(int v){
	int V = v;
	for(; v >= 0; v = p[v]){
		a_sub[v] = a[v];
	}
	for(v = V; v > 0; v = p[v]){
		a[p[v]] = a_sub[v];
	}
	a[V] = a_sub[0];
	for(v = V; v >= 0; v = p[v]){
		a_inv[a[v]] = v;
	}
}

int main(){
//	srand((unsigned)time(NULL));
	int i;
	scanf("%d", &N);
	p.assign(N, -1);
	c.assign(N, vector<int>(0));
	for(i = 1; i < N; i++){
		scanf("%d", &p[i]);
//		p[i] = rand() % i;
//		printf("p[%d] = %d\n", i, p[i]);
		c[p[i]].push_back(i);
	}
	a.assign(N, 0);
	a_inv.assign(N, 0);
	a_sub.assign(N, 0);
/*	for(i = 0; i < N; i++){
		a[i] = i;
		swap(a[i], a[rand() % (i + 1)]);
	}
*/	for(i = 0; i < N; i++){
		scanf("%d", &a[i]);
		a_inv[a[i]] = i;
	}
	is_confirm.assign(N, 0);
	is_leaf.assign(N, 0);
	is_progeny.assign(N, 0);
	progeny_count.assign(N, 0);
	vector<int> ans(0);
	while(do_confirm() == 0){
/*		printf("a:");
		for(i = 0; i < N; i++){
			printf("%d ", a[i]);
		}
		printf("\n");
		printf("a_inv:");
		for(i = 0; i < N; i++){
			printf("%d ", a_inv[i]);
		}
		printf("\n");
		printf("is_confirm:");
		for(i = 0; i < N; i++){
			printf("%d ", is_confirm[i]);
		}
		printf("\n");
		printf("is_leaf:");
		for(i = 0; i < N; i++){
			printf("%d ", is_leaf[i]);
		}
		printf("\n");
*/		int v = decide();
//		printf("v = %d\n", v);
		ans.push_back(v);
		insersion(v);
//		printf("\n");
	}
	printf("%d\n", ans.size());
	if(ans.size() > 20000){
		return 0;
	}
	for(i = 0; i < ans.size(); i++){
		printf("%d\n", ans[i]);
	}
	return 0;
}

Measured memory_bytes: 640
#include <cassert>
#include <utility>

template <class Abelian, template <class T> class Container>
class potentialized_union_find {
	class node_type;

public:
	using value_structure = Abelian;
	using value_type = typename value_structure::value_type;
	using container_type = Container<node_type>;
	using size_type = typename container_type::size_type;

protected:
	container_type c;

private:
	class node_type {
	public:
		typename potentialized_union_find::size_type parent, size;
		typename potentialized_union_find::value_type value;
	};
	value_type potential(size_type x) {
		value_type ret = value_structure::identity();
		while (x != c[x].parent) {
			c[x].value = value_structure::operation(c[x].value, c[c[x].parent].value);
			ret = value_structure::operation(ret, c[x].value);
			x = c[x].parent = c[c[x].parent].parent;
		}
		return ::std::move(ret);
	}

public:
	potentialized_union_find() : c() {}
	explicit potentialized_union_find(const size_type size)
		: c(size, { 0, 1, value_structure::identity() }) {
		for (size_type i = 0; i < size; ++i)
			c[i].parent = i;
	}

	bool empty() const { return c.empty(); }
	size_type size() const { return c.size(); }

	size_type find(size_type x) {
		assert(x < size());
		while (x != c[x].parent) {
			c[x].value = value_structure::operation(c[x].value, c[c[x].parent].value);
			x = c[x].parent = c[c[x].parent].parent;
		}
		return x;
	}
	value_type diff(const size_type x, const size_type y) {
		assert(x < size());
		assert(y < size());
		assert(same(x, y));
		return value_structure::operation(potential(y),
			value_structure::inverse(potential(x)));
	}
	bool same(const size_type x, const size_type y) {
		assert(x < size());
		assert(y < size());
		return find(x) == find(y);
	}
	size_type size(const size_type x) {
		assert(x < size());
		return c[find(x)].size;
	}

	::std::pair<size_type, size_type> unite(size_type x, size_type y,
		value_type d) {
		assert(x < size());
		assert(y < size());
		d = value_structure::operation(value_structure::operation(d, potential(x)),
			value_structure::inverse(potential(y)));
		x = find(x);
		y = find(y);
		if (x != y) {
			if (c[x].size < c[y].size) {
				::std::swap(x, y);
				d = value_structure::inverse(d);
			}
			c[x].size += c[y].size;
			c[y].parent = x;
			c[y].value = ::std::move(d);
		}
		return { x, y };
	}
};

template <class T> class plus_abelian {
public:
	using value_type = T;
	static value_type operation(const value_type &x, const value_type &y) {
		return x + y;
	}
	static value_type identity() { return value_type(0); }
	static value_type inverse(const value_type &x) { return -x; }
	static value_type reverse(const value_type &x) { return x; }
};

#include<iostream>
#include<vector>
template<class T>
using vec = ::std::vector<T>;

int main() {
	int n, m;
	::std::cin >> n >> m;
	potentialized_union_find<plus_abelian<int>, vec> T(n);
	while (m--) {
		int l, r, d;
		::std::cin >> l >> r >> d;
		--l;
		--r;
		if (T.same(l, r) && T.diff(l, r) != d) {
			::std::cout << "No" << ::std::endl;
			return 0;
		}
		else {
			T.unite(l, r, d);
		}
	}
	::std::cout << "Yes" << ::std::endl;
	return 0;
}


Measured memory_bytes: 2560
from sys import stdin
import sys

(N, Y) = stdin.readline().rstrip().split()

N = int(N)
Y = int(Y)

## 1 <= N <= 2000
## 1000 <= Y <= 2 * 10**7

## x y z
## x 10000
## y 5000
## z 1000

## N == x + y + z
## Y == 10000 * x + 5000 * y + 1000 * z


#for x in range(0, N+1):
for x in range(0, N+1):
    if 10000 * x > Y:
        break
    if 10000 * x + 5000 * N-x < Y:
        continue
    for y in range(0, N+1 - x ):
        if 10000 * x + 5000 * y > Y:
            break
        #print("total:%d 10000:%d 5000:%d 1000:%d" % (10000 * x + 5000 * y + 1000 * z, x, y, z))
        z = N - x - y
        if (Y == 10000 * x + 5000 * y + 1000 * z) and (N == x + y + z):
                print("%d %d %d" % (x, y, z))
                sys.exit()
                #example = "%d %d %d" % (x, y, z)
                #break

print('-1 -1 -1')


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

int main() {
    
    long int N,K;
    cin >> N >> K;
    
    long int sum = 0;
    
    
    sum += N+1-K+1 + (N+1)*(N+1+K)*(N+1-K+1)/2;
    sum %= 1000000007;
    sum += K*(K-1)*(2*K-1)/6;
    sum %= 1000000007;
    sum -= (N+1)*(N+2)*(2*N+3)/6;
    sum %= 1000000007;
    
    if(sum<0)
        sum +=1000000007;
    
    cout << sum << endl;
    
    return 0;
}


Measured memory_bytes: 3628
#pragma GCC optimize "-O3"
#pragma GCC target ("avx")
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())
#define SPEED ios::sync_with_stdio(false);cin.tie(0);cout<<fixed<<setprecision(12)
signed gcd(int a, int b){return b?gcd(b,a%b):a;}
signed lcm(int a, int b){return a*b/gcd(a,b);}
//priority_queue<int, vi, greater<int> > que;//昇順

using namespace std;

const int mod=1e9+7;

signed main(){
    SPEED;
    int n;
    cin >> n;
    cout << n/3 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;

int calc(char met, double nenri, int com, int money, int years){
   if(met=='0'){
       int total_risi=0;
       for(int i=0 ; i < years ; i++){
           total_risi += money * nenri;
           money -= com;
       }
       return(money+total_risi);
   }
   else if(met=='1'){
       for(int i=0 ; i < years ; i++){
          money = money + money * nenri - com;
       }
       return money;
   }
   else cout << "error!!" << endl;
}

int main(){
    int m;
    cin >> m;
    while(m>0){
        int money,years,n,ans=0;
        cin >> money >> years >> n;
        for(int i=0 ; i<n ; i++){
            char m; double n; int c;
            cin >> m >> n >> c;
            ans = max(calc(m,n,c,money,years),ans);
        }
        cout << ans << endl;
        m--;
    }
}

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

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define dbg(x) cout<<#x<<"="<<x<<endl
//using ld=long double;
using ll=long long;
//constexpr ld INF=1<<29;
//constexpr ld EPS=1e-10;

ll mod_pow(ll a,ll n,ll mod){
  ll res=1;
  while(n>0){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll mod_inv(ll a,ll mod){
  return mod_pow(a,mod-2,mod);
}

struct Int3{
  ll v1,v2,v3;
  const static ll MOD1=1e9+7, MOD2=1e9+9, MOD3=1e9+33;

  Int3()
    :v1(-1),v2(-1),v3(-1){}
  Int3(ll a, ll b, ll c)
    :v1(a),v2(b),v3(c){}

  bool isnull(){
    return v1==-1 && v2==-1 && v3==-1;
  }

  Int3 mul(ll cost){
    Int3 res = *this;
    (res.v1*=cost)%=MOD1;
    (res.v2*=cost)%=MOD2;
    (res.v3*=cost)%=MOD3;
    return res;
  }
  Int3 div(ll cost){
    Int3 res = *this;
    (res.v1*=mod_inv(cost,MOD1))%=MOD1;
    (res.v2*=mod_inv(cost,MOD2))%=MOD2;
    (res.v3*=mod_inv(cost,MOD3))%=MOD3;
    return res;
  }
  bool equal(Int3 opp){
    return v1==opp.v1
    && v2==opp.v2
    && v3==opp.v3;
  }
  void debug(){
    cout<<v1<<","<<v2<<","<<v3<<endl;
  }
};

int main(){
  int N,M;
  cin>>N>>M;
  // if positive, mul. else, div
  vector<vector<pair<int,ll>>> edges(N);
  rep(i,M){
    int a,b;
    ll x;
    cin>>a>>b>>x;
    a--;b--;
    edges[a].push_back({b,x});
    edges[b].push_back({a,-x});
  }

  // see all
  vector<bool> see(N,false);
  vector<Int3> costs(N,Int3());

  rep(i,N)if(!see[i]){
    costs[i]=Int3(1,1,1);
    queue<int> cands;
    cands.push(i);
    see[i]=true;

    while(!cands.empty()){
      int now=cands.front();cands.pop();
      //cerr<<"pos: "<<now<<" . ";
      //costs[now].debug();
      for(auto edge:edges[now]){
        int next;
        ll cost;
        tie(next,cost)=edge;

        Int3 ncost = cost>0
        ? costs[now].mul(cost)
        : costs[now].div(-cost);
        //ncost.debug();

        if(costs[next].isnull()){
          costs[next]=ncost;
          //cerr<<"now: "<<now<<" next: "<<next<<" : ";
          //costs[next].debug();
          cands.push(next);
          see[next]=true;
        }else{
          if(!costs[next].equal(ncost)){
            cout<<"No"<<endl;
            //cout<<"now: "<<now<<"next: "<<next<<endl;
            //costs[next].debug();
            //ncost.debug();
            return 0;
          }
        }
      }
    }
  }
  
  cout<<"Yes"<<endl;
  return 0;
}



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

int main() {
    int n, t, sum = 0;
    cin >> n;
    int m = 0;
    for (int i = 0; i < n; ++i) {
        cin >> t;
        m = max(t, m);
        sum += t;
    }
    sum -= m / 2;
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> a;
vector<ll> b;
bool po[(ll)1e5] = {1, 1};
vector<ll> v[(ll)1e5];
void dfs(ll now, bool yo){
	for(ll next : v[now]){
		if(po[next]) continue;
		po[next] = 1;
		(yo ? a : b).push_back(next);
		dfs(next, yo);
	}
}
int main(){
	ll n, m; cin >> n >> m;
	for(ll i = 0; i < m; ++i){
		ll a, b; cin >> a >> b;
		v[--a].push_back(--b);
		v[b].push_back(a);
	}
	a.push_back(0);
	b.push_back(1);
	dfs(0, 1);
	dfs(1, 0);
	bool yo = a.size() >= b.size();
	for(ll i = 0; i < n; ++i){
		if(po[i]) continue;
		(yo ? a : b).push_back(i);
	}
	ll ans = a.size() * (a.size() - 1) / 2 + b.size() * (b.size() - 1) / 2 - m;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 12916
c = [list(map(int, input().split())) for _ in range(3)]
a1 = c[0][0]
for i in range(a1+1):
    b1 = a1 - i
    b2 = c[0][1] - i
    b3 = c[0][2] - i
    a2 = c[1][0] - b1
    a3 = c[2][0] - b1

    if a2+b2 ==c[1][1] and a2+b3==c[1][2] and a3+b2 == c[2][1] and a3+b3 == c[2][2]:
        print('Yes')
    else:
        print('No')
    exit()

Measured memory_bytes: 9124
/*
 * I'm strong. Stronger than all of you. Extremely strong.
 * I can kill all those Titans there. Even if I'm alone.
 * You're either incompetent or you're spineless cowards.
 * How pathetic.
 * You can sit here and suck on your fingers. Yeah, do that.
 * ~ Mikasa Ackerman
 */

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> II;
typedef vector<II> VII;
typedef vector<int> VI;
typedef vector<VI> VVI;

typedef long long int LL;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(), a.end()
#define SET(a, b) memset(a, b, sizeof(a))
#define si(n) scanf("%d", &n)
#define dout(n) printf("%d\n", n)
#define sll(n) scanf("%lld", &n)
#define lldout(n) printf("%lld\n", n)

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

#define fast_io                                                                \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(NULL)

#define endl '\n'

int main() {
  fast_io;
  int n, a, b;
  cin >> n >> a >> b;
  cout << min(n * a, b) << endl;
  return 0;
}


Measured memory_bytes: 256
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from itertools import combinations # (string,3) 3回
#from collections import deque
#import collections.defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,m = readInts()
    s = input()
    t = input()
    from fractions import gcd
    g = gcd(n,m)
    res = n // g * m
    # 互いに素なn,mを作成する
    n //= g
    m //= g
    ok = True
    for i in range(g):
        # 0 ~ (g-1)まで調べる
        if s[i*n] != t[i*m]:
            ok = False
    if ok:
        print(res)
    else:
        print(-1)
if __name__ == '__main__':
  main()


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

using namespace std; 

int n; 
int x[101010], y[101010], vis[101010], vv[101010], dis[101010], maxdis, num, deg[101010]; 
char c[101010]; 
vector <int> G[101010], H[101010];
int d[101010], Q[101010]; 

void del() {    
    int h = 1, t = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 1 && c[i] == 'B') {
            Q[++t] = i; 
        }
    } 
    while (h <= t) {
        int u = Q[h++];
        vis[u] = 1;  
        for (auto v : G[u]) {
            deg[v]--; 
            if (deg[v] == 1 && c[v] == 'B') {
                Q[++t] = v; 
            }
        }
    }
    memset(deg, 0, sizeof(deg)); 
    for (int i = 1; i <= n; i++) {
        G[i].clear(); 
    }
    for (int i = 1; i < n; i++) {
        if (!vis[x[i]] && !vis[y[i]]) {
            G[x[i]].push_back(y[i]); 
            G[y[i]].push_back(x[i]); 
            deg[x[i]]++; 
            deg[y[i]]++; 
            num += 2; 
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            if ((c[i] == 'B' && deg[i] & 1) or (c[i] == 'W' && deg[i] % 2 == 0)) {
                vv[i] = 2; 
                num++; 
            }
        }
    }
}

void dfs(int u, int pre) {
    dis[u] = vv[u]; 
    for (auto v : G[u]) {
        if (v == pre) continue ;
        dfs(v, u);  
        maxdis = max(maxdis, dis[u] + dis[v]);
        dis[u] = max(dis[u], dis[v] + vv[u]); 
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v; 
        scanf("%d %d", &u, &v);
        x[i] = u, y[i] = v;  
        G[u].push_back(v); 
        G[v].push_back(u); 
        deg[u]++, deg[v]++; 
    }
    scanf("%s", c + 1); 
    del(); 
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i, 0); 
            break ; 
        }
    }
    printf("%d\n", num - maxdis); 
    return 0; 
} 


Measured memory_bytes: 15744
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
using namespace std;
typedef pair<int, int> P;

const int INF = 1e13;

int n, m;
int d[110][110];

void init(int n){
    rep(i, 0, n){
        rep(j, 0, n){
            d[i][j] = INF;
            if(i == j) d[i][j] = 0;
        }
    }
}

void warshall_floyd(){
    rep(k, 0, n){
        rep(i, 0, n){
            rep(j, 0, n){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

signed main(){
    cin >> n >> m;
    init(n);
    rep(i, 0, m){
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = c;    
    }
    warshall_floyd();
    rep(i, 0, n){
        if(d[i][i] != 0){
            cout << "NEGATIVE CYCLE" << endl;
            return 0;
        }
    }
    rep(i, 0, n){
        rep(j, 0, n){
            if(j != 0) cout << " ";
            if(d[i][j] >= 1e10) cout << "INF";
            else cout << d[i][j];
        }
        cout << endl;
    }
}

Measured memory_bytes: 3172
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using VVV = vector<VV>;
using VVVll = vector<VVll>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) (a).begin(), (a).end()
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline int sz(T &x) { return x.size(); }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << '(' << p.first << ", " << p.second << ')'; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << '\n'; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int fLog2(const int x) { assert(x > 0); return 31-__builtin_clz(x); } // floor(log2(x))
inline int fLog2(const ll x) { assert(x > 0); return 63-__builtin_clzll(x); }
inline int cLog2(const int x) { assert(x > 0); return (x == 1) ? 0 : 32-__builtin_clz(x-1); } // ceil(log2(x))
inline int cLog2(const ll x) { assert(x > 0); return (x == 1) ? 0 : 64-__builtin_clzll(x-1); }
inline int popcount(const int x) { return __builtin_popcount(x); }
inline int popcount(const ll x) { return __builtin_popcountll(x); }
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const ld PI    = acos(-1.0);
// const int MOD  = int(1e9)+7;
// const int MOD  = 998244353;


int main() {
  int n; cin >> n;
  V x(n), y(n);
  Vll p(n);
  rep(i, n) cin >> x[i] >> y[i] >> p[i];

  int N = 1<<n;
  VV xdst(n, V(N));
  VV ydst(n, V(N));

  rep(S, N) {
    VV rx(n, V(n+1, INF));
    VV ry(n, V(n+1, INF));
    rep(i, n) if (S>>i&1) {
      rep(j, n) rx[j][i] = abs(x[i]-x[j]);
      rep(j, n) ry[j][i] = abs(y[i]-y[j]);
    }
    rep(i, n) {
      rx[i][n] = abs(x[i]);
      ry[i][n] = abs(y[i]);
    }
    rep(i, n) xdst[i][S] = *min_element(all(rx[i]));
    rep(i, n) ydst[i][S] = *min_element(all(ry[i]));
  }

  Vll ans(n+1, INFll);

  rep(S, N) drep(T, S+1) {
    T &= S;
    int U = S^T;
    ll res = 0;
    rep(i, n) res += p[i] * min(xdst[i][T], ydst[i][U]);
    int k = popcount(S);
    chmin(ans[k], res);
  }

  cout << ans;
  return 0;
}


Measured memory_bytes: 7212
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);

	static ArrayDeque<int[]> que = new ArrayDeque<int[]>();

	static void solve() {
		int n = in.nextInt();
		int cnt = 1;
		while (n-- > 0) {
			char[][] table = new char[8][8];
			for (int i=0; i<8; i++) {
				table[i] = in.next().toCharArray();
			}

			que.add(new int[]{in.nextInt()-1,in.nextInt()-1});
			while (!que.isEmpty()) {
				burst(table, que.pollFirst());
			}

			out.println("Data " + (cnt++) + ":");

			for (int i=0; i<8; i++) {
				for (int j=0; j<8; j++) {
					out.print(table[i][j]);
				}
				out.println();
			}
		}
	}

	static void burst(char[][] table, int[] p) {
		int x = p[0], y = p[1];
		int[] dy = {0,1,0,-1};
		int[] dx = {1,0,-1,0};
		table[y][x] = '0';
		for (int k=0; k<4; k++) {
			int tx = x, ty = y;
			for (int i=0; i<3; i++) {
				tx += dx[k];
				ty += dy[k];
				if (tx < 0 || ty < 0 || 7 < tx || 7 < ty) continue;
				if (table[ty][tx] == '1') {
					que.add(new int[]{tx,ty});
				}
			}
		}
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();

		solve();
		out.flush();

		long end = System.currentTimeMillis();
		//trace(end-start + "ms");
		in.close();
		out.close();
	}

	static void trace(Object... o) { System.out.println(Arrays.deepToString(o));}
}

Measured memory_bytes: 26628
package main

import "fmt"

func main() {
	var b string
	fmt.Scan(&b)

	switch b {
	case "A":
		fmt.Println("T")
	case "T":
		fmt.Println("A")
	case "G":
		fmt.Println("C")
	case "C":
		fmt.Println("G")
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rp(i, n) for(int i = 0; i < n; i++)
#define rp2(i, a, n) for(int i = a; i < n; i++)

using namespace std;
using ll = long long;

int main(){
    int n; cin >> n;
    int ans = 0;
    int d;
    if(n < 5){
        cout << 0 << endl;
        return 0;
    }else{
        ans = 1000 * (n / 500);
        d = n % 500;
        ans += 5 * (d / 5);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        int ans = 0;
        for(int i = 1; i < b - a; i++) {
            ans += i;
        }
        System.out.println( ans - a );
    }
}


Measured memory_bytes: 35768
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#define _USE_MATH_DEFINES
using namespace std;
typedef long long ll;
double pi = 3.141592653589793;
ll mod = 1000000007;

int main() {
    string s, t;
    cin >> s >> t;
    int slen = s.length();
    int tlen = t.length();
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());
    bool ok = false;
    if (s < t) {
        ok = true;
    }
    if (ok) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


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

int main(){

  int H,W,N;
  cin >> H>>W>>N;
  
  if(H>W){ if(N%H==0)cout << N/H << endl;
          else cout << N/H+1 << endl;
         }
  else { if(N%W==0) cout << N/W << endl;
        else cout << N/W+1 << endl;
       }
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,l,r) for(int (i)=(l);(i)<(r);(i)++)
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<ll> a(n);
    rep(i,0,n) cin>>a[i];
    sort(a.begin(),a.end());
    ll ans=0,sum=0;
    rep(i,0,n-1){
        sum+=a[i];
        if(sum*2<a[i+1])ans=0;
        else ans++;
    }
    cout<<ans+1<<endl;
}

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

int main() {
  int n;
  cin >> n;
  if (n / 10 % 10 == n / 100 % 10)
  {
    if (n / 10 % 10 == n / 1000 % 10 || n / 10 % 10 == n % 10)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  }
  else
    cout << "No" << endl;   
}

Measured memory_bytes: 256
<?php

$loop = 0;
$N = 0;
$x = 0;
$a = 0;
while ($line = fgets(STDIN)){ 
  $arr = explode(" ", $line);
  if($loop == 0) {
    $N = (int)$arr[0];
    $x = (int)$arr[1];
  }
  $loop++;
};
$a = $arr;

$z = [];
$count = 0;
array_unshift($a, 0);
for($i=0; $i<$N; $i++){
    $tmp = $a[$i] + $a[$i + 1]; 
    if ($tmp > $x) {
      $sub = $tmp - $x;
      $a[$i + 1] = $a[$i + 1] - $sub;
      $count = $count + $sub;
    }
}

echo $count;

Measured memory_bytes: 29976
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int ans = Math.min(n * a, b);
        System.out.println(ans);
    }
}

Measured memory_bytes: 35816
#include<iostream>
using namespace std;

int main()
{
  int n,l;
  cin>>n>>l;
  int a=n*l+(n*(n+1))/2-n;
  int b=a-l+1;
  int k=9999999,ans=0;
  for(int i=1;i<=n;i++)
  {
    if(abs(a-b+i)<k)
    {
      k=abs(a-b+i);
      ans=b-i;
    }
  }
  cout<<ans<<endl;
}

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

#define M 1000000007

using namespace std;

unsigned long long int f(unsigned long long int a){
	if(a==0){
		 return 1;	
	}else if(a==1){
		return 2;
	}else if(a&1){
		return (f(a-1)<<1)%M;
	}else{
		unsigned long long int b=f(a/2);
		return (b*b)%M;
	}
}

int main(){
	int n, a;
	vector<int> v;
	unsigned long long int ans=0;
	
	cin>>n;
	v.resize((n+1)/2);

	for(int i=0; i<(n+1)/2; i++){
		v[i]=0;
	}

	if(n&1){
		for(int i=0; i<n; i++){
			cin>>a;
			if(a&1){
				cout<<0<<endl;
				return 0;
			}
			v[a/2]++;
		}
	}else{
		 for(int i=0; i<n; i++){
			 cin>>a;
			 if(!(a&1)){
				cout<<0<<endl;
				return 0;
			 }
			 v[(a-1)/2]++;
		 }
	}

	if(n&1){
		if(v[0]!=1){
			cout<<0<<endl;
			return 0;
		}
		for(int i=1; i<(n+1)/2; i++){
			if(v[i]!=2){
				cout<<0<<endl;
				return 0;
			}
		}
	}else{
		for(int i=0; i<(n+1)/2; i++){
			if(v[i]!=2){
				cout<<0<<endl;
				return 0;
			}
		}
	}

	cout<<f(n/2)<<endl;

	return 0;
}


Measured memory_bytes: 512
import java.util.*;
import java.io.*;
import java.lang.Math.*;

class Main{
    
    static int[] mData = new int[100000];
    static int[] dp = new int[100000];

    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        for(int i = 0; i < N; i++){
            mData[i] = sc.nextInt();
        }

        dp[0] = 0;
        dp[1] = Math.abs( mData[0] - mData[1] );

        for(int i = 2; i < N; i++){
            if(i - K < 0){
                int mmini = Math.abs( mData[0] - mData[i] );
                for(int j = 1; j < i; j++){
                    if(mmini > (dp[j] + Math.abs(mData[j]-mData[i])))
                        mmini = dp[j] + Math.abs(mData[j]-mData[i]);
                }
                dp[i] = mmini;
            }
            else{
                int mmini = Math.abs( mData[i-K] - mData[i] ) + dp[i-K];
                for(int j = i-K+1; j < i; j++){ 
                    if(mmini > (dp[j] + Math.abs(mData[j]-mData[i])))
                        mmini = dp[j] + Math.abs(mData[j]-mData[i]);
                }
                dp[i] = mmini;
            }
        }


        System.out.println(dp[N-1]);
        sc.close();
    }
}


Measured memory_bytes: 57728
N = int(input())
d = {}

def f(x):
  if x in d:
    return d[x]
  if x % 2 == 0:
    d[x] = 1 + f(x / 2)
    return d[x]
  else:
    d[x] = 0
    return d[x]

A = list(map(lambda x: f(x), [int(x) for x in input().split()]))
print(sum(A))

Measured memory_bytes: 14676
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

bool went[50 + 10][50 + 10][50 + 10][50 + 10] = { 0 };

int map[50 + 10][50 + 10]/* = { 0 }*/;

int gx[] = { 1,0,-1,0,-1,0,1,0 };
int gy[] = { 0,1,0,-1,0,-1,0,1 };

struct ST
{
	int tx, ty;
	int kx, ky;
	int tim=0;
};

bool ChekNow(ST);


ST GoMap(ST, int);

void test(ST ex, int h, int w)
{
	int i, j;
	cout << endl;
	for (i = 1; i <= h; i++)
	{
		for (j = 1; j <= w; j++)
		{
			if ((i == ex.ky && j == ex.kx) || (i == ex.ty && j == ex.tx))
				cout << "*";
			else cout << map[i][j];
		}
		cout << endl;
	}
	cout << ex.tim << endl;
}


int main()
{
	ST now,tmp;

	queue <ST> nx;


	int w, h;
	int tsx, tsy;
	int ksx, ksy;

	bool flg;
	int i, j;

	while (cin >> w >> h, w != 0 && h != 0)
	{
		flg = true;

		cin >> tsx >> tsy;
		cin >> ksx >> ksy;
		
		for (i = 1; i <= h; i++)
		{
			map[i][0] = map[i][w + 1] = 1;

			for (j = 1; j <= w; j++)
			{
				cin >> map[i][j];
			}
		}

		for (i = 0; i <= w + 1; i++)
		{
			map[0][i] = 1;
			map[h + 1][i] = 1;
		}


		now.tx = tsx;
		now.ty = tsy;
		now.kx = ksx;
		now.ky = ksy;
		now.tim = 0;

		nx.push(now);

		while (!nx.empty()) // && now.tim<100)
		{
			now = nx.front();
			nx.pop();


			if (now.tim >= 100)
			{
				break;
			}


			//if (ChekNow(now))
			//{
			//	continue;
			//}
			//went[now.tx][now.ty][now.kx][now.ky] = true;


			//test(now, h, w);


			if (now.tx == now.kx && now.ty == now.ky)
			{
				cout << now.tim << endl;

				flg = false;

				break;
			}

			for (i = 0; i < 4; i++)
			{
				//tmp=GoMap(now, i);


				tmp = now;

				if (map[now.ty + gy[i]][now.tx + gx[i]] == 0)
				{
					tmp.ty += gy[i];
					tmp.tx += gx[i];
				}
				if (map[now.ky + gy[i + 4]][now.kx + gx[i + 4]] == 0)
				{
					tmp.ky += gy[i + 4];
					tmp.kx += gx[i + 4];
				}


				if (!ChekNow(tmp))
				{
					tmp.tim++;

					went[tmp.tx][tmp.ty][tmp.kx][tmp.ky] = true;

					nx.push(tmp);
				}
			}
		}

		if (flg)
		{
			cout << "NA\n";
		}

		while (!nx.empty())
		{
			nx.pop();
		}


		memset(went, 0, sizeof(went));
	}
	return 0;
}


bool ChekNow (ST ex)
{
	return went[ex.tx][ex.ty][ex.kx][ex.ky];
}


ST GoMap(ST ex, int i)
{
	if (map[ex.ty + gy[i]][ex.tx + gx[i]] == 0)
	{
		ex.ty += gy[i];
		ex.tx += gx[i];
	}
	if (map[ex.ky + gy[i + 4]][ex.kx + gx[i + 4]] == 0)
	{
		ex.ky += gy[i + 4];
		ex.kx += gx[i + 4];
	}


	return ex;
}

Measured memory_bytes: 15856
#include<stdio.h>

#define CNST_DAY 365
#define NUM_CONTEST 26

int D,c[NUM_CONTEST+1]={},s[CNST_DAY+1][NUM_CONTEST+1]={},last[NUM_CONTEST+1]={},t[CNST_DAY+1]={};
long v[CNST_DAY+1]={};

void Scoring(int d){
    int i;

    last[t[d]]=d;
    
    v[d]=v[d-1]+s[d][t[d]];
    for(i=1;i<=NUM_CONTEST;i++){
        v[d]-=c[i]*(d-last[i]);
    }
    return;
}

void ReAllScoring(int day, int newcon){
    int i,d,oldcon=t[day];

    t[day]=newcon;
    for(i=1;i<=NUM_CONTEST;i++){
        last[i]=0;
    }
    for(d=1;d<=D;d++){
        v[d]=0;
    }
    for(d=1;d<=D;d++){
        //開催するコンテストt[d]を決めた後
        last[t[d]]=d;
        Scoring(d);
    }

    return;

}

int main(void){

    int i,j,k,d,n;

    int smax[CNST_DAY+1]={},maxcon[CNST_DAY+1]={};

    //入力
    scanf("%d",&D);
    for(d=1;d<=NUM_CONTEST;d++){
        scanf("%d",&c[d]);
    }
    for(d=1;d<=D;d++){
        for(i=1;i<=NUM_CONTEST;i++){
            scanf("%d",&s[d][i]);
        }
    }
    
    //スコア計算
    //よさそうなものを選ぶ
    int z;
    for(d=1;d<=D;d++){
        smax[d]=s[d][1];
        maxcon[d]=1;
        for(i=2;i<=NUM_CONTEST;i++){
            z=s[d][i]+c[i]*(d-last[i]);
            if(z>smax[d]){
                smax[d]=z;
                maxcon[d]=i;
            }
        }
        last[maxcon[d]]=d;
    }
    for(d=1;d<=D;d++){
        //その日一番大きい満足度が得られるコンテストを開く(満足度の低下を無視したもの)
        t[d]=maxcon[d];

        //開催するコンテストt[d]を決めた後
        //Scoring(d);
    }

    //出力
    for(d=1;d<=D;d++){
        //printf("%ld\n",v[d]);
        printf("%d\n",t[d]);
    }

    return 0;
}

Measured memory_bytes: 1776
//おまじない
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int n;
  cin>>n;
  
  vector<int> v(n);
  for (int i = 0; i < n; i++) {
  cin >> v.at(i);}

  
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
  cin >> c.at(i);}
  
  int sum=0;
  
  for(int i=0;i<n;i++){
    int d = v.at(i)-c.at(i);
    if(d>0){
      sum +=d;}}
  
  cout<<sum<<endl;}

  
  

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

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

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

constexpr int th = 300;
constexpr int sz = 112345;
LL imos[sz];
LL up = 0;
LL latte[th+1][th+1];
LL ret[sz];
int main() {
	int N, M;
	cin >> N >> M;
	for (int i : range(M)) {
		LL A, B;
		cin >> A >> B;
		A++;
		A %= B;
		if (B > th) {
			imos[0] += A;
			LL pos = B - A;
			while (pos < N) {
				imos[pos] -= B;
				pos += B;
			}
			up++;
		}
		else {
			latte[A][B]++;
		}
	}
	for (int i : range(1,N)) {
		imos[i] += imos[i - 1];
	}
	for (int i : range(N)) {
		ret[i] += up * i + imos[i];
	}
	for (int b : range(1, th + 1)) {
		vector<LL> m(b, 0);
		for (int a : range(b)) {
			for (int i : range(b)) {
				m[i] += latte[a][b]*((a + i) % b);					
			}
		}
		for (int i : range(N)) {
			ret[i] += m[i%b];
		}
	}
	for (int i : range(N)) {
		cout << ret[i] << endl;
	}
	return 0;
}



Measured memory_bytes: 5276
#include<iostream>
using namespace std;
 
int f(int _i)
{
    return _i*_i;
}
 
int main()
{
    int d;
    while(cin >> d){
        int S = 0;
 
        for(int i=1;i<600/d;++i){
            S += f(d*i)*d;
        }
 
        cout << S << endl;
 
    }
    return 0;
}

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

int main() {
    string S,R;
    cin >> S;
    R = S;
    reverse(R.begin(), R.end());
    int ans=0;
    for (int i=0; i<S.size()/2; i++) {
        if (S.at(i)!=R.at(i)) ans++;
    }
    cout << ans;
}

Measured memory_bytes: 256