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

#define LL long long

int n, m, k, S, T, c;
int a[55];
int bc[1 << 19], cnt[1 << 19];
LL C[55][55], coef[55];

int main()
{
	scanf("%d %d %d %d", &m, &k, &S, &T);
	
	if((S | T) != T) return puts("0"), 0;

	for(int i = 1; i <= m; i++)
	{
		int x, v = 0; 
		bool fk = true;
		scanf("%d", &x);
		for(int j = 0; j < 18; j++)
		{
			if((S >> j & 1) && !(x & 1)) fk = false;
			if(!(T >> j & 1) && (x & 1)) fk = false;
			if(!(S >> j & 1) && (T >> j & 1)) v = (v << 1) | (x & 1);
			x >>= 1;
		}
		if(fk) a[++ n] = v;
	}
	
	for(int i = 0; i < 18; i++)
		if(!(S >> i & 1) && (T >> i & 1)) c ++;
	
	S = 0, T = (1 << c) - 1;
	for(int i = 0; i <= n; i++)
	{
		C[i][0] = 1;
		for(int j = 1; j <= i; j++)
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
		for(int j = 0; j < k; j++) coef[i] += C[i][j];
	}

	for(int i = 1; i <= T; i++) bc[i] = bc[i >> 1] + (i & 1);

	LL ans = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int s = 0; s <= T; s++) cnt[s] = 0;
		for(int j = i + 1; j <= n; j++) cnt[ a[i] ^ a[j] ] ++;
		
		for(int j = 0; j < c; j++)
			for(int s = 0; s <= T; s++)
				if(s >> j & 1) cnt[s] += cnt[s ^ (1 << j)];

		for(int s = 0; s <= T; s++)
			if(bc[T ^ s] & 1) ans -= coef[ cnt[s] ];
			else ans += coef[ cnt[s] ];
	}

	printf("%lld\n", ans);
	return 0;
}


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

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vs = vector<string>;
using vvl = vector<vl>;
using pll = pair<ll,ll>;
using vb = vector<bool>;

const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-9;

#define sz(c) ll((c).size())
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define xx first
#define yy second

#define has(c,i) ((c).find(i) != end(c))
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define FORD(i,a,b) for (int i=int(b)-1; i>=(a); i--)

#define rv(type,name,count) vector<type> name(count); FOR(_i,0,count) cin >> name[_i];
#define grid(type,name,c1,c2) vector<vector<type>> name(c1, vector<type>(c2)); FOR(_i,0,c1)FOR(_j,0,c2)cin >> name[_i][_j];

int main() {
	ll h, w;
	cin >> h >> w;
	vs v(h); FOR(i,0,h) cin >> v[i];
	vvl dp(2, vl(w));
	dp[1][0] = 1;
	const ll MOD = 1e9 + 7;
	FOR(r, 0, h) {
		dp[r%2][0] = dp[(r+1)%2][0];
		if (v[r][0] == '#') dp[r%2][0] = 0;
		FOR(c, 1, w) {
			dp[r%2][c] = (dp[(r+1)%2][c] + dp[r%2][c-1]) % MOD;
			if (v[r][c] == '#') dp[r%2][c] = 0;
		}
	}
	cout << dp[(h+1)%2][w-1] << endl;
}


Measured memory_bytes: 1280
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
#include <set>
using namespace std;

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


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

	rep(i, N) {
		string s;
		cin >> s;

		if (s == "Y") {
			cout << "Four" << endl;
			return 0;
		}
	}
	cout << "Three" << endl;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  int ans = -1;
  for (int i = 1; i < (10100); ++i){
    int x = i*0.08;
    int y = i*0.10;
    if(a == x && b == y) {
      ans = i;
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
  int n;
  cin >> n;
  int b[n-1];
  int ans = 0;
  for(int i=0; i<n-1; i++){
    cin >> b[i];
  }
  ans += b[0];
  ans += b[n-2];
  for(int i=1; i<n-1; i++){
    ans += min(b[i-1],b[i]);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#define P pair<long long, long long>


using namespace std;
const long long int MOD=1e9+7;
const long long INF=(1<<30)-1;
long long dp[20009];

int main(){
  long long h,n,a[1009],b[1009], mxa=0;
  cin >> h>> n;
  for(int i=0;i<n;i++){
    cin >> a[i] >> b[i];
    mxa = max(mxa, a[i]);
  }
  for(int i=0;i<=20000;i++){
    dp[i]=INF;
  }
  dp[0]=0;
  long long mna=0, mnb=INF;
  for(int i=0;i<n;i++){
    mnb= min(mnb, b[i]);
  }
  for(int i=0;i<n;i++){
    if(b[i]==mnb){
      mna = max(mna, a[i]);
    }
  }
  for(int i=1;i<=min(h, mna);i++){
    dp[i]=mnb;
  }
  for(int i=0;i<=h;i++){
    for(int j=0;j<n;j++){
      dp[i+a[j]] = min(dp[i+a[j]], dp[i]+b[j]);
    }
  }
  long long mn=INF;
  for(int i=0;i<mxa;i++){
    mn = min(mn, dp[h+i]);
  }
  cout << mn << endl;
}


Measured memory_bytes: 384
import sys

input = sys.stdin.readline


def main():
    a, b, c, d = map(int, input().split())
    l = a + b
    r = c + d
    if l == r:
        print("Balanced")
    elif l > r:
        print("Left")
    else:
        print("Right")


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
n = int(input())
cnt = [0] * n
for i in input().split():
    cnt[int(i)] += 1
for i in range(1 + n % 2, n, 2):
    if cnt[i] != 2:
        print(0)
        exit(0)
print(pow(2, n // 2, int(1e9 + 7)))

Measured memory_bytes: 11188
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner reader = new Scanner(System.in);
        int a = reader.nextInt();
        int b = reader.nextInt();
        int c = reader.nextInt();
        
        System.out.println((a<b)&&(b<c)?"Yes":"No");
    }
}


Measured memory_bytes: 26264
from operator import itemgetter
N, K = map(int, input().split())
td = [list(map(int, input().split())) for _ in range(N)]
td.sort(key=itemgetter(1, 0), reverse=True)
t, d = zip(*td)

s = set()
q = []
tmp = 0
now = 0
for i in range(K):
    if t[i] not in s:
        s.add(t[i])
    else:
        q.append(d[i])

    tmp += d[i]
    now += 1
kind = len(s)
sums = [-100000000000]*(kind+1)
sums[kind] = tmp
#for i in range(K, N):
#    if not q:
#        break
#    if t[i] not in s:
#        s.
while q:
    kind += 1
    tmp = q.pop()
    for i in range(now, N):
        now += 1
        if t[i] not in s:
            s.add(t[i])
            sums.append(sums[kind-1] + d[i] - tmp)
            break
for i in range(len(sums)):
    sums[i] += i**2
print(max(sums))



Measured memory_bytes: 81624
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

const int maxn=50001;

int prime[maxn],isprime[maxn],res;

void maketable()
{
    int cnt=0,base=(int)sqrt(double(maxn));
    for(int i=2;i<maxn;i++){
        if(!isprime[i]){
            prime[cnt++]=i;
        }
        if(i<base){
            for(int j=i+i;j<maxn;j+=i){
                isprime[j]=1;
            }
        }

    }
}

void solve(int n)
{
    int k=(int)sqrt(double(n));
    for(int i=0;prime[i]<=k;i++){
        if(n%prime[i]==0){
            return ;
        }
    }
    res++;
}

int main()
{
    maketable();
    int n,s;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&s);
        solve(s);
    }
    printf("%d\n",res);
    return 0;
}



Measured memory_bytes: 3424
#                         author:  kagemeka 
#                         created: 2019-11-07 02:35:07(JST)
import sys
# import collections
import math
# import string
# import bisect
# import re
# import itertools
# import statistics
# import functools
# import operator

def main():
    *n, = (int(x) for x in sys.stdin.readline().split())
    n.sort()
    diff = n[2] * 2 - n[1] - n[0]
    print(diff // 2 if diff % 2 == 0 else math.ceil(diff / 2) + 1)
    


if __name__ == "__main__":
    # execute only if run as a script
    main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
typedef tuple<ll, ll, ll> T;

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;cin>>s;
    if(s[0]=='9'||s[1]=='9') cout<<"Yes";
    else cout<<"No";
    cout<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
int main() {
    cin>>n;
    for(int i=0;i<n;++i) {
        int x;
        cin>>x;
        v.push_back(x);
    }
    sort(v.begin(),v.end());
    int sum = 0;
    for(int i=0;i<v.size()-1;++i) {
        sum+=v[i];
    }
    sum+=v.back()/2;
    cout<<sum;
}

Measured memory_bytes: 256
inf = 10**9+7
import sys
a = 0
def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result = (result * numerator[k])%inf
    return result

x, y = map(int, input().split())
key = 0
if x == 2*y:
    print(1)
    sys.exit()
if y == 2*x:
    print(1)
    sys.exit()
while x>0 and y>0:
    x, y = x-3, y-3
    key += 1
    if x == 2*y:
        a = 1
        break
    if y == 2*x:
        a = -1
        break

if x < 0 or y < 0:
    print(0)
    sys.exit()

if a == 0:
    print(0)
elif a == 1:
    print(int(nCr(key*2+y ,key)))
else:
    print(int(nCr(key*2+x ,key)))

Measured memory_bytes: 45580
<?php

fscanf(STDIN,"%d %d",$a,$b);

if(($a+$b)%3 == 0) {
    echo 'Possible';

}else if ($a%3 == 0 )
{
    echo 'Possible';   
}else if ($b%3 == 0 )
{
    echo 'Possible';   
}
else{
    echo 'Impossible';
}

Measured memory_bytes: 4856
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;} 



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

int N, Q; string S;
cin >> N >> S >> Q;

vector<set<int>> pos(26, set<int>({1<<30}));
rep(i, 0, N) {
    pos[S[i] - 'a'].insert(i+1);
}

while(Q--){
    int q; cin >> q;
    if (q == 1){
        int i; char c; cin >> i >> c;
        pos[S[i-1] - 'a'].erase(i);
        pos[c - 'a'].insert(i);
        S[i-1] = c;
    }
    else {
        int l, r; cin >> l >> r;
        int c = 0;
        rep(i, 0, 26) if (!pos[i].empty())
            if (*pos[i].lower_bound(l) < *pos[i].lower_bound(r+1)) ++c;

        cout << c << "\n";
    }
}

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



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

int main(void) {
	int A, B; cin >> A >> B;
	int i, sum = 0;
	for (i = A; i <= B; i++) {
		if (i / 10000 == i % 10 && i / 10 % 10 == i / 1000 % 10) {
			sum += 1;
		}
	}

	cout << sum << endl;

	return 0;
}


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

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int x, percent;
	double p;

	cin >> x >> percent;
	p = percent / 100.0;

	double e = ((x + 1) / 2) / p;

	cout << setprecision(6) << fixed << e << endl;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;


fn main() {
    let n : usize = read();
    let ans = 2_u8.pow((1..n+1).map(|x| x.trailing_zeros()).max().unwrap());   
    println!("{}", ans);
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

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

int main(){
  int a,b;
  cin >> a >> b;
  int total = 1;
  int ans = 0;
  while (total < b) {
    // total += a -1とは意味合いが変わる
    total--;
    total += a;
    ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3568
#include <bits/stdc++.h>
#include <iostream>	
#define pb push_back
#define mp make_pair
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
typedef long long ll;

const int inf = int(2e9);
const int mod = inf + 7;
using namespace std;

void solve()
{
	int a, b;
	cin >> a >> b;
	cout << max(2 * a - 1, max(2 * b - 1, a + b));
}

int main()
{
	Red;
	solve();
	return 0;
}


Measured memory_bytes: 256
n=int(input())
lists=[list(map(int,input().split())) for _ in range(n-1)]  
for x in range(n):
    nums=x+1
    if nums==n:
        print(0)
    elif nums!=n:
        times=0
        while nums<n:
            if times>lists[nums-1][1]:
                if (times-lists[nums-1][1])%lists[nums-1][2]!=0:
                    a=(times-lists[nums-1][1])%lists[nums-1][2]  
                    times=times+lists[nums-1][2]-a
                    times+=lists[nums-1][0]
                    nums+=1  
                else:
                    times+=lists[nums-1][0]
                    nums+=1
            else:
                times=lists[nums-1][1]
                times+=lists[nums-1][0]   
                nums+=1 
        print(times)
        

Measured memory_bytes: 3188
n, m=map(int, input().split())
x=list(map(int, input().split()))

if n>=m:#全ての座標にコマを置ける
    print(0)
else:
    x.sort()
    dif=[]
    for i in range(m-1):#座標間距離を求める
        dif.append(x[i+1]-x[i])
    
    dif.sort()
    
    S=sum(dif)
    remove=0
    
    for j in range(1, n):#(コマの数-1)だけ長い区間を除く
        remove+=dif[-j]

    print(S-remove)

Measured memory_bytes: 13960
N = int(input())
txy = [list(map(int, input().split())) for _ in range(N)]
result = True

for pol in txy:
    dist = abs(pol[1]) + abs(pol[2])
    
    if(dist > pol[0]): result = False
    if(dist % 2 != pol[0] % 2): result = False

print(("No", "Yes")[result])

Measured memory_bytes: 27380
#include<iostream>
#include<string>

int main(){
  int n;
  std::string x,y;
  std::cin>>n;
  int a[1001][1001];
  int b[n];

  for(int i=0;i<n;i++){
    std::cin>>x;
    std::cin>>y;
    for(int j=0;j<1001;j++){
      for(int k=0;k<1001;k++){
	a[j][k]=0;
      }
    }
    for(int j=1;j<=x.size();j++){
      for(int k=1;k<=y.size();k++){
	if(x[j-1]==y[k-1]){
	  a[j][k]=a[j-1][k-1]+1;
	}else{
	  if(a[j-1][k]>a[j][k-1]){
	    a[j][k]=a[j-1][k];
	  }else{
	    a[j][k]=a[j][k-1];
	  }
	}
      }
    }
    b[i]=a[x.size()][y.size()];
  }

  for(int i=0;i<n;i++){
  std::cout<<b[i]<<"\n";
  }

  return 0;
}



Measured memory_bytes: 7136
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <queue>
#include <map>
using namespace std;

#define mod 1000000007
#define ten5 100005
#define ten6 1000005
#define PI 3.1415926

typedef long long LL;


//int numAC[ten5];
//int numWA[ten5];

int main(void)
{
    long long int sum=0,range=0,ceiling;
    double ans=0.0,half;
    long long int m,n,o,i,j,k=0,money;
    long long int a1,a2=0,a3=0,ar,as,at1;
    char c;
    //vector <int> v;
    //float f,g,h;
    //int c,d,big=0;
    string s,s1;
    cin>>n>>m;
    if(m==n)
    {
        for(i=0;i<n;i++)
        {
            cout<<m;
        }
    }
    else
    {
        a1=max(m,n);
        a2=min(m,n);
        for(i=0;i<a1;i++)
        {
            cout<<a2;
        }
    }
    return 0;
}





Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define EPS (1e-10)
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

signed main() {
	double r1, r2; cin >> r1 >> r2;
	printf("%.10lf\n", 1. / (1. / r1 + 1. / r2));
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long

signed  main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int ans = 0;
    int a[100010];
    rep(i, N) cin >> a[i];
    int sum = 0;
    int cnt = 0;
    rep(i, N) {
        sum += abs(a[i]);
        if (a[i] < 0) cnt++;
    }
    if (cnt % 2 == 0) {cout << sum << endl; return 0;}
    rep(i, N) {
        ans = max(ans, sum - abs(a[i]) * 2);
    }
    cout << ans << endl;
    

    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T> inline bool chmin(T&x,T y){if(x>y){x=y;return true;}return false;}
template<class T> inline bool chmax(T&x,T y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

template<class T> struct STree{
    int n;
    T e;
    vector<T> dat;

    inline T f(T x,T y){
        return x+y;
    }

    STree(int n_,T e_){
        n=1;e=e_;
        while(n<n_) n<<=1;
        dat.resize((n<<1),e);
    }

    STree(vector<T> v,T e_){
        int n_=v.size();
        n=1;e=e_;
        while(n<n_) n<<=1;
        dat.resize((n<<1),e);
        for(int i=0;i<n_;++i) dat[i+n]=v[i];
        for(int i=n-1;i>0;--i) dat[i]=f(dat[(i<<1)],dat[(i<<1)^1]);
    }

    void ud(int k,T c){
        k+=n;
        dat[k]+=c;
        while(k){
            if(k&1) dat[k>>1]=f(dat[k^1],dat[k]);
            else dat[k>>1]=f(dat[k],dat[k^1]);
            k>>=1;
        }
    }

    T gt(int l,int r){
        l+=n;r+=n;
        T s=e;
        while(l<r){
            if(r&1){
                --r;
                s=f(dat[r],s);
            }
            if(l&1){
                s=f(s,dat[l]);
                ++l;
            }
            l>>=1,r>>=1;
        }
        return s;
    }

    T operator[](int i){return dat[i+n];}
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,a;
    cin>>n;
    char c;
    vector<int> v(2*n);
    fr(i,2*n){
        cin>>c>>a;
        v[a-1+n*(c=='B')]=i;
    }
    vector<vector<int>> dp(2*n+1,vector<int>(n+1,INT_MAX));
    dp[0][0]=0;
    Fr(i,2*n){
        STree<int> b(2*n,0),w(2*n,0);
        fr(j,max(0,i-n)) w.ud(v[j],1);
        fr(j,min(n,i)) b.ud(v[j+n],1);
        for(int j=max(0,i-n);j<=min(n,i);++j){
            int k=i-j;
            if(j){
                w.ud(v[j-1],-1);
                dp[i][j]=min(dp[i][j],dp[i-1][j-1]+v[j-1]
                        -w.gt(0,v[j-1])
                        -b.gt(0,v[j-1]));
                w.ud(v[j-1],1);
            }
            if(k){
                b.ud(v[k+n-1],-1);
                dp[i][j]=min(dp[i][j],dp[i-1][j]+v[k+n-1]
                        -w.gt(0,v[k+n-1])
                        -b.gt(0,v[k+n-1]));
                b.ud(v[k+n-1],1);
            }
            if(j<n) w.ud(v[j],1);
            if(k) b.ud(v[k+n-1],-1);
        }
    }
    cout<<dp[2*n][n]<<endl;
}

Measured memory_bytes: 33792
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const int MOD = 1000000007;

template <typename T>
void print(const T &v);

int main()
{
    int n;
    cin >> n;
    vector<int> x(3, 0);
    ll ans = 1;
    for (int i = 0; i < n; i++)
    {
        int tar;
        cin >> tar;
        int tmp = 0;
        for (int j = 0; j < 3; j++)
        {
            if (x[j] == tar)
            {
                tmp++;
            }
        }
        ans = (ans * tmp) % MOD;
        for (int j = 0; j < 3; j++)
        {
            if (x[j] == tar)
            {
                x[j]++;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

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

  if(n<6){
    if(n==3)cout<<"2 5 63"<<endl;
    if(n==4)cout<<"2 5 20 63"<<endl;
    if(n==5)cout<<"2 5 20 30 63"<<endl;
    return 0;
  }
  
  vector<ll> ans;

  ll sum=0;
  ll k=0;
  ll x[4]={2,3,4,6};
  for(int i=0;i<n;i++){
    k=i/4;
    ll t=k*6+x[i%4];
    sum+=t;
    ans.pb(t);
  }

  for(int i=0;i<n;i++){
    if(sum%6==2&&ans[i]==8){
	 ll tmp;
	 for(int i=1;i<=6;i++){
	   if((ans[n-1]+i)%6==0)tmp=ans[n-1]+i;
	 }
	 ans[i]=tmp;
	 continue;
    }
    if(sum%6==3&&ans[i]==9){
	 ll tmp;
	 for(int i=1;i<=6;i++){
	   if((ans[n-1]+i)%6==0)tmp=ans[n-1]+i;
	 }
	 ans[i]=tmp;
	 continue;
    }
    if(sum%6==5&&ans[i]==9){
	 ll tmp;
	 for(int i=1;i<=6;i++){
	   if((ans[n-1]+i)%6==4)tmp=ans[n-1]+i;
	 }
	 ans[i]=tmp;
	 continue;
    }
    //cout<<ans[i];
  }

  ll ma=0;
  for(int i=0;i<n;i++){
    if(i)cout<<" ";
    cout<<ans[i];
    ma=max(ma,ans[i]);
  }
  cout<<endl;
  // dbg(ma);
  return 0;
}


Measured memory_bytes: 640
using System;

namespace B_Painting_Balls_with_AtCoDeer
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(' ');
            var n = int.Parse(inputs[0]);
            var k = int.Parse(inputs[1]);

            var answer = k * (Math.Pow(k - 1, n - 1));

            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=a;i<=n;++i)
#define lpd(i,a,n) for(int i=a;i>=n;--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 2004;
int n,z,w,a[N],dp[N][2];

int solve(int i, int j){
    int &ret = dp[i][j];
    if(~ret) return ret;
    ret = j ? infi : -infi;
    if(j){
        lp(k,i,n-1) ret = min(ret, solve(k+1, !j));
        ret = min(ret, abs(a[n] - a[i-1]));
    }
    else{
        lp(k,i,n-1) ret = max(ret, solve(k+1, !j));
        ret = max(ret, abs(a[n] - a[i-1]));
    }
    return ret;
}

int main(){
    read3i(n,z,w);
    a[0] = w;
    lp(i,1,n) readi(a[i]);

    mem(dp, -1);
    cout <<solve(1, 0);
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/


Measured memory_bytes: 384
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var vLine = Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
            var cLine = Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();

            var total = 0;
            for (var i = 0; i < n; i++)
            {
                if (vLine[i] - cLine[i] > 0)
                {
                    total += vLine[i] - cLine[i];
                }
            }

            Console.WriteLine(total);
        }
    }
}


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


int main() {
  int N;
  cin >> N;
  vector< int > L(N);
  ll ans = 0;

  REP(i,N)  cin >> L[i];
  sort( L.begin(), L.end() ) ;

//  REP(i,N) cout << L[i] << " "; cout << endl;
  
  for (int i=0; i<N-2; ++i ) {
    for (int j=i+1; j<N-1; ++j ) {
      int ab = L[i] + L[j];
//      cout << L[i] << " " << L[j] << " : ab " << ab << " : ans " << ans << endl;
      // 全部対象外
      if ( L[j+1] >= ab ) continue;
      // 全部対象内
      if ( L[N-1] < ab ) {
        // 2 2 3 3
        // N=4, j=1, ab=4 2個 = 4 - 1 - 1
        ans += N-j-1;
//        cout << "  all ans += " <<  N-j-1 << endl;
        continue;
      }
      // 二部探索で、c < a + b の c になる位置を探す
      int l = j;
      int r = N-1;
      int mid;
      while( r-l>1 ) {
        mid = (r+l) / 2;
//        cout << "    2bu " << l << " " <<  mid << " " << r << endl;
        if ( L[mid] < ab ) {
          l = mid;
        } else {
          r = mid;
        }
      }
      // 2 2 3 3 4
      // N=5, j=1, ab=4 2個 =  3 - 1;
      ans += l - j;
//      cout << "  2bu ans += " <<  l - j << endl;
    }
  }
  cout << ans << endl;

}


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

int main() {
    int n;
    double a;
    cin >> n;
    double sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        a = 1 / a;
        sum += a;
    }
    sum = 1 / sum;
    cout << sum;
}

Measured memory_bytes: 764
while 1:
    n,k,m = map(int,raw_input().split())
    if n == 0: break
    stone = range(1,n+1)
    p = m-1
    while len(stone) > 1:
        stone.pop(p)
        p = (p+k-1)%len(stone)
    print stone[0]

Measured memory_bytes: 4580
#include<bits/stdc++.h>
#include<vector>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> N(n);
    for(int i=0; i<k; i++){
        int m;
        cin >> m;
        for(int j=0; j<m; j++){
            int a;
            cin >> a;
            N[a-1] = 1;
        }
    }

    int ans=0;
    for(int i=0; i<n; i++){
        if(N[i] == 0) ans++;
    }

    cout << ans << endl;

    return 0;
}

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

template <typename T, typename E>
struct SegmentTree {
private:
    typedef function<T(T, T)> F;
    typedef function<T(T, E)> G;
    int n;
    F f;
    G g;
    T d1;
    vector<T> nodes;

public:
    SegmentTree(int n_, F f, G g, T d1, const vector<T>& v=vector<T>()) {
        this->f = f;
        this->g = g;
        this->d1 = d1;
        nodes_init(n_);
        if (n_ == (int)v.size()) build(n_, v);
    }

    void nodes_init(int n_) {
        n = 1;
        while (n < n_) n *= 2;
        nodes.clear();
        nodes.resize(2 * n - 1, d1);
    }

    void build(int n_, const vector<T>& v) {
        for (int i = 0; i < n_; i++) {
            nodes.at(i + n - 1) = v.at(i);
        }
        for (int i = n - 2; i >= 0; i--) {
            nodes.at(i) = f(nodes.at(i * 2 + 1), nodes.at(i * 2 + 2));
        }
    }

    void update(int idx, E value) {
        int node_idx = idx + n - 1;
        nodes.at(node_idx) = g(nodes.at(node_idx), value);
        int current_idx = node_idx;
        while (current_idx) {
            current_idx = (current_idx - 1) / 2;
            nodes.at(current_idx) = f(nodes.at(2 * current_idx + 1), nodes.at(2 * current_idx + 2));
        }
    }

    T query(int query_left, int query_right, int cur_idx, int cur_left, int cur_right) {
        if (cur_right <= query_left || query_right <= cur_left) return d1;
        if (query_left <= cur_left && cur_right <= query_right) return nodes.at(cur_idx);
        T value_from_left = query(query_left, query_right, 2 * cur_idx + 1, cur_left, (cur_left + cur_right) / 2);
        T value_from_right = query(query_left, query_right, 2 * cur_idx + 2, (cur_left + cur_right) / 2, cur_right);
        return f(value_from_left, value_from_right);
    }

    T query(int query_left, int query_right) {
        return query(query_left, query_right, 0, 0, n);
    }
};

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

    int n, q;
    cin >> n >> q;
    vector<int> a_list(n, INT_MAX);
    SegmentTree<int, int> segtree(n,
        [](int a, int b){return min(a, b);},
        [](int a, int b){return b;},
        INT_MAX,
        a_list);

    for (int i = 0; i < q; i++) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 0) {
            segtree.update(x, y);
        }
        else {
            cout << segtree.query(x, y + 1) << "\n";
        }
    }
}



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

using namespace std;
int const MAX = 51;

int n[2];
int deck[2][MAX];
int sum[2][MAX];

const int IniVal = (1<<29)+1234321;
int dp[MAX][MAX][MAX][MAX][2][4];

int rec(int l1, int r1, int l2, int r2, int which, int pass) {

  auto& ret = dp[l1][r1][l2][r2][which][pass];
  if(ret != IniVal) return ret;

  if(pass == 3) {
    return ret = 0;
  }

  // pass
  ret = -rec(r2, r2, r1, r1, !which, pass + 1)
        + (sum[which][r1] - sum[which][l1])
        - (sum[!which][r2] - sum[!which][l2]);

  if(r1 == n[which])
    return ret;

  if(deck[which][r1] != -1)
    ret = max(ret, -rec(l2, r2, l1, r1 + 1, !which, 0));
  else
    ret = max(ret, -rec(r2, r2, l1, r1 + 1, !which, 0));

  return ret;
}
 
int main() {

  for(int i=0; i<MAX; i++)
    for(int j=0; j<MAX; j++)
      for(int k=0; k<MAX; k++)
        for(int l=0; l<MAX; l++)
          for(int a=0; a<2; a++)
            for(int b=0; b<4; b++)
              dp[i][j][k][l][a][b] = IniVal;

  for(int i=0; i<2; i++)
    cin >> n[i];

  for(int i=0; i<2; i++)
    for(int j=0; j<n[i]; j++)
      cin >> deck[i][j];

  for(int i=0; i<2; i++) {
    sum[i][0] = 0;
    for(int j=0; j<n[i]; j++) {
      int point = deck[i][j];
      if(point == -1) point = 0;
      sum[i][j + 1] = sum[i][j] + point;
    }
  }

  cout << rec(0, 0, 0, 0, 0, 0) << endl;

  return 0;
}

Measured memory_bytes: 214508
n = int(input())

a, b = [*map(list, zip(*[[*map(int, input().split())] for _ in range(n)]))]
a.sort()
b.sort()

l0, r0 = a[(n-1)//2], b[(n-1)//2]
if n % 2 == 1:
    print(r0-l0+1)
else:
    l1, r1 = a[n//2], b[n//2]
    print((r1+r0)-(l1+l0)+1)


Measured memory_bytes: 59524
n,k=map(int,input().split())
s=list(input())

if s[k-1]=="A":
    s[k-1]="a"
elif s[k-1]=="B":
    s[k-1]="b"
elif s[k-1]=="C":
    s[k-1]="c"
    
print(''.join(s))

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

using namespace std;

#define lp(i,n) for(int i = 0; i <n;i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define MP make_pair
#define SZ(v) ((int)((v).size()))
typedef long long ll;

const ll MOD = 1e9 + 7;
const int OO = (int)1e6;
const int N = (int)1e7;

void init(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main() {
	#   ifdef LOCAL_PROJECT
        freopen("in.txt", "r", stdin);
    #   endif
    string x;
    int k,n;
    cin>>n>>k>>x;
    x[k-1]=x[k-1]-'A'+'a';
    cout<<x;
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

vi topological_sort(vvi& G, vi& degin)
{
    //トポロジカルソートを記録する配列
    vi sorted_vertices;

    //入次数が0の頂点を発見したら、処理待ち頂点としてキューに追加する
    queue<int> q;
    rep(i, G.size())
    {
        if (degin[i] == 0) q.push(i);
    }

    while (!q.empty())
    {
        int v = q.front(); q.pop();

        //その頂点と隣接している頂点の入次数を減らし、0になればキューに追加
        rep(i, G[v].size())
        {
            int u = G[v][i];
            degin[u] -= 1;
            if (degin[u] == 0) q.push(u);
        }

        //頂点vを配列の末尾に追加する 
        sorted_vertices.push_back(v);
    }

    return sorted_vertices;
}

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

    int N, M;
    cin >> N >> M;

    vvi G(N);
    vi degin(N);


    rep(i, M)
    {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        G[x].push_back(y);
        degin[y]++;
    }


    //動的計画法を行うためにトポロジカルソート
    vi V = topological_sort(G, degin);

    //終点から処理したいので逆順にする
    reverse(all(V));

    vi dp(N);

    //2重ループだが辺の数しかループしないので、O(M)で処理可能。
    for (auto v : V)
    {
        for (auto x : G[v])
        {
            chmax(dp[v], dp[x] + 1);
        }
    }

    //最大値を取り出す
    int res;
    rep(i, N) chmax(res, dp[i]);

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 7032
using System;

namespace ASDS1_4_wariate_
{
    class Program
    {
        class hikkoshi
        {
            public int P;
            public int k;
            public int[] A;
            public hikkoshi(int P,int k,int[] A)
            {
                this.P = P;
                this.k = k;
                this.A = A;
            }

        }

        static void Main(string[] args)
        {
            var input = getsplit();
            int n = getint(input[0]);
            int k = getint(input[1]);
            var A = new int[n];
            int sum = 0;
           

            for (int i = 0; i < n; i++)
            {
                A[i] = getint(Console.ReadLine());
                sum += A[i];
            }

            Console.WriteLine(BinarySearch(sum,k,A));


        }
        static bool check(hikkoshi a)
        {
            
            int stack= 0;
            int track = 0;

            foreach (var s in a.A)
            {
                if (stack+s <= a.P)
                {
                    stack += s;
                   
                }
                else
                {
                    if (s > a.P ||track == a.k-1)
                    {
                        return false;
                    }
                    else
                    {
                        track++;
                        stack = s;
                    }
                }
            }
            return true;
        }

        static int BinarySearch(int sum,int k,int[] A)
        {
            int left = 0;
            int right = sum+1;
            int mid;

            while (left < right)
            {
                mid = (left + right) / 2;
                hikkoshi Z = new hikkoshi(mid,k,A);
              

                if (check(Z))
                {
                    right = mid;
                }
                
                else
                {
                    left = mid + 1;
                }
            }
            return right;
        }




        public static string[] getsplit()
        {
            string[] x = Console.ReadLine().Split(' ');
            return x;
        }
        public static int getint(string a)
        {
            int x = int.Parse(a);
            return x;
        }
    }
}

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

min_v = int(input())
r = int(input())
max_v = r - min_v
if min_v > r:
    min_v = r

for _n in range(2, N):
    r = int(input())
    if max_v < r - min_v:
        max_v = r - min_v
    if min_v > r:
        min_v = r
print(max_v)



Measured memory_bytes: 5612
import java.util.Arrays;
import java.util.Scanner;

//Leaky Cryptography
public class Main{

	int[][] a;
	int[] cs, t;
	char[] key;
	
//	boolean check(int[][] a, int[] c, int[] key){
//		int[] t = new int[32];
//		int carry = 0;
//		for(int i=31;i>=0;i--){
//			int s = carry;
//			for(int j=0;j<8;j++){
//				if(key[i]==0)s+=a[j][i];
//				else s+=(a[j][i]+1)%2;
//			}
//			t[i] = s%2;
//			carry = s/2;
//		}
//		for(int i=31;i>=0;i--){
//			if(key[i]==0&&t[i]!=c[i])return false;
//			if(key[i]==1&&t[i]!=(c[i]+1)%2)return false;
//		}
//		return true;
//	}
	
	boolean dfs(int k, int c){
		if(k==-1){
			return true;
//			return check(a, cs, key);
		}
//		key[k] = 0;
//		if(dfs(k-1, c))return true;
//		key[k] = 1;
//		if(dfs(k-1, c))return true;
//		return false;
		key[k] = '0';
		int x = c;
		for(int i=0;i<8;i++){
			x+=a[i][k];
		}
		if(x%2==cs[k]){
			if(dfs(k-1, x/2))return true;
		}
		key[k] = '1';
		x = c;
		for(int i=0;i<8;i++){
			x+=(a[i][k]+1)%2;
		}
		if(x%2==(cs[k]+1)%2){
			if(dfs(k-1, x/2))return true;
		}
		return false;
	}
	
	int[] make(String s){
		int[] r = new int[32];
		long x = Long.parseLong(s, 16);
		int i = 31;
		while(x>0){
			r[i--] = (int) (x%2);
			x>>=1;
		}
		return r;
	}
	
//	String tohex(int[] key){
//		String res = "";
//		int j = 0;
//		for(int i=0;i<8;i++){
//			String r = "";
//			for(int k=0;k<4;k++)r+=key[j++];
//			
//		}
//	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T--!=0){
			a = new int[8][32];
			for(int i=0;i<8;i++)a[i] = make(sc.next());
			cs = make(sc.next());
			key = new char[32];
//			System.out.println(check(a, cs, make(sc.next())));
			dfs(31, 0);
			String k = new String(key);
			long l = Long.parseLong(k, 2);
			System.out.println(String.format("%h", l));
//			debug(key);
//			for(int i=0;i<8;i++)debug(a[i]);
//			debug(cs);
//			key = new char[32];
//			dfs(31, 0);
//			System.out.println(new String(key));
		}
	}
	
	void debug(Object...o){
		System.out.println(Arrays.deepToString(o));
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll n;
P c[100010];

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

  cin>>n;
  rep(i,n){
    ll a,b;
    cin>>a>>b;
    c[i]=P(a+b,a);
  }
  sort(c,c+n);
  reverse(c,c+n);
  ll res=0;
  rep(i,n){
    if(i%2==0)res+=c[i].se;
    else res-=c[i].fi-c[i].se;
  }
  cout<<res<<endl;

  return 0;
}


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

using pii = pair<int,int> ;
using pll = pair<long,long> ;
using umpii = unordered_map<int,int> ;
using mpii = map<int,int> ;

#define f first
#define s second

int32_t main(){
	int count = 0 ;
	string s, t ;
	cin >> s >> t ;
	for(int i = 0 ; i < 3 ; i++) count += s[i] == t[i] ;
	cout << count ; 
	return 0 ;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define repp(i,q) for(int i = 0; q > i; i++)
#define rep(i,q) for(int i = 0; q >= i; i++)
int main(){
  int n,m,d;
  cin >> n >> m >> d;
  char mp[n][m];
  repp(i,n){
    repp(j,m){
      cin >> mp[i][j];
    }
  }
  int ok = 0;
  repp(i,n){
    rep(j,m-d){
      bool kabe = false;
      repp(k,d){
        if(mp[i][k+j] == '#'){
          kabe = true;
          break;
        }
      }
      if(!kabe){
        ok++;
      }
    }
  }
  rep(i,n-d){//2回
    repp(j,m){//5回
      bool kabe = false;
      repp(k,d){//二回
        if(mp[k+i][j] == '#'){
          kabe = true;
          break;
        }
      }
      if(!kabe){
        ok++;
      } 
    }
  }
  cout << ok << endl;
}


Measured memory_bytes: 3104
program kadai
implicit none
integer  ::  n
integer,allocatable  ::  a(:)
integer  ::  i
integer  ::  shita
real(8)  ::  ans,ue

read(*,*) n
allocate(a(n))
read(*,*) a

do i=1,n
    ue=ue+1/real(a(i),8)
end do

ans=1/ue

write(*,*) ans

end program kadai


Measured memory_bytes: 256
W, H, N = [int(_) for _ in input().split()]
XYA = [[int(_) for _ in input().split()] for i in range(N)]

sx, sy, ex, ey = 0, 0, W, H

for x, y, a in XYA:
    if a == 1:
        sx = max(sx, x)
    elif a == 2:
        ex = min(ex, x)
    elif a == 3:
        sy = max(sy, y)
    elif a == 4:
        ey = min(ey, y)
    
result = max(ex - sx, 0) * max(ey - sy, 0)
print(result)


Measured memory_bytes: 3064
N = int(input())
W = list(map(int, input().split()))
S1 = W[0]
S2 = sum(W[1:])
ans = abs(S1 - S2)
for i in range(1, N - 1):
    S1 += W[i]
    S2 -= W[i]
    ans = min(ans, abs(S1 - S2))
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pf push_front
#define mod 1000000007
#define endl '\n'
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


int main()
{
    unordered_map<ll,ll>mp;
    ll i,j;
    for(i=1;i<=9;i++)
    {
        for(j=1;j<=9;j++)
        {
            mp[i*j]++;
        }
    }
    ll n;
    cin>>n;
    if(mp.find(n)!=mp.end())
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No";
    }
}


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

using namespace std;

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

int N;
vector<tuple<char, int>> v;
int idx;

int solve(int depth) {
  int d; char c; tie(d, c) = v[idx];
  assert(d == depth);
  if(isdigit(c)) {
    idx++;
    return c - '0';
  } else {
    idx++;
    if(c == '+') {
      int n1 = solve(depth + 1);
      while(idx < N) {
	int d2; char c2; tie(d2, c2) = v[idx];
	if(d2 < depth + 1) break;
	n1 += solve(depth + 1);
      }
      return n1;
    }
    else if(c == '-') {
      int n1 = solve(depth + 1);
      while(idx < N) {
	int d2; char c2; tie(d2, c2) = v[idx];
	if(d2 < depth + 1) break;
	n1 -= solve(depth + 1);
      }
      return n1;
    }
    else if(c == '*') {
      int n1 = solve(depth + 1);
      while(idx < N) {
	int d2; char c2; tie(d2, c2) = v[idx];
	if(d2 < depth + 1) break;
	n1 *= solve(depth + 1);
      }
      return n1;
    }
    else assert(0);
  }
}

int main() {
  
  while(cin >> N && N) {
    v.clear();
    rep(i, N) {
      char c; cin >> c;
      int depth = 0;
      while(c == '.') {
	depth ++;
	cin >> c;
      }
      
      v.push_back(make_tuple(depth, c));
    }
    
    idx = 0;
    cout << solve(0) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 3104
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define print(x) cout<<(x)<<endl
#define INF10 1001001001 
#define INF5 100000
#define EPS 1e-10


int main() {
	int N, D; cin >> N >> D;
	int cnt = 0;
	while (N > 0) {
		cnt++;
		N -= (2 * D + 1);
	}
	cout << cnt << endl;







	return 0;
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=a[::-1] #逆順

ans=[]

if len(a)%2==0: #偶数の場合
    for i in range(0,n,2):
        ans.append(b[i])
    for i in range(0,n,2):
        ans.append(a[i])
else: #奇数の場合
    for i in range(0,n,2):
        ans.append(b[i])
    for i in range(1,n,2):
        ans.append(a[i])
print(*ans)

Measured memory_bytes: 102996
#include<bits/stdc++.h>
#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 each(a,x) for(auto a : (x))
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) ((a) = min((a),(b)))
#define chmax(a,b) ((a) = max((a),(b)))
#define in_range(x,l,r) ((l)<=(x) && (x)<(r))
#define printvec(a) rep(i,a) cout << a[i] << " \n"[i+1==(a).size()];
#define fs first
#define sc second
#define em emplace
#define eb emplace_back
#define sz size()
#define MP make_pair
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;

const ll INF = 1e8;
const D EPS = 1e-8;
const ll MOD = 1e9+7;

int main(){
  string s;
  cin >> s;
  cout << (s[0] == s.back() ^ s.size() % 2 ? "First" : "Second") << endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}

void No(){
	cout<<"No"<<endl;
	exit(0);
}

int main(){
  string S; cin>>S;
  S[3]='8';
  cout<<S<<endl;
}



Measured memory_bytes: 256