akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
	
	int N, M, Q;
	
	while(true){
		
		cin >> N >> M >> Q;
		
		if(N == 0){
			break;
		}
		
		long long int BIT[2000];
		long long int init = 0;
		for(int i = 0; i < N; i++){
			init *= 2;
			init += 1;
		}
		for(int i = 0; i < M; i++){
			BIT[i] = init;
		}
		long long int BIT_on = 0;
		for(int loop = 0; loop < Q; loop++){
			string str1, str2;
			cin >> str1 >> str2;
			init = 0;
			for(int i = N - 1; i >= 0; i--){
				init *= 2;
				init += str1[i] - '0';
			}
			BIT_on = BIT_on ^ init;
			
			for(int i = 0; i < M; i++){
				if(str2[i] == '1'){
					BIT[i] = BIT[i] & BIT_on;
				}else{
					BIT[i] = BIT[i] & (~BIT_on);
				}
			}
		}
		for(int i = 0; i < M; i++){
			long long int hoge = 1;
			int ans = -1;
			for(int j = 0; j < N; j++){
				if(hoge == BIT[i]){
					ans = j;
					break;
				}
				hoge *= 2;
			}
			if(ans == -1){
				cout << "?";
			}else if(ans < 10){
				cout << ans;
			}else{
				string str = "A";
				str[0] += ans - 10;
				cout << str;
			}
		}
		cout << endl;
		
	}
	
	return 0;
}

Measured memory_bytes: 3180
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	char s[110];
	cin>>(s+1);
	int len=strlen(s+1);
	int l,r;
	l=1;
	int ans=0;
	r=len;
	while(l<=r)
	{
		if(s[l]!=s[r]) ans++;
		l++;
		r--;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 504
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 2e4+5;
int n, d = 4e4, b[N];
int main()
{
    n = (N-5)*d;
    n = read(); 
    for(int i = 1; i <= n; ++i) b[read()] += i, b[i] += (n-i+1)*d, printf("%d ", i*d); puts("");
    for(int i = 1; i <= n; ++i) printf("%d ", b[i]); 
    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{

    int a, b, c;

    scanf("%d %d %d", &a, &b, &c);

    if (a <= b && b <= c)
        printf("%d %d %d\n", a, b, c);
    else if (a <= c && c <= b)
        printf("%d %d %d\n", a, c, b);
    else if (b <= a && a <= c)
        printf("%d %d %d\n", b, a, c);
    else if (b <= c && c <= a)
        printf("%d %d %d\n", b, c, a);
    else if (c <= b && b <= a)
        printf("%d %d %d\n", c, b, a);
    else if (c <= a && a <= b)
        printf("%d %d %d\n", c, a, b);

    return 0;
}

Measured memory_bytes: 596
// Comment 
// easy, boring implement

#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 2e5 + 100;

int N;
ll Nr[MAX_N], Sum[MAX_N];
int Ix[2][MAX_N];

void fillIx(int ix[MAX_N]) {
	vector<ll> sum(MAX_N+1);
	for(int i=1; i<=N; i++) sum[i] = sum[i-1] + Nr[i];

	int j = 0;
	for(int i=1; i<=N; i++) {
		while(sum[j+1] <= sum[i] - sum[j+1]) j++;
		ix[i] = j;
	}
}

int main() {
	cin >> N;
	for(int i=1; i<=N; i++) {
		scanf("%lld", &Nr[i]);
		Sum[i] = Sum[i-1] + Nr[i];
	}
	for(int k=0; k<2; k++) {
		fillIx(Ix[k]);
		reverse(Nr+1, Nr+N+1);
	}
	reverse(Ix[1]+1, Ix[1]+N+1);
	for(int i=1; i<=N; i++) Ix[1][i] = N+1 - Ix[1][i];

	ll ans = LINF;
	for(int i=2; i<=N-2; i++) {
		vector<int> ls, rs;
		ls.push_back(Ix[0][i]);
		ls.push_back(Ix[0][i]+1);
		rs.push_back(Ix[1][i+1]-1);
		rs.push_back(Ix[1][i+1]-2);
		for(int l: ls) for(int r: rs) {
			if(!(0 < l && l < i && i < r && r < N)) continue;
			ll pp = Sum[l], qq = Sum[i] - Sum[l];
			ll rr = Sum[r] - Sum[i], ss = Sum[N] - Sum[r];
			ll now = max(max(pp, qq), max(rr, ss)) - min(min(pp, qq), min(rr, ss));
			ans = min(ans, now);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 9944
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N; cin>>N;
    int ans=0;
    REP(i,N){
        int a; cin>>a;
        while(a%2==0){
            a/=2;
            ans++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
     int cat;
     int dog;
     int i;
     int x;

     scanf("%d %d %d",&cat, &dog, &x);
     i = cat + dog;
     if(cat > x){printf("NO\n");}
     else if(i >= x){printf("YES\n");}
     else{printf("NO\n");}

     return 0;
}

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

int main()
{
  int N, K;
  cin >> N >> K;
  
  int val = 1;
  for(int i = 0; i < N; ++i){
    if(K >= val){
      val *= 2;
    }
    else{
      val += K;
    }
  }
  
  cout << val << endl;
  return 0;
}

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

using namespace std;

int main(void){
    string S;
    string T;
    int N;

    cin >> S >> T;
    cin >> N;

    int s_s = 0;
    int s_e = 0;
    int t_s = 0;
    int t_e = 0;

    int s_a = 0;
    int S_asum[1000000+1];
    S_asum[0] = 0;
    for(int j=1;j<=S.length();j++){
        /*if(S[j-1] == 'A'){
            s_a++;
        }
        S_asum[j] = s_a;
        */
        S_asum[j] = S_asum[j-1] + S[j -1] - 'A' + 1;
    }
    int t_a = 0;
    int T_asum[1000000+1];
    T_asum[0] = 0;
    for(int j=1;j<=T.length();j++){
        /*
        if(T[j-1] == 'A'){
            t_a++;
        }
        T_asum[j] = t_a;
        */
        T_asum[j] = T_asum[j-1] + T[j -1] - 'A' + 1;
    }
    S_asum[0] = 0;
    T_asum[0] = 0;

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

        cin >> s_s >> s_e >> t_s >> t_e;
        int s_tmp = 0;
        int t_tmp = 0;

        s_tmp = S_asum[s_e] - S_asum[s_s-1];
        t_tmp = T_asum[t_e] - T_asum[t_s-1];

        string ans = "NO";
        if(s_tmp % 3 == t_tmp % 3){
            ans = "YES";
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 7168
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int S1=0; int S2=0; int S3=0;
		int N = sc.nextInt();
		//整数型配列の宣言と初期化
		int [] arys;
		arys = new int [N];
		
		for(int i=0; i<N;i++)
		{		
		arys[i]=sc.nextInt();
		}
		
		int [] anss;
		anss = new int [N-1];

		for(int j=0;j<=N-2;j++){
			S1=0;S2=0;S3=0;
			for(int k=0;k<=j;k++){			
			S1=S1+arys[k];		
			}
			for(int k=j+1;k<=N-1;k++){			
			S2=S2+arys[k];	
			}	
			S3=Math.abs(S1-S2);
			anss[j]=S3;	
		}		
		// 最小値を求める		
		int ans=anss[0];	
        for(int i = 0; i <=N-2 ; i++){
            ans = Math.min(ans,anss[i]);
        }
		System.out.println(ans);
		}
}


Measured memory_bytes: 21716
import sys
input = sys.stdin.readline

N=int(input())
A=[0]+[0]+list(map(int,input().split()))

C=[[] for i in range(N+1)]

for i in range(2,N+1):
    C[A[i]].append(i)

for i in range(1,N+1):
    print(len(C[i]))

        



Measured memory_bytes: 44064
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cmath>

using namespace std;

int main(){

    string s;
    cin >> s;

    int s_count = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'S'){
            s_count ++;
        }
        else{
            if(s_count > 0){
                s_count --;
            }
        }
    }

    cout << 2 * s_count << endl;


}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INFTY 1.0e9+1
#define N 500000
int merge_count = 0;
int array[N];
long int inv_count_sum = 0;

void merge(int left, int right) {
	int mid = (left+right)/2;
	int n1 = mid-left;
	int n2 = right-mid;
	int l[n1+1];
	int r[n2+1];
	for(int i = 0; i < n1; i++) {
		l[i] = array[left+i];
	}
	for(int i = 0; i < n2; i++) {
		r[i] = array[mid+i];
	}
	l[n1] = INFTY;
	r[n2] = INFTY;

	int p = 0;
	int q = 0;
	int inv_count = 0;
	int x1, x2;
	for(int i = left; i < right; i++) {
		merge_count++;
		if(l[p] <= r[q]) {
			array[i] = l[p];
			p++;
			inv_count_sum += inv_count;
		}
		else {
			x2 = l[p];
			if(l[p] != INFTY && l[p] > r[q]) {
				inv_count++;
				/*
				*/
				
			}
			
			array[i] = r[q];
			q++;
		}
	}
	
}

void merge_sort(int left, int right) {
	if(left+1 < right) {
		int mid = (left+right)/2;
		merge_sort(left, mid);
		merge_sort(mid, right);
		merge(left, right);
	}
}

int main() {
	int n;
	cin >> n;
	
	for(int i = 0; i < n; i++) {
		cin >> array[i];
	}

	merge_sort(0, n);

	cout << inv_count_sum << endl;
	return 0;
}



Measured memory_bytes: 4636
#include<bits/stdc++.h>
using namespace std;
# define pb push_back
# define FOR(i,a,n) for(int i=a;i<n;i++)
# define mp make_pair
# define RFOR(i,a,n) for(int i=n;i>a;i--)
# define pii pair<long long int,long long int>
#define ub upper_bound
#define lb lower_bound
#define MOD 1000000007
typedef long long int ll;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
        cout.tie(0);
	ll n,k;
	cin>>n>>k;
	vector<ll> vec;
	for(int i=0;i<n;i++)
	{
		ll x;
		cin>>x;
		vec.pb(x);
	}
	ll cnt=0;
	sort(vec.begin(),vec.end());
	for(int i=0;i<k;i++)
	cnt+=vec[i];
	cout<<cnt<<endl;
}

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

#define MAX_N 50

using namespace std;

typedef long long lint;

const lint sqrInf = 1LL * (1e18) + 1;

int c[MAX_N + 1];

lint w[MAX_N + 1];
int v[MAX_N + 1];

lint dp[MAX_N * MAX_N * MAX_N + 1];

int rez;
int n, x, d;

struct cmp
{
    bool operator () (const int &a, const int &b) const
    {
        return v[a] * w[b] > w[a] * v[b];
    }
};

vector <int> g[MAX_N + 1];

void add(int a, int b)
{
    g[a].push_back(b);
}

void dfs(int a)
{
    w[a] = c[a];
    v[a] = 1;

    for(auto u : g[a])
    {
        dfs(u);

        w[a] += w[u];
        v[a] += v[u];
    }
}

int main()
{
    cin >> n >> x >> d;
    cin >> c[1];

    int i, b;
    for(i = 2; i <= n; i ++)
    {
        cin >> c[i] >> b;

        add(b, i);
    }

    dfs(1);

    int n3 = n * n * n;
    for(i = 1; i <= n3; i ++)
        dp[i] = sqrInf;

    int j, k;
    for(i = 1; i <= n; i ++)
    {
        int mx = min(n, d);
        for(k = 1; mx > 0; k <<= 1)
        {
            int bag = min(mx, k);
            mx -= bag;

            for(j = n3 - bag * v[i]; j >= 0; j --)
                dp[j + bag * v[i]] = min(dp[j + bag * v[i]], dp[j] + bag * w[i]);
        }
    }

  //  cout << dp[9] << "++\n";

    vector <int> ord(n);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), cmp());
    for(i = 0; i <= n3; i ++)
    {
        if(dp[i] <= x)
        {
            int cate = i;
         //   cout << cate << "\n";
            int rest = x - dp[i];
            int cat = d - min(n, d);
            for(j = 0; j < n; j ++)
            {
             //   cout << j << " " << ord[j] << " " << ((ord[j] != 1) ? min(1LL * cat, rest / w[ord[j]]) : rest / w[ord[j]]) * v[ord[j]] << " REST " << rest << " " << rest / w[ord[j]]  << "\n";
              //  cout << fixed << setprecision(6) << 1.0D * v[ord[j]] / w[ord[j]] << "\n";
                int bag = ((ord[j] != 1) ? min(1LL * cat, rest / w[ord[j]]) : rest / w[ord[j]]);
                cate += bag * v[ord[j]];
                rest -= bag * w[ord[j]];

            }
        //    cout << "REZ " << cate << "\n";
         //   cout << "\n";

            rez = max(rez, cate);
        }
    }

    cout << rez << "\n";

    return 0;
}


Measured memory_bytes: 1280
#include "bits/stdc++.h"

#define REP(i, n, N) for(ll i=(n); i<(N); i++)
#define RREP(i, n, N) for(ll i=(N-1); i>=(n); i--)
#define LREP(lst,itr) for(auto itr = lst.begin(); itr != lst.end(); ++itr)
#define CK(n, a, b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(),(v).end()
#define MCP(a, b) memcpy(b,a,sizeof(b))
#define P(s) cout<<(s)<<endl
#define P2(a, b) cout<<(a)<<" "<<(b)<<endl
#define P3(a, b, c) cout<<(a)<<" "<<(b)<<" "<<(c)<<endl
#define V2(T) vector<vector<T>>
typedef long long ll;
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int main(){
    int N;
    cin >> N;
    vector<int> vec(N);
    REP(i,0,N){
        cin >> vec[i];
    }

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

    vector<pair<int, int>> pairs;
    REP(i,0,N){
        REP(j,i+1,N){
            pairs.push_back(make_pair(vec[i], vec[j]));
        }
    }

    vector<int> len(1001,0);
    REP(i,1,1001){
        REP(j,0,N){
            if(vec[j]<i) len[i]++;
        }
    }

    ll sum=0;
    ll plus,sub;
    REP(i,0,pairs.size()){
        plus = pairs[i].first+pairs[i].second;
        sub = abs(pairs[i].first-pairs[i].second);
        if(plus > 1000){
            sum+=N-len[sub+1]-2;
            if(sub>=pairs[i].first) sum++;
            if(sub>=pairs[i].second) sum++;
        }else{
            sum+=len[plus]-len[sub+1]-2;
            if(sub>=pairs[i].first) sum++;
            if(sub>=pairs[i].second) sum++;
        }
    }


    P(sum/3);
}

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

#define fastio                  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define input_output            freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); 

#define ll                      long long
#define read1(x)                 cin>>x
#define read2(x,y)               cin>>x>>y
#define pii                     pair<int, int>
#define pli                     pair<ll, int>
#define pil                     pair<int, ll>
#define pll                     pair<ll, ll>
#define vi                      vector<int>
#define vll                     vector<ll>
#define vb                      vector<bool>
#define vd                      vector<double>
#define vs                      vector<string>
#define ff                      first
#define ss                      second
#define pb                      push_back
#define ppb                     pop_back
#define pf                      push_front
#define ppf                     pop_front
#define vpii                    vector<pii>
#define umap                    unordered_map
#define uset                    unordered_set
#define clr(a,b)                memset(a,b,sizeof a)
#define all(ds)                 ds.begin(), ds.end()
#define rev(ds)                 ds.rbegin(), ds.rend()
#define asc(A)                  sort(A.begin(), A.end())
#define dsc(A)                  sort(A.begin(), A.end(), greater<int>())
#define gcd(x,y)                __gcd(x,y)
#define clr(a,b)                memset(a,b,sizeof a)
#define fr(i, n)                for(int i=0; i<n;++i)
#define fr1(i, n)               for(int i=1; i<=n; ++i)
#define rfr(i, n)               for(int i=n-1; i>=0; --i)
#define printVector(v)          for(int i= 0;i<v.size();i++) {cout<<v[i]<<" ";} cout<<endl;
#define precise(x)              cout<<fixed<<setprecision(x)
#define inf                     10000000000000

 

ll lcm(ll a, ll b) {return (a*b)/__gcd(a, b); }
ll power(ll x, ll y, ll m) { if(!y) return 1; ll p=power(x, y>>1, m)%m; p=p*p%m; return (y&1)?(x*p)%m:p;}
ll modInverse(ll a, ll m){ return power(a, m-2, m); }
bool isPrime(ll num){bool flag=true;for(ll i =2;i<=num/2;i++){if(num%i==0) {flag=false; break;} }return flag;}
ll sumofdigits(ll n){ll c=0;while(n>0){c++;n/=10;}return c;}
bool sortinrev(const pair<int,int>&a,const pair<int,int>&b) {return a.first > b.first; }
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b) {return a.second < b.second; }

//const double PI= 2*acos(0.0);
const long long MOD= 1000000007;



void solve(){
    int n; cin>>n;
    vector<int>v(n);
    fr(i, n)cin>>v[i];
    vector<ll>postsum(n-1);
    postsum[n-2] = v[n-1];
    for(int i = n-3; i >= 0; --i){
    	postsum[i] = (postsum[i+1] + v[i+1])%MOD;
    }
   	ll ans = 0;
    fr(i,n-1){
    	ans = (ans + (v[i]*postsum[i])%MOD)%MOD;
    }
    cout<<ans<<endl;
}
int main()
{
#ifndef ONLINE_JUDGE  
    input_output  
#else   
    fastio
#endif

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

    return 0;
}

Measured memory_bytes: 5556
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int a,b;
int main() {
  	ios::sync_with_stdio(false);
  	cin>>a>>b;
  	if(a==b)cout<<"Yes\n";
  	else cout<<"No\n";
 	return 0;
}

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

int main() {
    ll H, W, K;
    cin >> H >> W >> K;
    vector<string> c(H);
    rep(i, H) { cin >> c[i]; }

    ll ans = 0;
    rep(i, pow(2, H)) {
        rep(j, pow(2, W)) {
            ll tmp = 0;
            rep(k, H) {
                rep(l, W) {
                    // k,lが塗ってるところではなく、cが#
                    if (((i >> k) & 1) == 0 && ((j >> l) & 1) == 0 && c[k][l] == '#') {
                        tmp++;
                    }
                }
            }
            if (tmp == K) {
                ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


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

int main() {
  int N, M, X, Y;
  cin >> N >> M >> X >> Y;
  vector<int> vecA(N + 1), vecB(M + 1);
  vecA.at(0) = X;
  vecB.at(0) = Y;
  for (int i = 1; i < N + 1; i++) {
    cin >> vecA.at(i);
  }
  for (int i = 1; i < M + 1; i++) {
    cin >> vecB.at(i);
  }
  sort(vecA.begin(), vecA.end());
  sort(vecB.begin(), vecB.end());
  if (vecA.at(N) < vecB.at(0)) {
    cout << "No War" << endl;
  } else {
    cout << "War" << endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.Iterator;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.Random;
    import java.util.Map;
    import java.util.HashMap;
     
    class Main{
    	public static void main(String args[]){
    		Scanner sc = new Scanner(System.in);
    		int N = sc.nextInt();
    		int[] a = new int[N];
    		for(int i=0; i<N; i++) a[i] = sc.nextInt();
    		
    		int count = 0;
    		for(int i=0; i<N; i++){
    		    while(a[i]%2 == 0){
    		        a[i] /= 2;
    		        count ++;
    		    }
    		}
    		System.out.println(count);
    	}
    }

Measured memory_bytes: 36316
N = int(input())
XY = []
for i in range(N):
  A = int(input())
  XY.append([list(map(int, input().split())) for _ in range(A)])

ans = 0
for bit in range(1 << N):
  honest_cnt = 0
  flag = True
  for i in range(N):
    if (bit >> i) & 1 == 0:
      continue
    honest_cnt += 1
    for x, y in XY[i]:
      if (bit >> (x-1)) & 1 != y:
        flag = False
        break
  if flag:
    ans = max(ans, honest_cnt)
    
print(ans)

Measured memory_bytes: 3064
import math

N,K=map(int, raw_input().split())
A=map(int, raw_input().split())
i=A.index(1)

ans=99999999
for k in range(K):
    tmp=1
    kk=(K-1)-k
    lefti=max(0, i-k)
    righti=min(N-1, i+kk)
    left= int(math.ceil((lefti)/float(K-1)))
    right= int(math.ceil((N-righti-1)/float(K-1)))
    ans=min(ans, tmp+left+right)
print ans


Measured memory_bytes: 11304
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
g = [[]*n for _ in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
v = [int(x) for x in range(n)]
from itertools import permutations
v_per = list(permutations(v, n))
ans = 0
for per in v_per:
    if per[0] != 0:
        continue
    flag = 1
    for i in range(len(per) - 1):
        if per[i + 1] not in g[per[i]]:
            flag = 0
            break
    if flag:
        ans += 1
print(ans)

Measured memory_bytes: 72064
from collections import*
mod=10**9+7
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dx=[0,1]
dy=[1,0]
d=[[0]*w for _ in range(h)]
v=[[0]*w for _ in range(h)]
d[0][0]=1
q=deque([(0,0)])
while q:
  x,y=q.popleft()
  if v[x][y]:continue
  v[x][y]=1
  for i,j in zip(dx,dy):
    nx=x+i
    ny=y+j
    if 0<=nx<h and 0<=ny<w and a[nx][ny]==".":
      d[nx][ny]+=d[x][y]
      d[nx][ny]%=mod
      q.append((nx,ny))
print(d[-1][-1])

Measured memory_bytes: 108640
#include<stdio.h>
#include<math.h>

int main(){
	double x;

	while (scanf("%lf",&x)!=EOF)
	{
		x=x/9.8;
		x=4.9*x*x;
		x=(x+5)/5;
		x=ceil(x);
		printf("%.0f\n",x);
	}

	return 0;
}

Measured memory_bytes: 652
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> pos(M);
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        pos[i] = make_pair(a,b);
    }
    vector<int> temp;
    for(int i = 0; i < M; i++){
        if(pos[i].first==1){
            temp.push_back(pos[i].second);
         }
        if(pos[i].second==1){
            temp.push_back(pos[i].first);
        }
    }
    sort(temp.begin(), temp.end());
    bool ans = false;
    for(int i = 0; i < M; i++){
        if(pos[i].first == N){
            //cout << pos[i].first << " " << pos[i].second << "\n";
             if(binary_search(temp.begin(), temp.end(), pos[i].second)){
                ans = true;
                break;
            }
        }
        if(pos[i].second == N){
            if(binary_search(temp.begin(), temp.end(), pos[i].first)){
                ans = true;
                break;
            }
        }
    }
    if(ans){
        cout << "POSSIBLE" << "\n";
    }else{
        cout << "IMPOSSIBLE" << "\n";
    }
    return 0;
}

Measured memory_bytes: 2428
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline().rstrip())
p = [int(readline().rstrip()) for i in range(n)]
print(sum(p) - max(p) // 2)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define rep(i,a) for(auto i=0;i<a;i++)
#define rbf(it,a) for(auto &it:a)
using namespace std;

int main(){
	cout<<fixed;
	while(true){
		int n,w;
		cin>>n>>w;
		if((n|w)==0)break;
		map<int,int> cnt;
		rep(i,n){
			int h;
			cin>>h;
			cnt[h/w]++;
		}
		int h_max,w_max;
		h_max=w_max=0;
		rbf(it,cnt){
			h_max=max(h_max,it.second);
			w_max=max(w_max,it.first);
		}
		double res=0;
		rbf(it,cnt){
			double h=it.second;
			double w=it.first;
			h=h/h_max;
			w=(w_max-w)/w_max;
			res+=h*w;
		}
		cout<<res+0.01<<endl;


	}
	return 0;
}

Measured memory_bytes: 1256
#include<stdio.h>

int main()
{
	int n;
	int i;
	int count = 0;
	int s[30];

	scanf("%d", &n);

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

	for(i = 1; i < n-1; i++){
		if((s[i-1] < s[i] && s[i] <  s[i+1]) || (s[i-1] > s[i] && s[i] >  s[i+1])) count++;
	}

	printf("%d", count);
	
	return 0;
}	

Measured memory_bytes: 128
#prag\
ma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

struct node{
	int x,y,t;
}q[2501];
bool a[51][51],vis[51][51];
int d[4][2]={0,1,0,-1,1,0,-1,0};
int main()
{
	ios::sync_with_stdio(false);
	int n,m,tot=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			char c;
			cin>>c;
			if(c=='.') a[i][j]=1,tot++;
		}
	if(!a[1][1]||!a[n][m]){
		cout<<-1;return 0;
	}
	int t=1,w=1;
	q[1].x=1,q[1].y=1,q[1].t=1;vis[1][1]=1;
	while(t<=w){
		for(int i=0;i<4;i++){
			int x=q[t].x+d[i][0],y=q[t].y+d[i][1];
			if(x>0&&x<=n&&y>0&&y<=m&&a[x][y]&&!vis[x][y]){
				++w,q[w].x=x,q[w].y=y,q[w].t=q[t].t+1;
				if(x==n&&y==m){
					cout<<tot-q[w].t;
					return 0;
				}
				vis[x][y]=1;
			}
		}
		++t;
	}
	cout<<-1;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<climits>
#include<set>
#include<map>
#define ll long long
using namespace std;

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

}


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

int main(void){
    int n,k,s;
    cin >> n >> k >> s;
    int a;
    if(s != 1000000000)a = 1000000000;
    else a = 1;
    
    if(k == 0){
        cout << a;
        for(int i = 1;i < n;i++)cout << " " << a;
    } else {
        for(int i = 0,j = 0;i < n;i++){
            if(j < k){
                cout << s;
                j++;
            }
            else cout << a;
            if(i+1 != n)cout << " ";
        }
    }
}

Measured memory_bytes: 1280
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

const int INF = 123456789;
const int N_MAX = 100000;

vector<int> G[N_MAX];
queue<int> q;
int d[3*N_MAX];

int main() {
	int n, m, s, t;
	scanf("%d %d", &n, &m);
	for(int i=0;i<m;i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		G[u-1].push_back(v-1);
	}
	scanf("%d %d", &s, &t);
	s--; t--;
	for(int i=0;i<3*n;i++) d[i] = INF;
	q.push(s);
	d[s] = 0;
	while(!q.empty()) {
		int v = q.front();
		if(v == t) break;
		int mod = v / n;
		int nxmod = (mod + 1) % 3;
		v %= n;
		q.pop();
		for(int i=0;i<G[v].size();i++) {
			if(d[mod*n+v] + 1 < d[nxmod*n+G[v][i]]) {
				d[nxmod*n+G[v][i]] = d[mod*n+v] + 1;
				q.push(nxmod*n+G[v][i]);
			}
		}
	}
	printf("%d\n", d[t] < INF ? d[t]/3 : -1);
	return 0;
}


Measured memory_bytes: 6912
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long[] a = new long[7];
		for(int i=0; i<7; i++)
			a[i] = sc.nextLong();
		
		long ans = a[1] + a[0]/2*2 + a[3]/2*2 + a[4]/2*2;
		
		if(a[0]>=1 && a[3]>=1 && a[4]>=1) {
			ans = Math.max(ans, a[1] + 3 + (a[0]-1)/2*2 + (a[3]-1)/2*2 + (a[4]-1)/2*2);
		}
		
		System.out.println(ans);
		sc.close();
	}
}


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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define MOD 1000000007
#define cey ce("Yes")
#define cen ce("No")
#define ceY ce("YES")
#define ceN ce("NO")

int main()
{

int N, R;
	cin >> N >> R;

	if (N>=10) {
		ce(R)
	}
	else {
		ce(R+100*(10-N))
	}
    return 0;
}



Measured memory_bytes: 768
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)n; i++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007//1e9+7
typedef long long ll;
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int> a(n,0);
  REP(i,n){cin >> a[i];}
  sort(all(a), greater<int>());
  int sa, sb;
  sa = sb = 0;
  int c = 0;
  REP(i,n/2){
    c+= a[2*i] - a[2*i + 1];
  }
  if(n%2 == 1){c += a[n - 1];}
  cout << c << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int h, w;
char  s[maxn][maxn];
int vis[maxn][maxn];
struct node {
    int x, y;
    int val;
};
queue<node> qu;
int xc[] = {1, 0, -1, 0};
int yc[] = {0, 1, 0, -1};

int main() {
    cin >> h >> w;
    int res = 0;
    for (int i = 0; i < h; ++i) {
        cin >> s[i];
        for (int j = 0; j < w;++j) {
            if(s[i][j] == '#'){
              qu.push(node{i, j, 0});
              vis[i][j] = 1;
            }
        }
    }
    while (!qu.empty()) {
        node tmp = qu.front();
        res = max(res, tmp.val);
        qu.pop();
        for (int i = 0; i <4; ++i) {
            int xx = xc[i] + tmp.x;
            int yy = yc[i] + tmp.y;
            if (xx < 0 || yy<0||xx>=h||yy>=w||vis[xx][yy]) {
                continue;
            }
            vis[xx][yy] = 1;
            qu.push(node{xx,yy,tmp.val + 1});
        }
    }
    cout <<res << endl;
    return 0;
}


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


int main(void) {
	int h, w, k, i, j, a[13][1003] = {}, t, l, ans = 1e9;
	string s[13];

	cin >> h >> w >> k;
	for (i = 0; i < h; i++) cin >> s[i];

	for (i = 0; i < h; i++) for (j = 0; j < w; j++) {
		a[i][j] = s[i][j] - '0';
	}

	for (i = 1; i < h; i++) a[i][0] += a[i - 1][0];

	for (j = 1; j < w; j++) a[0][j] += a[0][j - 1];

	for (i = 1; i < h; i++) for (j = 1; j < w; j++) {
		a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
	}

	int lim = 1 << (h - 1);
	for (t = 0; t < lim; t++) {
		int bsum[13][1003] = {}, res = 0;
		vector<int> d;
		l = t;
		i = 0;
		while (l > 0) {
			if ((l & 1) == 1) {
				d.push_back(i);
				res++;
			}
			l >>= 1;
			i++;
		}
		d.push_back(h - 1);

		for (i = 0; i < d.size(); i++) {
			for (j = 0; j < w; j++) {
				if (i == 0) bsum[i][j] = a[d[i]][j];
				else bsum[i][j] = a[d[i]][j] - a[d[i - 1]][j];
			}
		}

		j = 0;
		int bf = -1;
		bool cut;
		while (j < w) {
			cut = false;
			for (i = 0; i < d.size(); i++) {
				if (bf == -1) {
					if (bsum[i][j] > k) cut = true;
				}
				else {
					if (bsum[i][j] - bsum[i][bf] > k) cut = true;
				}
			}
			if (cut) {
				if (bf == j - 1) break;
				bf = j - 1;
				res++;
			}
			else {
				j++;
			}
		}
		if (j == w) ans = min(ans, res);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    int ret = 100000;
    for (int i = 0; i < n; i++) {
        ret += ret * 0.05;
        if (ret%1000) {
            ret = ret - ret % 1000 + 1000;
        }
    }
    cout<<ret<<endl;
    return 0;
}

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

class Procon
{
    public Procon() { }
    static void Main(string[] agrs)
    {
        new Procon().Do();
    }

    Scanner cin;

    public void Do()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        int[] d = cin.arrayInt();

        Array.Sort(d);
        Console.WriteLine(d[N / 2] - d[N / 2 - 1]);
    }
}

class Scanner
{
    string[] s;
    int i;
    int max_i;

    public Scanner()
    {
        s = new string[0];
        max_i = 0;
        i = 0;
    }

    public string nextString()
    {
        if (i >= s.Length)
        {
            s = Console.ReadLine().Split(' ');
            max_i = s.Length;
            i = 0;
            if (max_i == 0)
            {
                return "";
            }
            return s[i++];
        }
        else
        {
            return s[i++];
        }
    }

    public int nextInt()
    {
        return int.Parse(nextString());
    }


    public long nextLong()
    {
        return long.Parse(nextString());
    }

    public double nextDouble()
    {
        return double.Parse(nextString());
    }

    public string[] arrayString()
    {
        return Console.ReadLine().Split(' ');
    }

    public int[] arrayInt()
    {
        string[] str = Console.ReadLine().Split(' ');
        int[] array = new int[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = int.Parse(str[i]);
        }
        return array;
    }

    public long[] arrayLong()
    {
        string[] str = Console.ReadLine().Split(' ');
        long[] array = new long[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = long.Parse(str[i]);
        }
        return array;
    }

    public double[] arrayDouble()
    {
        string[] str = Console.ReadLine().Split(' ');
        double[] array = new double[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = double.Parse(str[i]);
        }
        return array;
    }
}



Measured memory_bytes: 18656
/* ex3_4
    nnasy */

#include <stdio.h>

int main(void) {
    int num;    //整数変数の宣言
    scanf("%d", &num);    //numに入力

    int count = 0;    //整数変数の宣言　ただし、countの値で九九の答えになるかを判断するので初期値は0とする

    for (int i=1; i<10; i++){    //iがnumの因数かつnumが1から9までの二整数の積で表せるとき、countを増やす
        if (num%i==0 && num/i<10){
            count += 1;
        }
    }

    if (count == 0){    //countが0つまりnumが九九の答えでないとき No を、そうでないとき Yes を出力
        printf("No\n");
    }else{
        printf("Yes\n");
    }

    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main(int argc, char const *argv[]){
	int a[3],i,max=0,t,s;
	scanf("%d%d%d",&a[0],&a[1],&a[2]);
	max=a[0];
	if(a[1]>max)max=a[1];
	if(a[2]>max)max=a[2];
	t=3*max;
	s=a[0]+a[1]+a[2];
	if(t%2!=s%2)
		t=3*(max+1);
	printf("%d\n",(t-s)/2);
	return 0;
}

Measured memory_bytes: 128
#include"bits/stdc++.h"
using namespace std;
#define int int64_t
int ar[(int)1e5+10];
int br[(int)1e5+10];
int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b,c,k;cin>>a>>b>>c>>k;
    int ans=0;
    ans+=min(k,a);
    k-=min(k,a);
    k-=min(k,b);
    ans-=min(k,c);
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 3640
"use strict"
function main(arg) {
    const inputs = arg.split("\n")[0].split(" ").map((x)=>{return parseInt(x)})
    const A = inputs[0]
    const B = inputs[1]
    let ans = A
    if (A == B){
        ans = A + B
    }else if(A > B){
        ans = A + A - 1
    }else{
        ans = B + B - 1
    }
    console.log(ans)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using ll = long long;
const ll MOD = 1e9+7; ll LLINF = 1LL << 60; int INF = INT_MAX;

//

int main(){
    // 各アルファベットに対するsetを作って要素が2つ以上ならできない.

    string s,t; cin>>s>>t;
    vector<set<char>> alp1(26);
    vector<set<char>> alp2(26);
    rep(i,0,s.size()){
        alp1[t[i]-'a'].insert(s[i]);
        alp2[s[i]-'a'].insert(t[i]);
    }
    bool ok=true;
    rep(i,0,26){
        if(alp1[i].size()>=2) {ok=false; break;}
        if(alp2[i].size()>=2) {ok=false; break;}
    }
    if(ok==true) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 776
#n=(-2)*?+0or1をして、?を新たなnとする。出てきたあまりを逆にたどれば答え
n=int(input())
L=[]
if n==0:
    print('0')
else:
# if が多数あるときelifでないと計算がおかしくなる
    while n!=0:
        if n>0 and n%2==0:
            n=-n//2
            L.append('0')
        elif n>0 and n%2==1:
            n=(-n+1)//2
            L.append('1')
        elif n<0 and -n%2==0:
            n=-n//2
            L.append('0')
        elif n<0 and -n%2==1:
            n=(-n+1)//2
            L.append('1')
    print(int(''.join(L[::-1])))


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

int main() {
	int num, Harray[100], count = 1;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> Harray[i];
	}
	int high = Harray[0];
	for (int i = 1; i < num; i++) {
		if (Harray[i] >= Harray[i - 1] && Harray[i] >= high) {
			count++;
			high = Harray[i];
		}
	}
	cout << count << endl;
}

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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<int, int> P;


ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}


/******************************************
** A main function is start from here  ****
*******************************************/
int main(){
  int ans=0;
  rep(i, 3){
    int tmp; cin >> tmp;
    ans += tmp;
  }
  if(ans <=21)cout << "win";
  else cout << "bust";
  
  return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
a = LIST()

xor = lambda x, y:x^y

X = reduce(xor, a)

ans = [0]*N
for i, x in enumerate(a):
    ans[i] = X^x
print(*ans)


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

int H, W, K;

int countBlack(vector<string> tmpS){
  int count = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (tmpS[i][j]=='#') {
        count++;
      }
    }
  }
  return count;
}

int main() {
  cin >> H >> W >> K;

  vector<string> S;
  for (int i = 0; i < H; i++) {
    string s;
    cin >> s;
    S.push_back(s);
  }

  int ans = 0;
  for (int bitH = 0; bitH < 1<<H ; bitH++) {
    for (int bitW = 0; bitW < 1<<W ; bitW++) {
      vector<string> tmpS = S;
      for (int i = 0; i < H; i++) {
        if(bitH>>i & 1) {
          for (int w = 0; w < W; w++) {
            tmpS[i][w] = 'R';
          }
        }
      }
      for (int i = 0; i < W; i++) {
        if(bitW>>i & 1) {
          for (int h = 0; h < H; h++) {
            tmpS[h][i] = 'R';
          }
        }
      }
      if (countBlack(tmpS)==K){
        ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

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

int N;
int H[1010];
int dif[1010];
int T, A;
int main(){
  cin >> N >> T >> A;
  for(int i = 0;i < N; i++){
    cin >> H[i];
  }
  for(int i = 0; i < N; i++){
    H[i] = T*1000 - (H[i] * 6);
  } 
  for(int i = 0; i < N; i ++){
    if(H[i] > 1000*A) dif[i] = H[i] - 1000*A;
    else  dif[i] = 1000*A - H[i];
  }
  int min = dif[0];
  int re =1;
  for(int i = 0; i < N; i++){
    if(dif[i] < min){
      min = dif[i];
      re = i+1;
    }
  }
  cout << re << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 500;
const int MAXC = 30;
int D[MAXC + 5][MAXC + 5];
int c[MAXN + 5][MAXN + 5];
long long key[MAXC + 5][3];
int main() {
	int N, C;
	scanf("%d%d", &N, &C);
	for(int i=1;i<=C;i++)
		for(int j=1;j<=C;j++)
			scanf("%d", &D[i][j]);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			scanf("%d", &c[i][j]);
	for(int i=1;i<=C;i++)
		for(int j=1;j<=N;j++)
			for(int k=1;k<=N;k++)
				key[i][(j+k)%3] += 1ll * D[c[j][k]][i];
	long long ans = (1ll<<60);
	for(int i=1;i<=C;i++) {
		for(int j=1;j<=C;j++) {
			if( i == j ) continue;
			for(int k=1;k<=C;k++) {
				if( i == k || j == k ) continue;
				ans = min(ans, key[i][0] + key[j][1] + key[k][2]);
			}
		}
	}
	printf("%lld\n", ans);
}

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

void main_()
{
    array<int, 3> Ns;
    cin >> Ns[0] >> Ns[1] >> Ns[2];
    sort(begin(Ns), end(Ns));

    auto ans = (Ns[2] - Ns[1]) + (Ns[1] - Ns[0] + 1) / 2 + (((Ns[1] - Ns[0]) % 2 == 1) ? 1 : 0);

    cout << ans << endl;
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int,int>
const int maxm=2e5+5;
const int mod=1e9+7;
//n<=2e5
//a[i],b[i]<=2e3
int fac[maxm],inv[maxm];
int a[maxm],b[maxm];
int d[4444][4444];
int n;
int ppow(int a,int b,int mod){
    int ans=1%mod;a%=mod;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void init(){
    fac[0]=1;
    for(int i=1;i<maxm;i++)fac[i]=fac[i-1]*i%mod;
    inv[maxm-1]=ppow(fac[maxm-1],mod-2,mod);
    for(int i=maxm-2;i>=0;i--)inv[i]=(i+1)*inv[i+1]%mod;
}
int C(int n,int m){
    if(m<0||m>n)return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
    init();
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    const int base=2e3+5;//base>2000比较方便,=2000的话下面的dp得从0开始.
    for(int i=1;i<=n;i++){
        d[-a[i]+base][-b[i]+base]++;
    }
    for(int i=1;i<=4010;i++){
        for(int j=1;j<=4010;j++){
            d[i][j]+=d[i-1][j]+d[i][j-1];
            d[i][j]%=mod;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=d[a[i]+base][b[i]+base];
        ans%=mod;
    }
    for(int i=1;i<=n;i++){
        ans-=C(2*(a[i]+b[i]),2*a[i]);
        ans%=mod;
    }
    ans=(ans*ppow(2,mod-2,mod)%mod+mod)%mod;
    cout<<ans<<endl;
    return 0;
}
/*
发现a[i]和b[i]很小,是可以O(n^2)的范围

C(x+y,x)可以看作是(0,0)到(x,y)的方案数,
如果我们要求(0,0)到(x,y)的方案数,
可以令d[i][j]表示(0,0)到(i,j)的方案数,一开始d[0][0]=1.
转移方程为d[i][j]=d[i-1][j]+d[i][j-1].

C(a[i]+a[j]+b[i]+b[j],a[i]+a[j])可以看作:
(0,0)到(a[i]+a[j],b[i]+b[j])的方案数.

枚举i和j是O(n^2)的,显然要优化,
尝试将i和j分开:
将坐标位移一下变为(-a[i],-b[i])到(a[j],b[j])的方案数.
这样i和j就分离了,然后就可以单独计算每个部分的贡献.

观察前面的dp方程,我们一开始令d[0][0]=1,
然后计算出的d[x][y]就是(0,0)到(x,y)的方案数,
那么我们令d[-a[i]][-b[i]]=1,
那么计算出的d[x][y]就是(-a[i],-b[i])到(x,y)的方案数.
这样的话,我们一开始只需要令所有的d[-a[i]][-b[i]]++,
那么计算出来的d[x][y]就是所有数对到达(x,y)的方案数.
因此最后只需要累加d[a[i]][b[i]]即可.
但是存在(-a[i],-b[i])到(a[i],b[i])的方案数,也就是自己和自己匹配,
而题目只需要计算i<j的,因此减掉自己和自己匹配的,方案数为C(2*(a[i]+b[i]),2*a[i]).
最后答案还要再除以2,因为是计算出的是无序的,题目要的是有序的.

参考:
https://www.luogu.com.cn/blog/Ebola-Emperor/solution-at1983
https://www.luogu.com.cn/blog/208529/solution-at1983
*/


Measured memory_bytes: 149072
def bubbleSort(A, N):
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                flag = 1


def selectionSort(A, N):
    count =0
    for i in range(N):
        minidx = i
        for j in range(i,N):
            if A[j] < A[minidx]:
                minidx = j
        if minidx == i:
            continue
        A[i],A[minidx] = A[minidx],A[i]
        count += 1
    return count



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

count = selectionSort(A, N)
print(" ".join(map(str, A)))
print(count)


Measured memory_bytes: 5600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll a,b,n;
    cin>>a>>b>>n;
    if(n<b)
	cout<<(a*n)/b-a*(n/b)<<"\n";
	else
		cout<<(a*(b-1))/b-a*((b-1)/b)<<"\n";
	return 0;
}

Measured memory_bytes: 3596
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int Limit=100001;
using edge = struct{int to;};
vector<edge> Tree[Limit]; // vector の配列
int Depth[2][Limit] = {};

void dfs(int playerNum , int currentPoint, int parentPoint , int64_t d )
{
	Depth[playerNum][currentPoint] = d;
	for(auto &e : Tree[currentPoint] ){
		if (e.to == parentPoint){continue;}
		dfs(playerNum, e.to, currentPoint, d + 1);
	}
}

int main(int argc , char **argv)
{
	(void)argc;
	(void)argv;

	int N;
	cin >> N;
	for(int i=0; i<N-1; i++){
		int a,b;
		cin >> a >> b;
		a--;b--;
		Tree[a].push_back({b});
		Tree[b].push_back({a});
	}

	dfs(0,0,-1,0); // Fennec 側からの距離を求める
	dfs(1,N-1,-1,0); // Snuke 側からの距離を求める

	int sum_Fennec = 0, sum_Snuke = 0;
	for(int i=0; i<N; i++){
		if (Depth[0][i] <= Depth[1][i]){sum_Fennec++;}else{sum_Snuke++;}
	}
	if (sum_Fennec <= sum_Snuke){
		printf("Snuke\n");
	}else{
		printf("Fennec\n");
	}

	return 0;
}


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

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define all(x) (x).begin(), (x).end()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<int MOD> struct modnum {
    int v;
    modnum() : v(0) {}
    modnum(ll _v) : v(_v % MOD) { if (v < 0) v += MOD; }
    explicit operator int() const { return v; }
    friend ostream& operator << (ostream& o, const modnum& n) { return o << n.v; }
    friend istream& operator << (istream& i, modnum& n) { ll v; i >> v; n = modnum(v); return i; }

    friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
    friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

    modnum& operator += (const modnum& o) { v += o.v; if (v >= MOD) v -= MOD; return *this; }
    modnum& operator -= (const modnum& o) { v -= o.v; if (v < 0) v += MOD; return *this; }
    modnum& operator *= (const modnum& o) { v = int(ll(v) * ll(o.v) % MOD); return *this; }
    modnum operator - () { modnum res; if (v) res.v = MOD - v; return res; }
    friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
    friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
    friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }

    modnum pow(int e) const {
        if (e == 0) return 1;
        if (e & 1) return *this * this->pow(e-1);
        return (*this * *this).pow(e/2);
    }

    modnum inv() const {
        int g = MOD, x = 0, y = 1;
        for (int r = v; r != 0; ) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        }

        assert(g == 1);
        assert(y == MOD || y == -MOD);
        return x < 0 ? x + MOD : x;
    }
    modnum& operator /= (const modnum& o) { return (*this) *= o.inv(); }
    friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= modnum(b); }
};
using mn = modnum<1000000007>;

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

    int N;
    cin >> N;

    vi vals(N);
    for (int i = 0; i < N; i++) {
        cin >> vals[i];
    }

    vector<mn> ways(N + 1), tot(int(2e5 + 1));
    ways[N] = 1;

    for (int i = N - 1; i >= 0; i--) {
        if (i == N - 1 || vals[i+1] != vals[i])
            tot[vals[i]] += ways[i + 1];
        ways[i] = tot[vals[i]];
    }

    cout << ways.front() << endl;

    return 0;
}



Measured memory_bytes: 2560