akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define N 10005
#define INF (long long)12345679*12345679
using namespace std;
long long dp[N];
struct node
{
	int h,p;
	bool operator < (node b)
	{
		return h+p<b.h+b.p;
	}
}a[N];
int n;
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d%d",&a[i].h,&a[i].p);
	sort(a+1,a+n+1);
	for (int i=1;i<=n;i++)
		dp[i]=INF;
	dp[0]=0;
	
	for (int i=1;i<=n;i++)
		for (int j=i;j>=1;j--)
			if (dp[j-1]<=a[i].h)
				dp[j]=min(dp[j],dp[j-1]+a[i].p);
	for (int i=0;i<=n;i++)
		if (dp[i]==INF)
		{
			printf("%d\n",i-1);
			return 0;
		}
	printf("%d\n",n);
	return 0;
}

Measured memory_bytes: 3832
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<cmath>
#include<bitset>
#include<cassert>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<fstream>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main()
{
    fast_io;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    string str;
    cin >> str;

    ll sum = 0;
    for (auto i : str)
        sum += (i - '0');

    if (sum % 9 == 0)
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3368
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, a;

int main(){
	cin >> n;
	ll cnt = 0;
	for(ll i = 1; i <= n; i++){
		cin >> a;
		if(a%2 == 1){cnt++;}
	}
	
	if(cnt%2 == 0){cout << "YES" << endl;}
	else{cout << "NO" << endl;}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
#include<math.h>
using namespace std;
int main()
{
    int a,b,c,d,e,f,g,h,i,j,k=0;
    cin>>a>>b>>c;
    if(a==b&&b==c&&c==a)
    {
        cout<<"No"<<endl;
    }
    else if(a==b||b==c||c==a)
    {
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;

}


Measured memory_bytes: 256
k = int(input())

ans = [
1,
9,
30,
76,
141,
267,
400,
624,
885,
1249,
1590,
2208,
2689,
3411,
4248,
5248,
6081,
7485,
8530,
10248,
11889,
13687,
15228,
17988,
20053,
22569,
25242,
28588,
31053,
35463,
38284,
42540,
46581,
50893,
55362,
61824,
65857,
71247,
76884,
84388,
89349,
97881,
103342,
111528,
120141,
128047,
134580,
146316,
154177,
164817,
174438,
185836,
194157,
207927,
218812,
233268,
245277,
257857,
268182,
288216,
299257,
313635,
330204,
347836,
362973,
383709,
397042,
416448,
434025,
456967,
471948,
499740,
515581,
536073,
559758,
583960,
604833,
633651,
652216,
683712,
709065,
734233,
754734,
793188,
818917,
846603,
874512,
909496,
933081,
977145,
1006126,
1041504,
1073385,
1106467,
1138536,
1187112,
1215145,
1255101,
1295142,
1342852,
1373253,
1422195,
1453816,
1502376,
1553361,
1595437,
1629570,
1691292,
1726717,
1782111,
1827492,
1887772,
1925853,
1986837,
2033674,
2089776,
2145333,
2197483,
2246640,
2332104,
2379085,
2434833,
2490534,
2554600,
2609625,
2693919,
2742052,
2813988,
2875245,
2952085,
3003306,
3096024,
3157249,
3224511,
3306240,
3388576,
3444609,
3533637,
3591322,
3693924,
3767085,
3842623,
3912324,
4027884,
4102093,
4181949,
4270422,
4361548,
4427853,
4548003,
4616104,
4718640,
4812789,
4918561,
5003286,
5131848,
5205481,
5299011,
5392008,
5521384,
5610705,
5739009,
5818390,
5930196,
6052893,
6156139,
6239472,
6402720,
6493681,
6623853,
6741078,
6864016,
6953457,
7094451,
7215016,
7359936,
7475145,
7593865,
7689630,
7886244,
7984165,
8130747,
8253888,
8403448,
8523897,
8684853,
8802826,
8949612,
9105537,
9267595,
9376656,
9574704,
9686065,
9827097,
9997134,
10174780,
10290813,
10493367,
10611772,
10813692
]

print(ans[k-1])

Measured memory_bytes: 9384
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
#define ll long long int

#define repab(i,a,b) for(int i=(a);i<=(b);i++)
#define reprab(i,a,b) for(int i=(a);i>=(b);i--)
#define repll(i,a,b) for(ll i=(a);i<=(b);i++)
#define rep(i,n) for(int i=(0);i<(n);i++)

ll max(ll a,ll b)
{
    if(a>b)return a;return b;
}
ll min(ll a,ll b)
{
    if(a<b)return a;return b;
}

ll mypow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll gcd(ll a,ll b)
{
    if(b==0)
    return a;
    return gcd(b,a%b);
}
//..............................!!!!!!Get ready to fight!!!!!!............................
ll solve(ll a[],ll n){
    
    ll dp[n+1];
    dp[1]=0;
    dp[2]=abs(a[2]-a[1]);
    for(ll i=3;i<=n;i++){
       
        dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    }
    return dp[n];
}

int main()
{   
     
    ll n;
    cin>>n;
    ll a[n+1];
    repab(i,1,n)cin>>a[i];
    cout<<solve(a,n);
   
    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>

int main(){

	int a, b;

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

	if(a < b){
		printf("a < b\n");
	}
	else if(a > b){
		printf("a > b\n");
	}
	else{
		printf("a == b\n");
	}

	return 0;
}

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

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

using namespace std;
using ll = long long;
int mod = 1000000007;

int main(void){
    int N; cin >> N;
    ll A[N]; rep(i, N) cin >> A[i];
    ll acc[N] = {}; acc[0] = A[0]; rep(i, N-1) acc[i+1] = acc[i] + A[i+1];
    ll ans = powl(10, 15);
    rep(i, N-1){
        ll eval = 0;
        if(acc[i]*2 > acc[N-1]){
            eval = 2*acc[i] - acc[N-1];
        }
        else{
            eval = acc[N-1] - 2*acc[i];
        }
        ans = min(ans, eval);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3328
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long INF=1e18;

struct ST {

  vector<long long> t;
  vector<long long> lazy;

  ST(int N) {
    t.assign(N*4+1, 0);
    lazy.assign(N*4+1, 0);
  }

  void push(int nodeid) {
    t[nodeid*2] += lazy[nodeid];
    t[nodeid*2+1] += lazy[nodeid];
    lazy[nodeid*2] += lazy[nodeid];
    lazy[nodeid*2+1] += lazy[nodeid];
    lazy[nodeid] = 0;
  }

  void update(int l, int r, int ql, int qr, int nodeid, long long addvalue) {
    if(ql > qr) return;
    if (l==ql && r==qr) {
      t[nodeid] += addvalue;
      lazy[nodeid] += addvalue;
    } else {
      push(nodeid);
      int m = (l + r) / 2;
      
      update(l  , m, ql          , min(m, qr), nodeid*2  , addvalue);
      update(m+1, r, max(m+1, ql), qr        , nodeid*2+1, addvalue);

      t[nodeid] = max( t[nodeid*2], t[nodeid*2+1] );
    }
  }

  long long query(int l, int r, int ql, int qr, int nodeid) {
    if (ql > qr) return -INF;
    if (l>=ql && r <=qr) return t[nodeid];
    push(nodeid);
    int m = (l+r) / 2;
    return max(
      query(l  , m, ql          , min(m, qr), nodeid*2  ),
      query(m+1, r, max(m+1, ql), qr        , nodeid*2+1)
    );
  }
};

struct seg {
  int start, end, value;
};

vector<seg> l;

int main() {

  int N, M;

  cin >> N >> M;

  l.resize(M);

  vector< vector<int> > open_seg(N+1), close_seg(N+1);
  
  ST st(N+1);

  for (int i=0; i<M; i++) {
    cin >> l[i].start >> l[i].end >> l[i].value;
    open_seg[ l[i].start ].push_back(i);
    close_seg[ l[i].end ].push_back(i);
  }

  for (int i=1; i<=N; i++) {
    for (int si: open_seg[i]) {
      st.update(0, N, 0, l[si].start-1, 1, l[si].value);
    }

    auto dp = st.query(0, N, 0, i-1, 1);
    st.update(0, N, i, i, 1, dp);

    for (int si: close_seg[i]) {
      st.update(0, N, 0, l[si].start-1, 1, -l[si].value);
    }

  }
  cout << st.query(0, N, 0, N, 1) << endl;

  return 0;
}

Measured memory_bytes: 36992
// in the name of god 
// vaght hast vali kam ast !

#include <bits/stdc++.h>
using namespace std ;

const int MAXN = 1e6 + 100 ;

bool vis[MAXN] ; 
int32_t main(){
	ios_base::sync_with_stdio(0) ;
	cin . tie(0) ; cout . tie(0) ; 

	string s ; cin >> s ; 
	int res = 0 , ans = MAXN , help = 0 ; 
	for(char ch = 'a' ; ch <= 'z' ; ch ++){
		for(int i = 0 ; i < s . size() ; i ++){
			if(s[i] == ch)help = 0 ; 
			else help ++ ; 
			res = max(help , res) ; 
		}
		ans = min(ans , res) ;
		help = 0 ; 
		res = 0 ; 
	}
	cout << ans << '\n'; 


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;

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

  long long a, b;
  cin >> a >> b;
  if(a > 9 or b > 9){
    cout << "-1\n";
  }else{
    cout << a*b << endl;
  }
  return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

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

    ll N, K;
    cin >> N >> K;
    vector<ll> h(N);
    REP(i, N) cin >> h[i];
    sort(h.begin(), h.end());

    ll res= (1ll<<60);
    REP(i, N-K+1){
    	chmin(res, h[i+K-1]-h[i]);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1024
t;
main(N){
    int a=1000000,b=-1000000;
    long long c=0;
    for(scanf("%d",&N);N--;c+=t){
        scanf("%d",&t);
        if(a>t)a=t;
        if(b<t)b=t;
    }
    printf("%d %d %lld\n",a,b,c);
}

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

int n;
// n?????°????°????????????§?????¨??¢?´¢??§??¨??????
bool existsCombination(int* A, int sum, int left){
	// left??°?????????????´?????????????????´??????????????????????????¨?sum?????§?????????
	if(left >= n) return false; 
	if(sum == A[left]) return true;
	else
		return existsCombination(A, sum, left+1) || existsCombination(A, sum-A[left], left+1);

}


int main(){

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

	int q;
	cin >> q;
	int m[q];
	for(int i=0; i<q; i++) cin >> m[i];

	for(int i=0; i<q; i++){
		if(existsCombination(A, m[i], 0))
			cout << "yes" << endl;
		else
			cout << "no" << endl;
	}

	return 0;
}

Measured memory_bytes: 3072
/*
 ID: bradyawn
 PROG: contest
 LANG: C++11
 */

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <deque>
#include <string>
#include <cmath>
#include <map>
#include <unordered_map>
#include <utility>
#include <set>
#include <unordered_set>
#include <ctime>
#include <queue>
#include <stack>
#include <bitset>
#include <random>
#include <cstring>
#include <functional>

using namespace std;

typedef long long ll;
typedef pair<int,int> i2;
typedef pair<ll,ll> ll2;

int n;
ll c;

ll xVal[100002];
ll v[100002];
int f[100002];
int f2[100002];

ll calc(int a, int b) //a to b
{
    if (a < b) return -1e18;
    
    ll ret = 0;
    
    ll x = c-xVal[a];
    ll y = xVal[b];
    
    
    ret += v[n]-v[a-1]; //cover x
    ret += v[b]; //cover y

    ret -= min({2*x + y, 2*y + x, xVal[n], c-xVal[1]});
    
    if (a == b)
    {
        return v[n] - min({2*x + y, 2*y + x, xVal[n], c-xVal[1]});
    }
    
    return ret;
}

ll solve()
{
    ll ret = 0;
    
    for (int a = 0; a <= n+1; a++) //fix A
    {
        ret = max(ret, calc(a,f[a]));
        ret = max(ret, calc(a,f2[a]));
        
        //cout << a << ' ' << f[a] << '\n';
        //cout << calc(a, f[a]) << "\n\n";
    }

    return ret;
}

int main()
{
    //ifstream inf("");
    //ofstream outf("");
    //cout << setprecision(10);
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> c;
    
    for (int i = 1; i <= n; i++) cin >> xVal[i] >> v[i];
    for (int i = 1; i <= n; i++) v[i] += v[i-1];
    xVal[n+1] = c;
    xVal[0] = 0;
    
    
    ll mx = 0;
    int w = 0; //best choice for B
    for (int i = 0; i <= n+1; i++)
    {
        ll cur = v[i]-xVal[i];
        f[i] = w;
        if (cur > mx)
        {
            mx = cur;
            w = i;
        }
    }
    
    mx = 0;
    w = 0; //best choice for B
    for (int i = 0; i <= n+1; i++)
    {
        ll cur = v[i]-2*xVal[i];
        f2[i] = w;
        if (cur > mx)
        {
            mx = cur;
            w = i;
        }
    }
    
    cout << solve() << '\n';
    
    return 0;
    
}




Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define MOD 1e9+7
#define EPS 1e-8
#define INF 1e9+10
typedef long long ll;
using namespace std;
int main()
{
  int X,Y;
  cin >> X >> Y;
  ll ans=0;
  if(X==1){ans+=300000;}
  else if(X==2){ans+=200000;}
  else if(X==3){ans+=100000;}
  if(Y==1){ans+=300000;}
  else if(Y==2){ans+=200000;}
  else if(Y==3){ans+=100000;}

if(X==1&&Y==1){ans+=400000;}
cout << ans << endl;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
	char S[11];
	scanf("%s", S);

	int i, judge, num_c;
//	printf("%ld\n", strlen(S));
	for (i = 0, judge = 0, num_c = 0; i < strlen(S); i++) {
		if (i == 0) {
			if (S[0] != 'A')
				judge = 1;
		} else if (i >= 2 && i <= strlen(S)-2) {
			if (S[i] == 'C')
				num_c++;
			else if (S[i] <= 'Z' && S[i] >= 'A')
				judge = 1;
		} else {
			if (S[i] >= 'A' && S[i] <= 'Z') 
				judge = 1;
		}
	}
	
	if (judge == 0 && num_c == 1)
		printf("AC\n");
	else
		printf("WA\n");

	return 0;
}


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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

typedef long long ll;
typedef long double R;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

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

// Problem Specific Parameter:

int main() {
  int A, B; cin >> A >> B;
  if(A <= 5) {
    cout << 0 << endl;
  } else if(A <= 12) {
    cout << B/2 << endl;
  } else {
    cout << B << endl;
  }

  return 0;
}


Measured memory_bytes: 256
n = int(input())
l = sorted(list(list(map(int,input().split())) for _ in range(n)), key=lambda x:x[1])
t = 0
amari = 0
for a,b in l:
  #print(a,b,t,amari)
  if b-t>=a:
    amari += (b-t)-a
    t = b
  else:
    if amari>=a-(b-t):
      amari -= a-(b-t)
      t = b
    else:
      print("No")
      exit()
 # print(a,b,t,amari)
print("Yes")

Measured memory_bytes: 55264
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
int main(){
    long long n, k; cin >> n >> k;
    long long m = n;
    if(n % k == 0) {
        cout << 0;
        return 0;
    }   
    if(n > k) {
        n = n % k;
    }
    else {
        cout << min(n, k - n);
        return 0;
    }
    cout << min(m, min(n, abs(k - n)));
    return 0;
}

Measured memory_bytes: 256
n=int(input())
f=[0]*45
def Fib(n):
    if n==0:
        return 1
    elif n==1:
        return 1
    else:
        if f[n]!=0:
            return f[n]
        else:
            f[n]=Fib(n-1)+Fib(n-2)
            return f[n]
print(Fib(n))
    


Measured memory_bytes: 5600
#include<stdio.h>
int main(void){
  int k,x,i;
  scanf("%d",&k);
  scanf("%d",&x);
  for(i=k-1;i>0;i--){
    printf("%d ",x-i);
  }
  printf("%d ",x);
  for(i=k-1;i>0;i--){
    x += 1;
    printf("%d ",x);
  }
  printf("\n");
  return 0;
}
  
  

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

int ctoi(char c){
    switch(c){
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        default : return -1;
    }
}

int main(){

    string N;
    cin >> N;

    int sum = 0;
    rep (i, N.size()){
        sum += ctoi(N[i]);
    }

    if (sum%9 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3752
n = gets.to_i
S = gets.split.map(&:to_i)
q = gets.to_i
T = gets.split.map(&:to_i)

  cnt= 0
  T.each do |x|
    s = S + [x]
    i = 0
    while x != s[i]
      i += 1
    end
    cnt += 1 if i != n
  end
  puts cnt



Measured memory_bytes: 14948
from collections import defaultdict

n = int(input())
a = tuple(map(int, input().split()))

if n == 3:
    if a[0] ^ a[2] == a[1] and a[1] ^ a[2] == a[0] and a[0] ^ a[1] == a[2]:
        print('Yes')
    else:
        print('No')
elif n % 3 == 0:
    d = defaultdict(int)
    for aa in a:
        d[aa] += 1
    m = n // 3
    bl = True
    t = []
    for k, v in d.items():
        if v % m != 0:
            bl = False
            break
        else:
            q = v // m
            t.append((k, q))

    if len(t) == 3:
        if t[0][0] ^ t[1][0] == t[2][0] and t[1][0] ^ t[2][0] == t[0][0] and t[2][0] ^ t[0][0] == t[1][0]:
            pass
        else:
            bl = False
    elif len(t) == 2:
        if t[0][1] > t[1][1]:
            if t[0][0] ^ t[0][0] == t[1][0] and t[0][0] ^ t[1][0] == t[0][0]:
                pass
            else:
                bl = False
        else:
            if t[1][0] ^ t[1][0] == t[0][0] and t[0][0] ^ t[1][0] == t[1][0]:
                pass
            else:
                bl = False


    elif len(t) == 1:
        if t[0][0] != 0:
            bl = False

    print('Yes' if bl else 'No')

else:
    if all(aa == 0 for aa in a):
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 15364
// J'aime
// Chemise Blanche

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  vector<int> a(3);
  for (auto &i : a) cin >> i;
  int k; cin >> k;
  sort(all(a));
  for (int i = 0; i < k; i++) {
    a[2] *= 2;
  }
  cout << a[0] + a[1] + a[2] << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define sf1(n) scanf("%d",&n)
#define sf2(n,q) scanf("%d %d",&n,&q)
#define f first
#define ss second
#define pb push_back
#define lli long long
#define mem(ar,false) memset(ar,false,sizeof(ar))
#define mpr make_pair
#define endl "\n"
#define mod 1000000007
#define inf 9000000000000000000LL
#define M 200005

using namespace std;



int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    lli ans = -inf;

    lli a,b,c,d;
    cin >> a >> b >> c >> d;

    ans = max(ans,a*c);
    ans = max(ans,a*d);
    ans = max(ans,b*c);
    ans = max(ans,b*d);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3684
N,X = map(int,input().split())
donut_count = 0
cheep_donut = 1001
for n in range(N):
    donut = int(input())
    X -= donut
    donut_count += 1
    if donut < cheep_donut:
        cheep_donut = donut
while X >= cheep_donut:
    donut_count += 1
    X -= cheep_donut

print(donut_count)


Measured memory_bytes: 2940
# coding: utf-8
n = int(input())
dic = {}
for i in range(n):
    t = ''.join(sorted(input()))
    dic.setdefault(t, 0)
    dic[t] += 1
ans = 0
for x in dic.values():
    ans += x * (x - 1) // 2
print(ans)

Measured memory_bytes: 62040
#include <stdio.h>

int main()
{
    int l,r,d;
    int i;
    int count = 0;

    scanf("%d %d %d\n", &l, &r, &d);

    for (i = l; i <= r; i++)
    {
        if (i % d == 0)
        {
            count++;
        }
        
    }

    printf("%d\n", count);

    return 0;
    
}

Measured memory_bytes: 2140
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

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

int main() {
  ll N, M;
  cin >> N >> M;
  ll dai = max(N, M);
  ll sho = min(N, M);

  ll ans = 0;
  if (sho == 1) {
    if (dai == 1) ans = 1;
    else ans = dai - 2;
  } else if (sho == 2) {
    ans = 0;
  } else {
    ans = (sho - 2) * (dai - 2);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin,(a).end()
#define vi vector<int>
#define pb push_back
#define INF 999999999

#define MAX_V 100
vector<int> G[MAX_V];
vector<int> rG[MAX_V];

vector<double> p;


void add_edge(int from, int to){
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(int v, bool used[MAX_V], vector<int> &vs){
	used[v] = true;
	rep(i, G[v].size()){
		if(!used[G[v][i]]) dfs(G[v][i], used, vs);
	}
	vs.push_back(v);
}

void rdfs(int v, int k, vector<int> &sccs, vector<int> &cmp, bool used[MAX_V], vector<double> &elm){
	used[v] = true;
	sccs.push_back(v);
	cmp[v] = k;
	elm[k] *= p[v];
	rep(i, rG[v].size()){
		if(!used[rG[v][i]]) rdfs(rG[v][i], k, sccs, cmp, used, elm);
	}
}

int scc(int V, vector< vector<int> > &each_scc, vector<int> &cmp, vector<double> &elm) {
	vector<int> vs;
	bool used[MAX_V];
	rep(i, MAX_V) used[i] = false;
	vs.clear();
	rep(v, V){
		if(!used[v]) dfs((int)v, used, vs);
	}
	rep(i, MAX_V) used[i] = false;
	int k=0;
	for(int i=(int)vs.size()-1; i >=0; i--){
		vector<int> sccs;
		if(!used[vs[i]]){
			rdfs(vs[i], k++, sccs, cmp, used, elm);
			each_scc.push_back(sccs);
		}
	}
	return k;
}

void getSccedGraph(vector<vector<int>> each_scc, vector<int> cmp, vector<int> newGraph[MAX_V]){
	rep(i, each_scc.size()){
		set<int> edges;
		rep(j, each_scc[i].size()){
			rep(k, G[each_scc[i][j]].size()){
				int to = G[each_scc[i][j]][k];
				if(cmp[to] != i) edges.insert(cmp[to]);
			}
		}
		for(auto &edge:edges) newGraph[i].pb(edge);
	}
}

int main(){
	int n;
	while(cin >> n&&n){
		rep(i,MAX_V){
			G[i].clear();
			rG[i].clear();
		}
		
		p.clear();
		p.resize(n);
		rep(i,n){
			cin >> p[i];
			int m;
			cin >> m;
			rep(j, m){
				int a;
				cin>>a;
				add_edge(i,a-1);
			}
		}
		vector<vector<int>> each_scc;
		vector<int> cmp(MAX_V);
		vector<double> elm(MAX_V,1.0);
		int k=scc(n,each_scc,cmp,elm);
		
		vector<int> newGraph[MAX_V];
		getSccedGraph(each_scc,cmp,newGraph);
		
		vector<int> nyuuji(MAX_V,0);
		rep(i,k){
			rep(j,newGraph[i].size()){
				nyuuji[newGraph[i][j]]++;
			}
		}
		double ans=1.0;
		rep(i,k){
			if(nyuuji[i]==0){
				if(elm[i]==1)continue;
				ans*=(1-elm[i]);
			}
		}
		printf("%.9lf\n",ans);
	}
}

Measured memory_bytes: 3376
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxm=1e6+5;
int pre[maxm];
int num[maxm];
int n,m;
int ffind(int x){
    return pre[x]==x?x:pre[x]=ffind(pre[x]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        pre[i]=i;
        num[i]=1;
    }
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        int x=ffind(a);
        int y=ffind(b);
        if(x==y)continue;
        pre[x]=y;
        num[y]+=num[x];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(pre[i]==i){
            ans=max(ans,num[i]);
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
有n个人，给定m个点对<a,b>，表示a和b是朋友，
如果<a,b>且<b,c>那么<a,c>，即关系举有传递性，
保证m对关系没有自环,但是可能有重边。
现在你要将这n个人分成若干个团体，
要求每个团体里的人两两不是朋友关系。
问最少分成多少个团体。

数据范围：n,m<=2e5

仔细想了想,因为朋友关系具有传递性,
那么并查集合并之后,每个集合内部就是完全图,
假设集合内有n个人,要将他们拆开,那么要分成n堆.
那么并查集维护一下集合人数,对所有集合的人数取max就是答案.
*/


Measured memory_bytes: 5184
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    long n;
    scanf("%ld", &n);
    vector<long> viMax(n);
    vector<long> viMin(n);
    for(long i = 0; i < n; i++){
        scanf("%ld %ld", &viMin[i], &viMax[i]);
    }
    sort(viMax.begin(), viMax.end());
    sort(viMin.begin(), viMin.end());
  
    if(n % 2 == 1){
        long i = viMax[n / 2];
        long j = viMin[n / 2];
        printf("%ld", i - j + 1);
    } else {
        long i = viMax[n / 2] + viMax[n / 2 - 1]; //2倍
        long j = viMin[n / 2] + viMin[n / 2 - 1];
        printf("%ld", i - j + 1);
    }
    return 0;
}

Measured memory_bytes: 6044
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int A, B, C;
    cin >> A >> B >> C;

    if (A == B){
        cout << C << endl;
    }
    else if (B == C){
        cout << A << endl;
    }
    else {
        cout << B << endl;
    }
}

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


void solve(long long H, long long W, std::vector<std::vector<long long>> c, std::vector<std::vector<long long>> A){
    const ll INF = numeric_limits<ll>::max();

    for (int k=0;k<10;k++){
        for (int i=0;i<10;i++){
            for (int j=0;j<10;j++){
                if (c[i][k] != INF && c[k][j] != INF && c[i][k]+c[k][j]<c[i][j]){
                    c[i][j] = c[i][k]+c[k][j];
                }
            }
        }
    }
    ll final_cost=0;
    for (int i=0;i<H;i++){
        for (int j=0;j<W;j++){
            if (A[i][j] !=-1) final_cost+=c[A[i][j]][1];
            else final_cost=final_cost;
        }
    }
printf("%lld\n",final_cost);


}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    std::vector<std::vector<long long>> c(9-0+1, std::vector<long long>(9-0+1));
    for(int i = 0 ; i < 9-0+1 ; i++){
        for(int j = 0 ; j < 9-0+1 ; j++){
            scanf("%lld",&c[i][j]);
        }
    }
    std::vector<std::vector<long long>> A(H, std::vector<long long>(W));
    for(int i = 0 ; i < H ; i++){
        for(int j = 0 ; j < W ; j++){
            scanf("%lld",&A[i][j]);
        }
    }
    solve(H, W, std::move(c), std::move(A));
    return 0;
}


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

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

int main(){

    int A,P; cin >> A >> P;

    int piece = A*3;
    int allPiece = piece + P;
    
    if((allPiece/2)<=0){
        cout << 0 << endl;
    }else{
        cout << allPiece/2 << endl;
    }



}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n,i,x=1;
  char s[11];
  scanf("%s",s);
  for(n=0;s[n];n++);
  for(i=1;i<n;i++){if(s[i]=='C')x*=2;else if(s[i]<'a')x=0;}
  printf(x==2&&s[0]=='A'&&s[1]!='C'&&s[n-1]!='C'?"AC":"WA");
}


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

using lli = long long int;
const lli INF = 1LL<<60;

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

template <class T>ostream &operator<<(ostream &o,const pair<T, T>&p)
{o<<"("<<p.first<<", "<<p.second<<")";return o;}

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

int main(void){
    int n;
    cin >> n;
    vector<lli> a(n), b(n), c(n);
    for(int i = 0; i < n; i++){
        cin >> a.at(i);
        cin >> b.at(i);
        cin >> c.at(i);
    }
    lli dp[100010][3];
    for(int i = 0; i < 100010; i++){
        for(int j = 0; j < 3; j++){
            dp[i][j] = -INF;
        }
    }
    for(int k = 0; k < 3; k++) dp[0][k] = 0;
    for(int i = 1; i <= n; i++){
        chmax(dp[i][0], dp[i-1][1]+a.at(i-1));
        chmax(dp[i][0], dp[i-1][2]+a.at(i-1));
        chmax(dp[i][1], dp[i-1][2]+b.at(i-1));
        chmax(dp[i][1], dp[i-1][0]+b.at(i-1));
        chmax(dp[i][2], dp[i-1][0]+c.at(i-1));
        chmax(dp[i][2], dp[i-1][1]+c.at(i-1));
    }
    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;;
    return 0;
}


Measured memory_bytes: 4992
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M, K = rl()

A = rl()
B = rl()

s = 0
j = 0
for i, b in enumerate(B):
	if s+b > K:
		break
	s += b
	j += 1

ans = j
j -= 1
for i, a in enumerate(A):
	s += a
	while j >= 0 and s > K :
		s -= B[j]
		j -= 1
	if s > K: break
	ans = max(ans, i+1+j+1)
print(ans)



Measured memory_bytes: 118020
N,M = map(int,input().split())
dp = [1 for i in range(N)]
trace = [0 for i in range(N)]
trace[0] = 1
for i in range(M):
    x,y = map(int,input().split())
    dp[y-1] += 1
    dp[x-1] -= 1
    if trace[x-1] >= 1:
        trace[y-1] = trace[x-1]
    if dp[x-1] == 0:
        trace[x-1] = 0

print(len(trace) - trace.count(0))

Measured memory_bytes: 4656
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define poly vector<ll>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
inline ll read(){
	ll x=0;char ch=getchar();bool d=1;
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') d=0;
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return d?x:-x;
}
inline void write(ll x){
	if(x<0) x=-x,putchar('-');
	if(x>=10) write(x/10);
	putchar('0'+x%10);
}
inline void writeln(ll x){write(x);puts("");}
inline void writep(ll x){write(x);putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=1e6+5;
int a[N];
char s[N];
bool check(int md){
	int n=strlen(s+1);
	For(i,1,n) a[i]=(s[i]-'0')*9;
	a[1]+=9*md;
	For(i,1,n){
		if(a[i]>9){
			if(i==n) a[++n]=0;
			a[i+1]+=a[i]/10;
			a[i]%=10;
		}
	}
	int cnt=0;
	For(i,1,n) cnt+=a[i];
	return cnt<=9*md;
}
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	reverse(s+1,s+n+1);
	int l=1,r=n,mid,ans=0;
	while(l<=r){
		check(mid=l+r>>1)?r=(ans=mid)-1:l=mid+1;
	}
	cout<<ans;
}

Measured memory_bytes: 6208
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <regex>
#include <iomanip>
#include <climits>
#include <utility>
#include <queue>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return b;
    }
    return gcd(b, a % b);
}

ll fact(ll n)
{
    if (n == 0)
    {
        return 1;
    }
    if (n == 1)
    {
        return 1;
    }
    return n * fact(n - 1) % MOD;
}

ll pow_fast(ll n, ll k) {
    if (k == 0) {
        return 1;
    }
    if (k == 1) {
        return n;
    }

    if (k % 2 == 0) {
        ll tmp = pow_fast(n, k / 2LL);
        return tmp * tmp % MOD;
    } else {
        ll tmp = pow_fast(n, k / 2LL);
        tmp *= tmp;
        tmp %= MOD;
        return tmp * n % MOD;
    }
}

int main()
{
    ll H1, M1;
    ll H2, M2;
    ll K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;

    ll minutes = (H2 * 60 + M2) - (H1 * 60 + M1);
    cout << max(0LL, minutes - K) << endl;
}

Measured memory_bytes: 3624
#include<cstdio>
#include<cstring>

int Check(int x){
    char s[10];
    sprintf(s+1,"%d",x);
    int len=strlen(s+1);
    for(int i=1;i<=len/2;i++)
        if(s[i]!=s[len-i+1])
            return 0;
    return 1;
}

int main(){
    int A,B,Ans=0;
    scanf("%d%d",&A,&B);
    for(int i=A;i<=B;i++)
        Ans+=Check(i);
    printf("%d",Ans);
}
/***/

Measured memory_bytes: 128
/* - - - - - - - - - - - - - - -
	User : 		VanishD
	problem :
	Points : 	
- - - - - - - - - - - - - - - */
# include <bits/stdc++.h>
# define 	ll 		long long
using namespace std;
const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
int read(){
	int tmp = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9'){ if (ch == '-') fh = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9'){ tmp = tmp * 10 + ch - '0'; ch = getchar(); }
	return tmp * fh;
}
const int N = 8010;
bitset <16384> f;
char s[N];
int sx, sy, p[2], d[2][N];
int main(){
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	scanf("\n%s", s + 1);
	sx = read(), sy = read();
	int now = 0, l = strlen(s + 1);
	int tmp = 1;
	while (tmp <= l && s[tmp] == 'F'){
		tmp++;
		sx--;
	}
	if (abs(sx) + abs(sy) > l){
		printf("No\n");
		return 0;
	}
	p[0] = 0, p[1] = 0;
	for (int i = tmp; i <= l; i++){
		if (s[i] == 'F') d[now][p[now]]++;
			else p[now ^= 1]++;
	}
	f[l] = true; 
	for (int i = 1; i <= p[0]; i++)
		f = (f << d[0][i]) | (f >> d[0][i]);
	if (f[sx + l] == 0){
		printf("No\n");
		return 0;
	}
	f.reset();
	f[l] = true;
	for (int i = 1; i <= p[1]; i++)
		f = (f << d[1][i]) | (f >> d[1][i]);
	if (f[sy + l] == 0)
		printf("No\n");
		else printf("Yes\n");
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define ull unsigned long long int
#define ll long long
#define l long
#define sd(x) scanf("%d",x) 
#define sld(x) scanf("%ld",x) 
#define slld(x) scanf("%lld",x) 
#define sllu(x) scanf("%llu",x) 
#define ss(x) scanf("%s",x) 

int main(){
  ll A,B,C,K;
  slld(&A);slld(&B);slld(&C);slld(&K);
  if(A>=K)printf("%lld",K);
  else if(A+B>=K)printf("%lld",A);
  else printf("%lld",2*A-K+B);
};


Measured memory_bytes: 1732
#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;
int main(void){
    
    int N,D;
    scanf("%d%d",&N,&D);
    int ans=0;
    for(int i=0;i<N;i++){
        int a;
        scanf("%d",&a);
        int po=(a-1)%(D+1);
        ans^=po;
    }
    if(ans!=0)printf("First\n");
    else printf("Second\n");
    return 0;
}



Measured memory_bytes: 3140
#include <iostream>
#include <vector>

using namespace std;

const int mx = 1e5 + 5;
vector<int> edges[mx];
int in_degree[mx];
int dis[mx];
bool visited[mx];

void dfs(int a){
    visited[a] = true;
    for(int b : edges[a]){
       dis[b] = max(dis[b], dis[a] + 1);
       --in_degree[b];
       if(in_degree[b] == 0){
           dfs(b);
        }
    }
}

int main(){

   int n, m;
   scanf("%d%d", &n, &m);
   while(m--){
       int a, b;
       scanf("%d%d", &a, &b);
       edges[a].push_back(b);
       ++in_degree[b];
    }

    for(int i = 1; i <= n;++i){
        if(!visited[i] && in_degree[i] == 0){
            dfs(i);
        }
    }
    int answer = 0;
    for(int i = 1; i<= n;++i){
        answer = max(answer, dis[i]);
    }
    printf("%d\n", answer);

    return 0;
}

Measured memory_bytes: 9728
N = input()
H = list(map(int, input().split()))
for i in range(len(H) - 1):
  if H[i] - 1 < H[i + 1]:
    pass
  elif H[i] -1 == H[i + 1]:
    H[i + 1] = H[i]
  else:
  	print('No')
  	exit()
print('Yes')

Measured memory_bytes: 14224
S=input()
length=int(len(S))
#print(length)

if length<=1:
    print("No")
elif length%2!=0 :
    print("No")
else:
    for i in range(length//2):
        if S[2*i]=="h" and S[2*i+1]=="i":
            temp=0
        else:
            print("No")
            temp=1
            break
            
    if temp==0:
        print("Yes")
    else:
        nothing=0

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int N;cin>>N;vector<int>A(N);vector<int>B(N);vector<int>C(N);
  for(int i=0;i<N;i++)cin>>A[i];
  for(int i=0;i<N;i++){cin>>B[i];C[i]=A[i]-B[i];}
  int count=0;int ans=0;
  sort(C.begin(),C.end());
  for(int i=0;i<N;i++){
    if(C[i]>=0)break;
    ans++;
    count+=C[i];
  }
  for(int i=N-1;i>=0;i--){
    if(count>=0){cout<<ans<<endl;return 0;}
    ans++;
    count+=C[i];
  }
  cout<<-1<<endl;
}

Measured memory_bytes: 5628
def main():
    n,k = map(int,input().split())
    a = list(map(int, input().split()))

    if max(a) < k:
        print("IMPOSSIBLE")
    else:
        from fractions import gcd
        gmax = a[0]
        for i in range(1, n):
            gmax = gcd(gmax, a[i])
        if gmax == 1:
            print("POSSIBLE")
        else:
            if k % gmax == 0:
                print("POSSIBLE")
            else:
                print("IMPOSSIBLE")

    


if __name__ == '__main__':
    main()


Measured memory_bytes: 81684
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean;

const int N = 1e5 + 5;

int n;
int f[N], g[N];
vector<int> G[N];

void dfs(int p, int fa) {
	f[p] = 1, g[p] = 0;
	for (auto e : G[p]) {
		if (e ^ fa) {
			dfs(e, p);
			f[p] += g[e];
			g[p] += max(f[e], g[e]);
		}
	}
}

int main() {
	scanf("%d", &n);;
	if (n & 1) {
		puts("First");
		return 0;
	}
	for (int i = 1, u, v; i < n; i++) {
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 0);
	puts((max(f[1], g[1]) == (n >> 1)) ? ("Second") : ("First"));
	return 0;
}


Measured memory_bytes: 6656
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ALL(x) x.begin(), x.end() 
int main(){
    int X, Y, Z, K;
    cin >> X >> Y >> Z >> K;
    vector<long long> 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];
    vector<long long> sumab;
    for(int i = 0; i < X; i++){
        for(int j = 0; j < Y; j++){
            long long temp = A[i] + B[j];
            sumab.push_back(temp);
        }
    }
    sort(ALL(sumab));
    sort(ALL(C));
    vector<long long> ans;
    for(int i = 0; i < min(K, Z); i++){
        for(int j = 0; j < min(X * Y, K); j++){
            long long temp = C[Z - 1 - i] + sumab[X * Y - 1 - j];
            ans.push_back(temp);
        }
    }
    sort(ALL(ans));
    for(int i = 0; i < K; i++){
        cout << ans[(int)ans.size() - 1 - i] << endl;
    }
}

Measured memory_bytes: 44032
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,x,y;

int main(){
  ll ans=0;
  cin >> n;
  vector<string> s(n);
  vector<int> t(n);
  REP(i,n){
    cin>>s[i]>>t[i];
  }
  string x;
  cin>>x;
  int ix=0;
  REP(i,n){
    if (s[i]==x){
      ix=i;
      break;
    }
  }

  for (int i = ix+1; i < n; i++)
  {
    ans+=t[i];
  }
  
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const ll mo = 1000000007;
const ll INF = 1LL << 60; //MAX 9223372036854775807
ll ans = 0;

int main()
{
ll n,k;
cin >> n>>k;
ll t[n] = {};
rep(i, n){
    cin >> t[i];
}
ll tt[n] = {};
ll ma=t[n-1];
rep(i,n){
    if(ma<t[n-i-1])ma=t[n-i-1];
    tt[n-i-1]=ma-t[n-i-1];
}
ma=0;
rep(i,n){
    if(ma<tt[i])ma=tt[i];
}
rep(i,n){
    if(ma==tt[i])ans++;
}



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


Measured memory_bytes: 1792
def dfs(i, now,  count):
    ans = 0
    if count == len(s)-1:
        calc = list(map(int, now.split('+')))
        return sum(calc)
    else:
        ans += dfs(i + 1, now, count+1)
        now = now[:i] + '+' + now[i:]
        ans += dfs(i + 2, now, count+1)
    return ans


s = input()
print(dfs(1, s, 0))


Measured memory_bytes: 39156
#include <vector>
#include <iostream>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<long long> A(N), B(N);
	for (int i = 0; i < N; ++i) cin >> A[i];
	for (int i = 0; i < N; ++i) cin >> B[i];
	long long sd = 0, opa = 0, opb = 0;
	for (int i = 0; i < N; ++i) {
		sd += B[i] - A[i];
		if (A[i] <= B[i]) {
			opa += (B[i] - A[i] + 1) / 2;
			opb += (B[i] - A[i]) % 2;
		}
		else opb += A[i] - B[i];
	}
	cout << (opa <= sd && opb <= sd ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 384
def dfs(i, f, Sum):
    if i == 3:
        if Sum == 7:
            print(f + "=7")
            exit()
    else:
        dfs(i + 1, f + "-" + s[i + 1], Sum - int(s[i + 1]))
        dfs(i + 1, f + "+" + s[i + 1], Sum + int(s[i + 1]))
  
if __name__ == '__main__':        
    s = input()
    dfs(0, s[0], int(s[0]))

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

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

int N, M, R; cin >> N >> M >> R;
VI r(R); invec(r);
sort(ALL(r));
VVI d(N+1, VI(N+1, INF));
rep(i, 1, N+1) d[i][i] = 0;
rep(i, 0, M){
    int64_t a, b, c; cin >> a >> b >> c;
    d[a][b] = c;
    d[b][a] = c;
}
rep(k, 1, N+1) rep(i, 1, N+1) if (d[i][k] < INF) 
    rep(j, 1, N+1) if (d[k][j] < INF)
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

i64 mini = INF;
do {
    i64 dist = 0;
    rep(i, 0, R-1) dist += d[r[i]][r[i+1]];
    mini = min(mini, dist);
} while(next_permutation(ALL(r)));

cout << mini << "\n";

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



Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int vis[27],i,j,m,k;
char s[27];
int main()
{
	scanf("%s",s);
	m=strlen(s);
	for(i=0;i<m;i++)vis[s[i]-'a']=1;
	if(m<26)
	{
		for(i=0;i<26;i++)
		{
			if(vis[i]==0)
			{
				printf("%s",s);
				printf("%c",(char){i+'a'});
				return 0;
			}
		}
	}
	else
	{
		for(i=25;i>=0;i--)
		{
			for(j=s[i]-'a'+1;j<26;j++)if(vis[j]==0)break;
			if(j<26)
			{
				k=j;
				for(j=0;j<i;j++)printf("%c",s[j]);
				printf("%c",(char){k+'a'});
				return 0;
			}
			vis[s[i]-'a']=0;
		}
	}
	printf("-1");
	return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#include<limits.h>
#define MAXBUF 100000
long long gcd(int a, int b);
long long lcm(int a,int b);
int main()
{
    int n, m;

    scanf("%d%d", &n, &m);

    fgetc(stdin);
    char s1[MAXBUF+2];

    char s2[MAXBUF+2];


    fgets(s1,MAXBUF+2,stdin);

    fgets(s2,MAXBUF+2,stdin);

    long long l=lcm(n,m);

    bool ok=1;
    for(long long q=0;q<m;q++)
    {
        if((1LL*q*n)%m==0 && (1LL*q*n)/m < n )
        {
            long long k=(1LL*q*n)/m;
            if(s1[(int)k] != s2[(int) q])
            {
                ok=0;
            }
        }
    }

    if(ok)
    {
        printf("%lld", l);
    }
    else
    {
        printf("-1");
    }


    return 0;

}

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

long long lcm(int a,int b)
{
    return (1LL*a*b)/gcd(a,b);
}


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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 30)
#define MOD 1000000007
//int dy[4] = {-1,0,0,1};
//int dx[4] = {0,1,-1,0};



int main(){

  int n;
  cin >> n;
  vector<vector<int>> v(n);
  REP(i,n-1){
    int x,y;cin >> x >> y;
    x--,y--;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  auto bfs = [&](bool flag)-> vector<int>{
    queue<int> que;
    vector<int> dist(n,-1);
    if(flag)dist[0] = 0,que.push(0);
    else dist[n-1] = 0,que.push(n-1);
    while(!que.empty()){
      int ov = que.front();que.pop();
      for(auto nv : v[ov]){
        if(dist[nv] != -1)continue;
        dist[nv] = dist[ov] + 1;
        que.push(nv);
      }
    }
    return dist;
  };
  vector<int> fene = bfs(true),snu = bfs(false);
  int f = 0,s  = 0;
  REP(i,n){
    if(fene[i] <= snu[i])f++;
    else s++;
  }
  if(f > s)cout << "Fennec" << endl;
  else cout << "Snuke" << endl;





  return 0;
}


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

constexpr int N = 10;

void drop( int p[N][N], int x, int y, int s ) {
	static const vector<vector<int>> ink = {
		{ 0,-1, -1,0, 0,0, 1,0, 0,1 },
		{ -1,-1, 0,-1, 1,-1, -1,0, 0,0, 1,0, -1,1, 0,1, 1,1 },
		{ 0,-2, -1,-1, 0,-1, 1,-1, -2,0, -1,0, 0,0, 1,0, 2,0, -1,1, 0,1, 1,1, 0,2 }
	};

	auto& v = ink[s-1];
	for( int i = 0; i < v.size()/2; ++i ) {
		uint32_t a = y + v[2*i + 1];
		uint32_t b = x + v[2*i];

		if( a < N && b < N ) {
			p[a][b] += 1;
		}
	}
}

int main() {
	ios_base::sync_with_stdio( false );

	int paper[N][N] = {};

	int x, y, s;
	char c;
	while( cin >> x >> c >> y >> c >> s ) {
		drop( paper, x, y, s );
	}

	int w = 0;
	int d = 0;

	for( int i = 0; i < N; ++i ) {
		for( int j = 0; j < N; ++j ) {
			if( paper[i][j] == 0 ) {
				w += 1;
			}
			else if( paper[i][j] > d ) {
				d = paper[i][j];
			}
		}
	}

	cout << w << '\n' << d << '\n';
}



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

using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define endl "\n"

const ll N = 1e6 + 7;
const double PI = acos(-1);
ll mod = 998244353;


int32_t main()
{
	
	IOS
	
	ll n, a;
	cin>>n;
	vector<ll> v;
	for(int i=0;i<n;i++)
	{
		cin>>a;
		v.pb(a);
	}
	ll cnt = 0;
	sort(v.begin(), v.end());
	ll f = v[n/2-1];
	ll s = v[n/2];
	cout<<s-f<<endl;
	return 0;
}

Measured memory_bytes: 1400