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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair<int,int> P;
//typedef pair<int,P> PP;

//-----------------------------------------------------------------------------

#define INIT INF
typedef int Weight;
typedef pair<P,P> PP;
typedef vector< vector< vector<Weight> > > DIST;

// ^0 >1 v2 <3

int w,h;
int fld[30][30];
int change_dir[4];
int convert_x[]={0,1,0,-1},convert_y[]={-1,0,1,0};

bool check(int x,int y) {
	if(x<0||x>=w||y<0||y>=h) return false;
	return true;
}

void dijkstra(const int fld[30][30],DIST &dist) {
	dist.assign(h,vector< vector<Weight> >(w,vector<Weight>(4,INIT)));
	dist[0][0][1]=0;
	priority_queue< PP,vector<PP>,greater<PP> > Q;
	Q.push(PP(P(0,1),P(0,0)));
	while(!Q.empty()) {
		PP p=Q.top();Q.pop();
		int cost=p.fi.fi,from_dir=p.fi.se,x=p.se.fi,y=p.se.se;
		int cur_dir=(from_dir+fld[y][x])%4;
		if(dist[y][x][from_dir]<cost) continue;
		REP(i,4) {
			int nx=x+convert_x[i],ny=y+convert_y[i];
			if(!check(nx,ny)) continue;
			if(i==cur_dir&&fld[y][x]!=4) {
				if(dist[ny][nx][i]<=cost) continue;
				dist[ny][nx][i]=cost;
				Q.push(PP(P(dist[ny][nx][i],i),P(nx,ny)));
			}
			else {
				int new_cost=change_dir[(i-from_dir+4)%4];
				if(dist[ny][nx][i]<=cost+new_cost) continue;
				dist[ny][nx][i]=cost+new_cost;
				Q.push(PP(P(dist[ny][nx][i],i),P(nx,ny)));
			}
		}
	}
}

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

	while(true) {
	cin>>w>>h;
	if(w==0&&h==0) break;
	REP(i,h) REP(j,w) cin>>fld[i][j];
	REP(i,4) cin>>change_dir[i];
	DIST dist(h,vector< vector<Weight> >(w,vector<Weight>(4)));
	dijkstra(fld,dist);
	int ans=INF;
	REP(i,4) ans=min(ans,dist[h-1][w-1][i]);
	cout<<ans<<endl;
	}

	return 0;
}



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

int p[1111];
int main() {
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> p[i];
    nth_element(p, p + k, p + n);
    partial_sum(p, p + k, p);
    cout << p[k - 1] << endl;
    return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll suma;
ll sumb;
const ll maxn=100000+100;
ll maxx[2];
int nums[maxn];
struct nnode
{
	ll a,b;

}nnod[maxn];
struct node
{
	ll num;
	ll gs;
	
 } nod[200000+100];
 bool cmp(struct node a,struct node b)
 {
 	return a.num<b.num;
 }
 ll my_min(ll a,ll b)
 {
 	return a<b ?a:b;
 }
 ll my_max(ll a,ll b)
 {
 	return a>b?a:b;
 }
 void swap(int &a,int &b)
 {
 	int z=a;
 	a=b;
 	b=z;
 }
int main()
{
	int n;
	scanf("%d",&n);
	maxx[0]=maxx[1]=-1; 
	suma=sumb=0;
	for(int i=0;i<n;i++)
	{
		scanf("%lld %lld",&nnod[i].a,&nnod[i].b);
		suma+=nnod[i].a;
		sumb+=nnod[i].b;
		if(nnod[i].a>nnod[i].b)
			swap(nnod[i].a,nnod[i].b);
		for(int k=0;k<2;k++)
		{
		 	int a=nnod[i].a;
		 	if(a>maxx[k])
		 	{
			 	if(k==0)
		 			maxx[k+1]=maxx[k];
		 		maxx[k]=a;
		 		break;
		 	}
		} 
		nod[i*2].gs=i;
		nod[i*2].num=nnod[i].a;
		nod[i*2+1].gs=i;
		nod[i*2+1].num=nnod[i].b;
	}
	sort(nod,nod+2*n,cmp);
	suma=my_min(suma,sumb);
	sumb=0;
	bool flag=false;
	for(int i=0;i<n;i++)
	{
		sumb+=nod[i].num;
		nums[nod[i].gs]++;
		if(nums[nod[i].gs]==2) 
			flag=true;
	}
	if(flag==true)
		printf("%lld\n",sumb);
	else 
	{
		ll sumc=suma;
		for(int i=0;i<n;i++)
		{
			ll z=sumb+nnod[i].b;
			if(nnod[i].a==maxx[0])
				z-=maxx[1];
			else
				z-=maxx[0];
			sumc=my_min(sumc,z);
		} 
		printf("%lld\n",sumc); 
	}
	return 0;
 } 

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

table = [0] * 10001

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            k = (x * x) + (y * y) + (z * z) + (x * y) + (y * z) + (z * x)
            if k < 10001:
                table[k] += 1

for i in range(1, n + 1):
    print(table[i])


Measured memory_bytes: 74224
#include<bits/stdc++.h>
#define LL long long
#define R register int
#define G if(++ip==ie)if(fread(ip=buf,1,SZ,stdin))
#define F(S) if(freopen(S".in","r",stdin))//;if(freopen(S".out","w",stdout))
using namespace std;
const int SZ=1<<19,N=1e5+9,M=2*N;
char buf[SZ],*ie=buf+SZ,*ip=ie-1;
inline int in(){
	G;while(*ip<'-')G;
	R x=*ip&15;G;
	while(*ip>'-'){x*=10;x+=*ip&15;G;}
	return x;
}
int he[N],ne[M],to[M],f[N],a[N],b[N];
int Getf(R x){
	return x==f[x]?x:f[x]=Getf(f[x]);
}
void Dfs(R x,R op){
	//printf("x=%d op=%d\n",x,op);
	a[x]=op;
	for(R y,i=he[x];i;i=ne[i])
		if((y=to[i])!=f[x])
			f[y]=x,Dfs(y,-op),a[x]+=a[y];
}
int main(){
	R n=in(),m=in(),rt=1,re=1,p=0;
	for(R i=1;i<=n;++i)f[i]=i;
	for(R p=0,i=1;i<=m;++i){
		R x=in(),y=in();
		if(Getf(x)!=Getf(y))f[f[x]]=f[y];
		else{rt=x,re=y;continue;}
		ne[++p]=he[x];to[he[x]=p]=y;
		ne[++p]=he[y];to[he[y]=p]=x;
	}
	f[rt]=0;Dfs(rt,1);
	//for(R i=1;i<=n;++i)printf("%d ",a[i]);puts("");
	//for(R i=1;i<=n;++i)printf("%d ",f[i]);puts("");
	if(n==m){
		for(R x=re;x;x=f[x])b[++p]=a[x];
		if(p&1){
			//puts("Case1");
			if(a[rt]&1)return puts("-1"),0;
			for(R x=re;x;x=f[x])a[x]-=a[rt]>>1;
		}
		else{
			if(a[rt])return puts("-1"),0;
			sort(b+1,b+p+1);a[rt]=b[p>>1];
			for(R x=re;x!=rt;x=f[x])a[x]-=a[rt];
		}
	}
	else if(a[rt])return puts("-1"),0;
	LL ans=0;
	for(R i=1;i<=n;++i)ans+=abs(a[i]);
	return cout<<ans<<endl,0;
}


Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  REP(i, N) cin >> A[i];
  sort(ALL(A));
  
  ll ans = 0;
  int cnt = 0;
  REP(i,N){
    if((cnt<=N-2&&A.at(i)<0)||i==0){
      ans+=-A.at(i);
      cnt++;
    }else{
      ans+=A.at(i);
    }
  }
  cout << ans << endl;

  int x = A.at(0);
  FOR(i,cnt,N-1){
    cout << x << " " << A.at(i) << endl;
    x=x-A.at(i);
  }
  cout << A.at(N-1) << " " << x << endl;
  x = A.at(N-1)-x;
  FOR(i,1,cnt){
    cout << x << " " << A.at(i) << endl;
    x=x-A.at(i);
  }
}

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

int main() {
    int N;
    long A, B;
    cin>>N>>A>>B;
    long X[N];
    for(int i=0;i<N;++i){
        cin>>X[i];
    }
    long hiro[N];
    hiro[0] = 0;
    for(int i=1;i<N;++i){
        if(hiro[i-1] + A*(X[i]-X[i-1]) < hiro[i-1] + B){
            hiro[i] = hiro[i-1] + A*(X[i] - X[i-1]);
        }
        else {
            hiro[i] = hiro[i-1] + B;
        }
    }
    cout<<hiro[N-1]<<endl;
}


Measured memory_bytes: 1792
w, h, x, y, r = map(int, input().split())

if ( x - r ) < 0:
  print("No")
elif ( y - r) < 0:
  print("No")
elif w < ( x + r ):
  print("No")
elif h <  ( y + r ):
  print("No")
else:
  print("Yes")


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

typedef pair<int, int> ii;
typedef pair<string, ii> psii;
typedef vector<psii> vpsii;

bool sortRank(psii a, psii b) {
	if (a.first == b.first)
		return a.second.first > b.second.first;
	return a.first < b.first;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int i, n, p;
	string city;
	vpsii rank;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> city >> p;
		rank.push_back(psii(city, ii(p, i + 1)));
	}
	sort(rank.begin(), rank.end(), sortRank);
	for (i = 0; i < rank.size(); i++)
		cout << rank[i].second.second << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

using LL = long long;

int main()
{
	LL n, m;
	cin >> n >> m;

	LL sum = 0;

	LL a = 0;

	for (int i = 1; i <= m; ++i)
	{
		cin >> a;
		sum += a;
	}

	if (sum <= n)
	{
		cout << n - sum << endl;
	}
	else
	{
		cout << -1 << endl;
	}

	return 0;
}

Measured memory_bytes: 3636
import math

def main():
	N = int(input())
	A = [int(a) for a in input().split(" ")]
	gcd1 = []
	gcd2 = []
	for i in range(len(A)):
		if i == 0:
			gcd1.append(A[0])
			gcd2.append(A[-1])
		else:
			gcd1.append(math.gcd(A[i], gcd1[-1]))
			gcd2.insert(0, math.gcd(A[-i-1], gcd2[0]))

	gcds = []
	for i in range(N):
		if i == 0:
			gcds.append(gcd2[1])
		elif i == N - 1:
			gcds.append(gcd1[-2])
		else:
			gcds.append(math.gcd(gcd1[i-1], gcd2[-N+i+1]))
	print(max(gcds))

main()


Measured memory_bytes: 25096
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int (i)=(a);(i)<(int)(b);(i)++)
#define RREP(i,a,b) for(int (i)=(a);(i)>=(int)(b);(i)--)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;

int n;
ll a[100010], sum[100010];

ll func(int x){
    memset(sum, 0, sizeof(sum));

    ll cnt = 0;
    REP(i,0,n){
        ll t = sum[i] + a[i];
        if (i % 2 == x && t <= 0){
            cnt += (1 - t);
            sum[i + 1] = 1;
        }else if (i % 2 != x && t >= 0){
            cnt += (t + 1);
            sum[i + 1] = -1;
        }else{
            sum[i + 1] = t;
        }
    }

    return cnt;
}


int main(){
    cin >> n;
    REP(i,0,n){
        cin >> a[i];
    }

    cout << min(func(0), func(1)) << endl;    
    
    return 0;
}

Measured memory_bytes: 1792
n, m = map(int, input().split())
likes = [0] *  m

for i in range(n):
    k, *a = map(int, input().split())
    for j in a:
        likes[j-1] += 1

count = 0
for i in likes:
    if i == n:
        count += 1

print(count)

Measured memory_bytes: 3060
#include<iostream>
#include<cmath>
#include<numeric>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define ll long long
#define INF 2147483647
using namespace std;
using Graph=vector<vector<int>>;

int main(){
  int n; cin>>n; int a[n];
  ll s=0;
  rep(i,n){
    cin>>a[i];
    s=s^a[i];
  }
  rep(i,n){
    ll t=s^a[i];
    cout<< t <<" ";
  }
}


Measured memory_bytes: 4364
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
using ll = long long int;

int a, p;
int main(void) {
	cin >> a >> p;
	int ret = 0;

	ret = (a * 3 + p) / 2;
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <cmath>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;

int main(int argc, char const* argv[])
{
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;
  a *= 100;
  b *= 100;
  int all = 0;
  int de = 0;
  for(int i = 0; i * a <= f; i++){
    for(int j = 0; j * b <= f - i * a; j++){
      int target = min(f - i * a - j * b, (i * a + j * b) * e / 100);
      if(target == 0)continue;
      int tmp = 0;
      for(int k = 0; k * c <= target; k++){
        tmp = max(tmp, k * c + d * int((target - k * c) / d));
      }
      if(tmp == 0)continue;
      if(all == 0 || (double(de)/double(all) < double(tmp)/double(tmp + i * a + j * b))){
        all = tmp + i * a + j * b;
        de = tmp;
      }
    }
  }
  if(all == 0)all = a;
  cout << all << " " << de << endl;
	return 0;
}


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

using namespace std;


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, y;
  cin >> n >> y;
  for (int a = 0; a <= n; ++a) {
    for (int b = 0; b <= n; ++b) {
      int c = n-a-b;
      if (c<0) continue;
      if (a*10000+b*5000+c*1000==y) {
        cout << a << " " << b << " " << c << endl;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
  int N;
  cin >> N;
  int ans = 0;
  int preH = 0;
  for (int i = 0; i < N; i++) {
    int H;
    cin >> H;
    if (preH <= H) {
      ans++;
    }
    preH = max(preH, H);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
// copy of https://atcoder.jp/contests/abc132/submissions/6970968 to see what is wrong with my code
#include <iostream>
using namespace std;

long long n, k, M=1e9+7, c[2005][2005];
int main() {
	cin >> n >> k;
	int i, j;
	for(i=0; i<=n; i++) {
		c[i][0] = 1;
		for(j=1; j<=i; j++) c[i][j] = (c[i-1][j-1] + c[i-1][j]) % M;
	}
	for(i=1; i<=k; i++) cout << c[n-k+1][i] * c[k-1][i-1] % M << endl;
	return 0;
}


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

int main(){
	auto read_string 	=	[](){ string s; cin >> s; return s; };
	auto read_int       =   [](){ int tmp; cin >> tmp; return tmp; };
	auto read_char      =   [](){ char c; cin >> c; return c; };
	auto str_repeat	 	=	[](string a,int count){	string res = ""; for(size_t i = 0 ; i < count ; i++) res += a; return res;	};
	auto to_lower_case 	= 	[](string s){ string res=""; for(size_t i = 0 ; i < s.size() ; i++) res += tolower(s[i]); return res; };
	auto to_upper_case 	= 	[](string s){ string res=""; for(size_t i = 0 ; i < s.size() ; i++) res += toupper(s[i]); return res; };
	auto read_vec_int   =   [](int count){ vector<int> tmp(count); for(size_t i = 0 ; i < count ; i++) cin >> tmp[i]; return tmp; };
	auto title_case     =   [](string s) { string ret = ""; ret+=toupper(s[0]); ret += s.substr(1); return ret; };

	int a = read_int();
	int b = read_int();
	int s = a * b;
	int v = 1 * b;
	int h = a * 1;
	int ans = s - ((v+h)-1);
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()
n,m=MI()
lis=[]
for i in range(m):
    lis.append(LI())
lis.sort(key=lambda x:x[1])
#print(lis)
bri=0
count=0
for i in range(m):
    if bri<=lis[i][0]:
        bri=lis[i][1]
        count+=1
        
print(count)

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

int read(){
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9') f|=c=='-',c=getchar();
    while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
    return f?-x:x;
}

int main(){
    char str[100];
    scanf("%s",str+1);
    if(str[1]=='S') puts("Cloudy");
    else if(str[1]=='C') puts("Rainy");
    else puts("Sunny");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int h[500001],w[500001],o,q[500001],f[500001],c[500001],v[500001],qw,wq,a,b,qq=1,ww=1,ans=0;
int get(int y)
{
    if(y==f[y]) return y ; 
    return f[y]=get(f[y]);
}
void dfs(int n, int m)
{
    c[n]=m;
    for (int i=h[n]; i; i=w[i])
    {
        if (q[i]!=f[n])
        {
            f[q[i]]=n;
            dfs(q[i], -m);
            c[n] += c[q[i]];
        }
    }
}
int main()
{
    for (int i = 1; i <= 500000; ++i)
    {
        f[i] = i;
    }
    cin>>a>>b;
    for (int i = 1; i <= b; ++i)
    {
        cin>>qw>>wq;
        if (get(qw) != get(wq))
        {
            f[f[qw]] = f[wq];
        }
        else
        {
            qq = qw;
             ww = wq;
            continue;
        }
        o++;
        w[o] = h[qw];
        q[o] = wq;
        h[qw]=o;
        o++;
        w[o] = h[wq];
        q[o] = qw;
        h[wq]=o;
    }
    f[qq]=0;
    dfs(qq,1);
    if(a==b)
    {
        long long u=0;
        for(int i=ww;i;i=f[i])
        {
            u++;
            v[u]=c[i];
        }
        if(u%2)
        {
            if((c[qq]%2))
            {
                cout<<"-1";
                return 0;
            }
            for (int i = ww; i; i = f[i])
            {
                c[i] -= c[qq] / 2;
            }
        }
        else
        {
            if (c[qq])
            {
                cout<<"-1";
                return 0;
            }
            sort(v + 1, v + u + 1);
            for (int i = ww; i; i = f[i])
            {
                c[i] -= v[u / 2];
            }
        }
    }
    else if (c[qq])
    {
        cout<<"-1";
        return 0;
    }
    for (int i = 1; i <= a; ++i)
    {
        ans += abs(c[i]);
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 16080
#include <cstdio>
using namespace std;
long long h,a;
int main()
{
	scanf("%lld%lld",&h,&a);
	if(h%a)
	{
		printf("%lld",h/a+1);
	}
	else
	{
		printf("%lld",h/a);
	}
	return 0;
}

Measured memory_bytes: 128
n = gets.to_i
x = gets.split.map(&:to_i)
y = x.sort{|a, b| a<=>b}
m1 = y[n / 2 - 1]
m2 = y[n / 2]
if m1 == m2
  n.times do
    puts m1
  end
  exit
end
0.upto(n-1) do |i|
  if x[i] <= m1
    puts m2
  else
    puts m1
  end
end

Measured memory_bytes: 25340
import java.util.*;

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

        int n = sc.nextInt();
        int[] a = new int[] {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

        System.out.println(a[n-1]);
    }
}

Measured memory_bytes: 23764
#include<stdio.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include <string.h>
#include<limits.h>
int main(void){
	int x, y, z, i;
	/////////////////////////
	scanf("%d", &x);
	int a[1000];
	for (i = 0; i < x; i++) {
		scanf("%d", &a[i]);
	}
	for (i = 0; i +1< x; x--) {
		printf("%d ", a[x - 1]);
	}
	printf("%d", a[x -1]);












	/////////////////////////
	printf("\n");
	return 0;
}


Measured memory_bytes: 2108
#include <iostream>
using namespace std;
int main()
{
    unsigned long long q,h,s,d,n,v1,v2,v3,v4,mi,nry;
    cin>>q>>h>>s>>d>>n;
    v1=q*8;
    mi=v1;
    v2=h*4;
    if(mi>v2)
        mi=v2;
    v3=s*2;
    if(mi>v3)
        mi=v3;
    v4=d;
    if(mi>v4)
        mi=v4;
    if(mi==v1)
        cout<<q*4*n;
    if(mi==v2)
        cout<<h*2*n;
    if(mi==v3)
        cout<<s*n;
    if(mi==v4)
    {

        mi=v1;
        if(mi>v2)
            mi=v2;
        if(mi>v3)
            mi=v3;
        nry=n/2*d+n%2*mi/2;
        cout<<nry;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
void printA(int A[],int n){
  for(int i=0; i<n; i++){
    cout << A[i];
    if(i!=n-1)
      cout << " ";
  }
  
  cout << endl;
}

int main(){
  int n,A[100];
  cin >> n;

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

  printA(A,n);
  for(int i=1; i<n; i++){
    int v = A[i];
    int j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
    }

    A[j+1] = v;

    printA(A,n);
  }
}

Measured memory_bytes: 3092
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (300006)
ll n;
int main(){
	cin>>n;
	vector<ll>v(n);
	FOR(i,0,n-1)cin>>v[i];
	function<bool(vector<ll>)>recur=[&](vector<ll>v){
		if(*max_element(all(v))==1)return false;
		ll even=0;
		for(auto i:v)even+=(i%2==0);
		if(even&1)return true;
		if(n-even >= 2)return false;
		assert(n-even==1);
		bool done=0;
		for(auto &i:v)if((i&1)&&i>1)--i,done=1;
		if(done==0)return false;
		ll gd=0; for(auto &i:v) gd=gcd(gd,i);
		for(auto&i:v)i/=gd;
		return !recur(v);
	};
	cout<<(recur(v)?"First":"Second")<<'\n';
}


Measured memory_bytes: 19840
#include <stdio.h>
#include <stdlib.h>


// ?????¬??????stdin ????????\????????????

char *garden;
int h,w;


int dfs(int x,int y, char c){
    if(x < 0 || y < 0 || x >= w | y >= h){
        return 0;
    }

    if(c == '.')
        return 0;

    if(c == garden[y*h+x]){
        garden[y*h+x]= '.';
        dfs(x+1,y, c);
        dfs(x-1,y, c);
        dfs(x,y-1, c);
        dfs(x,y+1, c);
    }
    return 0;
}

void solve(){

    int x,y,sum=0;
    char c;

    // ??§?????¢?´¢????????????
    for(y=0;y<h;y++){
        for(x=0;x<w;x++){
            c = garden[y*h+x];
            if(c != '.'){
                dfs(x,y,c);
                sum++;
            }
        }
    }
    free(garden);
    printf("%d\n", sum);


}

int main()
{
    int i;
    while(1){
        scanf("%d %d", &h,&w);
        if(h ==0 && w==0)
            return 0;;

        garden = malloc(sizeof(char)*h*w);

        for(i=0;i<h;i++){
            scanf("%s", &garden[i*h]);
        }

        solve();
    }
    return 0;
}

Measured memory_bytes: 924
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int[] a = new int[n*3];
		for(int i=0; i<n*3; i++){
			a[i] = in.nextInt();
		}
		Arrays.sort(a);

		long sum = 0;
		for(int i=0; i<n; i++){
			sum += a[n*3-(i+1)*2];
		}

		System.out.println(sum);
	}

}


Measured memory_bytes: 91908
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE RankNTypes #-}
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Maybe
import Data.List
import qualified Data.Vector.Unboxed as VU
-- import qualified Data.Vector.Unboxed.Mutable as VUM
-- import Control.Monad
-- import Control.Monad.ST
import Debug.Trace
-- trace _ = id

solve :: Int -> [Int] -> Int
solve bL as = minimum finVals
  where
  finVals = foldl f [0,0,0,0,0] as
    where
    f vals a = zipWith (\fn !v -> v + fn a)
                 fns (tail (scanl' min maxBound vals))

fns = [id, gRet, gOw, gRet, id]

gRet 0 = 2
gRet x | odd x = 1
       | even x = 0

gOw x | odd x = 0
      | even x = 1

-------------------------------------------------------------------------------

traceL :: Show a => String -> a -> b -> b
traceL label showObj val = trace (label ++ " " ++ show showObj) val

traceLM :: (Monad m, Show a) => String -> (b -> a) -> m b -> m b
traceLM label showFn act = do
  aaa <- act
  traceL label (showFn aaa) (return ())
  return aaa

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

tmain :: B.ByteString -> Int
tmain cont =
  let remLines0 = map B.words (B.lines cont)
      [bs_bL]:remLines1 = remLines0
      bL = readBInt bs_bL
      as = map (\[x] -> readBInt x) remLines1
  in solve bL as

outAnswer :: Int -> IO ()
outAnswer = putStrLn . show

main :: IO ()
main = outAnswer . tmain =<< B.getContents


-------------------------------------------------------------------------------

inp1 = "4\n1\n0\n2\n3\n"
inp2 = "8\n2\n0\n0\n2\n1\n3\n4\n1\n"
inp3 = "7\n314159265\n358979323\n846264338\n327950288\n419716939\n937510582\n0\n"
tv1 = tmain $ B.pack inp1
tv2 = tmain $ B.pack inp2
tv3 = tmain $ B.pack inp3
test1 = tv1 == 1
test2 = tv2 == 3
test3 = tv3 == 1
alltest = test1 && test2 && test3



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

int main() {
    int a,b;
    cin>>a>>b;
    if(a%2!=0&&b%2!=0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}



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

using namespace std;
const int mod = 1e9+7;
const int N = 5005;

int get(char c) {
	if(c == 'R') return 0;
	if(c == 'G') return 1;
	return 2;
}

int n;
char s[N];

int ps[N][3];

int main() {
	scanf("%d %s", &n, s + 1);

	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) ps[i][j] = ps[i - 1][j];
		ps[i][get(s[i])]++;
	}

	long long ans = 0;
	for(int j = 2; j <= n; j++) {
		for(int k = j + 1; k <= n; k++) {
			if(s[k] == s[j]) continue;
			int o = 0;
			while(o == get(s[j]) or o == get(s[k])) o++;
			ans += ps[j - 1][o];
			if(2 * j - k >= 1) {
				if(get(s[2 * j - k]) == o) ans--;
			}
		}
	}
	printf("%lld\n", ans);
}


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

typedef long long int ll;
typedef vector<int> vi;			
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef pair<int, int> 	pii;
typedef vector<bool> vb;
#define endl '\n'
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define MOD 1000000007
#define F first
#define S second
#define pb push_back
#define pf push_front
#define rb pop_back
#define rf pop_front
#define in insert
#define mp make_pair
#ifdef LOCAL
	#include "../../trace.h"
#else
    #define trace(args...)
#endif

ll div_floor(const ll &a,const ll &b) { return a / b - (((a ^ b) < 0) and a % b);}
ll div_ceil(const ll &a,const ll &b) { return a / b + (((a ^ b) >= 0) and a % b);}

#define forn(i, n) for(ll i = 0; i<n; i++)

void solve(){
	ll n; cin>>n;
	vl x(n), y(n), p(n);
	forn(i, n) cin>>x[i]>>y[i]>>p[i];


	vvl leastx(n, vl(1<<n, 1e18));//which x open
	vvl leasty(n, vl(1<<n, 1e18));//which y open
	
	forn(i, n) forn(j, 1<<n){
		leastx[i][j] = abs(x[i]);
		leasty[i][j] = abs(y[i]);
		forn(k, n) 
			if((j>>k)&1) 
				leastx[i][j] = min(leastx[i][j], abs(x[i]-x[k])),
				leasty[i][j] = min(leasty[i][j], abs(y[i]-y[k]));
	}
	//found all shortest distances
	ll tc = 1;
	for(ll i = 0; i<n; i++) tc *= 3;

	vl answer(n+1, 1e18);
	
	for(ll i = 0; i<tc; i++){
		
		ll temp = i;//number
		ll cntr = 0;//cnt
		ll repx = 0, repy = 0;//x, y
		while(temp>0){
			ll rem = temp%3;
			if(rem==2) repy += (1<<cntr);
			else if(rem==1) repx += (1<<cntr);
			cntr++;
			temp = temp/3;
		}

		cntr = __builtin_popcount(repy) + __builtin_popcount(repx);

		ll curr_sum = 0;
		for(ll j = 0; j<n; j++)//jth house
			curr_sum += p[j]*min(leastx[j][repx], leasty[j][repy]);
		answer[cntr] = min(answer[cntr], curr_sum);
	}
	for(auto &e: answer)
		cout<<e<<endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	#ifdef LOCAL
		freopen(".inp.txt", "r", stdin);
    	freopen(".out.txt", "w", stdout);
    	freopen(".err.txt", "w", stderr);
	#endif
	int t=1;
	// cin>>t;
	while(t--)
		solve();
}

Measured memory_bytes: 11192
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e18+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int x;
    cin >> x;
    cout << (x^1) << endl;
}


Measured memory_bytes: 3620
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		String anc = String.valueOf(str.charAt(0));
		int cnt = 0;
		int a = sc.nextInt();
		for(int i = 1;i < str.length();i++) {
			cnt++;
			if(cnt == a) {
				anc = anc + String.valueOf(str.charAt(i));
				cnt = 0;
			}
		}
		System.out.println(anc);
	}
}

Measured memory_bytes: 22996
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

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

  vector<long long> L(N);
  for(int i = 0;i < N;i++) {
    cin >> L[i];
  }

  sort(L.begin(),L.end());
  int s = L.size(),ans = 0;
  for(int i = 0;i < s;i++) {
    for(int j = i+1;j < s;j++) {
      for(int k = j+1;k < s;k++) {
        if(L[i] == L[j] || L[i] == L[k] || L[j] == L[k]) continue;
        if(L[i]+L[j] > L[k]) ans++;
      }
    }
  }

  cout << ans << endl;
 



}


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

int main()
{
	int N,K,P;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> K >> P;
		if (K%P != 0)
			cout << K%P << endl;
		else
			cout << P << endl;
	}
	return 0;
}

Measured memory_bytes: 3124
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc  = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		
		int count = 0;
		int ans = 0;
		while (true) {
			if (count < B ) {
				count = count + A-1;
				ans++;
				if (count == B-1) {
					break;
				}
			}
			else {
				break;
			}
		}
		if (B == 1) ans = 0;
		System.out.println(ans);
		
		
	}

}


Measured memory_bytes: 22996
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
int main(){
    string s;cin>>s;
    if(s[2]==s[3]&&s[4]==s[5])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
import java.util.*;
class Main
{
  public static void main(String[] args)
  {
     Scanner sc=new Scanner(System.in);
    int x=sc.nextInt();
    int k=sc.nextInt();
    int arr[]=new int[x];
    for(int i=0;i<x;i++)
      arr[i]=sc.nextInt();
    Arrays.sort(arr);
    int sum=0;
    for(int i=0;i<k;i++)
      sum+=arr[i];
    System.out.print(sum);
  }
}

Measured memory_bytes: 38728
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			double r = sc.nextDouble();
			System.out.printf("%f %f\n", areaOfCircle(r),lengthOfCircumference(r));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	private static double areaOfCircle(Double r) {
		return Math.pow(r, 2) * Math.PI;
	}

	private static double lengthOfCircumference(Double r) {
		return 2 * Math.PI * r;
	}

}

Measured memory_bytes: 28196
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int arr[MAX];
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    ll n,m;
    cin>>n>>m;
    vector<pair<ll,ll> >v;
    for(int i=0; i<n; i++)
    {
        ll a,b;
        cin>>a>>b;
        v.push_back({a,b});
    }
    sort(all(v));
    ll sum=0;
    for(int i=0; i<n; i++)
    {
        if(v[i].second<=m)
        {
            m-=v[i].second;
            sum+=v[i].first*v[i].second;
        }
        else
        {
            sum+=v[i].first*m;
            m=0;
            break;
        }
    }
    cout<<sum<<endl;

    return 0;
}


Measured memory_bytes: 5312
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

N, M, L = [int(_) for _ in readline().split()]
ABCQST = np.array(read().split(), dtype=np.int64)
ABC = ABCQST[:3 * M]
ST = ABCQST[3 * M + 1:]
A, B, C = ABC[::3], ABC[1::3], ABC[2::3]
S, T = ST[::2], ST[1::2]
G = csr_matrix((C, (A, B)), shape=(N + 1, N + 1))
G2 = floyd_warshall(G, directed=0)
G3 = np.full((N + 1, N + 1), np.inf)
np.fill_diagonal(G3, 0)
G3[G2 <= L] = 1
G4 = floyd_warshall(G3, directed=0)
G4[G4 == np.inf] = 0
print(*(G4.astype(np.int64)[S, T] - 1), sep='\n')


Measured memory_bytes: 32520
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <math.h>
#include <ctype.h>
#include <limits>
#include <numeric>
#include <type_traits>
using namespace std;
int a,b,c;

int main(){
    cin >> a >> b >> c;
    int res=0;
    res = max(a,b);
    res = max(res, c);

    if(res == a){
        cout << res*10 + b + c;
    }else if(res == b){
        cout << res*10 + a + c;
    }else{
        cout << res*10 + a + b;
    }

    return 0;
}

Measured memory_bytes: 256
class BinaryTree:
    class Node:
        def __init__(self, n):
            self.num = n
            self.parent = -1
            self.right = None
            self.left = None

    
    def __init__(self):
        self.root = None


    def insert(self, n):
        if not self.root:
            node = self.Node(n)
            self.root = node
        else:
            current, parent = self.root, None
            while current:
                parent = current
                if n < current.num:
                    current = current.left
                else:
                    current = current.right
            if n < parent.num:
                parent.left = self.Node(n)
            else:
                parent.right = self.Node(n)
            


#    def load(self, tree_info):
#        for i in range(self.node_num):
#            self.nodes[i].num = tree_info[i][0]
#            self.nodes[i].left = tree_info[i][1]
#            self.nodes[i].right = tree_info[i][2]
#            if self.nodes[i].left != -1:
#                self.nodes[self.nodes[i].left].parent = self.nodes[i].num
#            if self.nodes[i].right != -1:
#                self.nodes[self.nodes[i].right].parent = self.nodes[i].num


    
    def print_preorder(self, node):
        if not node.left and not node.right:
            return [node.num]
        elif not node.left:
            return [node.num] + self.print_preorder(node.right)
        elif not node.right:
            return [node.num] + self.print_preorder(node.left)
        else:
            return [node.num] + self.print_preorder(node.left) + self.print_preorder(node.right)


    def print_inorder(self, node):
        if not node.left and not node.right:
            return [node.num]
        elif not node.left:
            return [node.num] + self.print_inorder(node.right)
        elif not node.right:
            return self.print_inorder(node.left) + [node.num]
        else:
            return self.print_inorder(node.left) + [node.num] + self.print_inorder(node.right)


    def print_postorder(self, node):
        if not node.left and not node.right:
            return [node.num]
        elif not node.left:
            return self.print_inorder(node.right) + [node.num]
        elif not node.right:
            return self.print_inorder(node.left) + [node.num]
        else:
            return self.print_inorder(node.left) + self.print_inorder(node.right) + [node.num]



if __name__ == '__main__':
    n = int(input())
    qs = [ input().rstrip().split() for _ in range(n) ]
    bt = BinaryTree()
    for q in qs:
        if q[0] == 'insert':
            bt.insert(int(q[1]))
        elif q[0] == 'print':
            print(' ' + ' '.join(map(str,bt.print_inorder(bt.root))))
            print(' ' + ' '.join(map(str,bt.print_preorder(bt.root))))



Measured memory_bytes: 282692
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end() 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9+7;
int main(){
    ll n;cin>>n;
    string s;cin>>s;
    ll cnt=0;
    rep(i,10){
        rep(j,10){
            rep(k,10){
                char a=(char)('0'+i),b=(char)('0'+j),c=(char)('0'+k);
                ll cn=0;
                //cout<<a<<b<<c<<endl;
                rep(l,n){
                    if(cn==0){
                        if(s[l]==a)cn++;
                        continue;
                    }
                    if(cn==1){
                        if(s[l]==b)cn++;
                        continue;
                    }
                    if(cn==2){
                        if(s[l]==c)cn++;
                        continue;
                    }
                }
                if(cn==3)cnt++;
            }
        }
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;

class _Class
{
	void _Do()
	{
		//
		var _s = _stringArray();
		var N_ = int.Parse(_s[0]);
		var a_ = _intArray();


		int[] e = new int[9];

		for (int i=0;i<N_ ;i++){
			var cc = a_[i];
			//
			int c;
			{

				if (cc < 400) c = 0;
				else if (cc < 800) c = 1;
				else if (cc < 1200) c = 2;
				else if (cc < 1600) c = 3;
				else if (cc < 2000) c = 4;
				else if (cc < 2400) c = 5;
				else if (cc < 2800) c = 6;
				else if (cc < 3200) c = 7;
				else c = 8;
			}

			e[c] +=1;
		}

		int z = 0;
		for (int i = 0; i <= 7; i++)
			z +=Math.Sign(e[i]);	 
		//
		if (z > 0)
		{
			Console.WriteLine(z+" "+(z+e[8]));
		}
		else
		{
			Console.WriteLine("1 " +(z+e[8]));
		}


	}

	static void Main(string[] args)
	{
		new _Class()._Do();
	}


	// 1
	string[] _stringArray()
	{
		return Console.ReadLine().Split();
	}

	// 2.1 -2,147,483,648 ~ +2,147,483,647
	int[] _intArray()
	{
		var _s = Console.ReadLine().Split();

		var x = new int[_s.Length];
		for (var i = 0; i < _s.Length; i++)
			x[i] = int.Parse(_s[i]);

		return x;
	}

	// 2.2 -9,223,372,036,854,775,808 ~ +9,223,372,036,854,775,807
	long[] _longArray()
	{
		var _s = Console.ReadLine().Split();

		var x = new long[_s.Length];
		for (var i = 0; i < _s.Length; i++)
			x[i] = long.Parse(_s[i]);

		return x;
	}
}


Measured memory_bytes: 11092
L,R = map(int,input().split())

d = 10 ** 10

if R -L > 2019:
  print(0)
else:
  N = R -L 
  for i in range(N):
    for j in range(i+1,N+1):
      
      a = L+i
      b = L+j
      
      c = a * b % 2019
      d = min(c,d)
  print(d)


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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
#define int ll

const ll MOD = 1000000007;
const ll INF_LL = (ll)1000000007 * 1000000007;
const int INF_INT = (int)1000000007;
const double PI = 3.14159265358979323846;

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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define irep(itr, st) for (auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for (auto itr = (st).rbegin(); itr != (st).rend(); ++itr)

#define m0(x) memset((x), 0, sizeof((x)))
#define m1(x) memset((x), -1, sizeof((x)))

// xにはvectorなどのコンテナ
#define ALL(x) (x).begin(), (x).end()  // sortなどの引数を省略したい
#define RALL(x) (x).rbegin(), (x).rend()  // sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())     // sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))  //最大値を求める
#define MIN(x) *min_element(ALL(x))  //最小値を求める
#define all(x) (x).begin(), (x).end()

//略記
#define pb emplace_back  // vectorヘの挿入
#define mp make_pair     // pairのコンストラクタ
#define F first          // pairの一つ目の要素
#define S second         // pairの二つ目の要素

#define BITCOUNT __builtin_popcount
#define BITCOUNT_LL(x) __builtin_popcountll(x)

#define perm(c)             \
  sort(all(c));             \
  for (bool c##p = 1; c##p; \
       c##p = next_permutation(all(c)))  //順列 123 132 213 231 312 321

#define BIT(n) (1LL << (n))

#ifdef DEBUG
#define PRINT(A) std::cout << (#A) << ": " << (A) << std::endl;
#else
#define PRINT(A)
#endif

//入力高速化
struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

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;
}

signed main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  rep(i, N) {
    cin >> A[i];
    A[i]--;
  }
  int logK = 1;
  while (1LL << logK < K) logK++;

  vector<vector<int>> parent(logK, vector<int>(N, 0));

  rep(i, N) { parent[0][i] = A[i]; }
  rep(i, logK - 1) {
    rep(j, N) { parent[i + 1][j] = parent[i][parent[i][j]]; }
  }
  int current = 0;
  rep(i, INF_LL) {
    if (K & 1 == 1) {
      current = parent[i][current];
    }
    K = K >> 1;
    if (K == 0) break;
  }
  cout << current+1 << endl;
}

Measured memory_bytes: 100036
#include <iostream>
#include <algorithm>
#include <cmath>

int main()
{
    using namespace std;
    
    int n, a[200000];
    long long int sadness = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i] -= (i + 1);
    }
    sort(a, a + n);
    for(int i = 0; i < n; i++){
        sadness += abs(a[i] - a[n / 2]);
    }
    cout << sadness << endl;
    return 0;
}


Measured memory_bytes: 4416
#!/usr/bin/env python3

import array
import collections
import math
import sys


def sieve_of_eratosthenes(end, typecode="L"):
    assert end > 1
    is_prime = array.array("B", (True for i in range(end)))
    is_prime[0] = False
    is_prime[1] = False
    primes = array.array(typecode)
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


def factorize_trial_division(n, typecode="L"):
    factors = array.array(typecode)
    if n < 2:
        return factors
    for p in sieve_of_eratosthenes(math.ceil(math.sqrt(n)) + 1):
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def solve(n):
    if n < 2:
        return 0
    pf = collections.Counter(factorize_trial_division(n))
    # print(pf, file=sys.stderr)
    res = 0
    trigs = [i * (i + 1) // 2 for i in range(20)]
    num_trigs = len(trigs)
    for _, v in pf.items():
        for i in range(num_trigs - 1):
            if trigs[i] <= v < trigs[i + 1]:
                res += i
                break
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


if __name__ == '__main__':
    main()

Measured memory_bytes: 11128
#include "bits/stdc++.h"
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
ll MOD=1e9+7;
#define INF 2*1e9
#define N 1100000
#define MAX_V 900010
#define vec vector<int>
using namespace std;

ll a[N],b[N],n;
bool check(int k){
    ll int m=1<<(k+1);
    ll int A[N];
    ll int B[N];
    rep(i,n)A[i]=a[i]%m;
    rep(i,n)B[i]=b[i]%m;
    sort(A,A+n);
    int res=0;
    rep(i,n){
        res+=(lower_bound(A,A+n,m-B[i])-lower_bound(A,A+n,m/2-B[i]));
        res+=lower_bound(A,A+n,2*m-B[i])-lower_bound(A,A+n,m*3/2-B[i]);
        res%=2;
    }
    return res;
}
main(){
    cin>>n;
    rep(i,n)scanf("%lld",&a[i]);
    rep(i,n)scanf("%lld",&b[i]);
    ll int r=1;
    ll int ans=0;
    rep(i,31){
        ans+=check(i)*r;
        r<<=1;
    }
    cout<<ans;
}

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

int main() {

  int N, K;
  cin >> N >> K;
  
  int sum = 0;
  for(int i = 0; i < N; i++){
    int X;
    cin >> X;
    
    if(K / 2 >= X)
    sum += X;
      
      else
        sum += (K - X);
  }
  
  cout << sum * 2 << endl;
}


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

#define pb push_back
#define int ll

using ll=long long;
using pii=pair<int,int>;
using vpii=vector<pii>;
using vvpii=vector<vpii>;
using vi=vector<int>;
using vvi=vector<vi>;
using QU = vector<pair<char, int>>;


bool moved_out(const string& s, const QU& qs, int left, bool checkleft) {
    const int n = s.size();
    int i = left;
    for (const auto& qi: qs) {
        if (qi.first == s[i]) {
            if (qi.second == 1) {
                ++i;
                if (i == n)
                    return !checkleft;
            }
            else {
                --i;
                if (i < 0)
                    return checkleft;
            }
        }
    }
    return false;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    QU qs(q);
    for (int i=0; i<q; ++i) {
        char di;
        cin >> qs[i].first >> di;
        if (di == 'R')
            qs[i].second = 1;
        else
            qs[i].second = 0;
    }

    int leftlow = -1;
    int lefthigh = n;
    while (lefthigh-leftlow > 1) {
        int leftmid = leftlow + (lefthigh-leftlow)/2;
        if (moved_out(s, qs, leftmid, true))
            leftlow = leftmid;
        else
            lefthigh = leftmid;
    }
    //left ans is leftlow+1 (last out is at leftlow). right analogous

    int rightlow = -1;
    int righthigh = n;
    while (righthigh-rightlow > 1) {
        int rightmid = rightlow + (righthigh-rightlow)/2;
        if (moved_out(s, qs, rightmid, false))
            righthigh = rightmid;
        else
            rightlow = rightmid;
    }
    // last out is righthigh, so right ans is n-righthigh
    
    int ans = leftlow+1 + (n - righthigh);
    cout << n-ans << "\n";
    //cerr << "DBG: " << leftlow << " " << lefthigh << " " << rightlow << " " << righthigh << "\n";
}


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

using ull = unsigned long long;

ull C(int size, int count) {

    ull x = 1;
    ull y = 1;

    for(int i = 0; i < count; ++i) {
        x *= (size - i);
        y *= (i + 1);

        if(x % y == 0) {
            x /= y;
            y = 1;
        }

    }

    return x / y;
}

int main() {

    int n, p;

    cin >> n >> p;

    int even = 0;
    int odd = 0;

    for(int i = 0; i < n; ++i) {
        int a;
        cin >> a;

        if(a % 2 == 0)
            even++;
        else
            odd++;

    }

    ull answer = 0;

    if(p == 0) {

        for(int i = 0; i <= even; ++i)
            answer += C(even, min(i, even - i));

        ull evenC = answer;

        if(evenC != 0) {
            for(size_t i = 2; i <= odd; i+=2)
                answer += evenC * C(odd, min(i, odd - i));
        }

    }
    else {

        for(size_t i = 1; i <= odd; i+=2)
            answer += C(odd, min(i, odd - i));

        ull oddC = answer;

        if(oddC != 0) {
            for(size_t i = 1; i <= even; ++i)
                answer += C(even, min(i, even - i)) * oddC;
        }

    }


    cout << answer << endl;

    return 0;

}

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

int main() {
  int n;
  cin >> n;
  map<int, bool> mp;
  for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++) {
      mp[i * j] = true;
    }
  }
  if (mp[n]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define fi first
#define sec second
ll mod = 1000000007;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll v = (b * d);
  ll v1 = (a * d);
  ll v2 = (c * a);
  ll v3 = (b * c);
  ll ans = max(v, max(v1, max(v2, v3)));
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 3644