akhauriyash/Code-Regression huggingface dataset:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.size = [1]*n
        self.cost = 0
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unit(self,x,y,dist):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size[x] < self.size[y]:
            x,y = y,x
        self.size[x] += self.size[y]
        self.par[y] = x
        self.cost += dist
        
n,*xy = map(int,open(0).read().split())
x = [(x,i) for i,x in enumerate(xy[::2])]
y = [(y,i) for i,y in enumerate(xy[1::2])]

x.sort()
y.sort()

xdist = [(x2-x1, i1, i2) for (x1,i1),(x2,i2) in zip(x,x[1:])]
ydist = [(y2-y1, i1, i2) for (y1,i1),(y2,i2) in zip(y,y[1:])]

dist_list = sorted(xdist+ydist)

uf = UnionFind(n)
for dist,i1,i2 in  dist_list:
    uf.unit(i1,i2,dist)
print(uf.cost)

Measured memory_bytes: 61276
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int> >;
#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(int i = m; i < (int)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum accumulate
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
typedef long long ll;
const int INF = 2000000000;
const ll INF64 = 9223372036854775806ll;
const ll MOD = 1000000007LL;
/*メモ XOR問題のまとめ
性質 1「交換則、結合則が成り立つ」
　　 2「a xor a = 0」
　　 3「ある数xのb番目のビットが1である <=> x mod 2^(b+1) ≧ 2^b」
　　 4「0≦aのとき、4a, 4a+1, 4a+2, 4a+3のxor和は0」
方針 
!!!!!1「xor計算は各ビットで独立なので別々に計算」
　　 2「trieを使ったxorの最大最小探索がある解説」
・しゃくとり法は[ｌ,r)で考えるとわかりやすいよ！
*/
int main(){
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    rep(i,n)std::cin >> a[i];
    bool han=1;
    rep(i,n){
        if(a[i]%2==1)continue;
        else{
            if(a[i]%3!=0&&a[i]%5!=0)han=0;
        }
    }
    if(han){
        std::cout << "APPROVED" << std::endl;
    }
    else std::cout << "DENIED" << std::endl;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if(abs(a - c) <= d || (abs(a - b) <= d && abs(b - c) <= d)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
def main():
    N, K = map(int, input().split())

    snuke = [1] * N
    for _ in range(K):
        _ = int(input())
        A = (int(x) - 1 for x in input().split())
        for x in A:
            snuke[x] = 0
    print(sum(snuke))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9084
/*
	Look, if you had, one shot, or one opportunity
		To seize everything you ever wanted. In one moment
			Would you capture it,or just let it slip ?
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define nl cout<<endl

#define pii pair<ll,ll>
#define vi  vector<ll>
#define vii vector<pii>
#define mi  map<ll,ll>
#define all(a)  (a).begin(),(a).end()

#define pb push_back
#define ff first
#define ss second
#define hell 1000000007

#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;
#define N 300009

ll power(ll a,ll b,ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}
int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
        ll n;cin>>n;
	ll a[n+2],b[n+2],c[n+2];
	rep(i,1,n+1)
	cin>>a[i];
	rep(i,1,n+1)
	cin>>b[i];
	rep(i,1,n)
	cin>>c[i];
	
	ll ans=0;
	rep(i,1,n+1)
	ans+=b[a[i]];

	//test1(ans);
	rep(i,1,n)
	{
		if(a[i]+1==a[i+1])
		ans+=c[a[i]];
	}
	cout<<ans<<endl;
}
	
		

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n+1];
	int b[100005];
	long long ans=0;
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[a[i]]++;
		ans+=a[i];
	}
	int q,be,af;
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>be>>af;
		ans+=(af-be)*b[be];
		b[af]+=b[be];
		b[be]=0;
		cout<<ans<<endl;
	}
    return 0;
}

Measured memory_bytes: 4356
#include<bits/stdc++.h>
using namespace std;
int main()
{
	 int n,i;
	 cin>>n;
	 int arr1[n+1], arr2[n+1];
	 for(i=1; i<=n; i++)
	 {
	 	cin>>arr1[i];
	 	arr2[arr1[i]]=i;
	 }
	 for(i=1; i<=n; i++)
	 cout<<arr2[i]<<" ";
	}

Measured memory_bytes: 1536
import kotlin.math.max


fun main() {

    fun calcLCP(t: String, suffixArray: List<Int>): IntArray {
        val s = "${t}$"
        val n = s.length
        val lcp = IntArray(n - 1)
        val positions = IntArray(n)
        suffixArray.forEachIndexed { index, suff ->
            positions[suff] = index
        }

        var k = 0
        for (i in 0 until n - 1) {
            val position = positions[i]
            val j = suffixArray[position - 1]
            while (s[i + k] == s[j + k]) k++
            lcp[position - 1] = k
            k = max(k - 1, 0)
        }

        return lcp
    }

    fun suffixArray(inputString: String): List<Int> {
        val s = "$inputString$"
        val n = s.length
        var p: IntArray // Ordering of the strings
        val c = IntArray(n) { -1 } // Equivalence classes

        // k = 0
        val charPosition = s.mapIndexed { index, ch -> Pair(ch, index) }.sortedBy { it.first }

        p = charPosition.map { it.second }.toIntArray()

        charPosition.forEachIndexed { index, pair ->
            when {
                index == 0 -> c[p[index]] = 0
                pair.first == charPosition[index - 1].first -> c[p[index]] = c[p[index - 1]]
                else -> c[p[index]] = c[p[index - 1]] + 1
            }
        }

        fun countSort(ordering: IntArray, classes: IntArray): IntArray {
            val newOrdering = IntArray(n)
            val counts = IntArray(n)
            classes.forEach { `class` -> counts[`class`]++ }

            val position = IntArray(n)
            for (i in 1 until n) position[i] = position[i - 1] + counts[i - 1]

            ordering.forEach { index ->
                val `class` = classes[index]
                newOrdering[position[`class`]] = index
                position[`class`]++
            }
            return newOrdering
        }

        var k = 0
        while (1 shl k < n) {
            // k -> k + 1

            for (i in p.indices) p[i] = (p[i] - (1 shl k) + n) % n

            p = countSort(p, c)
            val cNew = IntArray(n)
            cNew[p[0]] = 0
            for (i in 1 until n) {
                val prev = Pair(c[p[i - 1]], c[(p[i - 1] + (1 shl k)) % n])
                val curr = Pair(c[p[i]], c[(p[i] + (1 shl k)) % n])
                cNew[p[i]] = if (prev == curr) cNew[p[i - 1]] else cNew[p[i - 1]] + 1
            }
            cNew.forEachIndexed { index, `class` -> c[index] = `class` }
            k++
        }

        return p.toList()
    }

    fun numberOfDifferentSubstrings(t: String): Long {
        val tSuffix = suffixArray(t)
        val lcp = calcLCP(t, tSuffix)
        var ans = 0L
        for (i in 1 until tSuffix.size) {
            ans += t.length - tSuffix[i] - lcp[i - 1]
        }

        return ans
    }

    val s = readLn()
    println(numberOfDifferentSubstrings(s))
}

// Input Reader
private fun readLn() = readLine()!!


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

#define I inline
#define fi first
#define se second
#define R register
#define LL long long
#define mp make_pair
#define reg register int
#define pii pair<int,int>
#define fo(i, a, b) for(reg i = a; i <= b; i++)
#define fd(i, a, b) for(reg i = a; i >= b; i--)
#define bp __builtin_popcount
#define vi vector<int>
#define cr const reg&
using namespace std;
const int mod = 998244353, N = 1e6 + 1;

I int _max(cr x, cr y) {return x > y ? x : y;}
I int _min(cr x, cr y) {return x < y ? x : y;}
I int read() {
	reg x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return x * f;
}
I void ptt(LL x) {if(x >= 10) ptt(x / 10); putchar(x % 10 + '0');}
I void put(LL x) {x < 0 ? putchar('-'), ptt(-x) : ptt(x);}
I void pr1(LL x) {put(x), putchar(' ');}
I void pr2(LL x) {put(x), puts("");}

I int pow_mod(reg a, reg k) {reg ans = 1; for(; k; k >>= 1, a = (LL)a * a % mod) if(k & 1) ans = (LL)ans * a % mod; return ans;}

char ss[N];

int main() {
	scanf("%s", ss + 1);
	reg n = strlen(ss + 1);
	fo(i, 1, n) {
		if(ss[i] == '?') ss[i] = 'D';
	} puts(ss + 1);
	return 0;
}




Measured memory_bytes: 3880
MOD = 10 ** 9 + 7

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
A.append(N + 1)
S = [0] * (N + 2)


S[0] = 1
i = 1

for a in A:
    while i < a:
        S[i] = (S[i - 1] + S[i - 2]) % MOD
        i += 1
    i += 1

print(S[N])


Measured memory_bytes: 7848
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005,mod=1e9+7;
int n,m;
ll x;
struct node
{
    int u,v,w;
    bool operator<(const node&o)const
    {
        return w<o.w;
    }
}e[N];
int f[N];
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
ll solve(int k)
{
    for(int i=1;i<=n;i++)
        f[i]=i;
    ll ans=0;
    ans+=e[k].w;
    f[getf(e[k].u)]=getf(e[k].v);
    for(int i=1;i<=m;i++)
    {
        int fu=getf(e[i].u),fv=getf(e[i].v);
        if(fu==fv) continue;
        ans+=e[i].w;
        f[fu]=fv;
    }
    return ans;
}
ll qpow(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%lld",&x);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+1+m);
    ll ans=solve(1);
    if(ans>x){printf("0\n");return 0;}
    if(ans==x)
    {
        int a=0;
        for(int i=1;i<=m;i++)
            a+=solve(i)==x;
        printf("%lld\n",(qpow(2,a)+mod-2)*qpow(2,m-a)%mod);
        return 0;
    }
    int a=0,b=0;
    for(int i=1;i<=m;i++)
    {
        ll ans=solve(i);
        if(ans==x) a++;
        else if(ans>x) b++;
    }
    printf("%lld\n",2*(qpow(2,a)-1)%mod*qpow(2,b)%mod);
}


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

using namespace std;

int main(void) {
    long a, x, y;
    a = pow(10, 18);
    cin >>x >>y;

    if (x%y == 0 || x == y){
        cout << -1 << endl;
        return 0;
    }
    for(long i=x; i<=a; i+=x){
        if(i%y != 0) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

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

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

  int ans = 0;
  for (int i = 0; i < 4; i++) {
    if (N % 10 == 2) ans++;
    N /= 10;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        Set<String> dict = new HashSet<>();

        for(int i = 0; i < n; i++) {
            String cmd = sc.next();
            switch(cmd) {
                case "insert":
                dict.add(sc.next());
                break;
                case "find":
                if(dict.contains(sc.next())) {
                    System.out.println("yes");
                }else {
                    System.out.println("no");
                }
            }
        }

        sc.close();
    }
}


Measured memory_bytes: 261528
#include <stdio.h>
#include <math.h>
#include <string.h>

#define N	(2000000)

char isPrime[N];

int makePrime(void)
{
	int i, j;
	int lim;

	memset(isPrime, 0, sizeof(isPrime));

	lim = sqrt(N);
	for (i = 2; i < lim; i++){
		for (j = i * i; j < N; j += i){
			isPrime[j] = 1;
		}
	}
	return (0);
}

int main(void)
{
	int q, i;
	int count;

	makePrime();
	while (scanf("%d", &q),q){
		count = 0;
		for (i = 2; i <= q / 2; i++){
			if (isPrime[i] + isPrime[q - i] == 0){
				count++;
			}
		}
		printf("%d\n", count);
	}

	return (0);
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000000000000

struct renketu{
	int n,is_nibu;
};

int main(){
	int N,M;
	cin>>N>>M;
	
	vector<vector<int>> E(N,vector<int>(0));
	
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	
	vector<int> dis(N,-1);
	vector<renketu> V;
	int ko=0,nibu=0,normal=0;
	for(int i=0;i<N;i++){
		if(dis[i]!=-1)continue;
		int cnt = 1;
		dis[i] = 0;
		queue<int> q;
		q.push(i);
		int f = 1;
		while(q.size()!=0){
			int from = q.front();
			q.pop();
			for(int j=0;j<E[from].size();j++){
				int to = E[from][j];
				if(dis[to]!=-1){
					if(dis[to]%2==dis[from]%2){
						f=0;
					}
				}
				else{
					dis[to] = dis[from]+1;
					q.push(to);
					cnt++;
				}
			}
		}
		renketu R;
		R.n=cnt;
		R.is_nibu=f;
		V.push_back(R);
		
		if(R.n==1){
			ko++;
		}
		else{
			if(f)nibu++;
			else normal++;
		}
		
	}
	long long ans = 0;
	
	for(int i=0;i<V.size();i++){
		if(V[i].n==1){
			ans += (long long)N;
		}
		else{
			if(V[i].is_nibu){
				ans += (long long)V[i].n*ko;
				ans += (long long)2*nibu;
				ans += (long long)normal;
			}
			else{
				ans += (long long)V[i].n*ko;
				ans += (long long)nibu+normal;
			}
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}


Measured memory_bytes: 7296
n,x=map(int,input().split())
if x==1 or x==2*n-1:
  print('No')
else:
  print('Yes')
  m=[x-1,x,x+1]
  i=1
  for _ in range(n-2):
    while i in m:
      i+=1
    print(i)
    i+=1
  for mi in m:
    print(mi)
  for _ in range(n-2):
    while i in m:
      i+=1
    print(i)
    i+=1


Measured memory_bytes: 9220
#include<stdio.h>

int min(int a, int b){
    return a < b? a: b;
}

int main(void){
    int n, y;
    scanf("%d%d", &n, &y);
    int yen_1k = y / 1000;
    int yen_5k = 0;
    int yen_10k = 0;
    int cnt = yen_1k + yen_5k + yen_10k;
    if(cnt == n)
		printf("%d %d %d\n", yen_10k, yen_5k, yen_1k);
    else if(cnt < n)
		printf("-1 -1 -1\n");
    else {
        int dif=cnt-n;
        int y1k_2_y5k = min(dif / 4, yen_1k / 5);
        yen_5k+= y1k_2_y5k;
        yen_1k-= y1k_2_y5k * 5;
        cnt=yen_1k + yen_5k + yen_10k;
        if (cnt == n) printf("%d %d %d\n", yen_10k, yen_5k, yen_1k);
        else {
            dif = cnt - n;
            int y5k_2_y10k = min(dif, yen_5k / 2);
            yen_10k += y5k_2_y10k;
            yen_5k -= y5k_2_y10k * 2;
            cnt = yen_1k + yen_5k + yen_10k;
            if (cnt == n) printf("%d %d %d\n", yen_10k, yen_5k, yen_1k);
            else printf("-1 -1 -1\n");
        }
    }
    return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include <algorithm>
#include <iostream>
#include <functional>
#include<cmath>
#include<string.h>

using namespace std;

int main(){
	int n,r;
	double a, b;
	scanf("%d %d",&n,&r);
	a=log(n)/log(r);
	printf("%d\n",(int)floor(a)+1);
	return 0;
}

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

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

    vector<int> b(n - 1);
    for (int i = 0; i < n - 1; i++) cin >> b[i];

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

    cout << res << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a.at(i);
    sort(a.begin(),a.end());
    long long int ans=1, m = 1000000007;
    if(n%2){
        if(a.at(0)!=0)  ans = 0;
        for(int j = 0;j < n/2; j++){
            if(a.at(2*j+1)==2*j+2 && a.at(2*j+2)==2*j+2){
                ans *= 2;
                ans %= m;
            }else {
                ans = 0;
            }
        }
    }else{
        for(int j = 0;j < n/2; j++){
            if(a.at(2*j)==2*j+1 && a.at(2*j+1)==2*j+1){
                ans *= 2;
                ans %= m;
            }else {
                ans = 0;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <utility>
using namespace std;

#define gcu getchar_unlocked
#define pcu putchar_unlocked
#define _T template <typename T>
#define _HT template <typename H, typename... T>
#define _il inline
#define _in _il int in
#define _sc _il bool scan
_T T in(int c){T n=0;bool m=false;if(c=='-')m=true,c=gcu();
	do{n=10*n+(c-'0'),c=gcu();}while(c>='0');return m?-n:n;} //&&c<='9'
_in() {return in<int>(gcu());}
_T T scan(T &n){int c=gcu();return c==EOF?false:(n=in<T>(c),true);}
_sc(char &c){c=gcu();gcu();return c!=EOF;}
#ifdef _GLIBCXX_STRING
_sc(string &s){int c;s="";
	for(;;){c=gcu();if(c=='\n'||c==' ')return true;else if(c==EOF)return false;s+=c;}}
#endif
_HT _sc(H &h, T&&... t){return scan(h)&&scan(t...);}
#define _vo _il void out
#define _vl _il void outl
_vo(const char *s){while(*s)pcu(*s++);}
_vo(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_vo(string s){for(char c:s)pcu(c);}
#endif
_T _vo(T n){static char buf[20];char *p=buf;
	if(n<0)pcu('-'),n*=-1;if(!n)*p++='0';else while(n)*p++=n%10+'0',n/=10;
	while (p!=buf)pcu(*--p);}
_vl(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _vo(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);outl();}
#endif
_HT _vo(H&& h, T&&... t){out(h);out(move(t)...);}
template <typename... T> _vl(T&&... t){out(move(t)...);outl();}

void dump(int n) {
	out(n, ':');
	for (int i = 0, t; (t = n >> i); i++)
		if (t & 1)
			out(' ', i);
	outl();
}

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

int main() {
	int n = 1 << in(), i = (1 << in()) - 1;
	for (;i < n; i = next(i))
		dump(i);
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }
template<class T> bool isIn(T a,vector<T> v){ for(T x:v){ if(a==x){return true;}} return false;}
string strReplace(string s,string target, string replacement){
    if (!target.empty()) {
      std::string::size_type pos = 0;
      while ((pos = s.find(target, pos)) != std::string::npos) {
        s.replace(pos, target.length(), replacement);
        pos += replacement.length();
      }
    }
    return s;
}
const ll MOD = 1e9+7;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair

bool DEBUG = 0;
template<class T> void dprint(T s){
  if(DEBUG){ cout << s << "\n"; }
}

int main(int argc, char *argv[]){
  if(argc>1 && argv[1][0]=='D'){ DEBUG = 1;}

  ll N,K; cin>>N>>K;
  ll p[N],c[N];
  CINA(p,N);
  CINA(c,N);
  REP(i,N){--p[i];}

  ll ans = c[0];
  REP(start,N){
    int pos = start;
    vector<ll> score;
    ll scoreCircle = 0LL;
    while(1){
      pos = p[pos];
      score.push_back(c[pos]);
      scoreCircle += c[pos];
      if(pos==start){break;}
    }
    ll l = score.size();
    ll cumu = 0LL;
    REP(i,l){
      cumu += score[i];
      if(i+1 > K){break;}
      chmax(ans,cumu);
      if(scoreCircle>0){
        ll num = (K-i-1)/l;
        chmax(ans, cumu+scoreCircle*num);
      }
    }
  }
  cout << ans << "\n";
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

bool solve() {
    int h, w;
    cin >> h >> w;
    map<char, int> m;
    priority_queue<pair<int, char>> q;
    rep(i, h) {
        string s;
        cin >> s;
        rep(j, w) {
            m[s[j]]++;
        }
    }
    for (auto e: m) {
        q.emplace(e.second, e.first);
    }

    int fours = (h / 2) * (w / 2);
    int twos = (h % 2) * (w / 2) + (w % 2) * (h / 2);
    int ones = h % 2 && w % 2 ? 1 : 0;
    cerr << fours << " " << twos << " " << ones << endl;
    cerr << h * w << " " << fours * 4 + twos * 2 + ones << endl;

    while (fours) {
        auto e = q.top();
        q.pop();
        if (e.first < 4) return false;
        q.emplace(e.first - 4, e.second);
        fours--;
    }
    while (twos) {
        auto e = q.top();
        q.pop();
        if (e.first < 2) return false;
        q.emplace(e.first - 2, e.second);
        twos--;
    }
    return true;
}

int main() {
    cout << (solve() ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define N 100000
int pre[N+1],d[N+1];

int find(int x){
  if(pre[x]==x) return x;
  int now=find(pre[x]);
  d[x]+=d[pre[x]];
  return pre[x]=now;
}

int main(){
  int i,n,m;
  bool flag=0;

  scanf("%d %d",&n,&m);
  for(i=0;i<n;i++) pre[i]=i;

  int l,r,dd,fl,fr;
  for(i=0;i<m;i++){
    if(flag) continue;
    scanf("%d %d %d",&l,&r,&dd);
    fl=find(l);
    fr=find(r);
    if(fl==fr){
      if(d[r]-d[l]!=dd) flag=1;
    } else {
      pre[fr]=pre[fl];
      d[fr]=d[l]+dd-d[r];
    }
  }

  if(flag){
    printf("No");
    return 0;
  }
  printf("Yes");
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
// headers {{{
using namespace std;
// using namespace rel_ops;
 
typedef long long int64;
typedef unsigned long long uint64;
const double pi=acos(-1.0);
const double eps=1e-11;
const int INF=0x7FFFFFFF;
template<class T> inline bool checkmin(T &a,T b){return b<a?a=b,1:0;}
template<class T> inline bool checkmax(T &a,T b){return b>a?a=b,1:0;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define mem(a,b) memset(a, b, sizeof(a))
#define clr(a) memset(a, 0, sizeof(a))
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define ff first
#define ss second
#ifdef LOCAL
#define dbg(args...) printf(args); //##__VA_ARGS__
#define dout cout
#define out(x) (cout<<#x<<": "<<x<<endl)
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
#else
#define dbg(...)
#define dout if(true);else cout
#define out(...)
#define show(...)
#endif
// }}}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    int h1, m1, h2, s2, K;
    while (cin >> h1 >> m1 >> h2 >> s2 >> K) {
        int tot = (h2 * 60 + s2 ) - (h1 * 60 + m1);
        if (tot < K) tot += 24 * 60;
        cout << tot - K << endl;
    }

    return 0;
}



Measured memory_bytes: 3640
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int main() {
	int a,b;
	cin >> a >> b;
	if (a+b==15){
		cout << "+" << endl;
	}
	else if (a*b==15){
		cout << "*" << endl;
	}
	else{
		cout << "x" << endl;
	}

	return 0;
}



Measured memory_bytes: 256
N, P = list(map(int, input().split()))
A = list(map(int, input().split()))
has_odd = False
for a in A:
    if a % 2 != 0:
        has_odd = True
        break
if not has_odd:
    if P == 0:
        print(2**N)
        exit()
    else:
        print(0)
        exit()
else:
    print(2 ** (N - 1))

Measured memory_bytes: 3060
import sys
sys.setrecursionlimit(10000)

N = int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for i in range(N)]
INF = 10 ** 9

def dfs(s):
    if len(s) == 10:
        value = -INF
        if "1" in s:
            value = 0
            c = [0 for i in range(N)]
            for i in range(5):
                for j in range(2):
                    for k in range(N):
                        if int(s[2*i+j]) * F[k][2*i+j]:
                            c[k] += 1
            for i in range(N):
                value += P[i][c[i]]
        return value
    else:
        return max(dfs(s+"0"), dfs(s+"1"))

print(dfs(""))

Measured memory_bytes: 3064
// AOJ 2134: Deadly Dice Game
// 2017.11.9 bal4u@uu

#include <stdio.h>
#include <string.h>

double a[2002][2002];

char buf[2002], *bp;
int getint()
{
	int n = 0;
	while (*bp >= '0') n = (n<<3) + (n<<1) + (*bp++ & 0xf);
	return n;
}

int main()
{
	int n, t, i, j, jj, k;
	double p, ans;
	
	while (fgets(bp=buf, 20, stdin) && *bp != '0') {
		n = getint(), bp++, t = getint();
		memset(a, 0, sizeof(a));
		fgets(bp=buf, sizeof(buf), stdin);
		for (i = 0; i < n; i++) a[0][i] = (*bp++ == 'R');
		for (i = 0; i < t; i++) for (j = 0; j < n; j++) {
			for (p = 0, jj = j, k = 1; k <= 6; k++) {
				if (++jj == n) jj = 0;
				a[i+1][jj] += a[i][j]/6;
			}
		}
		for (ans = 0, i = 0; i < n; i++) if (a[t][i] > ans) ans = a[t][i];
		printf("%.12f\n", ans);
	}
	return 0;
}

Measured memory_bytes: 33000
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
using ll = long long;

//1 2 3 4 5
//1
//1 2 -> 2 1
//2 1 3 -> 3 1 2
//3 1 2 4 -> 4 2 1 3
//4 2 1 3 5 -> 5 3 1 2 4

int main(){
    int n;
    cin >> n;
    vector<ll> a;
    vector<ll> b;
    for(int i = 1; i <= n; i++){
        ll x;
        cin >> x;
        if(i % 2 == 1){
            a.push_back(x);
        } else {
            b.push_back(x);
        }
    }
    if(n % 2 == 0){
        reverse(b.begin(), b.end());
        for(int i = 0; i < b.size(); i++){
            cout << b[i] << " ";
        }
        for(int i = 0; i < a.size(); i++){
            cout << a[i] << " ";
        }
        cout << endl;
    } else {
        reverse(a.begin(), a.end());
        for(int i = 0; i < a.size(); i++){
            cout << a[i] << " ";
        }
        for(int i = 0; i < b.size(); i++){
            cout << b[i] << " ";
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3948
#include<bits/stdc++.h>
#define rep(i,a) for(int (i)=0; (i)<(a); (i)++)
#define rep2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define all(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
#define chmax(a,b) if(b>a) a = b
#define chmin(a,b) if(b<a) a = b
typedef long long ll;
using namespace std;

using namespace std;

vector<int> f(ll n){
        vector<int> ret;
        while(n>0){
                ret.push_back(n%26);
                n /= 26;
        }
        return ret;
        
}

int main(){
        ios_base::sync_with_stdio(false); 
        cin.tie(NULL);
        ll n; cin >> n;

        vector<char> ret;
        ll keta = 1;
        while(n>0){
                if(n % 26 == 0){
                        ret.push_back('z');
                        n -= 26;
                        n /= 26;
                }else{
                        ret.push_back('a' + n % 26 - 1);
                        n -= n%26;
                        n /= 26;
                }
        }
        
        reverse(all(ret));
        for(auto x: ret) cout << x;
        cout << endl;

        /*
        while(1){
                ll x = 26;
                if(n <= x * 26) break;
                x *= 26;
        }
        ret.push_back(char('a' + (n - x) - 1);
        n -= x;
*/
        return 0;
}

Measured memory_bytes: 3636
N, M = map(int, input().split())

A = list(sorted(map(int, input().split())))

cbs = []

for _ in range(M):
  b, c = map(int, input().split())
  cbs.append([c, b])

cbs = list(reversed(sorted(cbs)))

at = 0
while at < N and len(cbs) > 0:
  if A[at] < cbs[0][0]:
    A[at] = cbs[0][0]
    at += 1
    cbs[0][1] -= 1
    if cbs[0][1] == 0:
      cbs.pop(0)
  else:
    break

print(sum(A))

Measured memory_bytes: 25576
#include <bits/stdc++.h>
using namespace std;
const string YES = "Yes";
const string NO = "No";

void solve(int A, int B, int C, int D) {
  while (A > 0 && C > 0) {
    C -= B;
    if (C <= 0)
      break;
    A -= D;
  }
  cout << (A > 0 ? YES : NO) << endl;
}

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

  int A, B, C, D;
  cin >> A >> B >> C >> D;
  solve(A, B, C, D);
  return 0;
}


Measured memory_bytes: 3660
#include<iostream>
#define int long long 
using namespace std;

signed main()
{
  int q, h, s, d, n, ans = 0;
  cin >> q >> h >> s >> d >> n;

  n *= 4;
  int a[4];
  a[0] = q;
  a[1] = min(a[0] * 2, h);
  a[2] = min(a[1] * 2, s);
  a[3] = min(a[2] * 2, d);

  ans += a[3] * (n / 8);
  n %= 8;

  ans += a[2] * (n / 4);
  n %= 4;
  ans += a[1] * (n / 2);
  n %= 2;
  ans += a[0] * (n / 1);
  n %= 1;

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
m = gets.match(/(\d*)\.(\d*)\(?(\d*)\)?/)

d = m[1].to_i * (10 ** m[2].size) + m[2].to_i
n = 10 ** m[2].size
a = Rational(d, n)

d = m[3].to_i
n = 10 ** (m[2].size + m[3].size) - 10 ** m[2].size
n = 1 if n.zero?
b = Rational(d, n)

puts a + b

Measured memory_bytes: 8580
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
a = LI()

b = 0
for i in range(N):
    b ^= a[i]

print(*[b^a[i] for i in range(N)])


Measured memory_bytes: 115244
/*
				" اللهم صلي و سلم علي سيدنا محمد و علي اله وصحبه اجمعين "
*/


#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define f for
#define ll long long
#define ull unsigned long long
#define endl "\n"
using namespace std;
#define BI  acos(-1)
#define all(a) a.begin(), a.end()
void Open()
{
#ifndef ONLINE_JUDGE
	freopen("Input.txt", "r", stdin);
	freopen("Output.txt", "w", stdout);
#endif
}
ll gcd(ll a, ll b)
{
	return b == 0 ? a : gcd(b, a % b);
}
void madesetprobblem()
{
	//$ $
	//less than or equal => $ 1 \leq 100 $
	//  $(1 \le A,B \le 10^5 )$
	// a[i] => $a_i$
	// a[i][j] => $a_{i,j}$
	// double qoutes ''yext''
	/*
		image
		\begine{center}
		\includegraphics{image.jpg}
		\end{center}
	*/
	/*
		list
		\begin{itemize}
			\item first one
			\item second one
		\end{itemize}
	*/
}
int n;
vector<int>a(1e5 + 2),dp(1e5+2,-1);
int ans(int c = 0)
{
	if (c == n-1)
		return 0;
	int ans1 = INT_MAX, ans2 = INT_MAX;
	if (dp[c] != -1)
		ans1 = dp[c];
	else
	{
		if (c + 1 < n)
			ans1 = (abs(a[c] - a[c + 1]) + ans(c + 1));
		if (c + 2 < n)
			ans2 = (abs(a[c] - a[c + 2]) + ans(c + 2));
		dp[c] = min(ans1, ans2);
	}
	//cout <<c<<" "<< ans1 << " " << ans2 << endl;
	return min(ans1,ans2);
}
int main()
{
	// توكلت علي الله 
//Open();
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	f(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	cout << ans();
}

Measured memory_bytes: 5760
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

def f(n):
    r = 1
    for i in range(1, n+1):
        r *= i
    return r

@mt
def slv(N, K, A, F):
    A.sort()
    F.sort(reverse=True)

    def f(x):
        y = 0
        for a, f in zip(A, F):
            b = a - x//f
            if b > 0:
                y += b
        if y <= K:
            return 1

        return 0

    return Bisect(f).bisect_left(1, 0, 10**19)






def main():
    N, K = read_int_n()
    A = read_int_n()
    F = read_int_n()
    print(slv(N, K, A, F))


if __name__ == '__main__':
    main()


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

#define ll            long long
#define pb            push_back
#define si            set <int>
#define F             first
#define S             second
#define mii           map<int ,int >
#define msi           map<string,int >
#define mis           map<int , string>
#define fr(i,a,b)     for(int  i=a;i<=b;i++)
#define loop(i,n)     for(int i=0;i<n;i++)
#define all(v)        v.begin(),v.end()
#define vi            vector<int >
#define vii           vector<pair<int , int >>
#define vs            vector<string>
#define sz(x)         (int )x.size()
#define M             1000000007
#define mp            make_pair
#define input(arr,n)  loop(i,n) cin>>arr[i]
#define output(arr,n) loop(i,n) cout<<arr[i]<<" "
#define mod           998244353
#define sof           sizeof
using namespace std;
int gcd(int a,int b){
  if(b==0)return a;
  return gcd(b,a%b);
}

bool isPrime(int num){
    
    if(num==2) return true;
    if(num<2 || num%2==0) return false;
    for(int i = 3; i*i <=num; i+=2) {
       if(num % i == 0) {
          
          return false;
       }
    }
    return true;
   
}

bool comp(const pair<int,int> &a,const pair<int,int> &b){
  return a.F>b.F;
}

vector<vector<int>> L(3005,vector<int>(3005,-1));
string a,b;

const int N=1e5+1;
ll dp[N][101];


void solve(){
  //cout<<"gadbad";
  
  int n;
  cin>>n;
  int W;
  cin>>W;
  int w[n+1];
  int v[n+1];
  fr(i,1,n) cin>>w[i]>>v[i];

  dp[0][0]=0;
  loop(i,W+1){
    loop(j,n+1){
      if(i==0 || j==0) dp[i][j]=0;
      else{
        dp[i][j]=dp[i][j-1];
        if(i-w[j]>=0){
          dp[i][j]=max(dp[i][j], dp[i-w[j]][j-1] + v[j]);
        }
      }
    }
  }
  ll ma=0;
  fr(i,1,W){
    ma=max(dp[i][n],ma);
  }
  cout<<ma;
}




signed main()   
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); 
  cout.tie(0);
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout); 
  #endif  

  int t;
  t=1;
  //cin>>t;
  loop(i,t){

      solve();
      if(i<t-1) cout<<"\n";
  }

  
  
  //directed graph
    



}
  


  



Measured memory_bytes: 117808
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <queue>
#include <queue>
#include <stack> 
#include <sstream>
#include <set>

typedef  long long ll;
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = { 0, 1, 0,-1};
const int INF = 1e9;
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
int guki (int a){
    if(a%2==0) return 0;
    else return 1;
}
int gcd(int a, int b){
    if(a%b==0){
        return b;
    }else{
        return (gcd(b,a%b));
    }
}
int lcm(int a, int b){
    int x = gcd(a,b);
    return (a*b/x);
}

using namespace std;
ll k (ll a){
    a--;
    ll ans =0;
    while(a != 0){
        ans += a;
        a--;
        
    }
    return ans;
}


//global val ^^

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

    n--;
    int x;
    cin >> x;
    int i1,i2;
    int y;
    bool fl;
    i1 = x;
    REP(i,n){
        cin >> y;
        
        if(i==0){
            i2 = y;
            if(x == y+1){
                x = y;
                continue;
            }
        }

        if((x == y)||(x+1 == y)){
            continue;
        }else if(x+1 <y) {
            y--;
            x = y;
        }else{
            cout << "No" <<endl;
            return 0;
        }
    }

    cout << "Yes" <<endl;

    
}






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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define ppb pop_back
#define INF 1e18
typedef long long ll;

using namespace std;

int main(int argc,char* argv[])
{
    int n;
    cin >> n;
    vector<double> v(n);
    rep(i, n) cin >> v[i];
    sort(all(v));
    double sum = (v[0]+v[1])/2;
    for (int i = 2; i < n; i++)
    {
        sum = (sum+v[i])/2;
    }
    cout << sum << endl;
    return 0;
}

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


int main()
{
	//input
	int N, A, B; cin >> N >> A >> B;
	//compute
	int ans = 0;
	for (int i = 1; i <= N; i++){
		string S = to_string(i);
		int num = 0;
		for (int j = 0; j < S.size(); j++){
			num += (int)(S[j] - '0') % 10; 
		}
		if (num >= A && num <= B) ans += i;
	}
	
	//output
	cout << ans << endl;
} 

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

using namespace std;
ifstream fi("input.in");

const int NMAX = 100005;

struct punct
{
    int x, y, ord;
};

struct muchie
{
    int u, v, cost;
};

bool operator<(muchie a, muchie b)
{
    return a.cost > b.cost;
}

bool operator>(muchie a, muchie b)
{
    return a.cost < b.cost;
}

bool cX(punct a, punct b)
{
    return a.x < b.x;
}

bool cY(punct a, punct b)
{
    return a.y < b.y;
}


int n;
punct p[NMAX];
priority_queue <muchie> Q;
int par[NMAX];

int parinte(int x)
{
    if (par[x] == x)
        return x;
    return par[x] = parinte(par[x]);
}

void unite(int x, int y)
{
    par[parinte(x)] = parinte(y);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y, p[i].ord = i;

    sort(p + 1, p + n + 1, cX);
    for (int i = 1; i < n; i++)
    {
        Q.push({p[i].ord, p[i + 1].ord, p[i + 1].x - p[i].x});
    }

    sort(p + 1, p + n + 1, cY);
    for (int i = 1; i < n; i++)
    {
        Q.push({p[i].ord, p[i + 1].ord, p[i + 1].y - p[i].y});
    }

    /*while (!Q.empty())
    {
        muchie curr = Q.top();
        Q.pop();
        cout << "de la " << curr.u << " la " << curr.v << ": " << curr.cost << "\n";
    }*/

    for (int i = 1; i <= n; i++)
        par[i] = i;

    int total = 0;
    while (!Q.empty())
    {
        muchie curr = Q.top();
        Q.pop();

        if (parinte(curr.u) != parinte(curr.v))
        {
            total += curr.cost;
            unite(curr.u, curr.v);
        }
    }
    cout << total;
    return 0;
}


Measured memory_bytes: 6132
#include<stdio.h>
 
int main(){
  int i, len = 0, flag = 0, judge = 1;
  char s[10];
  
  scanf("%s", s);

  while(s[len]){
    len++;
  }

  if(s[0] != 'A'){
    judge = 0;
  }
  
  for(i = 2; i <= len - 2; i++){
    if(s[i] == 'C' && flag == 0){
      flag = 1;
    } else if(s[i] == 'C' && flag == 1){
      flag = 0;
      break;
    }
  }
  if(flag == 0){
    judge = 0;
  }

  for(i = 0; i < len; i++){
    if(s[i] == 'B' || (s[i] >= 'D' && s[i] <= 'Z')){
      judge = 0;
    }
  }
  
  if(judge == 0){
    printf("WA\n");
  } else {
    printf("AC\n");
  }
}

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

int main(void){
    int n,m;
    cin>>n>>m;
    int ans[n];
    for(int i=0;i<n;i++) ans[i]=0;

    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        ans[a-1] ++;
        ans[b-1] ++;    
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SIZE 55
typedef long long ll;

using namespace std;

char maze[SIZE][SIZE+1];
int H, W;
int sx, sy;
int gx, gy;
int d[SIZE][SIZE];

int bfs(){
    const int INF = 10000000;
    queue<pair<int, int>> que;
    for (int i = 0; i < H; i++){
	for (int j = 0; j < W; j++){
	    d[i][j] = INF;
	}
    }

    que.push(pair<int, int>(sx, sy));
    d[sx][sy] = 0;

    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    while (que.size()){
	pair<int, int> p = que.front();
	que.pop();

	if ((p.first == gx) && (p.second == gy)) break;

	for (int i = 0; i < 4; i++){
	    int nx = p.first+dx[i], ny = p.second+dy[i];

	    if ((0 <= nx) && (nx < H) && (0 <= ny) && (ny < W)){
		if ((maze[nx][ny] == '.') && (d[nx][ny] == INF)){
		    que.push(pair<int, int>(nx, ny));
		    d[nx][ny] = d[p.first][p.second]+1;
		}
	    }
	}
    }

    if (d[gx][gy] == INF) return -1;
    return d[gx][gy];
}

int main(){
    int cnt = 0;
    cin >> H >> W;
    for (int i = 0; i < H; i++){
	for (int j = 0; j < W; j++){
	    cin >> maze[i][j];
	    if (maze[i][j] == '.') cnt++;
	}
    }

    sx = 0;
    sy = 0;
    gx = H-1;
    gy = W-1;
    int res = bfs();
    if (res == -1){
	cout << res << endl;
	return 0;
    }

    cout << cnt-res-1 << endl;

    return 0;
}


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

/*
*/

ll n,ans=0,v[100],c[100];

void init(){
	cin>>n;
	rep(i,n)cin>>v[i];
	rep(i,n)cin>>c[i];
	rep(i,n)ans+=max(0LL,v[i]-c[i]);
}

int main(void){
	init();
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
/* C++14 (Clang 3.8.0) for AtCoder */

#include <iostream>
#include <vector>
#include <string>
// #include <cmath>
// #include <math.h>
// #include <algorithm>
// #include "./Debug.h"

namespace AtCoder {
	using Input = std::vector<std::string>;
	using Num = std::vector<int>;

	Input input(void) {
		Input result;
		{
			std::string buf = "", row = "";
			std::getline(std::cin, buf);
			for (unsigned int i = 0; i < buf.size(); i++) {
				if (' ' == buf[i]) {
					result.push_back(row);
					row = "";
				} else {
					row += buf[i];
				}
			}
			result.push_back(row);
		}
		return result;
	}

	Num replaceToInteger(Input original = { "" }) {
		Num result;
		for (unsigned int i = 0; i < original.size(); i++) {
			result.push_back(atoi(original[i].c_str()));
		}
		return result;
	}
}

int main(void) {

	AtCoder::Input s = AtCoder::input();

	bool f = false;
	if (s[0][0] == s[0][1]) {
		if (s[0][2] == s[0][3]) {
			if (s[0][0] != s[0][2]) {
				f = true;
			}
		}
	} else if (s[0][0] == s[0][2]) {
		if (s[0][1] == s[0][3]) {
			if (s[0][0] != s[0][1]) {
				f = true;
			}
		}
	} else if (s[0][0] == s[0][3]) {
		if (s[0][1] == s[0][2]) {
			if (s[0][0] != s[0][1]) {
				f = true;
			}
		}
	}

	if (f) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}

	return 0;
}


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

ll n,k;
vector<ll> a;
bool C(ll x){
    int cnt=0;
    for(int i=0;i<n;++i){
        if(a[i]>x) cnt+=a[i]/x;
    }
    return cnt<=k;
}
int main(){
    cin>>n>>k;
    ll h=0;
    a=vector<ll>(n);
    for(int i=0;i<n;++i){
        cin>>a[i];
        h=max(h,a[i]);
    }
    ll l=0;
    while(h-l>1){
        ll m=(h+l)/2;
        if(C(m)) h=m;
        else l=m;
    }
    cout<<h<<endl;

}

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

using namespace std;

#define MAX_N 100000
vector<int> prime;
bool is_prime[MAX_N + 1];

int sieve(int n)
{
  int p = 0;
  for (int i = 0; i <= n; i++) is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i <= n; i++) {
    if (is_prime[i]) {
      prime.push_back(i);
      for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;
    }
  }
  return p;
}

int main()
{
  sieve(100000);

  long long sum[100000] = { };
  for (int i = 1; i <= 100000; i++) {
    if (i % 2 == 1 && is_prime[i] && is_prime[(i + 1) / 2])
      sum[i] = 1;
  }
  for (int i = 1; i <= 100000; i++) {
    sum[i] += sum[i - 1];
  }

  int Q; cin >> Q;
  for (int i = 0; i < Q; i++) {
    int l, r; cin >> l >> r;
    cout << (sum[r] - sum[l - 1]) << endl;
  }

  return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int 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(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
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;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int N,K; cin >> N >> K;
    vector<int> x(N);
    for(int i=0;i<N;i++){
        cin >> x[i];
    }
    ll out=0;
    for(int i=0;i<N;i++){
        int a=2*x[i];
        int b=2*(K-x[i]);
        out += min(a,b);
    }
    cout << out << endl;
    return 0;
}


Measured memory_bytes: 256