akhauriyash/Code-Regression huggingface dataset:
import queue
n,m=map(int,input().split())
road_list=[set() for i in range(n)]
mitisirube=[0]*n
mitisirube[0]=1
for i in range(m):
    a,b=map(int,input().split())
    road_list[a-1].add(b)
    road_list[b-1].add(a)

q = queue.Queue()

counter_set=set()
counter_set.add(1)
for i in road_list[0]:
    q.put(i)
    mitisirube[i-1]=1
    counter_set.add(i)

while not q.empty():
    tmp=q.get()
    for i in road_list[tmp-1]:
        if i not in counter_set:
            q.put(i)
            counter_set.add(i)
            if mitisirube[i-1]==0:
                mitisirube[i-1]=tmp

if mitisirube.count(0)>0:
    print("No")
else:
    print("Yes")
    for i in range(1,len(mitisirube)):
        print(mitisirube[i])

Measured memory_bytes: 68996
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    int r = sc.nextInt();
    
    if(r<1200) System.out.print("ABC");
    
    else if(r>=1200) System.out.print("ARC");
  }
}

Measured memory_bytes: 21844
#include <stdio.h>
#include <stdbool.h>

int main(void) {
  int i, j, k, n;
  bool p[50000];
  for(i = 0; i < 50000; ++i) p[i] = true;
  p[0] = false, p[1] = false;
  for(i = 2; i < 250; ++i) {
    if(p[i]) for(j = 2; i * j < 50000; ++j) p[i * j] = false;
  }
  while( 1 ) {
    int ans = 0;
    scanf("%d", &n);
    if(!n) break;
    for(i = 2; i <= n / 2; ++i) if(p[i] &&p[n - i]) ++ans;
    printf("%d\n", ans);
  }
  return 0;
}


Measured memory_bytes: 2748
#include<cstdio>
const int MaxN=100010,MaxQ=100010;
int N,Q,A[MaxQ],B[MaxQ],C[MaxQ],fa[MaxN];
long long M;
int find(int i){return fa[i]==i?i:fa[i]=find(fa[i]);}
int main(){
	scanf("%d%lld%d",&N,&M,&Q);
	for(int i=0;i<N;i++)fa[i]=i;
	int blo=N;
	for(int i=0;i<Q;i++){
		scanf("%d%d%d",A+i,B+i,C+i);
		if(C[i]==0&&find(A[i])!=find(B[i]))fa[find(A[i])]=find(B[i]),blo--;
	}
	for(int i=0;i<Q;i++)if(C[i]==1){
		if(M<N||find(A[i])==find(B[i])||blo==2)return puts("No"),0;
	}
	if(M-(N-blo)>1ll*blo*(blo-1)/2)puts("No");
	else puts("Yes");
}

Measured memory_bytes: 1664
// Example program
#include <iostream>
#include <string>
using namespace std;

void solve()
{
 int l,r,d; 
 cin>>l>>r>>d;
 int cnt=0;
 for(int i=l;i<=r;i++)
     if(i%d==0)cnt++;
   cout<<cnt<<endl;
}

int main()
{
 //int t; cin>>t;
// while(t--)
    solve();
}


Measured memory_bytes: 3636
N, X, Y = list(map(int, input().split()))

ret = [0 for i in range(N)]
for i in range(1, N):
    for j in range(i+1, N+1):
        if j <= X:
            idx = j-i
            ret[idx] += 1
        elif j <= Y:
            if i <= X:
                idx = X-i + min(j-X, Y-j+1)
                ret[idx] += 1
            else:
                idx = min(j-i, Y-j+1+i-X)
                ret[idx] += 1
        else:
            if i <= X:
                idx = X -i + 1 + j-Y
                ret[idx] += 1
            elif i<=Y:
                idx = j-Y + min(Y-i,i-X+1)
                ret[idx] += 1
            else:
                idx = j-i
                ret[idx] += 1

for i in ret[1:]:
    print(i)

Measured memory_bytes: 3572
#include<stdio.h>
int main(void){
  int N;
  scanf("%d",&N);
  char s[N];
  char t[N];
  scanf("%s %s",&s,&t);
  int j;
  for(j=0;j<N;j++){printf("%c%c",s[j],t[j]);
  }return 0;
}


Measured memory_bytes: 1724
#include<iostream>
#include<string>
using namespace std;
int main()
{
	int n;
	string s;
	char c;
	long ans = 0;
	int i, j, k;
	long *r, *g, *b;

	cin >> n;
	cin >> s;
	r = new long[n+n];
	g = new long[n+n];
	b = new long[n+n];


	for (i = n + n - 1; i >= n; i--) {
		r[i] = g[i] = b[i] = 0;
	}

	for (i = n-1; i >= 0; i--) {
		r[i ] = r[i+1];
		g[i ] = g[i+1];
		b[i ] = b[i+1];
		if (s[i] == 'R') {
			r[i]++;
		}
		else if (s[i] == 'G') {
			g[i]++;
		}
		else {
			b[i]++;
		}
	}

	for (i = 0; i < n-2 ; i++) {
		for (j = i + 1; j < n-1; j++) {
			if (s[i] == s[j])continue;
			if (s[i] == 'R') {
				if (s[j] == 'G') {
					c = 'B';
					ans += b[j + 1];
				}
				else {
					c = 'G';
					ans += g[j + 1];
				}
			}
			else if (s[i] == 'G') {
				if (s[j] == 'B') {
					c = 'R';
					ans += r[j + 1];
				}
				else {
					c = 'B';
					ans += b[j + 1];
				}
			}
			else {
				if (s[j] == 'R') {
					c = 'G';
					ans += g[j + 1];
				}
				else {
					c = 'R';
					ans += r[j + 1];
				}
			}

			if (j + j - i < n) {
				if (s[j + j - i] == c) {
					ans--;
				}
			}

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




Measured memory_bytes: 3736
#include<bits/stdc++.h>
using namespace std;
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define F first
#define S second
#define pb emplace_back
#define mt make_tuple
#define gcd __gcd
#define PI 3.141592653589
// Input
#define in(a) scanf("%d",&a)
#define in2(a,b) scanf("%d%d",&a,&b)
#define in3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define llin(a) cin >> a
#define inl(a) scanf("%lld",&a)
#define read(v,i,n) for(i=0;i<n;i++)in(v[i])
#define twod(mat,i,j,n,m) rep(i,n){rep(j,m)in(mat[i][j]);}
#define sc(ch) scanf("%c",&ch)
#define sstr(str) scanf("%s",str)
// Output
#define pr(a) printf("%d ",a)
#define pr2(a,b) printf("%d %d\n",a,b)
#define pr3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out(a) printf("%d\n",a)
#define outl(a) printf("%lld\n",a)
#define llpr(a) cout << a << " "
#define llout(a) cout << a << "\n"
#define yes printf("YES\n")
#define no printf("NO\n")
#define lin printf("\n")
// Iterator
#define lp(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
#define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
#define tf(mytuple) get<0>(mytuple)
#define ts(mytuple) get<1>(mytuple)
#define tt(mytuple) get<2>(mytuple)
// Debug
#define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
#define what(x) cerr << #x << " : " << x << "\n"
#define ck printf("continue\n")
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
	cerr << *it << " = " << a << "\n";
	err(++it, args...);
}
// Data Type
#define ll long long int
#define ii pair<int,int>
#define pli pair<ll,int>
#define triple tuple<int,int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define viii vector<pair<pair<int,int>,int> >
#define vvii vector<vector<pair<int,int> > >
#define M 998244353
#define N 5000
ll calc(ll n,ll m)
{
    ll x,y,z;
    ll ans=M;
    ll temp,a,b;
    ll j;
    if(n&1)
        a=(n/2),b=a+1;
    else
        a=(n/2),b=a;
    lp(j,1,m+1)
    {
        temp=max((m-j)*n,b*j);
        ans=min(ans,temp-min(a*j,(m-j)*n));
    }
    return min(ans,n);
}
int main()
{
    ll n,m,j,temp,a,b;
    cin >> n >> m;
    if(n%3==0 || m%3==0)
        out(0),exit(0);
    llout(min(calc(n,m),calc(m,n)));
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
typedef long long ll;
using namespace std;

int ipow(int a, int b){
  int ans = 1;
  for(int i = 0; i < b; ++i){
    ans *= a;
  }
  return ans;
}

int main(){
  int X;
  cin >> X;
  int ans = 0;
  for(int i = 0; i <= 100; ++i){
    for(int j = 2; j <= 100; ++j){
      if(ipow(i,j) > X) break;
      ans = max(ans, ipow(i, j));
    }
  }
  cout << ans << endl;
}


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

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

  int sum = 0, max_p = 0;
  for ( int i = 0; i < N; i++ ) {
    int p;
    cin >> p;
    sum += p;
    max_p = max(max_p, p);
  }

  cout << sum - max_p + max_p/2 << endl;  
  
  return 0;
}


Measured memory_bytes: 3624
import math

a, b, h, m = map(int, input().split())

hour_hand = (60*h+m)/2
minute_hand = 6*m
theta = max(hour_hand, minute_hand) - min(hour_hand, minute_hand)
if theta > 180:
    theta = 360 - theta
theta = math.radians(theta)

print(math.sqrt(a**2 + b**2 - 2*a*b*math.cos(theta)))


Measured memory_bytes: 9488
/*
 *  author : Atul Anand   
 *  created on : Fri Apr 03 2020
 */

import java.io.*;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException {
        int N = in.nextInt();
        int K = in.nextInt();
        double ans = 0;
        for(int i = 1; i <= N; i++){
            double p = 1.0/N;
            int x = i;
            double pow = 1;
            while(x < K){
                x = x * 2;
                pow = pow * 0.5;
            }
            p = p * pow;
            ans += p;
        }
        println(ans);
        in.close();
        out.close();
    }

    static int MIN = Integer.MIN_VALUE;
    static int MAX = Integer.MAX_VALUE;
    static Reader in = new Reader();
    static PrintWriter out = new PrintWriter(System.out);

    static void read(int arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextInt(); 
    	} 
    }
    
    static void read(long arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextLong(); 
    	} 
    }
    
    static void read(String arr[], int N) throws IOException { 
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.next(); 
    	} 
    }
    
    static void print(Object O) {  
    	out.print(O); 
    }
    
    static void println(Object O) { 
    	out.println(O); 
    }
    
    static void println(int arr[]) { 
    	for(int i = 0; i < arr.length; i++){ 
    		print(arr[i]+" "); 
    	} 
    	println(""); 
    }

    static void println(int arr[][]) { 
    	for(int i = 0; i < arr.length; i++){ 
    		println(arr[i]); 
    	}
    }
    
    static void debug(Object O) { 
    	System.out.println(O); 
    }
}

class Reader {
    BufferedReader reader;
    StringTokenizer tokenizer;

    Reader() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    String next() throws IOException {
        while (!tokenizer.hasMoreTokens() ) { 
            tokenizer = new StringTokenizer(reader.readLine()); 
        }
        return tokenizer.nextToken();
    }

    int nextInt() throws IOException { 
        return Integer.parseInt(next()); 
    }
    
    double nextDouble() throws IOException { 
        return Double.parseDouble(next());
    }
    
    long nextLong() throws IOException { 
        return Long.parseLong(next()); 
    }
    
    String nextLine() throws IOException { 
        return reader.readLine(); 
    }
    
    void close() throws IOException { 
        reader.close(); 
    }
}

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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
double ep(int all,double p){
    return all*(1/p);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N=in();
    vector<ll> a(N);
    REP(i,N){
        cin>>a[i];
    }
    ll sum;sum=0;
    ll ans;ans=0;
    ll fugo;fugo=1;
    REP(i,N){
        sum+=a[i];
        if(sum==0){
            ans++;
            sum=fugo;
        }else if(sum*fugo<0){
            ans+=abs(sum-fugo);
            sum=fugo;
        }
        fugo*=-1;
    }
    fugo=-1;sum=0;
    ll ans_;ans_=0;
    REP(i,N){
        sum+=a[i];
        if(sum*fugo==0){
            ans_++;
            sum=fugo;
        }else if(sum*fugo<0){
            ans_+=abs(sum-fugo);
            sum=fugo;
        }
        fugo*=-1;
    }
    print(min(ans,ans_));
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
#define N 100000
#define M 200000
using namespace std;
vector<pair<int,int> > adj[2*(M+N)];
map<pair<int,int>,int> id;
int curr = 0; //# of nodes currently; id of nth node is n
int n, m;
void creati(int u, int c)
{
	int my_id = ++curr;

	adj[u].push_back({my_id,1}); //entering the hub is free, but then entering a terminal costs money
	adj[my_id].push_back({u,0}); 

	id[{u,c}] = my_id;
}
bool vis[2*(M+N)];
int d[2*(M+N)];
int main()
{
	cin >> n >> m;
	curr = n;

	while(m--)
	{
		int u, v, c; cin >> u >> v >> c;
		if(id.find({u,c})==id.end())
			creati(u,c);
		if(id.find({v,c})==id.end())
			creati(v,c);
		int a = id[{u,c}];
		int b = id[{v,c}];
		adj[a].push_back({b,0});
		adj[b].push_back({a,0});
	}
	//Start at the hub of 1, end at the hub of n

	memset(vis,false,sizeof vis);
	memset(d,-1,sizeof d);
	priority_queue<pair<int,int> > frontier;
	frontier.push({0,1});
	d[1] = 0;

	while(!frontier.empty())
	{
		int u = frontier.top().second;
		frontier.pop();
		if(!vis[u])
		{
			vis[u] = true;
			for(const auto& e : adj[u])
			{
				int v = e.first, w = e.second;
				if(d[v]==-1 || d[u]+w < d[v])
				{
					d[v] = d[u]+w;
					frontier.push({-d[v],v});
				}
			}
		}
	}
	cout<<d[n]<<endl;

	return 0;
}

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

		for(int i=0; i<N; i++){
		 s[i] = sc.next();
		}		
		Arrays.sort(s);
		for (String str : s) System.out.print(str);
        System.out.println();
		
	}	
}

Measured memory_bytes: 23508
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
long long h,w,ans;
int main(){
	cin>>h>>w;
	ans=1LL<<40;
	if (h<w) swap(h,w);
	for (int i=0; i<=h; i++) {
		long long s1=i*w;
		long long s2=0;
		long long s3=0;
		long long last=h-i;
		long long now=0;
		if (last % 2==0) s2=(last/2)*w,now=max(now,(long long)abs(s1-s2));
		else if (w % 2==0) s2=(w / 2)*last,now=max(now,(long long)abs(s1-s2));
		else {
			if (last < w) s2=(w/2)*last,s3=(w/2+1)*last;
			else s2=(w)*(last/2),s3=(w)*(last/2+1);
			now=max((long long)abs(s1-s2),(long long)abs(s1-s3));
			now=max(now,(long long)abs(s2-s3));
		}
		ans=min(ans,now);
	}
	swap(h,w);
	for (int i=0; i<=h; i++) {
		long long s1=i*w;
		long long s2=0;
		long long s3=0;
		long long last=h-i;
		long long now=0;
		if (last % 2==0) s2=(last/2)*w,now=max(now,(long long)abs(s1-s2));
		else if (w % 2==0) s2=(w / 2)*last,now=max(now,(long long)abs(s1-s2));
		else {
			if (last < w) s2=(w/2)*last,s3=(w/2+1)*last;
			else s2=(w)*(last/2),s3=(w)*(last/2+1);
			now=max((long long)abs(s1-s2),(long long)abs(s1-s3));
			now=max(now,(long long)abs(s2-s3));
		}
		ans=min(ans,now);
	}
	if (h % 3==0 || w % 3==0) ans=0;
	cout<<ans<<endl;
	return 0;
} 

Measured memory_bytes: 256
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let v : Vec<i32> = s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect();
    let x = v[0];
    let y = v[1];
    let z = v[2];

    let ans = (x - z) / (y + z);
    println!("{}", ans);
}


Measured memory_bytes: 4352
#E
X,Y,A,B,C = map(int,input().split())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
R = list(map(int,input().split()))

P.sort(reverse=True)
Q.sort(reverse=True)
R.sort(reverse=True)

rp = []
rq = []
rr = []

for i in range(A):
    if i == 0:
        rp.append(P[0])
    else:
        rp.append(rp[-1]+P[i])
for i in range(B):
    if i == 0:
        rq.append(Q[0])
    else:
        rq.append(rq[-1]+Q[i])
for i in range(C):
    if i == 0:
        rr.append(R[0])
    else:
        rr.append(rr[-1]+R[i])
    
p = 0
q = 0
r = 0
ans = 0
inf = float("inf")
for _ in range(X+Y):
    np,nq,nr = 0,0,0
    if p < A and p < X:
        np = P[p]
    if q < B and q < Y:
        nq = Q[q]
    if r < C:
        nr = R[r]
        
    if np == max(np,nq,nr):
        ans+=np
        p+=1
    elif nq == max(np,nq,nr):
        ans+=nq
        q+=1
    elif nr == max(np,nq,nr):
        ans+=nr
        r+=1
    
print(ans)
        



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

int main(){
  int x,y,z,K;
  cin >> x >> y >> z >> K;
  ll a[x],b[y],c[z];
  for(int i=0;i<x;i++) cin >> a[i];
  for(int i=0;i<y;i++) cin >> b[i];
  for(int i=0;i<z;i++) cin >> c[i];

  sort(a,a+x);
  sort(b,b+y);
  sort(c,c+z);
  reverse(a,a+x);
  reverse(b,b+y);
  reverse(c,c+z);

  priority_queue<ll> que;
  for(int i=0;i<x;i++){
    if(i+1 > K) break;
    for(int j=0;j<y;j++){
      if((i+1)*(j+1) > K) break;
      for(int k=0;k<z;k++){
        if((i+1)*(j+1)*(k+1) > K) break;

        que.push(a[i] + b[j] + c[k]);
      }
    }
  }

  for(int i=0;i<K;i++){
    cout << que.top() << endl;
    que.pop();
  }

  return 0;
}


Measured memory_bytes: 1400
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class TestObj(object):

    def __init__(self, b, l, u, x):
        self.aokip = b
        self.minval = l
        self.maxval = u
        self.maxp = l * b + u * (x-b)

    def calc_point(self, r, x):
        return self.minval * min(self.aokip, r) + self.maxval * max(0, r - self.aokip)


def judge(tests, cum, n, k, x, thr):
    q = k // x
    r = k % x
    takap = 0

    if q >= n:
        return True

    for i in range(1,n+1):
        if i <= q:
            takap = max(takap, cum[q+1] - tests[i].maxp + tests[i].calc_point(r,x))

        else:
            takap = max(takap, cum[q] + tests[i].calc_point(r,x))

        if takap >= thr:
            return True

    return False


def binary_search(tests, x):
    n = len(tests) - 1

    thr = sum([ti.minval * ti.aokip for ti in tests])

    if thr == 0:
        return 0

    low = 0
    high = 10**18

    cum = []
    for ti in tests:
        if len(cum) > 0:
            cum.append(cum[-1] + ti.maxp)
        else:
            cum.append(0)

    while high - low > 1:
        mid = (high+low) // 2

        if judge(tests, cum, n, mid, x, thr):
            high = mid

        else:
            low = mid

    return high

n, x = li()
tests = []
for _ in range(n):
    b,l,u = li()
    tests.append(TestObj(b,l,u,x))

tests.sort(key=lambda x: x.maxp, reverse=True)
tests = [TestObj(0,0,0,x)] + tests
print(binary_search(tests, x))

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

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main(){
	int n;
	int d[1000000];
	int k=0;
	int count=0,ans=0;

	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&d[i]);
	}
	//quick_sort_2(d,n);
	qsort(d, n, sizeof(int), compare_int);

	ans = d[n/2] - d[n/2-1];
	printf("%d\n",ans);
}

Measured memory_bytes: 2812
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define M (998244353)
#define INF 1e16
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll>Q;

ll suml[200010];
ll sumr[200010];

int main(void){
    ll n,k;
    cin>>n>>k;
    ll ans = 0;
    for(ll i=0;i<=n;i++){
        suml[i+1]=suml[i]+i;
    }
    for(ll i=0;i<=n;i++){
        sumr[i+1]=sumr[i]+n-i;
    }
    for(ll i=k;i<=n+1;i++){
        ll mi = suml[i];
        ll ma = sumr[i];
        ll tmp = (ma-mi+1)%N;
        ans = (ans+tmp+N)%N;
        ans = (ans+N)%N;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6756
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  string S[N];
  for(int i=0;i<N;++i) cin>>S[i];
  int ans = 0;
  int anum=0, bnum=0, abnum=0;
  for(int i=0;i<N;++i) {
    for(int j=0;j<S[i].size()-1;++j) {
      if(S[i][j]=='A' && S[i][j+1]=='B') ans++;
    }
    if(S[i][0]=='B' && S[i][S[i].size()-1]=='A') abnum++;
    else if(S[i][S[i].size()-1]=='A') anum++;
    else if(S[i][0]=='B') bnum++;
  }
  if(anum>0 || bnum>0) {
    ans += min(abnum+anum, abnum+bnum);
  }
  else if(abnum>0) ans += abnum-1;
  cout<<ans<<endl;
}



Measured memory_bytes: 3892
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

int M;
vector<int> num, cnt;
vec<int, 2> G;
vector<int> used;

pair<int, int> dfs(int v) {
  used[v] = true;
  int score = 0, child = 0;
  for (int u : G[v]) {
    if (used[u]) continue;
    auto p = dfs(u);
    score += p.fst;
    child += p.snd;
  }
  int c = cnt[v];
  int n = num[v];
  int got = min(child, c);
  score += got;
  c -= got;
  if (__builtin_popcount(n) == 1) {
    int got = c / 2;
    score += got;
    c -= 2 * got;
  }
  return make_pair(score, c);
}

int main() {
  int N;
  while (cin >> N) {
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    map<int, int> mp, ord;
    for (int i = 0; i < N; i++) ++mp[A[i]];
    int i = 0;
    for (auto& entry : mp) ord[entry.fst] = i++;
    M = mp.size();
    cnt.clear();
    cnt.resize(M);
    num.clear();
    num.resize(M);
    G.clear();
    G.resize(M);
    for (auto& entry : mp) {
      int n = entry.fst;
      int c = entry.snd;
      cnt[ord[n]] = c;
      num[ord[n]] = n;
      for (int k = 0; k < 40; k++) {
        ll pw = 1ll << k;
        if (pw < n) continue;
        ll target = pw - n;
        if (target != n && ord.count(target)) {
          G[ord[n]].push_back(ord[target]);
          G[ord[target]].push_back(ord[n]);
        }
      }
    }
    used.clear();
    used.resize(M, false);
    int res = 0;
    for (int i = 0; i < M; i++) {
      if (used[i]) continue;
      res += dfs(i).fst;
    }
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 32256
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vll2 = vector<vector<ll>>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int mi = INF, ma = -1, lo = 0;
    for (int i = 0; i < n; i++) {
        chmin(mi, s[i] - 'a');
    }
    char c = 'a' + mi;
    vector<string> vs;
    string rs = s;
    reverse(all(rs));
    vs.push_back(rs);
    for (int i = 0; i < n; i++) {
        string to = s.substr(i, n - i);
        to += rs.substr(0, i);
        vs.push_back(to);
    }
    sort(all(vs));
    for (int i = 0; i < n; i++) {
        if (vs[0][i] != c) {
            ma = i;
            break;
        }
    }
    if (ma == -1) {
        cout << s << endl;
        return 0;
    }
    for (int i = 0; i < k; i++) {
        string t = s;
        reverse(all(s));
        t += s;
        //   cout << t << endl;
        lo = 0;
        if (i == 0) {
            s = vs[0];
            if (i < k - 1) {
                reverse(all(s));
            }
            continue;
        }
        ma *= 2;
        if (ma >= n) {
            for (int j = 0; j < n; j++) {
                cout << c;
            }
            cout << endl;
            return 0;
        }
        for (int j = t.length() - 1; j >= 0; j--) {
            if (t[j] == c) {
                lo++;
            } else {
                lo = 0;
            }
            if (lo == ma) {
                s = t.substr(j + ma - n, n);
            }
        }
        if (i == k - 1) {
            reverse(all(s));
        }
    }
    cout << s << endl;
}


Measured memory_bytes: 40320
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[N];
		int sum = 0;

		for(int i=0; i<N; i++){
			a[i] = sc.nextInt();
			sum += a[i]-1;
		}

		System.out.println(sum);
	}
}


Measured memory_bytes: 24912
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}
using int64 = long long;

int N, Q;
struct LazySegmentTree {
private:
    int n;
    vector<int64> node, lazy;

public:
    LazySegmentTree(vector<int64> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, int64 x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

    int64 getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        int64 vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        int64 vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};


int main() {
    int64 n,d,a;
    int64 ans = 0;
    cin >> n >> d >> a;
    vector<pair<int64,int64>> xh;
    vector<int64> x(n);
    vector<int64> h(n+1,0);

    for (int64 i=0; i<n; i++) {
        cin >> x[i] >> h[i];
        xh.emplace_back(x[i], h[i]);
    }

    sort(xh.begin(), xh.end());

    for (int i=0; i<n; i++) {
        x[i] = xh[i].first;
        h[i] = xh[i].second;
    }
    LazySegmentTree seg(h);




    for (int64 i=0; i<n; i++) {
//        for (int64 j=0; j<n; j++) cout << seg.getsum(j,j+1) << " "; cout<<endl;

        h[i] = seg.getsum(i,i+1);
        if (h[i] <= 0) continue;
        int64 r = x[i] + 2*d;

        auto it = upper_bound(x.begin(), x.end(), r);
        it--;
        int64 index = it - x.begin();

        int64 nboms = (h[i] + a - 1) / a;
        ans += nboms;
        seg.add(i,index+1, -(nboms * a));
    }

    cout << ans << endl;
}


Measured memory_bytes: 17132
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define forab(i, a, b) for(int i=(a);i<(b);++i)
#define foreach(i, n) for (__typeof(n.begin()) i = n.begin(); i != n.end(); ++i)
#define sqr(x) ((x)*(x))
#define clr(a, b) memset(a, b, sizeof(a))
#define MP make_pair
#define PB push_back
#define SZ(a) ((int)a.size())
#define all(a) (a).begin(),(a).end()
#define inf 0x3f3f3f3f
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
const double eps = 1e-8;
int dcmp(double x) { if (x < -eps) return -1; else return x > eps;}
#define se(x) cout<<#x<<" = "<<x<<endl

#ifdef CHEN_PC
	#define debug(...) printf(__VA_ARGS__)
#else 
	#define debug(...)
#endif

const int N = 200010;
ll x[N], xx;
ll sum[N];
int n;

ll solve() {
	reverse(x + 1, x + n + 1);
	sum[0] = 0;
	forab (i, 1, n+1) {
		sum[i] = sum[i - 1] + x[i];
	}
	ll ret = 0;
	forab (i, 1, n+1) {
		ret += x[i] * 5 + 2 * xx;
	}
	forab (k, 1, n+1) {
		int m = n / k;
		if (n % k) m++;
		int l = 0;
		int r = k;
		ll val = n * xx + k * xx;
		forn (i, m) {
			int t = 5;
			if (i > 0) {
				t = i * 2 + 3;
			}
			val += (sum[r] - sum[l]) * t;
			l += k;
			r += k;
			if (r > n) {
				r = n;
			}
			if (val > ret) {
				break;
			}
		}
		ret = min(ret, val);
	}
	return ret;
}

int main(int argc, char *argv[]) {
#ifdef CHEN_PC
	freopen("B.in", "r", stdin);
#endif

	while (scanf("%d%lld", &n, &xx) != EOF) {
		forn (i, n) {
			scanf("%lld", x + i + 1);
		}
		ll ret = solve();
		printf("%lld\n", ret);
	}
	return 0;
}



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

using namespace std;

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

bool dfs(int y, int x, vector<vector<bool> > &trot){
	if(!trot[y][x]) return false;
	trot[y][x] = false;
	if(x == w && y == h ) return true;
	if(trot[y-1][x] || trot[y][x-1]) return false;
	if(!trot[y][x+1] && trot[y+1][x])return dfs(y+1,x,trot);
	if(trot[y][x+1] && !trot[y+1][x])return dfs(y,x+1,trot);
	return false;
}

int main(){
	cin >> h >> w;
	vector<vector<bool> > trot(h+2, vector<bool>(w+2,false));
	for(int i = 1; i <= h; ++i)
		for(int j = 1; j <= w; ++j){
			char c; cin >> c;
			if(c == '#')trot[i][j] = true;
		}
			
	//for(int i = 0; i < trot.size(); ++i){\
		for(int j = 0; j < trot[i].size(); ++j){\
			if(trot[i][j])cout << '#';\
			else cout << '.';}\
		cout << endl;}
	bool flag = dfs(1,1,trot);
	for(int i = 1; i <=h; ++i){
		for(int j = 1; j <=w; ++j){
			if(trot[i][j]){
				flag = false;
	//			cout << "#";
				break;
			}
	//		else cout << ".";
		}
	//	cout << endl;
		if(!flag)break;
	}
	if(flag)cout << "Possible" << endl;
	else cout << "Impossible" << endl;

	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<map>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const ll MOD = 1000000007;
 
using namespace std;

int main(){
    int N;  cin >> N;
    string S1, S2;  cin >> S1 >> S2;
    ll dp[N];
    int mode, j;
    if(S1[0] == S2[0]){
        dp[0] = 3;
        mode = 2;
        j = 1;
    }else if(S1[0] != S2[0]){
        dp[1] = 6;
        mode = 1;
        j = 2;
    }
    while(j<N){
        if(S1[j] == S2[j]){
            dp[j] = dp[j-1] * mode;
            dp[j] %= MOD;
            j++;
            mode = 2;
        }else{
            dp[j+1] = dp[j-1] * (4 - mode);
            dp[j+1] %= MOD;
            j += 2;
            mode = 1;
        }
    }
    cout << (MOD + dp[N-1])%MOD << endl;
    return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>> ve(3);
    vector<set<int>> se(3);
    string ss ="RGB";
    for(int i =0; i<n; i++){
        char tmp;
        cin>>tmp;
        for(int j=0; j<3; j++){
            if(ss.at(j)==tmp){
                ve.at(j).push_back(i);
                se.at(j).insert(i);
            }
        }
    }
    int r =ve.at(0).size();
    int g = ve.at(1).size();
    int b = ve.at(2 ).size();
    long long ans =0;
    for(int i=0; i<r; i++){
        for(int j =0; j<g; j++){
            int jj = ve.at(1).at(j);
            int ii= ve.at(0).at(i);
            if(jj-ii<0){
                swap(jj,ii);
            }
            ans += b;
            if(se.at(2).count(2 *jj -ii)) ans--;
            if(( jj+ii) %2 ==0 && se.at(2).count((jj+ii)/2)) ans --;
            if(se.at(2).count(2 * ii -jj)) ans--;
        }
    }
    cout<<ans<<endl;
    
}

Measured memory_bytes: 3748
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <cmath>
#include <map>
#define INF 100000000
#define MAX_C 100
using namespace std;
map<int, int> mp;
int main()
{
	int r, c, v;

	int csum[MAX_C], rsum;

	for (int i = 0; i < MAX_C; i++) { csum[i] = 0; }

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		rsum = 0;

		for (int j = 0; j < c; j++)
		{
			cin >> v;

			cout << v;

			rsum += v;

			csum[j] += v;

			if (j + 1 == c)
			{
				cout << ' ' << rsum << endl;
			}
			else
			{
				cout << ' ';
			}
		}
	}

	rsum = 0;

	for (int i = 0; i < c; i++)
	{
		cout << csum[i];

		rsum += csum[i];

		if (i + 1 == c)
		{
			cout << ' ' << rsum << endl;
		}
		else
		{
			cout << ' ';
		}
	}

	return 0;
}


Measured memory_bytes: 3084
import java.util.*;


public class Main {
	
	int n, m;
	int[] s, t;
	
	void swap(int[] a, int[] b, int i, int j) {
		int tmp = a[i];
		a[i] = b[j];
		b[j] = tmp;
	}
	
	int sum(int[] cards) {
		int sum = 0;
		for (int i = 0; i < cards.length; i++) {
			sum += cards[i];
		}
		return sum;
	}
	
	String solve() {
		List<int[]> swaps = new ArrayList<int[]>();
		for (int i = 0; i < s.length; i++) {
			for (int j = 0; j < t.length; j++) {
				swap(s, t, i, j);
				if (sum(s) == sum(t)) {
					swaps.add(new int[]{t[j], s[i]});
				}
				swap(s, t, i, j);
			}
		}
		
		if (swaps.size() > 0) {
			int[] min = swaps.get(0);
			for (int i = 1; i < swaps.size(); i++) {
				int[] c = swaps.get(i);
				if (c[0] + c[1] < min[0] + min[1]) {
					min = c;
				}
			}
			return min[0] + " " + min[1];
		} else {
			return "-1";
		}
	}
	
	void run() {
		Scanner sc = new Scanner(System.in);
		String output = "";
		while (sc.hasNext()) {
			n = sc.nextInt();
			m = sc.nextInt();
			if (n == 0 && m == 0) {
				break;
			} else {
				s = new int[n];
				t = new int[m];
				for (int i = 0; i < n; i++) s[i] = sc.nextInt();
				for (int i = 0; i < m; i++) t[i] = sc.nextInt();
				output += solve() + "\n";
			}
		}
		sc.close();
		System.out.print(output);
	}

	public static void main(String[] args) {
		new Main().run();
	}

}

Measured memory_bytes: 24512
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

int main(){
    string s,t;
    cin>>s>>t;
    int ans=inf;
    rep(i,1+(int)s.size()-(int)t.size()){
        int cnt=0;
        rep(j,t.size()){
            if(t[j]!=s[i+j]){
                ++cnt;
            }
        }
        ans=min(ans,cnt);
    }
    cout<<ans<<"\n";
}


Measured memory_bytes: 3624
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

const ll MOD = 1000000007;
const int N_MAX = 200001;
const long double EPS = 1e-10;
const int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

ll fact[N_MAX], rfact[N_MAX];

ll perm(ll n, ll r){
    return (fact[n] * rfact[r]) % MOD;
}

ll comb(ll n, ll r){
    return (perm(n, r) * rfact[n-r]) % MOD;
}

void init(ll n){
    fact[0] = fact[1] = 1;
    rfact[0] = rfact[1] = 1;
    for(int i=2;i<=n;++i) {
        fact[i] = (fact[i-1] * (ll)i) % MOD;
        rfact[i] = 1;
        ll k = MOD-2;
        ll a = fact[i];
        while(k > 0){
            if(k & 1){
                rfact[i] *= a;
                rfact[i] %= MOD;
            }
            a *= a;
            a %= MOD;
            k  >>= 1;
        }
    }
}

ll modpow(ll a, ll t) {
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    ll n,a,b,c;
    cin >> n >> a >> b >> c;

    init(2*n);

    vector<ll> pow_a(n+1, 1), pow_b(n+1, 1);
    for(int i=1;i<=n;++i) {
        pow_a[i] = (pow_a[i-1] * a) % MOD;
        pow_b[i] = (pow_b[i-1] * b) % MOD;
    }

    ll ans = 0LL;
    for(int i=n;i<2*n;++i){
        ll tmp = (((pow_a[n] * pow_b[i-n]) % MOD) + ((pow_a[i-n] * pow_b[n]) % MOD)) % MOD;
        tmp = (((tmp * i) % MOD) * comb(i-1, n-1)) % MOD;
        tmp = (tmp * modpow(modpow(a+b, i), MOD-2)) % MOD;
        ans = (ans + tmp) % MOD;
    }
    ans = (((ans * 100) % MOD)  * modpow(100-c, MOD-2)) % MOD;
    cout << ans << endl;


}


Measured memory_bytes: 4992
s = input()[::-1]
t = input()[::-1]
if len(s) < len(t):
    print("UNRESTORABLE")
    exit()
    
for i in range(len(s) - len(t) + 1):
    for j in range(len(t)):
        if s[i + j] == "?":
            continue
        elif s[i + j] == t[j]:
            continue
        break
    else:
        ans = ""
        for k in range(i):
            if s[k] == "?":
                ans += "a"
            else:
                ans += s[k]
        for tt in t:
            ans += tt
        for k in range(len(t) + i, len(s)):
            if s[k] == "?":
                ans += "a"
            else:
                ans += s[k]
        print(ans[::-1])
        exit()
print("UNRESTORABLE")

Measured memory_bytes: 9100
#include <cstdio>    // 入出力ライブラリ
#include <cstdlib>   // いろんなユーティリティ提供
#include <string>    // 文字列ライブラリ  
#include <iostream>  // 入出力ライブラリ
using namespace std;  // 名前空間の面倒な修飾を省略できるstd::count
                      // がcountにここだと、Nodeの定義時に、structを書く必要がなくなる

struct Node {
  int key;  // int型のkey
  Node *right, *left, *parent;
  // Node型へのポインタをright, left, parentは持つことができるという宣言
};  // struceの定義のあとは、セミコロンいる

Node *root, *NIL;  // Node型へのrootポインタroot, NILの定義

void insert(int k) {
  // cout << "\ngeho";
  // exit(0);
  Node *y = NIL;
  Node *x = root;
  Node *z;
  // cout << "\nhge";
  // exit(0); 
  z = (Node *)malloc(sizeof(Node));  // pointerに対してのメモリの動的な割り当て。zポインタからNodeのポインタへ渡してるっぽい.二重割り当てか?
  // 確保したメモリをNode型ポインタへキャスト。構造体のsizeofは構造体メンバのバイト数
  // cout << "\nheeeege";
  // exit(0); 
  z->key = k;  // zオブジェクトのポインタに対して参照
  // zはNode型へのポインタ型変数。あるノードへのアドレスが入る
  // 上でzが指すNode用のメモリが確保
  // ここではzつまり確保したノードのアドレスのkeyがさすアドレスに変数を代入
  z->left = NIL;
  z->right = NIL;
  // zに親の情報を入れ込む処理：yが親に相当
  // cout << "\nheeeege";
  // printf("\nhogeyasu"); 
  // printf("\nhogeyasu3333333333333333"); 
  // cout << "\n";
  // cout << x;
  // cout << "\n";
  // cout << NIL;
  // if ( x == NIL){
    // cout << "\nyes";
  // }
  // exit(0);
  while (x != NIL) {
    // cout << "\nstart hoge";
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  // cout << "hoge1\n";
  z->parent = y;
  // yに子の情報を入れる処理
  // exit(0); 
  // cout << y; 
  // cout << "\n";
  // cout << NIL;
  // cout << "hoge2\n";
  if (y == NIL) {
    // cout << "hoge3\n";
    root = z;
    // cout << "hoge4\n";
    // cout << z->key;
    // cout << "hoge5\n";
  } else {
    // cout << y->key;
    // cout << "hoge6\n";
    // cout << z->key;
    if (z->key < y->key) {
      y->left = z;
    } else {
      y->right = z;
    }
    // cout << "hoge5\n";
  }
  // printf("\nhoge2");
}

void inorder(Node *u) {
  if (u == NIL) return;
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}
void preorder(Node *u) {
  if (u == NIL) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}  
int main() {
  int n, i, x;
  string com;

  scanf("%d", &n);
  // printf("%d", n);
  // exit(0);
  for (i = 0; i < n; i++) {
    // printf("hogehoge");
    cin >> com;  // stdio::cinは >>として、その先のstdinからの入力を入れれる
    // scanf("%d", &x);  // dだと10進数でxのアドレスに入力
    // cout << com;
    // cout << x;
    // exit(0);
    // printf("hohoho");
    if (com == "insert"){
      // cout << com;
      // exit(0); 
      scanf("%d", &x);  // dだと10進数でxのアドレスに入力
      // cout << com;
      // cout << x;
      // cout << "hoge";
      // exit(0); 
      insert(x);
      // printf("hoge");
    } else if (com == "print" ) {
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  
  return 0;  // 0を返すと正常終了。それ以外だと異常。
}


Measured memory_bytes: 26628
#include<iostream>
#include<vector>
using namespace std;
const int mod=1e9+7;
int n,m,dp[1005][1005],i,j;
char dime[1005][1005];
int main(){
	cin>>n>>m;
	dp[0][1]=1;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin>>dime[i][j];
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
			if(dime[i][j]=='#'){
				dp[i][j]=0;
			}
		}
	}
	cout<<dp[n][m];
}

Measured memory_bytes: 5120
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N,K;
int A[110];
bool dp[100010];//石の個数が残りi個の局面が勝ちか負けか

signed main(){
	cin>>N>>K;
	REP(i,N){
		cin>>A[i];
	}
	for(int i=1;i<=K;i++){
		for(int j=0;j<N;j++){
			if(i-A[j]>=0){
				dp[i]|=!dp[i-A[j]];
			}
		}
	}
	if(dp[K]==true){
		cout<<"First"<<endl;
	}
	else{
		cout<<"Second"<<endl;
	}
	return 0;
}


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

typedef long long ll;
typedef long double ld;

#define pb push_back
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

const ll mod = 1e9+7;

//最大公約数
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

//最小公倍数
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

//素数判定
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

//桁和
int digsum(ll n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

//桁数
int dignum(ll n) {
    int res = 0;
    while(n > 0) {
        res++;
        n /= 10;
    }
    return res;
}

//文字列中の特定の文字カウント
ll stringcount(string s,char c){
    return count(s.cbegin(),s.cend(),c);
}

//階乗
ll ka(ll i){
    ll res=1;
    while(i>0){
        res=res*i;
        i--;
    }
    return res;
}
 
//ncr
ll ncr(ll x,ll y){
    ll a = x;
    ll b = 1;
    if(y>(x/2)){
        y=x-y;
    }
    for(ll i=1;i<y;i++){
        a*=x-i;
        b*=i+1;
    }
    return a/b;
}

//フィボナッチ数列 -92
ll f(ll x){
    ll dp[x+1];
    dp[1]=1;
    dp[2]=1;
    for(ll i=3;i<=x;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[x];
}



int main(){
    int a,b,c,x;
    cin >> a >> b >> c >> x;
    int ans = 0;

    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(500*i+100*j+50*k==x){
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

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

#define maxn 400010
#define LL long long
#define inf 10000000000
#define mod 100000000
#define pi 3.14159265359
using namespace std;
int dx[24] = { 1,0,-1,0 ,2,0,-2,0 ,-1,-1,-2,-2 ,1,1,2,2    ,-1,-1,-2,-2 ,1,1,2,2 };
int dy[24] = { 0,1,0,-1 ,0,2,0,-2 ,-1,-2,-1,-2 ,-1,-2,-1,-2,1,2,1,2     ,1,2,1,2  };


LL n, m, k;
LL arr[maxn];
//LL arr2[maxn];
//int visit[maxn];
//int cache[maxn];
//int c[maxn];
//int g[maxn];
//int dfsnum = 0;
//vector<vector<int>>rvi;
//vector<vector<int>>scc;
//vector<pair<int, int>>ett;
//stack<int>st;
//bool flg = 1;
//LL s, d;
//
//int findp(int a) {
//	if (c[a] <0)return a;
//	return c[a] = findp(c[a]);
//}
//void unionp(int a, int b) {
//	a = findp(a);
//	b = findp(b);
//
//	if (a != b) {
//		c[a] += c[b];
//		c[b] = a;
//	}
//
//}
//LL power(LL x, LL y) {
//	LL ret = 1;
//	while (y > 0) {
//		if (y % 2) {
//			ret *= x;
//			ret %= mod;
//		}
//		x *= x;
//		x %= mod;
//		y /= 2;
//	}
//	return ret;
//}
//void dfs2(int v) {
//	cache[v] = 1;
//	scc.back().push_back(v);
//	for (int nv : rvi[v]) {
//		if (cache[nv])continue;
//		dfs2(nv);
//	}
//
//}
//LL fac(LL n) {
//	if (n == 1) return 1;        
//	return (n * fac(n - 1) - power(2,n-1) )%mod;
//}
//int fac2(LL n) {
//	LL res, i;
//	if (n == 1)return n;
//	res = n;
//	for (int i = n - 1; i > 0; --i) {
//		res *= i;
//		res %= mod;
//	}
//	return res;
//}

LL gcd(LL a, LL b) {
	while (b != 0) {
		LL r = a % b;
		a = b;
		b = r;
	}
	return a;
}


int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	//int t;   cin >> t; cin.ignore();
	int t = 1;
	for (int test_case = 0; test_case < t; ++test_case) {
		int flg = 0;
		LL ans1 = 0, ans2 = 0;
		string ans[2] = { "No","Yes" };
		string s1, s2 = "";
		string s, t;
		cin >> s >> t;
		for (int i = 0; i <= s.size() - t.size(); ++i) {
			int cnt = 0;
			for (int j = 0; j < t.size(); ++j) {
				if (s[i+j] == t[j]) {
					cnt++;
				}
			}
			if (ans1 < cnt)ans1 = cnt;
		}
		ans1 = t.size() - ans1;
		cout << ans1;
		cout << '\n';

	}
	return 0;
}


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

int gcd(int x,int y){
    if(x%y==0){
        return y;
    }else{
        return gcd(y,x%y);
    }
}

int main(){
    int x,y;
    cin>>x>>y;
    int a=gcd(x,y);
    cout<<x+1+y+1-a-1<<endl;

    return 0;
}


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

using namespace std;

int main()
{
  int a,b,c,d,ans=0;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  if(a>=b)
      ans+=b;
  
  else
     ans+=a;
  
  if(c>=d)
      ans+=d;
  
  else
    ans+=c;
  
  printf("%d",ans);
}

Measured memory_bytes: 256