akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(char &c){
  int i;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c = i;
}
inline int rd(char c[]){
  int i, sz=0;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
int N;
char S[100002];
char res[100002];
int main(){
  int a, b, i, j, k;
  rd(N);
  rd(S);
  for(i=0;i<(N);i++){
    if(S[i]=='o'){
      S[i] =0;
    }
    else{
      S[i] =1;
    }
  }
  for(a=0;a<(2);a++){
    for(b=0;b<(2);b++){
      res[0] = a;
      res[1] = b;
      for(i=(2);i<(N);i++){
        res[i] = (res[i-2] + res[i-1] + S[i-1]) % 2;
      }
      if( (res[N-2] + res[N-1] + S[N-1] + res[0]) % 2 ){
        continue;
      }
      if( (res[N-1] + res[0] + S[0] + res[1]) % 2 ){
        continue;
      }
      for(i=0;i<(N);i++){
        if(res[i]==0){
          res[i] ='S';
        }
        else{
          res[i] ='W';
        }
      }
      wt_L(res);
      wt_L('\n');
      return 0;
    }
  }
  wt_L(-1);
  wt_L('\n');
  return 0;
}


Measured memory_bytes: 512
# ITP_11_A
class Dice :
    # クラス変数
    def __init__(self, dice) :
        self.dice = dice
    
    def roll(self, direction):
        tmp = self.dice[:]
        if direction == "N":
            self.dice[0] = tmp[1]
            self.dice[1] = tmp[5]
            self.dice[4] = tmp[0]
            self.dice[5] = tmp[4]
        elif direction == "E":
            self.dice[0] = tmp[3]
            self.dice[2] = tmp[0]
            self.dice[3] = tmp[5]
            self.dice[5] = tmp[2]
        elif direction == "W":
            self.dice[0] = tmp[2]
            self.dice[2] = tmp[5]
            self.dice[3] = tmp[0]
            self.dice[5] = tmp[3]
        else:
            self.dice[0] = tmp[4]
            self.dice[1] = tmp[0]
            self.dice[4] = tmp[5]
            self.dice[5] = tmp[1]
            
    def dice_show(self):
        print(self.dice[0])

dice = Dice(list(map(str, input().split())))

for dire in list(input()):
    dice.roll(dire)
    
dice.dice_show()


Measured memory_bytes: 5572
n,k=gets.split.map &:to_i;s=gets.chars.map{|c|c==?A?0:1};f=i=0;((~s[i]+f)%2>0?s[i]=1-f :(s[n+i]=f^=1;i+=1);k-=1)while i<n&&k>0;puts k>0?['',[?B,?A][(~s[i]+f+k)%2]][n%2]+'BA'*(n/2):s[i,n].map{|c|[?B,?A][(~c+f)%2]}*''

Measured memory_bytes: 31740
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int d = sc.nextInt();
    int dtmp = d;
    d++;
    int ans = 1;

    while (true) {
      d += (2 * dtmp) + 1;
      if ((d - dtmp) <= n) {
        ans++;
      } else {
        break;
      }
    }

    System.out.println(ans);

  }
}

Measured memory_bytes: 35692
#include <bits/stdc++.h>
using namespace std;
int a[21],b[21],c[21],cnt=0,last=-1,n;
int main()
{
    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)
    {
        if(a[i]-last==1)
            cnt+=b[a[i]-1]+c[last-1];
        else
            cnt+=b[a[i]-1];
        last=a[i];
    }
    cout<<cnt;
    return 0;
}

Measured memory_bytes: 256
import math
x = int(input())
if x < 4:
    print(1)
    exit()

ans = 1 # 1^b = 1
for i in range(2, x+1): # [2,x]
    a = i # a^1
    while a < x:
        a *= i # a^b,(b>=2)
        if a <= x: ans = max(ans, a)
print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
int n;
int u[101], k[101];
int d[101], f[101];
vector<vector<int>> g;
bool visit[101];
int t = 0;
void dfs(int a){
	if(visit[a]==false){
	 	visit[a] = true;
	 	t++;
	 	d[a] = t;
		for(auto c : g[a]){
			dfs(c);
		}
		t++;
		f[a] = t;
	}else{
		return;
	}
	return;
}

int main() {
	cin >> n;
	g.resize(n+1);
	for(int i=1;i<=n;i++){
		d[i] = 0;
		f[i] = 0;
		visit[i] = false;
		cin >> u[i] >> k[i];
		if(k[i]){
			for(int j=1;j<=k[i];j++){
				int v; cin >> v;
				g[u[i]].push_back(v);
			}
		}
	} 
	for(int i=1;i<=n;i++){
		if(visit[i]==false) dfs(i);
	}
	for(int i=1;i<=n;i++){
		cout << i << ' ' << d[i] << ' ' << f[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 3164
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x, y;
    cin >> x >> y;
    int ans = 0;
    while(x <= y){
        x *= 2;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
	int k;
	cin >> k;
	if(k % 2 != 0){
		cout << (k / 2 + 1) * (k / 2) << endl;
	} else {
		cout << (k / 2) * (k / 2) << endl;
	}
	return 0;
}

Measured memory_bytes: 256
def golf(k, a, b):
    for i in range(a, b+1):
        if i % k == 0:
            return 'OK'
    return 'NG'

def main():
    K = int(input())
    A, B = map(int, input().split())
    print(golf(K, A, B))
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 9116
#include<cstdio>
#include<algorithm>
#define ll long long
#define rg register
struct ios{
	template<typename TP>
	inline ios operator >> (TP &x)
	{
		TP f=1;x=0;rg char c=getchar();
		for(;c>'9' || c<'0';c=getchar()) if(c=='-') f=-1;
		for(;c>='0' && c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
		x*=f;
		return *this;
	}
	template<typename TP>
	inline ios operator << (TP x)
	{
		int top=0,s[66];
		if(x<0) x=-x,putchar('-');
		if(!x) putchar ('0');
		while(x) s[++top]=x%10+'0',x/=10;
		while(top) putchar(s[top--]);
		return *this;
	}
	inline ios operator << (char s)
	{
		putchar(s);
		return *this;
	}
}io;
#define int ll
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N=1e5+5;
int n,m;
const int inf=1ll<<60;
struct node{
	int l,r,val;
	inline bool operator < (const node &b) const {
		return l<b.l || (l==b.l && r<b.r);
	}
}seq[N];
int Mn[N<<2],lazy[N<<2];
inline void pushup(int rt) {Mn[rt]=std::min(Mn[rt<<1],Mn[rt<<1|1]);}
inline void build(int l,int r,int rt)
{
	Mn[rt]=lazy[rt]=inf;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(lson),build(rson);
	pushup(rt); 
}
inline void pushdown(int rt)
{
	if(lazy[rt]!=inf)
	{
		if(lazy[rt]<lazy[rt<<1])
	    {
	        Mn[rt<<1]=std::min(Mn[rt<<1],lazy[rt]);
	        lazy[rt<<1]=lazy[rt];
	    }
	    if(lazy[rt]<lazy[rt<<1|1])
	    {
	        Mn[rt<<1|1]=std::min(Mn[rt<<1|1],lazy[rt]);
	        lazy[rt<<1|1]=lazy[rt];
	    }
	    lazy[rt]=inf;
	}
}
inline void update(int L,int R,int val,int l,int r,int rt)
{
    if(L<=l && r<=R)
    {
        lazy[rt]=std::min(lazy[rt],val);
        Mn[rt]=std::min(Mn[rt],val);
        return;
    }
    int mid=(l+r)>>1;pushdown(rt);
    if(L<=mid) update(L,R,val,lson);
    if(R>mid) update(L,R,val,rson);
    pushup(rt);
}
inline int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R) return Mn[rt];
    int mid=(l+r)>>1,ret=inf;pushdown(rt);
    if(L<=mid) ret=std::min(ret,query(L,R,lson));
    if(R>mid) ret=std::min(ret,query(L,R,rson));
    return ret;
}
signed main()
{
	io>>n>>m;
	for(rg int i=1;i<=m;++i) io>>seq[i].l>>seq[i].r>>seq[i].val;
	std::sort(seq+1,seq+m+1);
	int cnt=0;
	build(1,n,1),update(1,1,0,1,n,1);
	for(rg int i=1;i<=n;++i)
	{
		int nw=query(i,i,1,n,1);
		while(cnt<m&&seq[cnt+1].l<=i)
		{
			++cnt;
			if(i>=seq[cnt].l&&i<seq[cnt].r) update(i+1,seq[cnt].r,nw+seq[cnt].val,1,n,1);
		}
	}
	int ans=query(n,n,1,n,1);
	if(ans==inf) puts("-1");
	else io<<ans;
	return 0;
}

Measured memory_bytes: 8704
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
    //System.out.print("1???100????????????????\?????????°???????????¨?????\????????????????????????");
    Scanner scan = new Scanner(System.in);
    int x = scan.nextInt();
    
    if (x > 0 && x <= 100) {
      System.out.println(x * x * x);  
    } else {
        System.out.println("ERROR????????£????????§???");
    }
}    
}

Measured memory_bytes: 26256
#include <stdio.h>
#include <string.h>

typedef long long ll;

#define N 1100
#define M 1100000

ll a[N], b[M], c[M];

int main() {
    int n, k;
    while (scanf("%d%d", &n, &k) != EOF) {
        a[0] = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &a[i]);
            a[i] = a[i - 1] + a[i];
        }
        int m = 0;
        for (int i = 1; i <= n; ++i) {
            b[m++] = a[i] - a[i - 1];
            for (int j = i + 1; j <= n; ++j) {
                b[m++] = a[j] - a[i - 1];
            }
        }
        ll res = 0;
        for (int i = 40; i >= 0; --i) {   //铵位枚举
            int cnt = 0;
            for (int j = 0; j < m; ++j) {   //判断某一位有多少出现了多少次
                if (b[j] & (1ll << i)) {   //是1加上小写的ll，不是111
                    c[cnt++] = b[j];
                }
            }
            if (cnt >= k) {
                for (int j = 0; j < cnt; ++j) b[j] = c[j];
                m = cnt;
                res = res + (1ll << i);
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}


Measured memory_bytes: 7168
/**   Created by: Marcos Portales
          Codeforces User: marcosportales
          Country: Cuba
          Copyright                    */
#include<bits/stdc++.h>
using namespace std;
/// Pragmas:
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2") //Enable AVX
/// Macros:
#define int long long
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define enl '\n'
#define vi vector<int>
#define sz(a) int((a).size())
#define rep(i,n) for(int i=0;i<(n);i++)
#define repi(i,n) for(int i=(1);i<=(n);i++)
typedef pair<int,int> ii;
typedef long double ld;
typedef unsigned long long ull;
/// Constraints:
const int maxn = 200005;
const int mod = 1000000007;
const ld eps = 1e-9;
const int inf = ((1ll<<31ll)-1ll);
const int INF = 2000000000000000000ll;
const ld pi = acos(-1);
/// Prime Numbers:
// 2, 173, 179, 181, 197, 311, 331, 737, 1009, 2011, 2027, 3079, 4001, 10037, 10079, 20011, 20089;
// 100003, 100019, 100043, 200003, 200017, 1000003, 1000033, 1000037, 1000081;
// 2000003, 2000029, 2000039, 1000000007, 1000000021, 2000000099;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lgx(x,b) ( log(x) / log(b) )
/// Red-Black Tree Test.insert(x)late ---------------------------------
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
/// Quick Pow------------------------------------------------
int qpow(int b,int e){
    if( !e ) return 1;
    if( e & 1 ) return qpow(b,e-1) * b % mod;
    int pwur = qpow(b,e>>1);
    return (pwur * pwur) % mod;
}
int modinv(int x){
    return qpow(x,mod-2);
}

/// My Code -------------------------------------------------

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(0);
    srand(time(NULL));
    //freopen("a.in","r",stdin);
    //freopen("a.in","w",stdout);
    int n,k;
    cin>>n>>k;
    int ans=0;
    rep(i,n){
        int x;
        cin>>x;
        if(x<=k){
            ans+=min({x,k-x});
        }
        else{
            ans+=min({x,x-k});
        }
    }
    cout<<2*ans<<enl;

    return 0;
}


Measured memory_bytes: 3636
N=input()
a=[]
for i in range(2*N):
	x,y=map(int, raw_input().split())
	if i<N: a.append([x,y,"R"])
	else: a.append([x,y,"B"])

b=sorted(a, key=lambda x: x[0], reverse=True)


q=[]
ans=0
for i in b:
	x=i[1]
	type=i[2]
	if type=="B":
		q.append(x)
	elif type=="R" and len(q)>0:
		up=0
		tmp=[]
		for j in q:
			if x<=j:
				tmp.append(j)
				up=1
		ans+=up
		if len(tmp)>0:
			val=min(tmp)
			q.remove(val)

print ans

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

char mark(int n){
	if (n % 2 == 0){
		return '#';
	}
	else{
		return '.';
	}
}

int main()
{
	int H, W, count;
	while (cin >> H >> W){
		count = 0;
		if (H == 0 && W == 0){
			break;
		}
		for (int i = 0; i < H; i++){
			for (int j = 0; j < W; j++){
				cout << mark(count++);
			}
			cout << endl;
			if (W % 2 == 0){
				count++;
			}
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
LL L;
LL A[200001];
LL dp[10][200011];
int main(){
	cin>>L;
	REP(i,L){
		cin>>A[i];
	}
	REP(i,6){
		dp[i][0]=1e16;
	}
	dp[0][0]=0;//一回も使ってない
	
	REP(i,L){
		//cout<<endl<<"A[i]"<<A[i]<<endl;
		dp[0][i+1]=dp[0][i]+A[i];
		dp[1][i+1]=min(dp[1][i],dp[0][i])+max(A[i]%2,2-A[i]);
		dp[2][i+1]=min(dp[0][i],min(dp[1][i],min(dp[2][i],dp[2][i])))+max((A[i]+1)%2,1-A[i]);
		dp[3][i+1]=min(dp[0][i],min(dp[1][i],min(dp[2][i],dp[3][i])))+max(A[i]%2,2-A[i]);
		dp[4][i+1]=min(dp[0][i],min(dp[1][i],min(dp[2][i],min(dp[3][i],dp[4][i]))))+A[i];
		//cout<<dp[0][i+1]<<" a"<<endl;
		//cout<<dp[1][i+1]<<" b"<<endl;
		//cout<<dp[2][i+1]<<" c"<<endl;
		//cout<<dp[3][i+1]<<" d"<<endl;
		//cout<<dp[4][i+1]<<" e"<<endl<<endl;
	}
	LL ans=1e18;
	ans=min(ans,dp[0][L]);
	ans=min(ans,dp[1][L]);
	ans=min(ans,dp[2][L]);
	ans=min(ans,dp[3][L]);
	ans=min(ans,dp[4][L]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 11264
#include <bits/stdc++.h>
    #define REP(i, n) for(int i = 0;i < n;i++)
    #define REPR(i, n) for(int i = n;i >= 0;i--)
    #define FOR(i, m, n) for(int i = m;i < n;i++)
    #define FORR(i, m, n) for(int i = m;i >= n;i--)
    #define SORT(v, n) sort(v, v+n);
    #define VSORT(v) sort(v.begin(), v.end());
    #define llong long long
    #define pb(a) push_back(a)
    #define INF
    using namespace std;
    typedef pair<int, int> P;
    typedef pair<llong, llong> LP;
    typedef pair<int, P> PP;
    typedef pair<llong, LP> LPP;
    //vector<tuple<long long, long long, long long>>vec;

    int dy[]={0, 0, 1, -1, 0};
    int dx[]={1, -1, 0, 0, 0};


    int main()
    {
        int n,k;
        string s;
        cin>>n;
        cin>>s;
        cin>>k;
        for(int i=0; i<n; i++)
        {
            if(s[i]!=s[k-1]){s[i]='*';}
        }
        cout<<s<<endl;
    }



Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		if(b-a == c-b){
			System.out.println("YES");
		}
		else{
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 22228
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;


public class B
{
	public static void Main()
	{
		int X = Int32.Parse(Console.ReadLine());
		int ans = 1;
		for(int b = 2; b <= Math.Sqrt(X); b++)
		{
			for(int p = 2; ; p++)
			{
				int num = (int)Math.Pow(b,p);
				if(num > X)
					break;
				ans = Math.Max(ans,num);
			}
		}

		Console.WriteLine(ans);
	}
}





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

int main(){
    long long a,b,c,d;
    cin >> a >> b >> c >> d;
    long long e = lcm(c,d);
    long long cc = (b/c) - ((a+c-1)/c) + 1;
    long long dd = (b/d) - ((a+d-1)/d) + 1;
    long long ee = (b/e) - ((a+e-1)/e) + 1;
    cout << b - a + 1 - cc - dd + ee << endl;
}

Measured memory_bytes: 3580
#include <iostream>
#include <string>
#include <map>
using namespace std;

int main(){
    typedef pair<int,string> P;
    map <P,int> data;
    map <P,int>::iterator itr;
    int tmp2;
    string tmp;
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> tmp >> tmp2;
        if(data.find(P(tmp.size(),tmp))!=data.end()) data[P(tmp.size(),tmp)] += tmp2;
        data.insert(map <P,int>::value_type(P(tmp.size(),tmp),tmp2));
    }
    for(itr=data.begin();itr!=data.end();itr++) cout << itr->first.second << " " << itr->second << endl;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main() {
  string s, t;
  cin >> s >> t;
  ll a, b;
  cin >> a >> b;
  string u;
  cin >> u;
  if (u == s) {
    cout << a - 1 << " " << b << endl;
  } else {
    cout << a << " " << b - 1 << endl;
  }
}

Measured memory_bytes: 256
use text_io::*;
use std::collections::*;
use std::process::exit;
use std::cmp::*;

fn main() {
    let mut n:usize = read!();
    let mut b:usize = 0;
    let mut c:usize = 0;
    let mut bi:usize = 0;
    for i in 0..n {
        let a:usize = read!();
        if a>=b {
            c=b;
            b=a;
            bi=i;
        }
        else if a>c {
            c=a;
        }
    }
    for i in 0..n {
        if i!=bi {
            println!("{}",b);
        }
        else {
            println!("{}",c);
        }
    }
}

Measured memory_bytes: 2064
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

int main() {
  ll n, k; cin >> n >> k;
  k--;
  vector<pair<ll, ll> > A;
  loop(i,0,n) {
    ll a, b; cin >> a >> b;
    A.emplace_back(a, b);
  }
  sort(A.begin(), A.end());
  ll sum = 0;
  for (auto a: A) {
    if (sum + a.second > k) {
      cout << a.first << endl;
      return 0;
    }
    
    sum += a.second;
  }
  cout << A[A.size()-1].first << endl;
  return 0;
}


Measured memory_bytes: 5280
import java.util.Scanner;
public class Main {
	static Scanner scan=new Scanner(System.in);
	static int gcd (int a, int b) {return b>0?gcd(b,a%b):a;}
	static long lcm (int a, int b) {return a*b/gcd(a,b);}
	static int max(int a,int b) {return a>b?a:b;}
	static int min(int a,int b) {return a<b?a:b;}
	static long factorial(int i) {return i==1?1:i*factorial(i-1);}
	static int lower_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<=key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static int upper_bound(int a[],int key) {
		int low=0,high=a.length;
		while(low<high) {
			int mid=((high-low)/2)+low;
			if(a[mid]<key)low=mid+1;
			else high=mid;
		}
		return high;
		}
	static boolean isPrime (int n) {
		if (n==2) return true;
		if (n<2 || n%2==0) return false;
		double d = Math.sqrt(n);
		for (int i=3; i<=d; i+=2)if(n%i==0){return false;}
		return true;
	}
	static int upper_division(int a,int b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lupper_division(long a,long b) {
		if(a%b==0) {
			return a/b;
		}
		else {
			return a/b+1;
		}
	}
	static long lmax(long a,long b) {return Math.max(a, b);}
	static long lmin(long a,long b) {return Math.min(a, b);}
	static int[] setArray(int a) {
		int b[]=new int[a];
		for(int i=0;i<a;i++) {
			b[i]=scan.nextInt();
		}
		return b;
	}
	static String reverce(String str) {
		String strr="";
		for(int i=str.length()-1;i>=0;i--) {
			strr+=str.charAt(i);
		}
		return strr;
	}
	public static void main(String[] args) {
		int a=scan.nextInt();
		int b=scan.nextInt();
		int c=scan.nextInt();
		System.out.println(a*b/2);
	}
}


Measured memory_bytes: 21716
<?php
const INPUT_DELIMITER = " ";
const OUTPUT_DELIMITER = " ";

// 標準入力
$N = fgets(STDIN);

// 標準入力
$input = fgets(STDIN);
$inputArray = explode(INPUT_DELIMITER, $input);

$border = 0;
for ($i = 0; $i < $N; $i++) {
    if ($border > $inputArray[$i]) {
        echo "No";
        return;
    }
    if ($border < $inputArray[$i]) {
        $border = $inputArray[$i] - 1 ;
    }
}
echo "Yes";

Measured memory_bytes: 22388
#include<bits/stdc++.h>
using namespace std; 
#define ll long long  
int main(){

ll n ; ll t; cin>>n>>t;  
vector<ll> a(n); 
for(int i=0;i<n;i++)
	cin>>a[i]; 

ll time =0 ;
for(int i=0;i<n-1;i++)
 {
 	time+=min(t,a[i+1]-a[i]);
 }

 time+=t; 
cout<<time; 

}

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

#define int long long

void solve(int R0, int W0, int C, int R) {
    int imin = -1;
    int imax = numeric_limits<signed>::max();
    while (imax - imin > 1) {
        int imid = (imax + imin) / 2;
        if (R0 + imid * R >= C * W0) {
            imax = imid;
        } else {
            imin = imid;
        }
    }
    cout << imax << endl;
}

signed main() {
    int R0, W0, C, R;
    while (true) {
        cin >> R0 >> W0 >> C >> R;
        if (!R0 && !W0 && !C && !R) {
            break;
        }
        solve(R0, W0, C, R);
    }
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)

const ll MOD = (ll)1e9 + 7;
const ll HIGHINF = (ll)1e18;

// 左子右兄弟表現
struct Node {
  ll parent, left, right;
};

Node t[100005];
ll n, d[100005];

void print(ll u) {
  cout << "node " << u << ": ";
  cout << "parent = " << t[u].parent << ", ";
  cout << "depth = " << d[u] << ", ";
  if (t[u].parent == -1) cout << "root, ";
  else if (t[u].left == -1) cout << "leaf, ";
  else cout << "internal node, ";
  cout << "[";
  for (ll i=0, c=t[u].left; c!=-1; i++, c=t[c].right) {
    if (i) cout << ", ";
    cout << c;
  }
  cout << "]" << endl;
}

ll rec(ll u, ll p) {
  d[u] = p;
  if (t[u].right != -1) rec(t[u].right, p);
  if (t[u].left != -1) rec(t[u].left, p+1);
}

int main() {
  cin >> n;
  ll l = 0, r = 0;
  REP(i, n) t[i].parent = t[i].left = t[i].right = -1;
  REP(i, n) {
    ll v, dim; cin >> v >> dim;
    REP(j, dim) {
      ll c; cin >> c;
      if (j == 0) t[v].left = c;
      else t[l].right = c;
      l = c;
      t[c].parent = v;
    }
  }
  REP(i, n) if (t[i].parent == -1) r = i;
  rec(r, 0);
  REP(i, n) print(i);
  return 0;
}



Measured memory_bytes: 9324
/*
AizuOnline A0233
Title
@kankichi573
*/
#include <stdio.h>
int n;
//
int solve100(int n)
{
        if(n < 10)
                return(n);
        else
                return((n % 10) + (100 - (n/10)*10));
}

int solve_p(int n)
{
        int c;
        
        if(n==0)
                return(0);
        c=n/100;
        if((n % 100) >= 10)
                c++;
        //printf(":%d\n",c);
        return(100*solve(c)+solve100(n % 100));
}

int solve100_n(int n)
{
        int c,c2;

        c=n/10;
        if((n % 10)>0)
                c++;
        c2=(10 - (n%10))%10;
        return(c*10+c2);
}

int solve_n(int n)
{
        int c1,c2;

        if(n==0)
                return(0);
        c2=n%100;
        c1=n/100;
        if(c2>90)
        {       c2=(10-c2%10)%10;
                c1++;
                return(100*solve_n(c1)+c2);
        }
        else
                return(100*solve_n(c1)+solve100_n(c2));
}
int solve(int n)
{
        if(n>=0)
                return(solve_p(n));
        else
                return(solve_n(-n));
}
main()
{
        int n;

        while(EOF!=scanf("%d",&n) && n)
                printf("%d\n",solve(n));
        return(0);
}

Measured memory_bytes: 600
import java.math.BigInteger;

public class Main {
    private static java.util.Scanner scanner = new java.util.Scanner(System.in);

    public static void main(String[] args) {
        int n = scanner.nextInt();
        BigInteger j = BigInteger.valueOf(scanner.nextInt());
        for (int i = 1; i < n; i++)
            j = j.gcd(BigInteger.valueOf(scanner.nextInt()));
        System.out.println(j.intValue());
    }
}

Measured memory_bytes: 62676
#include<bits/stdc++.h>
using namespace std;
int a[10212004],n,sum,ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		a[i]=i;
		sum+=i;
		if(sum>=n) break;
	}
	ans=sum-n;
	for(int i=1;i<=n;i++){
		if(!a[i]) continue;
		if(a[i]!=ans) cout<<a[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main
{
 static Hashtable<String ,Integer>hash=new Hashtable<>();
  public static void main(String args[]) throws java.lang.Exception
  {
    MyScanner sc = new MyScanner();
  
     //  hash=new Hashtable<>();

    int n=Integer.parseInt(sc.nextLine());
    long c=0;
    for(int k=1;k<=n;k++)
    {
      if(k%3==0 || k%5==0){}
        else{c+=(long)k;}
    }
    System.out.println(c);
      
       
     
     
   }
     
  
  

  
  }

   class MyScanner {
      BufferedReader br;
      StringTokenizer st;
 
      public MyScanner() {
         br = new BufferedReader(new InputStreamReader(System.in));
      }
 
      String next() {
          while (st == null || !st.hasMoreElements()) {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
 
      int nextInt() {
          return Integer.parseInt(next());
      }
 
      long nextLong() {
          return Long.parseLong(next());
      }
 
      double nextDouble() {
          return Double.parseDouble(next());
      }
 
      String nextLine(){
          String str = "";
    try {
       str = br.readLine();
    } catch (IOException e) {
       e.printStackTrace();
    }
    return str;
      }
 
   }

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

#define REP(i, start, count) for(int i=(start); i<(int)(count); ++i)
#define rep(i, count) REP(i, 0, count)
#define ALLOF(c) (c).begin(), (c).end()

typedef long long ll;
typedef unsigned long long ull;

int N, M, K;

struct person {
    vector<int> friends = vector<int>();
    set<int> blocks = set<int>();
    int candidates = 0;
    int t = 0;
};

int main(void) {

    cin >> N >> M >> K;

    
    vector<person> P(N + 1);

    rep(i, M) {
        int a, b;
        cin >> a >> b;
        P[a].friends.push_back(b);
        P[b].friends.push_back(a);
    }

    rep(i, K) {
        int a, b;
        cin >> a >> b;
        P[a].blocks.insert(b);
    }

    stack<int> S;
    vector<int> searched(N + 1, 0);


    for (int i = 1; i <= N; ++i) {
        if (searched[i] != 0) continue;
        S.push(i);
        searched[i] = 1;
        set<int> relations;
        relations.insert(i);

        while (!S.empty()) {
            int idx = S.top();
            bool found = false;
            for (int k = P[idx].t; k < P[idx].friends.size(); ++k) {
                int fidx = P[idx].friends[k];
                if (searched[fidx] == 0) {
                    searched[fidx] = 1;
                    S.push(fidx);
                    relations.insert(fidx);
                    P[idx].t = k;
                    found = true;
                    break;
                }
            }
            if (!found) {
                searched[idx] = 2;
                S.pop();
            }
        }

        for (int k : relations) {
            for (int r : P[k].blocks) {
                auto itr = relations.find(r);
                if (itr != relations.end()) {
                    P[k].candidates--;
                    P[*itr].candidates--;
                }
            }
            P[k].candidates += (relations.size() - P[k].friends.size() - 1);
        }
    }

    REP(i, 1, N + 1) {
        cout << P[i].candidates;
        if (i != N) cout << ' ';
    }
    cout << endl;


    return 0;
}

Measured memory_bytes: 21880
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PI 4*atan(1.0)
typedef long long ll;
typedef long double ld;
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
const int SIZE=205;
//int arr[SIZE]={};
//ここまでテンプレ
int main(){
	int A,B,C,D,E,F;
	cin>>A>>B>>C>>D>>E>>F;

	double maxi=0.0;
	int ansa=100*A,ansb=0;
	for(int a=0;a<=30;a++){
		for(int b=0;b<=30;b++){
			int w=100*a*A+100*b*B;
			if(w<=F && w!=0){
				for(int c=0;c<=w/100*E;c++){
					for(int d=0;d<=w/100*E;d++){
						//cout<<c<<" "<<d<<endl;
						int s=c*C+d*D;
						if(s<=w/100*E && s+w<=F){
							//cout<<w+s<<" "<<s<<endl;
							double node=(100*(double)s)/((double)w+(double)s);
							if(node>maxi){
								maxi=node;
								ansa=w+s;
								ansb=s;
							}
						}
					}
				}
			}
		}
	}
	cout<<ansa<<" "<<ansb<<endl;
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

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

    // start
    int x;
    cin >> x;
    cout << (x < 1200 ? "ABC" : "ARC") << endl;
    // end

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
#include <iterator>
#include <stdio.h>
#define ll long long
#define ull unsigned long long int
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define ff first
#define ss second
#define sz(a) int((a).size())
#define all(a) (a).begin(),(a).end()
#define fr(i,p,n) for(int i=p;i<n;i++)
#define precise cout << std::setprecision(10) << std::fixed;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
ll M=1000000007;
//ll M=  998244353;
typedef pair<int, int> pairs;

int main()
{
    fastio; precise;
    int T=1;
    //cin>>T;
    while(T--){
        int n,w,x=0;
        cin>>n>>w;
        ll wt[n];
        int v[n];
        fr(i,0,n){
        cin>>wt[i]>>v[i];
        }
        int m=1e5+1;
        ll dp[n+1][m];
        // cout<<1<<endl;
        fr(i,0,m) dp[0][i]=INT_MAX;
        dp[0][0]=0;
        fr(i,0,n){
        fr(j,0,m){
        // cout<<2<<endl;
        dp[i+1][j]=dp[i][j];
        if(j-v[i]>=0) dp[i+1][j]=min(dp[i+1][j],dp[i][j-v[i]]+wt[i]);
        }
        // cout<<2<<endl;
        }
        fr(i,0,m) if(dp[n][i]<=w) x=i;
        cout<<x<<endl;


    }
     return 0;
}


Measured memory_bytes: 82548
import sys

ABCD = input()
A = int(ABCD[0])
B = int(ABCD[1])
C = int(ABCD[2])
D = int(ABCD[3])

for i in range(2):
    s0 = A
    if i == 0:
        s1 = s0 + B
    else:
        s1 = s0 - B

    for j in range(2):
        if j == 0:
            s2 = s1 + C
        else:
            s2 = s1 - C

        for k in range(2):
            if k == 0:
                s3 = s2 + D
            else:
                s3 = s2 - D

            if s3 == 7:
                ans = str(A)
                if i == 0:
                    ans += '+'
                else:
                    ans += '-'
                ans += str(B)
                if j == 0:
                    ans += '+'
                else:
                    ans += '-'
                ans += str(C)
                if k == 0:
                    ans += '+'
                else:
                    ans += '-'
                ans += str(D)
                ans += '=7'
                print(ans)
                sys.exit()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <queue>
#include <set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef unordered_map<int,int> m32;
typedef map<ll,ll> m64;
typedef unordered_map<ll,set<ll> > m648;
typedef pair<ll,p64 > pp64;
ll MOD = 1e9 + 7;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF LLONG_MAX
v64 dp;

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s,t;
    cin >> s >> t;
    pair<ll, p64 > dp[1+(ll)s.size()][1+(ll)t.size()];
    forn(i,1+(ll)t.size()) dp[0][i]=mp(0,mp(-1,-1));
    forn(i,1+(ll)s.size()) dp[i][0]=mp(0,mp(-1,-1));
    forn(i,s.size()){
    	forn(j,t.size()){
    		if(s[i]==t[j]){
    			dp[i+1][j+1].fi=dp[i][j].fi+1;
    			dp[i+1][j+1].se = mp(i,j);
    		}
    		else{
    			if((ll)dp[i][j+1].fi>=(ll)dp[i+1][j].fi) {
    				dp[i+1][j+1].fi=dp[i][j+1].fi;
    				dp[i+1][j+1].se=mp(i,j+1);
    			}
    			else {
    				dp[i+1][j+1].fi=dp[i+1][j].fi;
    				dp[i+1][j+1].se=mp(i+1,j);
    			}
    		}
    	}
    }
    vector<char> ans;
    p64 c = mp((ll)s.size(),(ll)t.size());
    p64 k = mp(-1,-1);
    while(true){
    	p64 temp = dp[c.fi][c.se].se;
    	if(temp == k) break;
    	if(temp.fi+1==c.fi && temp.se+1==c.se){
    		ans.pb(s[temp.fi]);
    	}
    	c=temp;
    }
    rforn(i,(ll)ans.size()-1){
    	cout << ans[i];
    }
    cout << ln;
    return 0;
}

Measured memory_bytes: 211328
#include <iostream>
#include <algorithm>
#include <array>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define rep(i,a,b) for(i = (a); i < (b); i++)
#define bitget(a,b) (((a) >> (b)) & 1)
#define vint vector<int>
#define vvint vector<vector<int>>
#define vsort(x) sort(x.begin(),x.end())

using int64 = uint64_t;

using namespace std;
template<typename T>
T gcd(T m, T n)
{
	// ?????°???0???????????´??????0?????????
	if ((0 == m) || (0 == n))
		return 0;

	while (m != n)
	{
		if (m > n) m = m - n;
		else         n = n - m;
	}
	return m;
}
int a[101][4] = {};
int w[101] = {};
int64 cal(int n) {
	int64 ret;
	if (n == 0) {
		return 1;
	}
	else if (w[n] != 0) {
		return w[n];
	}
	int64 x, y;
	x = cal(a[n][2]);
	y = cal(a[n][3]);
	int64 temp = gcd(x*a[n][0], y*a[n][1]);
	ret = x*y*a[n][1] / temp + y*x*a[n][0] / temp;
	w[n] = ret;
	return ret;
}
int64 solve(int n){
	int64 ret;
	int now = 1;
	int64 temp;
	while (now<=n) {
		if (w[now] == 0) {
			temp = cal(now);
		}
		else {
			now++;
		}
	}
	ret = temp;
	return ret;
}

int main() {
	int temp;
	int i, j, k;
	int n;
	cin >> n;
	long long int ans;
	while (n != 0) {
		rep(i, 0, n) {
			cin >> a[i + 1][0] >> a[i + 1][1] >> a[i + 1][2] >> a[i + 1][3];
			if (temp=gcd<int>(a[i + 1][0], a[i + 1][1]) != 1) {
				a[i + 1][0] /= temp;
				a[i + 1][1] /= temp;
			}
			w[i] = 0;
		}
		w[n] = 0;
		ans = solve(n);
		cout << ans << endl;
		cin >> n;
	}
	return 0;
}

Measured memory_bytes: 3000
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  n++;
  int sums[n];
  int coor;
  sums[0] = 0;
  for (int i=1; i<n; i++){
    cin >> sums[i];
  }
  int sums2[n];
  long long fullsum = 0;
  for (int i=0; i<n-1; i++){
    sums2[i] = abs(sums[i]-sums[i+1]);
    fullsum += sums2[i];
  }
  sums2[n-1] = abs(sums[n-1]-sums[0]); 
  fullsum += sums2[n-1];
  for (int i=1; i<n-1; i++){
    long long t = fullsum-sums2[i-1]-sums2[i];
    t += abs(sums[i-1]-sums[i+1]);
    cout << t << endl;
  }
  long long t = fullsum-sums2[n-2]-sums2[n-1];
  t += abs(sums[n-2]-sums[0]);
  cout << t << endl;
}

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

long long n, m;
long long data[2][2];

long long solve(int f);

int main() {
  cin >> n >> m;
  cout << min(solve(1), solve(0)) << endl;
  return 0;
}

long long solve(int f) {
  long long o = 0, d = 1, cnt = 0, bf;
  data[0][0] = n;
  data[1][0] = m;
  data[0][1] = 0;
  data[1][1] = 0;
  while(data[0][0] > 0 && data[1][0] > 0) {
    data[d][1] += data[o][0];
    if(d == f) {
      bf = max(0LL, data[d][1] - data[d][0]);
    }else{
      bf = data[d][1]/2;
    }
    data[d][0] -= bf;
    data[d][1] -= bf * 2;
    if(data[0][0] <= 0 || data[1][0] <= 0) break;
    swap(o, d);
    ++cnt;
  }
  return cnt;
}



Measured memory_bytes: 3096
object Main extends App {
  val in = new java.util.Scanner(System.in)
  val N = in.nextInt
  val As = List.fill(N)(in.nextInt)

  def op(ps: List[(Int, Int)], money: Long): Long = ps match {
    case Nil => money
    case (now, next) :: xs =>
      op(xs, if (now <= next) money / now * next + money % now else money)
  }

  println(op(As.zip(As.tail), 1000))
}


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

using namespace std;

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

    vector<int> res(n, 0);
    for (int i = 1; i < n; i++) {
        int a;
        cin >> a;
        res[a - 1]++;
    }

    for (int i = 0; i < n; i++) {
        cout << res[i] << endl;
    }
}


Measured memory_bytes: 4052
#include <cstdio>
#include <algorithm>
using namespace std;

struct init{
	int x,y;
	long long z;
}e[600007];
int n,m;
int f[200007];
long long d[200007];
long long ans;

bool cmp(init x,init y)
{
	return x.z<y.z;
}

int find(int k)
{
	if(f[k]==k)	return k;
	return f[k]=find(f[k]);
}

void kruskal()
{
	int t=0;
	for(int i=1;i<=n;++i)	f[i]=i;
	for(int i=1;i<=m+n;++i)	{
		int x=find(e[i].x),y=find(e[i].y);
		if(x!=y)
		{
			f[x]=y;
			ans+=e[i].z;
			if((++t)==n-1)	break;
		}
	}
	return ;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;++i)	d[i]=1e9*1e9;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
		d[e[i].x]=min(d[e[i].x],e[i].z+1);
		d[e[i].y]=min(d[e[i].y],e[i].z+2);
	}
	for(int i=1;i<=2;++i)
	for(int j=1;j<=n;++j)
		d[(j%n)]=min(d[(j%n)],d[j-1]+2);
	for(int i=1;i<=n;++i)
		e[m+i].x=i%n,e[m+i].y=(i+1)%n,e[m+i].z=d[(i%n)];
	sort(e+1,e+n+m+1,cmp);
	kruskal();printf("%lld\n",ans);
	return 0;
}



Measured memory_bytes: 10624
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,a[2000000+10],ans=2100000000;
long long aa=0,bb=0,s;
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
    aa+=a[i];
  }
  for(int i=1;i<n;i++)
  {
    aa-=a[i];
    bb+=a[i];
    s=abs(aa-bb);
    if(s<ans)ans=s;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1024
# include <bits/stdc++.h>
# define ll long long
# define pb push_back
# define fi first
# define se second
# define mp make_pair
# define gcd(m,n)  __gcd(m, n)
# define pr_double(x) cout << fixed << setprecision(10) << x
using namespace std;

const ll mod = 1e9+7;
long long binpow(long long a, long long b) {
    a %= mod;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n;
  cin>>n;
  ll p1 = binpow(10,n);
  ll p2 = binpow(8,n);
  ll p3 = binpow(9,n);
  ll p4 = binpow(8,n);
  p3 = (p3%mod - p4%mod + mod)%mod;
  p3 = (p3%mod * (2)%mod)%mod;
  ll ans = (p1%mod - p2%mod + mod)%mod;
  ans = (ans%mod - p3%mod + mod)%mod;
  cout<<ans<<endl;
}


Measured memory_bytes: 3628
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        if ((a * b) % 2 == 0) {
          System.out.println("Even");
        }
        else {
          System.out.println("Odd");
        }
    }
}

Measured memory_bytes: 35808
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

#define f(i,x) for(int i=0;i<x;i++)


using namespace std;

int main()
{
	int a, b;

	cin >> a >> b;

	if (a > b)
		cout << a - 1;
	else
		cout << a;

	return 0;
}

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

int main() {
  int a, b, x;
  cin >> a >> b;
  x = (a * b) % 2;
  if(x == 0){
    cout << "Even" << endl;
  }
  else{
    cout << "Odd" << endl;
  } 
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr int MOD = 1000000007;
constexpr int INF = 1e18;

using namespace std;

int dist(int a, int b, int x, int y){
  return abs(a-x)+abs(b-y);
}

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

  vector<int> x(N);
  vector<int> y(N);
  vector<int> h(N);
  tuple<int, int, int> M = make_tuple(-1, -1, -1);
  REP(i, N){
    cin >> x[i] >> y[i] >> h[i];
    if(get<2>(M) < h[i]) M = make_tuple(x[i], y[i], h[i]);
  }

  REP(i, 101) REP(j, 101){
    tuple<int, int, int> cur = make_tuple(i, j, get<2>(M)+dist(i, j, get<0>(M), get<1>(M)));
    int cnt = 0;
    REP(k, N){
      if(h[k] == max(0LL, get<2>(cur)-dist(get<0>(cur), get<1>(cur), x[k], y[k]))) cnt++;
    }
    if(cnt == N){
      cout << get<0>(cur) << " " << get<1>(cur) << " " << get<2>(cur) << endl;
      return 0;
    }
  }
}

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

const ll INF = 1ll << 60;
ll MOD = 1e9 + 7;

int main()
{

    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    vector<bool> oks(n + 1, true);
    REP(i, m)
    {
        int x;
        cin >> x;
        oks[x] = false;
    }
    vector<ll> dp(n + 1);
    dp[0] = 1;

    for (int now = 0; now < n; ++now)
    {
        for (int next = now + 1; next <= min(n, now + 2); ++next)
        {
            if (oks[next])
            {
                dp[next] += dp[now];
                dp[next] %= MOD;
            }
        }
    }

    cout << dp[n] << endl;

    return 0;
}

Measured memory_bytes: 1408
package main

import (
	"fmt"
	"strings"
)

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

	ans := 0
	bc := 0
	s = strings.Replace(s, "BC", "X", -1)
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == 'X' {
			bc++
		} else if s[i] == 'A' && bc > 0 {
			ans += bc
		} else {
			bc = 0
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
#define INF 2000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

const ll MAX = 510010;
const ll mod = 1000000007;
vector<ll> fac(MAX), finv(MAX), inv(MAX);
bool init_called = false;
//=============modinv============================
void COMinit() {
  init_called = true;
  fac.at(0) = 1;
  fac.at(1) = 1;
  finv.at(0) = 1;
  finv.at(1) = 1;
  inv.at(1) = 1;
  for (ll i = 2; i < MAX; i++){
    fac.at(i) = fac.at(i - 1) * i % mod;
    inv.at(i) = mod - inv.at(mod % i) * (mod / i) % mod;
    finv.at(i) = finv.at(i - 1) * inv.at(i) % mod;
  }
}

ll COM(ll n, ll k){
  if (!init_called) {
    COMinit();
  }
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac.at(n) * (finv.at(k) * finv.at(n - k) % mod) % mod;
}
//=================================================

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N, K;
  cin >> N >> K;
  for (ll i = 1; i <= K; ++i) {
    ll ans = COM(N - K + 1, i) * COM(K - 1, K - i) % mod;
    cout << ans << "\n";
  }
}


Measured memory_bytes: 14924
import math
def isprime(n):
    if n==1:return(False)
    if n==2:return(True)
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:return(False)
    return(True)
n=int(input())
l=[]
tmp=11
while len(l)<n:
    if isprime(tmp):l.append(tmp)
    tmp+=10
print(*l)

Measured memory_bytes: 3060
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    string s;
    getline(cin, s);
    int n = s.size();
    for(int i=0; i<n; ++i){
        if('a' <= s[i] && s[i] <= 'z')
            s[i] += 'A' - 'a';
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 0
"""
ai             aj
bi             bj


1              2
2              1

1  how many pairs 
2
"""



import collections
n = int(raw_input())
mem = [0] * (n + 1)
mem[1] = 1
primes = [True] * (n + 1)
posprimes = []
d= 2
while( d <= n):
	if primes[d] is True:
		posprimes.append(d)
		k = 2
		while(k * d <= n):
			primes[k * d] = False
			k += 1
	d+=1
def f(k):
	if primes[k] is True:
		mem[k] = 2 if k > 1 else 1
		return mem[k]
	for pos in posprimes:
		if k % pos == 0:
			count = 0
			q = k
			while(q % pos == 0):
				q /= pos
				count += 1

			mem[k] = (count + 1) * mem[q]
			return mem[k]



s = 0
k = 1
while (k<= n):
	s += k * f(k)
	k += 1
print s




#2 4 6 8 10 12 14 16 18
#    6      12       18

Measured memory_bytes: 259508
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <cstdio>

using namespace std;

int main(){
  long v[200000] = {};
  long n, m;
  cin >> n >> m;
  for (long i=0;i<m;i++) {
    long a, b;
    cin >> a >> b;
    a--;
    b--;
    if (a==0) {
      v[b]++;
      if (v[b]==2) {
	cout << "POSSIBLE" << endl;
	return(0);
      }
    }
    if (b==(n-1)) {
      v[a]++;
      if (v[a]==2) {
	cout << "POSSIBLE" << endl;
	return(0);
      }
    }
  }
  cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main() 
{
    int w, h, x, y, r;
    cin >> w >> h >> x >> y >> r;
    if(x-r >= 0 && y-r >= 0 && w-x-r >= 0 && h-y-r >= 0)
        cout<< "Yes" << endl;
    else
        cout<< "No" << endl;
}


Measured memory_bytes: 3092