akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define pii pair<ll,ll>
#define ll long long
#define tii tuple<ll,ll,ll>
#define all(v) (v).begin(),(v).end()
#define deb(x) cout << #x << "=" << x << endl;
#define ull unsigned long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define ld long double
#define mod 1000000007
#define PI 3.141592653589793238
#define phi 1.638
#define eps 1e-9
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;      

int main() {
    fastio
    string s;
    cin>>s;
    if(s.back() == 's') {
        cout<<s<<"es"<<endl;
    }
    else {
        cout<<s<<"s"<<endl;
    }
}

Measured memory_bytes: 3644
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.array;

int N, M;
int[] a, b;
bool[] data;
int[][] e;
int[] memo;
int ans;

void Func(int n, int b){
    memo ~= n;
    foreach(i ; e[n]){
        bool check = false;
        if(i == b) continue;
        foreach(j ; memo){
            if(i == j){
                check = true;
            }
            if(check){
                data[j] = true;
            }
        }
        if(!check){
            Func(i, n);
        }
    }
    memo.popBack();
}

void main()
{
    auto input = readln.chomp.split.to!(int[]);
    N = input[0];
    M = input[1];

    a = new int[M];
    b = new int[M];
    data = new bool[N];
    e = new int[][N];
    foreach(i ; 0..M){
        auto input2 = readln.chomp.split.to!(int[]);
        a[i] = input2[0];
        b[i] = input2[1];
        --a[i], --b[i];
        e[a[i]] ~= b[i];
        e[b[i]] ~= a[i];
    }

    Func(0, 0);
    foreach(i; 0..M){
        if(!data[a[i]] || !data[b[i]]){
            ++ans;
        }
    }
    ans.writeln;
}

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

int main() {
  string s, t, u;
  int a, b;

  cin >> s >> t >> a >> b >> u;

  if (s == u) {
    cout << a-1 << " " << b << endl;
  } else if(t == u) {
    cout << a << " " << b-1 << endl;
  }
}

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

int main()
{
  int n,i,j;
  int p[50],a[50],b[50],c[50],d[50],e[50],f[50],s[50],m[50],in[50],time[50];
  string l[50],tmps;
  double eff[50],tmp;

  for(;;){
    cin>>n;
    if(!n) break;

    for(i=0;i<n;i++){
      cin>>l[i]>>p[i]>>a[i]>>b[i]>>c[i]>>d[i]>>e[i]>>f[i]>>s[i]>>m[i];
      in[i]=(f[i]*s[i])*m[i]-p[i]; 
      time[i]=a[i]+b[i]+c[i]+m[i]*(d[i]+e[i]);
      eff[i]=(double)in[i]/time[i];
    }
    for(i=0;i<n;i++){
      for(j=1;j<n;j++){
	if(eff[j-1]<eff[j]){
	  tmp=eff[j-1]; eff[j-1]=eff[j]; eff[j]=tmp;
	  l[j-1].swap(l[j]);
	} else if(eff[j-1]==eff[j]){
	  if(l[j-1].compare(l[j])>0)
	    l[j-1].swap(l[j]);
	}
      }
    }
    for(i=0;i<n;i++)
      cout<<l[i]<<endl;
    cout<<"#"<<endl;
  }
}


Measured memory_bytes: 1208
#include <bits/stdc++.h>
#define zcin(type, a) type a; cin >> a;
#define zcout(a, sep1, b, sep2) cout << a << sep1 << b << sep2;
#define zfor(i, b, n) for (int i = b; i < n; ++i)
#define pb push_back

using namespace std;

int main()
{
	#ifdef ME
		freopen("input.txt", "r", stdin);
		//freopen("output.txt", "w", stdout);
	#endif
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int taka = b, aoka = d, takd = a, aokd = c;
	while (true)
	{
		aokd -= taka;
		if (aokd <= 0)
		{
			cout << "Yes";
			break;
		}
		takd -= aoka;
		if (takd <= 0)
		{
			cout << "No";
			break;
		}
		
	}

	return 0;
}


Measured memory_bytes: 3636
import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), T = sc.nextInt();
        int[] c = new int[n];
        int[] t = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = sc.nextInt();
            t[i] = sc.nextInt();
        }
        int ans = INF;
        boolean exist = false;
        for (int i = 0; i < n; i++) {
            if (t[i] <= T) { 
                exist = true;
                ans = Math.min(ans, c[i]);
            }
        }
        if (exist) System.out.println(ans);
        else System.out.println("TLE");
    }
    public static final int INF = 10000;
}

Measured memory_bytes: 21844
#include <stdio.h>

int main(){
  int len, i, j, minj, temp, cnt = 0;
  int A[100];

  scanf("%d", &len);

  for(i = 0; i < len; i++){
    scanf("%d", &A[i]);
  }


  for(i = 0; i < len; i++){
    minj = i;

    for(j = i; j < len; j++){
      if(A[j] < A[minj]){
	minj = j;
      }
    }

    temp = A[i];
    A[i] = A[minj];
    A[minj] = temp;
    if(i != minj) cnt++;
  }

  for(i = 0; i < len - 1; i++){
    printf("%d ", A[i]);
  }

  printf("%d\n%d\n", A[len-1], cnt);

  return 0;
}



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

const int MAX = 1e5+5;
int indegree[MAX];
int dp[MAX];
vector<int> grafo[MAX];

int solve(int i){
    if(dp[i]!=-1) return dp[i];
    if(grafo[i].size()==0) return 1;
    int best = 0;
    for(auto v: grafo[i]){
        best = max(best, solve(v));
    }
    return dp[i]=1+best;
}

int main(void){
    int n, m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u, v;
        cin>>u>>v;
        grafo[u-1].push_back(v-1);
        indegree[v-1]++;
    }
    memset(dp, -1, sizeof dp);
    int best=-1;
    for(int i=0;i<n;i++){
        if(indegree[i]==0){
            best=max(best, solve(i));
        }
    }


    cout<<best-1<<endl;

    return 0;
}


Measured memory_bytes: 11136
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long[] a = new long[N];
		long[] sum = new long[N+1];
		for(int i=0;i<N;++i){
			a[i] = sc.nextLong();
			sum[i] = 0;
		}
		sum[N] = 0;
		for(int i=1;i<=N;++i) sum[i] = sum[i-1] + a[i-1];
		
        long ans = Long.MAX_VALUE;
		for(int border=2;border<=N-2;++border){
			long x1,x2,x3,x4;
			int left = 1;
			int right = border;
			while(left+1<right){
				int center = (left+right)/2;
				if(sum[border]-sum[center]<sum[center]) right = center;
				else left = center;
			}
            if(border!=2&&Math.abs(sum[border]-2*sum[left])>Math.abs(sum[border]-2*sum[left+1])) left++;
            if(border!=2&&Math.abs(sum[border]-2*sum[left])>Math.abs(sum[border]-2*sum[left-1])) left--;
			x1 = sum[left];
			x2 = sum[border]-sum[left];

			left = border+1;
			right = N;
			while(left+1<right){
				int center = (left+right)/2;
				if(sum[N]-sum[center]<sum[center]-sum[border]) right = center;
				else left = center;
			}
            if(border!=N-2&&Math.abs(sum[N]+sum[border]-2*sum[left])>Math.abs(sum[N]+sum[border]-2*sum[left+1])) left++;
            if(border!=N-2&&Math.abs(sum[N]+sum[border]-2*sum[left])>Math.abs(sum[N]+sum[border]-2*sum[left-1])) left--;
			x3 = sum[left] - sum[border];
			x4 = sum[N] - sum[left];

			long max = Math.max(Math.max(x1,x2),Math.max(x3,x4));
			long min = Math.min(Math.min(x1,x2),Math.min(x3,x4));
            if(max-min < ans) ans = max-min;
            //System.out.println(x1+" "+x2+" "+x3+" "+x4);
		}
		System.out.println(ans);
		return;
	}
}

Measured memory_bytes: 85920
import java.util.Scanner;

class Main {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(); //個数
		int total=in.nextInt(); //許容量
		int[] v = new int[n];//価値
		int[] w = new int[n];//重さ

		for (int i = 0; i < n; i++) {
			v[i] = in.nextInt();
			w[i] = in.nextInt();
		}

		int[][] t = new int[n][total + 1];
		//t[0][w[0]]= v[0];
		for (int i = 0; i < n; i++) {//品物１こずつループ

			for (int j = 1; j <=total; j++) {
				if(i==0) {
					if(j>=w[i]) {
						t[i][j]=v[i];
					}
				}else if(j<w[i]) {
					t[i][j]= t[i-1][j];
				}else {
					t[i][j]=Math.max(t[i-1][j], t[i-1][j-w[i]] +v[i]);
				}
				//System.out.printf("t[%d][%d]=%d\n",i,j,t[i][j]);
			}
		}

		System.out.println(t[n-1][total]);
		in.close();
	}
}





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

int main() {
  vector<int> vec(5);
  int cnt=0;
  rep(i,5){
    cin>>vec[i];
    cnt+=(vec[i]+9)/10*10;
  }
  int ans=cnt;
  rep(i,5){
    int x=vec[i]%10;
    if(x!=0)ans=min(ans,cnt+x-10);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <chrono>
#include <bitset>
using namespace std;

class Timer {
	chrono::high_resolution_clock::time_point start, end;
	double limit;

public:
	Timer() {
		start = chrono::high_resolution_clock::now();
	}
	Timer(double l) {
		start = chrono::high_resolution_clock::now();
		limit = l;
	}

	double getTime() {
		end = chrono::high_resolution_clock::now();
		return chrono::duration<double>(end - start).count();
	}

	bool Over() {
		if (getTime() > limit) {
			return true;
		}
		return false;
	}

	void setLimit(double l) {
		limit = l;
	}
	void setStart() { start = chrono::high_resolution_clock::now(); }
	double getLimit() { return limit; }
};


class Xor128 {
	unsigned static int x, y, z, w;
public:
	Xor128() {
		x = 31103110, y = 123456789, z = 521288629, w = 88675123;
	}

	unsigned int rand()
	{
		unsigned int t;
		t = (x ^ (x << 11)); x = y; y = z; z = w;
		return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
	}
};
unsigned int Xor128::x, Xor128::y, Xor128::z, Xor128::w;

int H, W;
int H2, W2;
bool mode = false;
bitset<5> GRID[12][12];
char odd = -1;
int ni = -1, nj = -1;
void swapGRID(int m, int i, int j) {
	if (m) {
		for (int k = 0; k < H; k++)swap(GRID[k][i], GRID[k][j]);
	}
	else {
		for (int k = 0; k < W; k++)swap(GRID[i][k], GRID[j][k]);
	}
}
bool is_() {
	bool flag = true;

	if (mode) {
		if (GRID[H2][W2] != odd)return false;
	}

	for (int i = 0; flag && i < H; i++) {
		for (int j = 0; flag && j < W; j++) {
			if (GRID[i][j] != GRID[H - 1 - i][W - 1 - j]) {
				ni = i, nj = j;
				flag = false;
			}
		}
	}
	return flag;
}

int main() {
	cin >> H >> W;
	if (H % 2 && W % 2)mode = true;
	H2 = H / 2; W2 = W / 2;
	vector<int>cnt(26);
	for (int i = 0; i < H; i++)for (int j = 0; j < W; j++) {
		char c; cin >> c;
		GRID[i][j] = c;
		cnt[c - 'a']++;
	}
	int oddcnt = 0;
	for (int i = 0; i < 26; i++) {
		if (cnt[i] % 2) {
			oddcnt++;
			odd = 'a' + i;
		}
	}

	if (oddcnt > 1) {
		cout << "NO" << endl;
		return 0;
	}
	else if (oddcnt == 1 && !mode) {
		cout << "NO" << endl;
		return 0;
	}
	else if (oddcnt == 0 && mode) {
		cout << "NO" << endl;
		return 0;
	}

	if (H == 1 && W == 1) {
		cout << "YES" << endl;
		return 0;
	}

	Timer tmr;

	Xor128 rnd;
	int loop = 0;
	while (1) {
		if (loop % 100000 == 0) {
			if (tmr.getTime()>1.9)break;
		}

		int m, i, j;
		m = rnd.rand() % 2;
		if (H == 1)m = 1;
		if (W == 1)m = 0;

		if (m) {
			if(nj==-1)i = rnd.rand() % W;
			else i = nj;
			do {
				j = rnd.rand() % W;
			} while (i == j);
		}
		else {
			if (ni == -1)i = rnd.rand() % H;
			else i = ni;
			do {
				j = rnd.rand() % H;
			} while (i == j);
		}


		swapGRID(m, i, j);
		if (is_()) {
			cout << "YES" << endl;
			return 0;
		}

		loop++;
	}
	cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 384
while True:
    N = input()
    if N == "0":
        break

    q1,b,c1,c2,q2 = [int(i) for i in N.split()]

    if c1 <= c2:
        x = min(q2, b // c1)
    else:
        x = min((b-c2*q1) // (c1-c2), q2, b // c1)
    y = (b-c1*x) // c2

    if x <= 0 or x + y < q1:
        print("NA")
    else:
        print(x,y)



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

int main() {
  for(double a, b, c, d, e, f; scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &e, &f) != EOF; ) {
    double det = a * e - b * d;
    double x = (e * c - b * f) / det;
    double y = (-d * c + a * f) / det;
    printf("%.3f %.3f\n", x + 1e-8, y + 1e-8);
  }
}

Measured memory_bytes: 1084
#include <iostream>
#include <cstdio>
#include <cctype>
#define il inline
#define vd void
#define rg register
#define ll long long
#define rep(i,x,y) for(rg int i=x;i<=y;++i)
#define drp(i,x,y) for(rg int i=x;i>=y;--i)
using namespace std;
const int Len=2333333;
char buf[Len],*p1=buf,*p2=buf,duf[Len],*q1=duf;
il char gc(); il int rd(); il vd pc(char c); il vd rt(int x); il vd flush();
int n;
char s[105],t[105];
int main(){
	scanf("%d",&n);
	scanf("%s%s",s+1,t+1);
	rep(i,1,n) printf("%c%c",s[i],t[i]);
	return flush(),0;
}

il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,Len,stdin),p1==p2)?-1:*p1++;}
il int rd(){char c;
	while(!isdigit(c=gc())&&c!='-');
	int f=c=='-'?c=gc(),1:0,x=c^48;
	while(isdigit(c=gc())) x=((x+(x<<2))<<1)+(c^48);
	return f?-x:x;
}
il vd pc(char c){q1==duf+Len&&fwrite(q1=duf,1,Len,stdout),*q1++=c;}
il vd rt(int x){x<0?pc('-'),x=-x:0,pc((x>=10?rt(x/10),x%10:x)+48);}
il vd flush(){fwrite(duf,1,q1-duf,stdout);}

Measured memory_bytes: 256
def cmb(n, r, mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
mod = 10**9 + 7
n , k = map(int,input().split())

fact = [1, 1]
factinv = [1, 1]
inv = [0,1]

for i in range(2,n+1):
    fact.append((fact[-1] * i) % mod)
    inv.append((inv[mod % i] * (mod - (mod // i))) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

for i in range(k):
    ans = 1
    ans *= cmb(k-1,i,mod)
    ans *= cmb(n-k+1,i+1,mod)
    ans %= mod
    print(ans)

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



int main() {
    int n;
    cin>>n;
    int height[n];
    for (int i=0;i<n;i++) cin>>height[i];
    int sum = 0;
    int max = 0;
    int j = 0;
    while(j<n){
        if (height[j]>=max) {
            max = height[j];
            sum ++;
        }
        j++;
    }
    cout<<sum;
}


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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int[] t = new int[4];
            for (int i = 0; i < 4; i++) {
                t[i] = sc.nextInt();
            }
            Arrays.sort(t);
            if ( t[0] == t[1] && t[2] == t[3] ) {
                System.out.println("yes");
            } else {
                System.out.println("no");
            }
        }
    }
}



Measured memory_bytes: 26264
import java.util.Scanner;

class Main {

    private static int count;

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

        int N = Integer.parseInt(scanner.next());

        int[] A = new int[N];

        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(scanner.next());
        }

        calculate(A, N, 0);
        System.out.println(count);
    }

    private static void calculate(int[] A, int N, int i) {
        if (i == N) {
            int num = 1;
            for (int j = 0; j < N; j++) {
                num *= A[j];
            }
            if (num % 2 == 0) {
                count++;
            }
        } else {
            for (int j = 0; j < 3; j++) {
                int tmp = A[i];
                A[i] = tmp - 1 + j;
                calculate(A, N, i+1);
                A[i] = tmp;
            }
        }
    }
}

Measured memory_bytes: 21968
#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main(){
	
	int W[250]={};
	for(int i=0;i<220;i++)
		W[i]=3000;

	int N,M;

	int h,m,k,g;
	cin>>N;
	for(int i=0;i<N;i++)
	{
		cin>>h>>m;
		W[i]=100*h+m;
	}
	cin>>M;
	for(int i=0;i<M;i++)
		{
		cin>>h>>m;
		W[i+100]=100*h+m;
	}
	sort(W,W+205);
	for(int i=0;i<220;i++)
		if(W[i+1]==W[i])W[i]=3000;
	sort(W,W+205);
	for(int i=0;i<N+M;i++)
	{
		if(W[i]<=2359){
		k=W[i]/100;
		g=W[i]%100;
		if(i>0)cout<<" ";
		cout<<k<<":";
		if(g<10)cout<<"0";
		cout<<g;}
	}
	cout<<endl;
	return 0;
}
		

Measured memory_bytes: 1180
# 全探索

n=int(input())

class People:
    def __init__(self):
        self.type=None

peoples=[People() for i in range(n+1)]

def change_10to2(i):
    ans=format(i, '#0' + str(n + 3) + 'b')[2:]
    return ans

def set_people_type(binary_list,peoples):
    for i,people in enumerate(peoples):
        if i!=0:
            people.type=binary_list[i]

def get_statement():
    shougen={}
    for i in range(1,n+1):
        ai=int(input())
        ans=[]
        for j in range(ai):
            kumi=[int(k) for k in input().split()]
            ans.append(kumi)
        shougen[str(i)]=ans
    return shougen

shougens=get_statement()

def shougen_dicide(peoples,shougens):
    for i in range(1,n+1):
        shougen=shougens[str(i)]
        for shou in shougen:
            people,type=shou
            people=int(people)
            type=str(type)
            # 正直者のとき
            if peoples[i].type=="1":
                if peoples[people].type!=type:
                    return False

            # #嘘つきのとき
            # else:
            #     if peoples[people].type==type:
            #         return False
    return True



ans=0
for i in range(2**n):
    binary_list=change_10to2(i)
    set_people_type(binary_list,peoples)
    if shougen_dicide(peoples,shougens):
        ans=max(ans,binary_list.count("1"))
print(ans)


Measured memory_bytes: 9196
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=200005;
const int maxe=2000005;
int n,m;
char str[maxn];

int main(){
  scanf("%s",str);
  ll len=strlen(str);
  ll ans=len*(len-1)/2;
  for(int i='a';i<='z';i++){
    ll tot=0;
    for(int j=0;j<len;j++){
        if(str[j]==i)tot++;
    }
    ans-=tot*(tot-1)/2;
  }
  printf("%lld\n",ans+1);
  return 0;
}


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

#define int long long
typedef vector<int> vint;
typedef pair<int, int> pint;
const double PI = 3.141592653589793238462643383279;
const int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
template<typename T, typename U> inline bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> inline bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
struct Init {
    Init() {
        cout << fixed << setprecision(20);
    };
} init;

string s, t, S = "";
bool match[550000];
int mod = 1e9 + 7;
void rolliha(int hash) {
    int hpow = 1;
    for (int i = 0; i < t.length(); i++) { hpow = hpow * hash % mod; }
    int th = 0, Sh = 0;
    for (int i = 0; i < t.length(); i++) {
        th = (th * hash % mod + t[i] % mod) % mod;
        Sh = (Sh * hash % mod + S[i] % mod) % mod;
    }
    for (int i = 0; i < s.length(); i++) {
        match[i] &= th == Sh;
        Sh = (Sh * hash % mod + S[i + t.length()] % mod - S[i] * hpow % mod + mod) % mod;
    }
}
int dp[550000];
int dfs(int idx, int depth = 0) {
    if (depth > 550000) {
        cout << -1 << endl;
        exit(0);
    }
    if (!match[idx]) { return 0; }
    if (dp[idx] != 0) { return dp[idx]; }
    return dp[idx] = dfs((idx + t.length()) % s.length(), depth + 1) + 1;
}
signed main() {
    cin >> s >> t;
    while (S.length() < s.length() + t.length()) { S += s; }
    fill(match, match + 550000, true);
    rolliha(114514), rolliha(1919), rolliha(810);
    int ans = 0;
    for (int i = 0; i < s.length(); i++) { chmax(ans, dfs(i)); }
    for (int i = 0; i < s.length(); i++) { cerr << dp[i] << endl; }

    cout << ans << endl;
}

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

typedef long long ll;

void max_self(ll &a, ll b) {
    a = max(a, b);
}

int main() {
    int N, W;
    scanf("%d%d", &N, &W);

    vector<ll> dp(W+1);
    // dp[i] - the maximum value obtained by taking items of weight exactly i
    int value, weight;

    for (int item = 0; item < N; ++item) {
        scanf("%d%d", &weight, &value);

        for (int w = W; w >= weight; --w)
            max_self(dp[w], dp[w-weight] + value);
    }

    printf("%lld\n", dp[W]);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int a[41];
int x[]={5,7,5,7,7};
int main(){
    int n;
    string s;
    while(cin>>n,n){
        rep(i,n){
            cin>>s;
            a[i]=s.size();
        }
        int ans=-1;
        rep(i,n){
            int cur=0,sum=0;
            FOR(j,i,n){
                sum+=a[j];
                if(sum>=x[cur]){
                    if(sum==x[cur]){
                        ++cur;sum=0;
                        if(cur==5){
                            ans=i+1;
                            break;
                        }
                    }
                    else break;
                }
                if(ans!=-1) break;
            }
            if(ans!=-1){
                cout<<ans<<endl;
                break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3208
#include <stdio.h>
int main(void){
    
    int n;
    int a;
    int x=0,y=0,z=0;
    scanf("%d",&n);
    for(;~scanf("%d",&a);){
        if(a%4==0){
            z++;
        }else if(a%2==0){
            y++;
        }else{
            z--;
        }
    }
    
    if(y && 0<=z){
        printf("Yes");
    }else if(!y && -1<=z){
        printf("Yes");
    }else{
        printf("No");
    }
}

Measured memory_bytes: 1704
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
int main() {
    int k,s;cin>>k>>s;
    int ans=0;
    for(int i=0;i<=k;++i){
        for(int j=0;j<=k;++j){
            if(s-i-j<=k && s-i-j>=0)ans++;
        }
    }
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int infI=1e9+5;
const long long infL=1e16;
const int MOD=1e9+7;
const int MAX=2e5+5;

#define mp make_pair
#define in &
#define pb push_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ll long long
#define pll pair<ll,ll>
#define vvl vector<vector<ll> >
#define vi vector<int>
#define vvi vector<vector<int> >
#define vl vector<ll>
#define eb emplace_back
#define forn(i,a,b) for(ll i=a;i<b;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define popb pop_back();
#define se second
#define fi first
#define debug(x) cerr<<x<<endl
#define test(t) int t;cin>>t;while(t--)
#define fordebug(x) cerr<<x<<" "

ll power(ll a,ll b){
    if(b==0){
        return 1;
    }
    if(b==1){
        return a;
    }
    ll temp=power(a,b/2);
    temp=(temp*temp)%MOD;
    if(b%2){
        temp=(temp*a)%MOD;
    }
    return temp;
}

//only use if mod is prime
ll mod_inv(ll a,ll mod){
    a%=mod;
    return power(a,mod-2);
}

void extended_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    ll x1,y1;
    extended_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-((a/b)*y1);
    return;
}

//TLE can also occur if vectors are not passed by reference

ll dp[405][405],a[405],cost[405][405];

int main(){
    int n;
    cin>>n;
    forn(i,0,n){
        forn(j,0,n){
            dp[i][j]=infL;
            cost[i][j]=infL;
        }
    }
    forn(i,0,n){
        cin>>a[i];
        dp[i][i]=a[i];
        cost[i][i]=0;
    }
    for(int i=n-2;i>=0;--i){
        forn(j,i+1,n){
            forn(k,i,j){
                if(dp[i][k]+dp[k+1][j]+cost[i][k]+cost[k+1][j]<cost[i][j]){
                    dp[i][j] = dp[i][k]+dp[k+1][j];//size
                    cost[i][j] = cost[i][k]+cost[k+1][j]+dp[i][j];//cost to create this slime between indices i and j
                }
            }
        }
    }
    cout<<cost[0][n-1];
    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define FORI(i,v) for (auto i = v.begin(); i != v.end(); i++)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)
#define YES(b) cout << ((b) ? "YES" : "NO") << endl
#define Yes(b) cout << ((b) ? "Yes" : "No") << endl

const int MAX = 2e5+10;

int N, A[MAX];

void solve() {
    vi l(MAX), r(MAX);
    REP (i, N) {
        l[i+1] = l[i]^A[i];
        r[i+1] = r[i]^A[N-1-i];
    }
    REP (i, N) {
        cout << (l[i] ^ r[N-1-i]) << endl;
    }
}

int main() {
    cout << fixed << setprecision(15);
    cin >> N;
    REP (i, N) cin >> A[i];
    solve();
}

Measured memory_bytes: 7204
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, n) for (int i = (n-1); i >= 0; i--)
#define rea(i, a, b) for (int i = (a); i < (b); i++)
#define reab(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const ll MOD = 1000000007;
const ll INF = 100000000000000000;
/* END OF TEMPLATE */

vi p;

bool ok(ll x, ll y){
    rea(i, x, y){
        if(p[i] && p[i+1]) return 0;
    }
    return 1;
}
bool ok2(ll x, ll y){
    rea(i, x-1, y){
        if(!p[i] && !p[i+1] && !p[i+2]) return 1;
    }
    return 0;
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    ll n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    a--; b--; c--; d--;
    string s;
    cin >> s;
    int szs = SZ(s);
    bool ans;
    rep(i, szs){
        if(s[i] == '.') p.emplace_back(0);
        else p.emplace_back(1);
    }
    if(d < c){
        if(ok(a, c) && ok(b, d) && ok2(b, d)) ans = 1;
        else ans = 0;
    }else{
        if(ok(a, c) && ok(b, d)) ans = 1;
        else ans = 0;
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 1608
s = input()
temp = [int(comp) for comp in s.split()]
[a, b, c, k] = temp
val = [1, 0, -1]
ans = 0
for i in range(3):
    memo = min(temp[i], k)
    ans += val[i] * memo
    k -= memo
    if (k <= 0):
        break
print(ans)

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

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

  vector<int> p(M);
  vector<string> S(M);

  for(int i = 0; i < M; i++){

      cin >> p.at(i) >> S.at(i);
  }

  vector<int> AC(N+1,0);
  vector<int> WA(N+1,0);

  for(int i = 0; i < M; i++){
       if(S.at(i) == "WA" && AC[p.at(i)] == 0){
        WA[p.at(i)] ++;
      }

      if(S.at(i) == "AC"){
          AC[p.at(i)] ++;
      }
  }
  
    for(int i = 0; i < N+1; i++){
        if(AC.at(i) == 0) WA.at(i) = 0;
    }


  int Pen = 0;
  int Cor = 0;

  for(int i = 0; i < N+1; i++){
            if(AC.at(i) > 0) Cor++;
          Pen += WA.at(i);
  }

cout << Cor << " " << Pen << endl;

}


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

#define debug(x) cout << '>' << #x << ':' << x << endl;
#define loop0(i,n) for(int i=0; i<(n); i++)
#define loop1(i,n) for(int i=1; i<=(n); i++)
#define fori(a,b,i) for(int i=(a); i<=(b); i++)
#define ford(a,b,i) for(int i=(a); i>=(b); i--)
#define fast_io ios_base::sync_with_stdio(false), cin.tie(NULL)
#define ign cin.ignore(numeric_limits<streamsize>::max(),'\n')

#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define endl "\n"
#define fir first
#define sec second
#define pb push_back
#define mp make_pair

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MII;
typedef map<int,int> MCI;
typedef unordered_map<int,int> UMII;
typedef unordered_map<char,int> UMCI;
typedef set<int> SI;
typedef unordered_set<int> USI;
typedef long long int llint;

// Display Map
//~for (auto const& pair: m) {
//~std::cout << "{" << pair.first << ": " << pair.second << "}\n";
//~}

// Extract word(w) from sentence(s)
//~stringstream str(s);
//~string w;
//~while(str >> w){
//~// w is your word
//~}

//Memset Syntax
// memset(array, value,sizeof(array)) val is 0,-1 or bool only

// To get accurate precision
//~cout.precision(20);

// Concatinate Vectors
//~

int main() {
    fast_io;
	int t;
	cin >> t;
	int a=0,b=0,c=0,d=0;
	while(t--){
		string s;
		cin >> s;
		if(s == "AC") a++;
		if(s == "WA") b++;
		if(s == "TLE") c++;
		if(s == "RE") d++;
	}
	
	cout << "AC x " << a << endl;
	cout << "WA x " << b << endl;
	cout << "TLE x " << c << endl;
	cout << "RE x " << d << endl;
}


Measured memory_bytes: 3656
function Main(input) {
    input = input.split("\n");
    n = input[0].split("");
    
    total = 0;

    
    for (let i = 0; i < n.length; i++) {
        num = parseInt(n[i], 10);
        total += num;        
    }



    if (total % 9 == 0) {

        console.log("Yes");
        
    } else if(total % 9 != 0){
        console.log("No");
    }



}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 34576
#include <iostream>

using namespace std;

int main()
{
    int A,B,conf,max;
    ios::sync_with_stdio(false);
    cin >> A >> B;
    if(A >= B)
    {
        max = A;
    }
    else
    {
        max = B;
    }
    
    for (int i = 1 ; i<max+1 ; i++)
    {
        if((A*B*i)%2 == 0)
        {
            conf = 0;
        }
        else
        {
            cout << "Yes" << endl;
            conf = 1;
            break;
        }
        
    }
    if(conf == 0)
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			int n = scan.nextInt();
			int[] num = new int[n];
			for(int i = 0;i < n;i++){
				num[i] = scan.nextInt();
			}
			Arrays.sort(num);
			int count = 0;
			System.out.println(1);
			for(int i = 2;i <= num[0];i++){
				count = 0;
				for(int j = 0;j < n;j++){
					if(num[j]%i != 0){
						break;
					}
					count++;
					if(count == n){
						System.out.println(i);
					}
				}
			}
		}
	}
}

Measured memory_bytes: 19388
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <functional>
using namespace std;

int main() {
	string O, E, S;
	cin >> O >> E;
	for (int i = 0; i < E.size(); i++) {
		S += O[i];
		S += E[i];
	}
	if (O.size() > E.size()) S += O.back();
	cout << S << endl;
	return 0;
}

Measured memory_bytes: 256
n = gets.to_s.to_i

memo = Array.new(n + 1).map{Array.new(n + 1, nil)}

ans = 0
1.upto(n) do |i|
  1.upto(n) do |j|
    t = memo[i][j] ||= i.gcd(j)
    1.upto(n) do |k|
      ans += memo[t][k] ||= t.gcd(k)
    end
  end
end
 
puts ans

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

int main(){
  int n;
  cin >> n;
  vector<int> x(4);
  rep(i, n){
    string s;
    cin >> s;
    if(s == "AC") x.at(0)++;
    else if(s == "WA") x.at(1)++;
    else if(s == "TLE") x.at(2)++;
    else if(s == "RE") x.at(3)++;
  } 
  cout << "AC x " << x.at(0) << endl;
  cout << "WA x " << x.at(1) << endl;
  cout << "TLE x " << x.at(2) << endl;
  cout << "RE x " << x.at(3) << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <cstdlib>
#include <deque>
#include <stack>

using namespace std;
const long long P = 1000000007;

int main() {
  long long n,m;
  cin >> n >> m;
  long long ans;
  if(n == 1 && m == 1) {
    ans = 1;
  }else if(n == 1) {
    ans = m-2;
  }else if(m == 1) {
    ans = n-2;
  }else {
    ans = (n-2)*(m-2);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef int q;
typedef double w;
typedef string s;
typedef long long ll;
int main(){
    q r; w c=M_PI,k; cin>>r;
    k=c*pow(r,2);
    cout<<k/c;
return 0;}
// HAY MY NAME IS MOHAMMED FNNOUN MOHD

Measured memory_bytes: 256
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
inline void read(int &x)
{
	x=0;
	int p=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
	while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^'0');c=getchar();}
	x*=p;
}
char s[100];
char tag[110]={" AKIHABARA"};
bool vis[110];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%s",s+1);
	int len=strlen(s+1);
	if(len>9)return puts("NO"),0;
	else
	{
		if(!strcmp(s+1,"KIHBR"))return puts("YES"),0;
		if(!strcmp(s+1,"AKIHBR"))return puts("YES"),0;
		if(!strcmp(s+1,"AKIHABR"))return puts("YES"),0;
		if(!strcmp(s+1,"AKIHABAR"))return puts("YES"),0;
		if(!strcmp(s+1,"AKIHABARA"))return puts("YES"),0;
		if(!strcmp(s+1,"AKIHBAR"))return puts("YES"),0;
		if(!strcmp(s+1,"AKIHBARA"))return puts("YES"),0;
		if(!strcmp(s+1,"AKIHBRA"))return puts("YES"),0;
		if(!strcmp(s+1,"AKIHABRA"))return puts("YES"),0;
		if(!strcmp(s+1,"KIHABR"))return puts("YES"),0;
		if(!strcmp(s+1,"KIHABAR"))return puts("YES"),0;
		if(!strcmp(s+1,"KIHABARA"))return puts("YES"),0;
		if(!strcmp(s+1,"KIHABRA"))return puts("YES"),0;
		if(!strcmp(s+1,"KIHBAR"))return puts("YES"),0;
		if(!strcmp(s+1,"KIHBARA"))return puts("YES"),0;
		if(!strcmp(s+1,"KIHBRA"))return puts("YES"),0;
		puts("NO");
	}
	return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static final int MOD = (int) (1e9 + 7);

    public void solve(InputReader in, PrintWriter out) {
        int n = in.nextInt(), k = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a);
        long sum = 0;
        for (int i = 0; i < n - k; ++i) {
            sum += a[i];
        }
        out.println(sum);
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        new Main().solve(in, out);
        out.flush();
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}

Measured memory_bytes: 58016
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>
#include<string>

using namespace std;
using ll = long long;

int main(){ 
        string str;
        cin >> str;
        if(str[5]=='1') cout << "TBD";
        else if(str[6]>='5') cout << "TBD";
        else cout << "Heisei";
        return 0;
}

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

int main(){

    // omajinai
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    // omajinai

    ll n,m;
    cin >> n >> m;

    ll ans = min(n,m/2);

    if(n < m / 2){
        ans += (m - 2 * n) / 4;
    }

    cout << ans << endl;
}

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

struct point {
	double x;
	double y;
	point() {
		x = 0;
		y = 0;
	}
	point(double a, double b) {
		x = a;
		y = b;
	}
};

void Koch(int n, point A, point B) {
	if (n == 0) {
		cout << A.x << " " << A.y << endl;
		return;
	}
	n--;
	point C, D, E;
	double temp1 = 1.0 / 3.0, temp2 = 2.0 / 3.0;
	C.x = temp2 * A.x + temp1 * B.x;
	C.y = temp2 * A.y + temp1 * B.y;
	E.x = temp1 * A.x + temp2 * B.x;
	E.y = temp1 * A.y + temp2 * B.y;
	// D has six special situation
	if (A.y - B.y < 0.000001 && A.y - B.y > -0.000001) {
		D.x = 1 / 2.0 * (A.x + B.x);
		D.y = sqrt(3) / 6.0 * (B.x - A.x) + A.y;
	} else if (B.y > A.y) {
		D.x = min(A.x, B.x);
		if (A.x < B.x) {
			D.y = temp1 * A.y + temp2 * B.y;
		} else {
			D.y = temp2 * A.y + temp1 * B.y;
		}
	} else {
		D.x = max(A.x, B.x);
		if (A.x > B.x) {
			D.y = temp1 * A.y + temp2 * B.y;
		} else {
			D.y = temp2 * A.y + temp1 * B.y;
		}
	}

	Koch(n, A, C);
	Koch(n, C, D);
	Koch(n, D, E);
	Koch(n, E, B);
}

int main(void) {
	cout << fixed << setprecision(8);
	int n;
	cin >> n;
	point start(0, 0), end(100, 0);
	Koch(n, start, end);
	cout << end.x << " " << end.y << endl;
}


Measured memory_bytes: 3280
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    ans = 0
    Ai = [(a, i + 1) for i, a in enumerate(A)]
    Ai.sort(key=lambda x: x[0])
    st = SegmentTree(n=N + 2, f=lambda x, y: x + y)
    st.set_val(0, 1)
    st.set_val(N + 1, 1)
    for a, i in Ai:
        lc = st.query(0, i)
        l = st.bisect_left(lambda x: x < lc)
        r = st.bisect_left(lambda x: x < lc + 1)
        ans += a * (i - l) * (r - i)
        st.set_val(i, 1)
    print(ans)

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i << 1], d[i << 1 | 1])

    def get_val(self, index):
        return self.__d[index + self.__n]

    def set_val(self, index, new_value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == new_value: return
        d[i], i = new_value, i >> 1
        while i:
            d[i], i = f(d[i << 1], d[i << 1 | 1]), i >> 1

    def modify(self, index, value):
        self.set_val(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l + 1
            if r & 1: ans, r = f(d[r - 1], ans), r - 1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, j, n, f, d, v = self.__n, self.__n + self.__n, self.__n, self.__f, self.__d, self.__e()
        while i < j:
            if i & 1:
                nv = f(v, d[i])
                if not func(nv): break
                v, i = nv, i + 1
            i, j = i >> 1, j >> 1
        while i < n:
            nv = f(v, d[i << 1])
            if func(nv): v, i = nv, i << 1 | 1
            else: i = i << 1
        return i - n

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)


Measured memory_bytes: 136444
//https://atcoder.jp/contests/abc094/submissions/8948179
//参考にさせて頂いたコード

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;


const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()


int main(){
    int N;
    cin>>N;
    vector<int>X(N);
    rep(i,N)cin>>X[i];
    //例外処理は中央値に設定されている値を消している時
    //それ以外はN/2-1で対応？
    //そもそも全部
    vector<int> Cop=X;
    sort(X.begin(),X.end());
    int MA=X[N/2-1];
    int MB=X[N/2];
    rep(i,N){
        if(Cop[i]<=MA)cout<<MB<<endl;//ソート前と比較して、小さいかったらそれは中央値の時に左側が縮まるので、MB
        else cout<<MA<<endl;
    }
    return 0;
}

//a=97,z=122

Measured memory_bytes: 3712
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
namespace Dango
{
	const int MAXN=200005,MOD=1000000007;
	vector<int> cir,node;
	int n;
	int head[MAXN],to[MAXN<<1],nxt[MAXN<<1];
	int tot;
	int fa[MAXN],size[MAXN];
	long long ans;
	bool vis[MAXN],on_cir[MAXN];
	int read()
	{
		int x=0,f=0;
		char ch=getchar();
		while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
		while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
		return f?-x:x;
	}
	void add(int u,int v)
	{
		static int cnt;
		cnt++;
		to[cnt]=v;
		nxt[cnt]=head[u];
		head[u]=cnt;
	}
	void dfs(int u)
	{
		node.push_back(u);
		vis[u]=true;
		tot+=2;
		for(int i=head[u];i;i=nxt[i])
		{
			tot--;
			int v=to[i];
			if(vis[v])continue;
			dfs(v);
		}
	}
	void findcircle(int u,int pre)
	{
		static bool vis[MAXN],flag;
		static int s,t;
		vis[u]=true;
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(v==pre)continue;
			if(vis[v])
			{
				flag=true;
				s=u;t=v;
				break;
			}
			findcircle(v,u);
			if(flag)break;
		}
		if(flag){cir.push_back(u);on_cir[u]=true;}
		if(u==t)flag=false;
	}
	long long pow_(long long a,long long b)
	{
		long long res=1;
		while(b)
		{
			if(b&1)res=res*a%MOD;
			a=a*a%MOD;
			b>>=1;
		}
		return res;
	}
	long long dfs_(int u)
	{
		if(size[u])return 1;
		long long res=1;
		size[u]=1;
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(v>=fa[u])continue;
			res=res*dfs_(v)%MOD;
			size[u]+=size[v];
		}
		res=res*pow_(size[u],MOD-2)%MOD;
		return res;
	}
	int calc()
	{
		long long res=1;
		for(int i=0;i<node.size();i++)
			size[node[i]]=0;
		for(int i=0;i<node.size();i++)
		{
			int x=node[i];
			if(size[x])continue;
			res=res*dfs_(x)%MOD;
		}
		return res;
	}
	void dfs_for_fa(int u)
	{
		static int vis[MAXN];
		vis[u]=true;
		for(int i=head[u];i;i=nxt[i])
		{
			int v=to[i];
			if(vis[v]||on_cir[v])continue;
			fa[v]=u;
			dfs_for_fa(v);
		}
	}
	void solve(int u)
	{
		long long res=0;
		cir.clear();
		node.clear();
		dfs(u);
		if(tot){ans=0;return;}
		findcircle(u,0);
		for(int i=0;i<cir.size();i++)
			dfs_for_fa(cir[i]);
		cir.push_back(cir[0]);
		for(int i=1;i<cir.size();i++)
			fa[cir[i]]=cir[i-1];
		res=(res+calc())%MOD;
		for(int i=0;i<cir.size()-1;i++)
			fa[cir[i]]=cir[i+1];
		res=(res+calc())%MOD;
		ans=ans*res%MOD;
	}
	int work()
	{
		n=read();
		n<<=1;
		for(int i=1;i<=n;i++)
		{
			int u=read(),v=read()+n/2;
			add(u,v);add(v,u);
		}
		ans=1;
		for(int i=1;i<=n&&ans;i++)
		{
			ans=ans*i%MOD;
			if(!vis[i])solve(i);
		}
		printf("%lld",ans);
		return 0;
	}
}
int main()
{
	return Dango::work();
}

Measured memory_bytes: 10612
#include<map>
#include<vector>
#include<cstdio>
using namespace std;
int n,N,i,j,k,c,m;
int main(){
	scanf("%d",&N);
	vector<map<int,int>>dist(N);
	vector<bool>used(N);
	vector<int>cost(N);
	for(;n<N;n++){
		cost[n]=1e9;
		for(scanf("%d%d",&i,&k);k--;dist[i][j]=c)scanf("%d%d",&j,&c);
	}
	for(cost[0]=0;;){
		m=1e9;
		for(i=0;i<N;i++)if(!used[i]&&m>cost[i])m=cost[i];
		if(m==1e9)break;
		for(j=0;j<N;j++)if(m==cost[j]){
			map<int,int>::iterator it=dist[j].begin();
			for(used[j]=1;it!=dist[j].end();it++)if(cost[it->first]>it->second+cost[j])cost[it->first]=it->second+cost[j];
		}
	}
	for(i=0;i<n;i++)printf("%d %d\n",i,cost[i]);
}



Measured memory_bytes: 26132
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var rdr = bufio.NewReader(os.Stdin)

func myReadLine() string {
	buf := make([]byte, 0, bufio.MaxScanTokenSize)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func calc(a int, b int, h int) int {
	return (a + b) * h / 2
}

func main() {
	a, _ := strconv.Atoi(myReadLine())
	b, _ := strconv.Atoi(myReadLine())
	h, _ := strconv.Atoi(myReadLine())
	fmt.Printf("%d\n", calc(a, b, h))
}


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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    int t=0,h=0;
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        string st,sh;
        cin >> st >> sh;
        if(st>sh) t+=3;
        else if(st<sh) h+=3;
        else{
            t++; h++;
        }
    }

    cout << t << " " << h << endl;
    
    return 0;
}


Measured memory_bytes: 3144
import java.util.*;

class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      long a = sc.nextInt();
      long b = sc.nextInt();
      long c = sc.nextInt();
      long d = sc.nextInt();
      
      long currentMax = -9223372036854775807L;

      if (a*c > currentMax) {
        currentMax = a*c;
      }

      if (a*d > currentMax) {
        currentMax = a*d;
      }

      if (b*c > currentMax) {
        currentMax = b*c;
      }

      if (b*d > currentMax) {
        currentMax = b*d;
      }

      System.out.println(currentMax);
    }
}

Measured memory_bytes: 35700
#include <stdio.h>
int main(void){

    double r;
    double are,circ,M_PI;
    
    M_PI=3.141592653589;
    
    scanf("%lf", &r);
    
    are=r*r*M_PI;
    circ=2*r*M_PI;
    
    printf("%f %f\n", are,circ);
    return 0;
    
}




Measured memory_bytes: 2144
#include <bits/extc++.h>
#define lowbit(x) ((x) & -(x))
using namespace std;

int n;
long long x, y, a;

int main() {
	scanf("%d%lld%lld", &n, &x, &y);
	for (int i = 2; i < n; ++i) {
		long long b; scanf("%lld", &b);
		a ^= b;
	}
	if (x + y < a || x + y - a & 1)
		puts("-1");
	else {
		auto t = x + y - a >> 1;
		if (t > x || t & a)
			puts("-1");
		else {
			for (int i = 62; i >= 0; --i)
				if (a >> i & 1 && (t | 1ll << i) <= x)
					t |= 1ll << i;
			printf("%lld\n", t ? x - t : -1);
		}
	}
	return 0;
}



Measured memory_bytes: 3732
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
#include <queue>

using namespace std;

bool comp(int n1, int n2){
	return n1>n2;
}

int main () {
	int A, B, C, X, Y;
	cin >> A >> B >> C>> X >> Y;
	int minXY = min(X,Y);
	int money=0;
	if (C>(A+B)/2){
		money+= (A+B)*minXY;
	}
	else money+=C*2*minXY;
	if(X>Y){
		if (2*C<A) money+=(X-Y)*C*2;
		else money+=(X-Y)*A;	
	}
	else{
		if (2*C<B) money+=(Y-X)*C*2;
		else money+=(Y-X)*B;	
	}
	cout<< money << endl;
	return 0;
}

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

int main()
{
    int a,b,i,j;
    while(cin>>a>>b)
    {
        string s[1001];
        int c[1001];
        for(i=0;i<a;i++)
            cin>>s[i];

        sort(s+0,s+a);

        for(j=0;j<a;j++)
            cout<<s[j];
            cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3668