akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>

using namespace std;

vector<int> pth[1010];
int val[1010];

struct ei {
	int a,b;
	ei operator+ (const ei &aa) const;
	ei swap() const;
};

ei ei::operator+ (const ei &aa) const {
	return ei{a+aa.a,b+aa.b};
}

ei ei::swap() const {
	return ei{b,a};
}

bool la(const ei &a, const ei &b) {
	if (a.a!=b.a) return a.a<b.a;
	return a.b<b.b;
}

bool lb(const ei &a, const ei &b) {
	if (a.b!=b.b) return a.b<b.b;
	return a.a<b.a;
}

int mic[1010][2];
ei ee[1010][2];

int mem[1010][5010];
int dp(vector<ei> &tt,int idx,int val) {
	//assert(val<2500);
	if (val<0) return 0;
	if (idx<0) return 0;
	if (idx==0) {
		int mn=0;
		if (tt[idx].a<=val) mn=min(mn,tt[idx].b);
		return mn;
	}
	if (mem[idx][val]!=-1) return mem[idx][val];
	int mn=0;
	mn=min(mn,dp(tt,idx-1,val));
	if (tt[idx].a<=val&&tt[idx].a>=0) mn=min(mn,tt[idx].b+dp(tt,idx-1,val-tt[idx].a));
	return mem[idx][val]=mn;
}

int dep(int idx,int col) {
	if (mic[idx][col]!=-1) return mic[idx][col];
	
	ei iB=ei{0,0};
	ei iW=ei{0,0};
	
	vector<ei> bb,ww;	

	for (int i=0;i<(int)pth[idx].size();i++) {
		int b=dep(pth[idx][i],0);
		int w=dep(pth[idx][i],1);
		if (b==0&&w==0) {
			return mic[idx][0]=mic[idx][1]=0;
		} else if (b==0) {
			//wht+=val[pth[idx][i]];
			iB=iB+ee[pth[idx][i]][1];
			iW=iW+ee[pth[idx][i]][1];
		} else if (w==0) {
			iB=iB+ee[pth[idx][i]][0];
			iW=iW+ee[pth[idx][i]][0];
		} else {
			ei &a0=ee[pth[idx][i]][0];
			ei &a1=ee[pth[idx][i]][1];
			if (la(a0,a1)) {
				iB=iB+a0;
				bb.push_back(ei{a1.a-a0.a,a1.b-a0.b});
			} else {
				iB=iB+a1;
				bb.push_back(ei{a0.a-a1.a,a0.b-a1.b});
			}

			if (lb(a0,a1)) {
				iW=iW+a0;
				ww.push_back(ei{a1.a-a0.a,a1.b-a0.b}.swap());
			} else {
				iW=iW+a1;
				ww.push_back(ei{a0.a-a1.a,a0.b-a1.b}.swap());
			}
			if (bb.back().b>=0) bb.pop_back();
			if (ww.back().b>=0) ww.pop_back();
		}
	}

	//memset(mem,-1,sizeof(mem));
	for (int j=0;j<1010;j++) for (int i=0;i<=val[idx]-iB.a;i++) mem[j][i]=-1;
	iB.b+=dp(bb,bb.size()-1,val[idx]-iB.a);
	//memset(mem,-1,sizeof(mem));
	for (int j=0;j<1010;j++) for (int i=0;i<=val[idx]-iW.b;i++) mem[j][i]=-1;
	iW.a+=dp(ww,ww.size()-1,val[idx]-iW.b);

	mic[idx][0]=(iB.a<=val[idx]);
	mic[idx][1]=(iW.b<=val[idx]);
	iB.a=val[idx];
	iW.b=val[idx];
	ee[idx][0]=iB;
	ee[idx][1]=iW;
	return mic[idx][col];
}

int main() {
	int n;
	scanf("%d",&n);
	int x;
	for (int i=2;i<=n;i++) {
		scanf("%d",&x);
		pth[x].push_back(i);
	}
	for (int i=1;i<=n;i++) {
		scanf("%d",&val[i]);
	}
	memset(mic,-1,sizeof(mic));
	//for (int i=1;i<=n;i++) {
		//printf("%d: %d, %d,%d %d, %d,%d\n",i,dep(i,0),ee[i][0].a,ee[i][0].b,dep(i,1),ee[i][1].a,ee[i][1].b);	
		//}

	printf("%sPOSSIBLE\n",(dep(1,0)||dep(1,1))?"":"IM");
}


Measured memory_bytes: 20096
#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define f first
#define s second
#define pb push_back
#define mod 1000000007
#define mp make_pair
#define fast 
#define f first
#define s second
#define endl "\n"
#define pie 3.1415926535

int main(){
    int n;
    cin >> n;
    set<string> s;
    for(int i=0;i<n;i++){
        string temp ;
        cin >> temp;
        s.insert(temp);
    }
    
    cout << s.size();
    
}

Measured memory_bytes: 19120
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int ans=700;
int main()
{
    string s;
    cin>>s;
    for(int i=0;i<3;i++){
        if(s[i]=='o')ans+=100;
    }
    cout<<ans;
system("pause");
return 0;
}

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

typedef long long int ll;

ll stair(ll x){
  if(x==1)return 1;
  else return stair(x-1)*x;
}

int main(){
  ll n;
  cin>>n;
  cout<<stair(n)<<endl;
  return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <fstream>

#include <vector>

using namespace std;

int main(){

    string n,res;

    cin >> n;

    for(int i = 0; i < n.size(); i++)
    {
        if(n[i] == '9')n[i] ='1';
        else n[i] = '9';
    }

    cout << n << endl;

}



Measured memory_bytes: 256
"use strict";

function _slicedToArray(arr, i) { return _arrayWithHoles(arr) || _iterableToArrayLimit(arr, i) || _nonIterableRest(); }

function _nonIterableRest() { throw new TypeError("Invalid attempt to destructure non-iterable instance"); }

function _iterableToArrayLimit(arr, i) { var _arr = []; var _n = true; var _d = false; var _e = undefined; try { for (var _i = arr[Symbol.iterator](), _s; !(_n = (_s = _i.next()).done); _n = true) { _arr.push(_s.value); if (i && _arr.length === i) break; } } catch (err) { _d = true; _e = err; } finally { try { if (!_n && _i["return"] != null) _i["return"](); } finally { if (_d) throw _e; } } return _arr; }

function _arrayWithHoles(arr) { if (Array.isArray(arr)) return arr; }

!function () {
  function splitNum(line) {
    return (Array.isArray(line) ? line : line.split(/\s+/)).map(function (n) {
      return parseInt(n);
    });
  }

  !function (input) {
    var lines = input.split("\n");

    var _splitNum = splitNum(lines[0]),
        _splitNum2 = _slicedToArray(_splitNum, 2),
        A = _splitNum2[0],
        P = _splitNum2[1];

    console.log(Math.floor((3 * A + P) / 2));
  }(require("fs").readFileSync("/dev/stdin", "utf8"));
}();


Measured memory_bytes: 21064
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(), vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout << endl;
#define prique(T) priority_queue<T, vector<T>, greater<T>>
struct edge { int to, cost; };
using P = pair<int, int>;
using PP = pair<P, int>;
const int mod = 1e9 + 7, inf = 1e16, mod2 = 998244353;

int modpow(int x, int n) {
	int ans = 1;
	while (n > 0) {
		if (n & 1) {
			if (mod <= ans * x) ans = ans * x % mod;
			else ans *= x;
		}
		if (mod <= x * x) x = x * x % mod;
		else x *= x;
		n >>= 1;
	}
	return ans;
}

int fact_memo[114514];
int fact(int n) {
	int ans = 1;
	if (fact_memo[n]) return fact_memo[n];
	rep(i, n) {
		ans *= (i + 1);
		if (mod <= ans) ans %= mod;
		fact_memo[i + 1] = ans;
	}
	return (ans + mod) % mod;
}

int comb(int n, int r) {
	if (n < r) return 0;
	if (n - r < r) r = n - r;
	return (fact(n) * modpow(fact(n - r), mod - 2) % mod * modpow(fact(r), mod - 2) + mod) % mod;
}

int perm(int n, int r) {
	if (n < r) return 0;
	if (n - r < r) r = n - r;
	return (fact(n) * modpow(fact(n - r), mod - 2) % mod + mod) % mod;
}

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

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

bool pri(int p) {
	for (int i = 2; i * i <= p; i++) if (p % i == 0) return false;
	return p > 1;
}

map<int, int>factring(int n) {
	map<int, int>ans;
	for (int i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			n /= i;
			ans[i]++;
		}
	}
	if (n != 1) ans[n]++;
	return ans;
}

P operator+(const P& a, const P& b) {
	return P(a.first + b.first, a.second + b.second);
}
P operator-(const P& a, const P& b) {
	return P(a.first - b.first, a.second - b.second);
}

int n;
vector<int>h;
signed main() {
	cin >> n;
	rep(i, n) {
		int a;
		cin >> a;
		if (i == 0) h.push_back(a);
		else {
			if (h[h.size()-1] == a) continue;
			h.push_back(a);
		}
	}
	n = h.size();
	rep(i, n - 1) {
		if (h[i] > h[i + 1]) {
			h[i]--;
		}
	}
	rep(i, n - 1) {
		if (h[i] > h[i + 1]) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
}


Measured memory_bytes: 1400
#include <cstdio>

int main(){
    int A,B,C;
    scanf("%d %d %d",&A,&B,&C);
    int a[]= {A,B,C};
    int count5 = 0;
    int count7 = 0;
    for(int i = 0; i < 3; i++){
        if(a[i] == 5){
            count5++;
        }
        if(a[i] == 7){
            count7++;
        }
    }

    if(count5 == 2 && count7 == 1){
        printf("YES");
    }
    else{
        printf("NO");
    }
    printf("\n");

    return 0;
}

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

int main() {
	string S;
	string A;
	string Z;
	cin >> S;
	int Q;
	cin >> Q;
	int nRev = 1;
	for (int n = 0;n<Q;++n) {
		int t;
		cin >> t;
		if (1==t) {
			//反転
			nRev *= -1;
		}
		else {
			int f;
			cin >> f;
			string s;
			cin >> s;
			if (1==f) {
				if (1 == nRev) {
					A += s;
				}
				else {
					Z += s;
				}
			}
			else {
				if (1 == nRev) {
					Z += s;
				}
				else {
					A += s;
				}
			}
		}
	}
	string ansstr;
	reverse(A.begin(), A.end());
	ansstr += A;
	ansstr += S;
	ansstr += Z;
	if (-1 == nRev) {
		reverse(ansstr.begin(), ansstr.end());
	}
	cout << ansstr<< endl;
	return 0;
}

Measured memory_bytes: 4276
using System;
using System.Collections.Generic;

namespace AOJ {
    class ALDS1_2_C {
        static int cnt = 0;
        static void Main(string[] args) {
            int n = int.Parse(Console.ReadLine());
            int[] data = new int[n];
            for (int i = 0; i < n; i++) {
                data[i] = int.Parse(Console.ReadLine());
            }
            ShellSort(data, n);
        }
        static void InsertionSort(ref int[] A, int n, int g) {
            for(int i = g; i < n; i++) {
                int v = A[i];
                int j = i - g;
                while (j >= 0 && A[j] > v) {
                    A[j + g] = A[j];
                    j = j - g;
                    cnt++;
                }
                A[j + g] = v;
            }
        }
        static void ShellSort(int[] A, int n) {
            int i = 1;
            List<int> g = new List<int>();
            while (i <= n) {
                g.Add(i);
                i = 3 * i + 1;
            }
            int[] G = g.ToArray();
            Console.WriteLine(G.Length);
            for(int j = G.Length - 1; j >= 0; j--) {
                InsertionSort(ref A, n, G[j]);
                Console.Write(G[j] + " ");
            }
            Console.WriteLine();
            Console.WriteLine(cnt);
            for(int j = 0; j < n; j++) {
                if (j != n) Console.WriteLine(A[j]);
                else Console.Write(A[j]);
            }
        }
    }
}



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

int cnt[11];

int main() {
    int n;
    while(cin >> n) cnt[n]++;
    if (cnt[5] == 2 && cnt[7] == 1) cout <<"YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	while (1) {
		long a[5001] = { 0 };
		long n;
		cin >> n;
		if (n == 0)break;
		a[0] = 0;
		long maxv = -100000;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		for (int i = 1; i <= n; i++) {
			a[i] = max(a[i], a[i] + a[i - 1]);
			maxv = max(maxv, a[i]);
		}
		cout << maxv << endl;
	}
}

Measured memory_bytes: 1204
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        long d = sc.nextLong();
        long p = d, q = c;
        while (p % q != 0) {
            long m = q;
            q = p % q;
            p = m;
        }
        long l = (c * d) / q;
        long counter_b = b - (b / c) - (b / d) + (b / l);
        long counter_a = (a - 1) - ((a - 1) / c) - ((a - 1) / d) + ((a - 1) / l);
        System.out.println(counter_b - counter_a);
        sc.close();
    }
}

Measured memory_bytes: 21844
def solve(m, bs):
    ans = 0
    x_y_z = 0

    for i in range(1 << 3):
        xyzs = []
        for b in bs:
            for j in range(3):
                if i >> j & 1:
                    x_y_z += b[j]
                else:
                    x_y_z -= b[j]
            xyzs.append(x_y_z)
            x_y_z = 0

        xyzs.sort(reverse=True)
        s_xyzs = sum(xyzs[:m])
        ans = s_xyzs if s_xyzs > ans else ans

    return ans


if __name__ == '__main__':
    n, m = map(int, input().split())
    x, y, z = 0, 0, 0
    bs = []

    for i in range(n):
        x, y, z = map(int, input().split())
        bs.append([x, y, z])

    print(solve(m, bs))


Measured memory_bytes: 3188
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<ll,ll> p;
const int inf=(1<<30);
#define rep(i,a,n)	for(int i=a;i<n;i++)
#define rrep(i,a,n) for(int i=(a-1);i>=n;i--)
	
int main(){
	ll a,b;
	cin>>a>>b;
	ll ans=0;
	if(a>b){
		ans+=a;
		a--;
	}
	else{
		ans+=b;
		b--;
	}
	cout<<ans+max(a,b)<<endl;
	
	
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>

using namespace std;
using ll = long long;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)

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 (b<a) { a=b; return 1;} return 0;}

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

//////////////////////////////////////////////////


int main() {
    int n; cin >> n;
    vector<int>  t(n);
    vector<string> s(n);
    string x;
    rep(i, n) cin >> s[i] >> t[i];
    cin >> x;
    int cnt = 0;
    rep(i, n) {
        if (x.compare(s[i]) == 0) break;
        cnt++;
    }
    int ans = 0;
    repf(i, cnt+1, n) ans += t[i];
    cout << ans << endl;
    return 0;
}

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

struct UnionFind {
    vector<int> par;
    vector<int> sz;

    UnionFind(int n=0){
        if(n>0) initialize(n);
    }

    void initialize(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0; i<n; i++){
            par[i] = i;
            sz[i] = 1;
        }
    }

    int find(int x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    }

    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(sz[x] > sz[y]) swap(x, y);
        par[x] = y;
        sz[y] += sz[x];
        return true;
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    int size(int x){
        return sz[find(x)];
    }
};

int64_t mod(int64_t a, int64_t m) {
    return (a % m + m) % m;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

pair<int64_t, int64_t> crt(int64_t b1, int64_t m1, int64_t b2, int64_t m2){
    int64_t p, q;
    int64_t d = extgcd(m1, m2, p, q);
    if((b2-b1) % d != 0) return {-1, -1};
    int64_t m = m1 * (m2/d);
    int64_t tmp = (b2 - b1) / d * p % (m2/d);
    int64_t r = mod(b1 + m1 * tmp, m);
    return make_pair(r, m);
}

int main(){
    int N;
    int P[200], Q[200];
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> P[i];
        P[i]--;
    }
    UnionFind uf(N);
    for(int i=0; i<N; i++){
        cin >> Q[i];
        Q[i]--;
        uf.unite(i, Q[i]);
    }
    pair<int64_t, int64_t> ans = {0, 1};
    for(int i=0; i<N; i++) if(uf.find(i) == i){
        int sz = uf.size(i), t = 0;
        bool ok = false;
        while(t <= sz){
            ok = true;
            for(int j=0; j<N; j++) if(uf.same(i, P[j]) && j != P[j]) ok = false;
            if(ok) break;
            t++;
            for(int j=0; j<N; j++) if(uf.same(i, P[j])) P[j] = Q[P[j]];
        }
        if(!ok){
            cout << -1 << endl;
            return 0;
        }
        ans = crt(ans.first, ans.second, t, sz);
        if(ans.first == -1){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans.first << endl;
    return 0;
}



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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(i,s,n) for(int i = (s); i < (n); ++i)
#define ll long long
#define ld long double
#define P pair<ll,ll>
#define all(v) v.begin(),v.end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll n,x; cin>>n>>x;
    vector<ll> m(n);
    rep(i,n){
        cin>>m[i];
        x-=m[i];
    }
    ll ans=n;
    sort(all(m));
    while(x>0){
        if(x-m[0]<0) break;
        x-=m[0];
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3620
/*  In the name of ALLAH */

#include<bits/stdc++.h>
using namespace std;
/*******  All Required define Pre-Processors and Constants    *******/

#define int long long
#define ull unsigned long long 
#define ld long double
#define mem(a, b) memset(a, (b), sizeof(a))
#define rep(i, j, k) for (int i = j ; i < k ; ++i)
#define rrep(i, j, k) for (int i = j; i > k; --i)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define foreach(i, a) for(auto i: a)
#define forEach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define in(A, B, C) assert( B <= A && A <= C)
#define debug(a) cout << #a << ": " << a << endl
#define Flag(n) cout << "here " << n << endl
#define w(x) int x;cin>>x;while(t--)
#define mp make_pair
#define pb push_back

#define endl '\n';
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int POSITIVE_INFINITY = 9223372036854775807;
const int NEGATIVE_INFINITY = -9223372036854775807;
const int MOD = 1000000007;
const ld PI = acos(-1.0);
 

#define TRACE
#ifdef TRACE
#define see(...) __f(#__VA_ARGS__,__VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr<<name<<" : "<<arg1<<endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma=strchr(names+1,',');cerr.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1, args...);
}
#else
#endif



int32_t main() {
    io;
    // freopen("input.txt","r",stdin); 
    // freopen("output.txt","w",stdout);
  
    int n,k,start  =1;
    cin>>n>>k;
    while (n--)
    {
        start = min(start*2, start+k);
        // see(start);
    }
    cout<<start<<endl;
    
    

 
    
 
    return 0;
}


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


/* macro */
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define int long long
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))
#define pb push_back


/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
const int inf = pow(2, 62);
const int mod = 1e9 + 7;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};
const string alpha = "abcdefghijklmnopqrstuvwxyz";

/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


/* general_method */
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 (b<a) { a=b; return 1; } return 0; }




/* main */


signed main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n = input();

    vi arr; rep(i,0,n) arr.push_back(input());

    map<int, int> mp;
    for(int e : arr){
        mp[e]++;
    }


    sort(all(arr));
    reverse(all(arr));

    int ans = 0;
    rep(i,0,n){
        if(mp[arr[i]] == 0) continue;

        for(int j = pow(2,32); j > 1; j /= 2){

            if(j - arr[i] < 1) continue;

            if(not exist(mp, j - arr[i])) continue;

            if(arr[i] < 1) break;

            if(arr[i] * 2 == j && mp[arr[i]] >= 2){

                mp[arr[i]] -= 2;
                ans++;
                break;
            }else if(mp[j - arr[i]] > 0){
                if(arr[i] * 2 == j) continue;
                mp[j - arr[i]]--;
                mp[arr[i]]--;
                ans++;
                break;
            }

        }

    }
    print(ans);




    



    





    


    

}



Measured memory_bytes: 14320
import bisect


h, w, n = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

set_ = set()
tate = [[] for _ in range(w + 1)]
for i, j in info:
    tate[j].append(i)
    set_.add((i, j))
for j in range(w + 1):
    tate[j].append(h + 1)
    tate[j] = sorted(tate[j])
    
i, j = 1, 1
ans = 10 ** 18

while True:
    ind = bisect.bisect_right(tate[j], i)
    ans = min(ans, tate[j][ind] - 1)
    if i == h:
        break
    i += 1
    if (i, j + 1) in set_ or j == w:
        pass
    else:
        j += 1

print(ans)

Measured memory_bytes: 138276
//#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f_(i,a,b) for (int i=a;i>=b;i--)
#define f(i,a,b) for (int i=a;i<=b;i++)
const ll mod=1000000007;

map<pair<int,int>,int> m;
int n,x[55],y[55],ans=0;
priority_queue<pair<int,int> > pq;
int main() {
//	freopen("","r",stdin);
//	freopen("","w",stdout);
	scanf("%d", &n);
	f(i,1,n) scanf("%d %d", &x[i], &y[i]);
	f(i,1,n) pq.push(make_pair(x[i],y[i]));
	f_(i,n,1) {
		x[i]=pq.top().first;
		y[i]=pq.top().second;
		pq.pop();
	}
	f(i,1,n-1) {
		f(j,i+1,n) {
			m[make_pair(x[j]-x[i],y[j]-y[i])]++;
			ans=max(ans,m[make_pair(x[j]-x[i],y[j]-y[i])]);
		}
	}
	printf("%d", n-ans);
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6;
const double PI = acos(-1.0);
#define Test ll tesnum;tesnum = read();while(tesnum--)
ll read();

int main()
{
    ll n;
    cin>>n;
    ll ans = 0;
    for(ll i = 1; i <= n; i++){
        for(ll j = i; j <= n; j+=i){
            ans+=j;
        }
    }
    cout<<ans<<endl;
    return "BT7274", NULL;
}

inline ll read() {
    ll hcy = 0, dia = 1;char boluo = getchar();
    while (!isdigit(boluo)) {if (boluo == '-')dia = -1;boluo = getchar();}
    while (isdigit(boluo)) {hcy = hcy * 10 + boluo - '0';boluo = getchar();}
    return hcy * dia;
}

Measured memory_bytes: 3636
N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))
ans = 0
minDiff = 10**4
for i in range(N):
    if minDiff > abs(A - T + H[i]*0.006):
        ans = i
        minDiff = abs(A - T + H[i]*0.006)
print(ans + 1)


Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include <vector>
#include <unordered_map>

using namespace std;


int main()
{
	int n;  cin >> n;
	vector<int> arr(n + 1, 0);
	for (int i = 1; i <= n; ++i)
		cin >> arr[i];

	for (int i = 1; i <= n; ++i) {
		cout << "node " << i << ": " << "key = " << arr[i] << ", ";
		if (i > 1)
			cout << "parent key = " << arr[i / 2] << ", ";
		if (2 * i <= n)
			cout << "left key = " << arr[2 * i] << ", ";
		if (2 * i + 1 <= n)
			cout << "right key = " << arr[2 * i + 1] << ", ";
		cout << endl;
	}


	return 0;
}


Measured memory_bytes: 3076
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    ll N,K;
    cin >> N >> K;
    ll maxi = (N-1) * (N-2) / 2;
    if(K > maxi){
        cout << -1 << endl;
        return 0;
    }
    ll edge = N - 1 + (maxi - K);
    cout << edge << endl;
    rep(i,0,N-1){
        cout << i + 1 << " " << N << endl;
    }
    ll rem = maxi - K;
    rep(i,0,N-1){
        rep(j,i+1,N-1   ){
            if(rem == 0){
                return 0;
            }
            rem--;
            cout << i + 1 << " " << j + 1 << endl;
        }
    }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    List<Integer>[] edges = new ArrayList[N];
    for (int i = 0; i < N; i++) {
      edges[i] = new ArrayList<Integer>();
    }
    for (int i = 0; i < M; i++) {
      int x = sc.nextInt();
      int y = sc.nextInt();
      int w = sc.nextInt();
      edges[x-1].add(y-1);
      edges[y-1].add(x-1);
    }
    boolean[] visited = new boolean[N];
    int ans = 0;
    for (int i = 0; i < N; i++) {
      if (visited[i]) continue;
      Queue<Integer> queue = new LinkedList<Integer>();
      queue.offer(i);
      visited[i] = true;
      ans++;
      while (queue.size() > 0) {
        int v = queue.poll();
        for (int w : edges[v]) {
          if (visited[w]) continue;
          queue.offer(w);
          visited[w] = true;
        }
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 106264
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>
#include <set>
#include <stack>
#include <queue>
using namespace std;

#define X first
#define Y second
#define N 100005
#define M 1010
typedef long long ll;
typedef pair<int,int> pii;

const int INF=1<<30;

bool flag=true;
int n,rt;
int a[N],b[N],deg[N];

vector<int> g[N];

void Dfs(int x,int father)
{
	if (!flag) return;
	if (deg[x]==1)
	{
		b[x]=a[x];
		return;
	}
	
	b[x]=2*a[x];
	for (int i=0,y;i<g[x].size();i++)
	{
		y=g[x][i]; if (y==father) continue;
		
		Dfs(y,x); b[x]-=b[y];
		if (b[x]<0 || b[y]>a[x]) {flag=false; return;}
	}
	if (b[x]>a[x]) flag=false;
	if (x==rt && b[x]!=0) flag=false;
}

int main()
{
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
		deg[x]++,deg[y]++;
	}
	if (n==2)
	{
		if (a[1]==a[2]) printf("YES\n");
		else printf("NO\n");
		return 0;
	}

	for (int i=1;i<=n;i++) if (deg[i]>1) rt=i;
	
	Dfs(rt,0);
	if (flag) printf("YES\n");
	else printf("NO\n");
	
	return 0;
}

Measured memory_bytes: 14080
#define DEBUG 1
#include <bits/stdc++.h>
using namespace std;
typedef          char      s8;
typedef unsigned char      u8;
typedef          short    s16;
typedef unsigned short    u16;
typedef          int      s32;
typedef unsigned int      u32;
typedef          long int s64;
typedef unsigned long int u64;
typedef float             f32;
typedef double            f64;
#define rep(_i, _n) for (int _i = 0; _i < (int)(_n); _i++)
#if DEBUG
#define PHERE()			{ cerr << "L" << setw(3) << __LINE__ << ": PHERE" << clock() << endl; }
#define PVAL( _var )	{ cerr << "L" << setw(3) << __LINE__ << ":" << #_var "=" << (_var) << endl; }
#else
#define PHERE()
#define PVAL( _var )
#endif


int main()
{
	//////// 入力 ////////
	int a;
	cin >> a;
	/////////////////////
	
	
	
	int out = a + (a*a) + (a*a*a);
	//////// 出力 ////////
	cout << out;
	/////////////////////
	
	return 0;
}
#if 0
#endif


Measured memory_bytes: 3592
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <algorithm>
#include <functional>

using namespace std;

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

	int X;
	cin >> X;

	int A;
	cin >> A;

	int B;
	cin >> B;

	int left_money = X - A;
	if (left_money < B)
	{
		cout << left_money;
	}
	else
	{
		cout << left_money % B;
	}

	return 0;
}

Measured memory_bytes: 3612
#include "bits/stdc++.h"
using namespace std;
int m = 1, seg[1 << 19 - 1], inf = (int)((1ll << 31) - 1);
void update(int x, int val)
{
	x += m - 1;
	seg[x] = val;
	for(; x > 0;) 
	{
		(x -= 1) /= 2;
		seg[x] = min(seg[2 * x + 1], seg[2 * x + 2]);
	}
}
int query(int a, int b, int ind, int l, int r)
{
	if(r <= a || b <= l)
	{
		return inf;
	}
	if(a <= l && r <= b)
	{
		return seg[ind];
	}
	return min(query(a, b, 2 * ind + 1, l, (l + r) / 2), query(a, b, 2 * ind + 2, (l + r) / 2, r));
}
int main()
{
	int n, q;	
	scanf("%d%d", &n, &q);
	for(; n > m; m <<= 1){}
	for(int i = 0; i < 2 * m - 1; seg[i++] = inf){}	
	for(int i = 0, c, x, y; i < q; ++i)
	{
		scanf("%d%d%d", &c, &x, &y);
		if(c)
		{
			printf("%d\n", query(x, y + 1, 0, 0, m));
		}
		else
		{
			update(x, y);
		}
	}
}



Measured memory_bytes: 4236
import sys
n=int(input())+1
e=list(map(lambda x:x.split(),sys.stdin))
p=[int(e[0][0])]+list(int(x[1])for x in e)
m=[[0]*n for _ in[0]*n]
for l in range(2,n):
 for i in range(1,n-l+1):
  j=i+l-1;m[i][j]=1e6
  for k in range(i,j):m[i][j]=min(m[i][j],m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j])
print(m[1][n-1])


Measured memory_bytes: 5732
import collections
n = int(input())
s = input()
dic = dict(collections.Counter(s))
#W,Eどちらかしか無い場合
if len(dic)==1:
  print(0)
  exit()
left_w = 0
right_e = dic["E"]

#(左にあるWの数+右にあるEの数)の最小値が答え
ans = n
for i in range(n):
  if s[i] == "W":
    ans = min(ans,left_w+right_e)
    left_w += 1
  elif s[i] == "E":
    ans = min(ans,left_w+right_e)
    right_e -= 1

#(右にあるWの数+左にあるEの数)の最小値が答えの場合もあるか
left_e = 0
right_w = dic["W"]

for i in range(n-1,-1,-1):
  if s[i] == "E":
    ans = min(ans,left_e+right_w)
    left_e += 1
  elif s[i] == "W":
    ans = min(ans,left_e + right_w)
    right_w -= 1

print(ans)



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

using namespace std;
typedef long long ll;
const ll mx = 10000007;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
#define ull unsigned long long
#define    ss   second
#define    ff   first
#define    pb   push_back
#define gcd(a, b) __gcd((a), (b))
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
#define FIO ios_base::sync_with_stdio(false);  cin.tie(NULL);

int main() {
    FIO;
   ll n;  cin >> n;
   ll a[n + 2];
   for(ll i = 0; i < n; i++) cin >> a[i];

   ll ans = 0;
   a[n] = a[n - 1];
   for(ll i = 0; i < n - 1; i++){
    if(a[i] > a[i+1]) {
        ans += a[i] - a[i + 1];
        a[i + 1] = a[i];
    }
   }

   cout << ans << endl;
}


Measured memory_bytes: 5200
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

struct node{
  int key;
  node *left,*right,*p;
  node(){}
  node(int key):key(key){left=right=p=NULL;};
};
node *root;
void insert(node z){
  node *y=NULL;
  node *x=root;
  while(x!=NULL){
    y=x;
    if(z.key<x->key) x=x->left;
    else x=x->right;
  }
  z.p=y;
  if(y==NULL) root=new node(z);
  else if(z.key<y->key) y->left=new node(z);
  else y->right=new node(z);
}
bool find(int z){
  node *x=root;
  while(x!=NULL){
    if(z==x->key) return true;
    if(z<x->key) x=x->left;
    else x=x->right;
  }
  return false;
}
node *nxt(node *x){
  if(x->left!=NULL) return nxt(x->left);
  return x;
}
void del(node *x){
  node *y=x->p;
  if(x->left==NULL&&x->right==NULL){
    if(y!=NULL&&y->left==x) y->left=NULL;
    if(y!=NULL&&y->right==x) y->right=NULL;
    delete(x);
    return;
  }
  if(x->left==NULL&&x->right!=NULL){
    if(y!=NULL&&y->left==x) y->left=x->right;
    if(y!=NULL&&y->right==x) y->right=x->right;
    x->right->p=y;
    delete(x);
    return;
  }
  if(x->left!=NULL&&x->right==NULL){
    if(y!=NULL&&y->left==x) y->left=x->left;
    if(y!=NULL&&y->right==x) y->right=x->left;
    x->left->p=y;
    delete(x);
    return;
  }
  node *z=nxt(x->right);
  x->key=z->key;
  del(z);
}
void del(int k){
  node *x=root;
  while(x!=NULL){
    if(k==x->key) break;
    if(k<x->key) x=x->left;
    else x=x->right;
  }
  del(x);
}
void inorderTreeWalk(node *v){
  if(v==NULL) return;
  inorderTreeWalk(v->left);
  cout<<" "<<v->key;
  inorderTreeWalk(v->right);
}
void preorderTreeWalk(node *v){
  if(v==NULL) return;
  cout<<" "<<v->key;
  preorderTreeWalk(v->left);
  preorderTreeWalk(v->right);
}
signed main(){
  int n;
  cin>>n;
  root=NULL;
  for(int i=0;i<n;i++){
    string s;
    cin>>s;
    if(s=="print"){
      inorderTreeWalk(root);
      cout<<endl;
      preorderTreeWalk(root);
      cout<<endl;
      continue;
    }
    int x;
    cin>>x;
    if(s=="insert"){
      insert(node(x));
    }
    if(s=="find"){
      cout<<(find(x)?"yes":"no")<<endl;
    }
    if(s=="delete"){
      del(x);
    }
  }
  return 0;
}



Measured memory_bytes: 21924
//Subhash Suman
//Date: 14/02/19 ; Day: Thursday ; Time: 07::44::50 
//Description : 

#include<bits/stdc++.h>
#define ll long long int
#define MAX INT_MAX
#define MIN INT_MIN
#define vi vector<int>
#define pii pair<int,int>
#define mii map<int,int>

using namespace std;
const int N = 105;
const int K = 1e5+5;
const int mod = 1e9+7;
int arr[N];
ll dp[N][K];

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
    int n,t;
    cin>>n>>t;
    for(int i = 1; i <= n; i++){
        cin>>arr[i];
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        dp[i][0] = 1;
        for(int j = 0; j <= t; j++){
            dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod;
            if(j-arr[i]-1>=0){
                dp[i][j] = (dp[i][j]-dp[i-1][j-arr[i]-1]+mod)%mod;
            }
        }
    }
    cout<<dp[n][t]<<'\n';
    return 0;
}

Measured memory_bytes: 79360
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cstdio>

#include<string>
using namespace std;
string s,t;
bool flag;
int main(){
    cin>>s>>t;
    for(int i=s.size()-t.size();i>=0;i--){
        flag=false;
        string ans=s;
        for(int j=i,k=0;k<t.size();j++,k++){
            if(t[k]!=s[j]&&s[j]!='?'){
                flag=true;
                break;
            }
            else{
                ans[j]=t[k];
            }
        }
        if(!flag){
            for(int j=0;j<s.size();j++){
                if(ans[j]=='?'){
                    putchar('a');
                }
                else{
                    cout<<ans[j];
                }
            }
            puts("");
            return 0;
        }
    }
    puts("UNRESTORABLE");
    return 0;
}

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

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

const int maxn = (3e3 + 12);
vector <int> ad[maxn], ans;
bool WinCheck[maxn];
pair <int, int> ver[maxn];
int n, a[maxn];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		ver[i] = {a[i], i};
	}
	sort(ver, ver + n);
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		ad[u].push_back(v);
		ad[v].push_back(u);
	}
	for (int i = 0; i < n; i++) {
		int id = ver[i].second;
		//cout << id << ' ' ;
		for (int j = 0; j < ad[id].size(); j++) {
			int x = ad[id][j];
			if(a[x] < a[id]) {
				WinCheck[id] |= !WinCheck[x];
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if(WinCheck[i] == 1) cout << i + 1 << ' ' ;
	}
	return 0;
}





Measured memory_bytes: 512
def insertionSort(A,N):
    for i in range(1,N):
        v=A[i]
        j=i-1
        while(j>=0 and A[j]>v):
            A[j+1]=A[j]
            j=j-1
            A[j+1]=v
        print(*A)

N=int(input())

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

print(*A)
insertionSort(A,N)


Measured memory_bytes: 5980
def sigma(n):
    return n * (n + 1) // 2

s = list(map(lambda x : 1 if x == '<' else -1, input()))
l = [s[0]]
for c in s[1:]:
    if c * l[-1] > 0:
        l[-1] += c
    else:
        l.append(c)
ans = 0
now = 0
for c in l:
    if c < 0:
        ans -= min(now, abs(c))
    ans += sigma(abs(c))
    now = abs(c)
print(ans)

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

int main() {
  int n;
  cin >> n;
  long long power = 1;
  int kaisu = 1;
  while(kaisu <= n){
    power *= kaisu;
    power %= 1000000007;
    kaisu++;
  }
  cout << power << endl;
}


Measured memory_bytes: 256
n=int(input())
robot=[]
for i in range(n):
	x,l=map(int,input().split())
	robot.append([x,l])
robot.sort()
ans=1
for i in range(n-1):
	if robot[i][0]+robot[i][1]>robot[i+1][0]-robot[i+1][1]:
		if robot[i][0]+robot[i][1]<robot[i+1][0]+robot[i+1][1]:
			robot[i+1]=robot[i]
	else:
		ans+=1
print(ans)


Measured memory_bytes: 20076
#include <stdio.h>

int main(void)
{
	int n,count;
	scanf("%d",&n);
	
	count=0;
	
	for(int i=0;7*i<=n;i++){
		if((n-7*i)%4==0){
			count++;
		}
	}
	
	if(count==0){
		printf("No\n");
	}else{
		printf("Yes\n");
	}
	
	return 0;
}
		
	

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from functools import reduce

def main():
    N = int(input())
    A = [int(c) for c in input().split()]
    B = [int(c) for c in input().split()]

    def save(i):
        n = min(A[i], B[i])
        m = 0
        if B[i] > A[i]:
            m = min(A[i+1], B[i] - A[i])
            A[i+1] -= m
        return n+m

    print(reduce(lambda total, i: total + save(i), range(N), 0))


main()

Measured memory_bytes: 19740
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

long long MOD = 1000000007;

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

    vector<vector<ll>> edge(M,vector<ll>(3,0));
    for(int i=0; i<M; i++){
        for(int j=0; j<3; j++){
            cin >> edge[i][j];
        }
    }

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

    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> cp;
    cp.push(make_pair(0,1));
    for(int i=0; i<M; i++){
        int L=edge[i][0];
        int R=edge[i][1];
        ll C=edge[i][2];

        ll cost=cp.top().first;
        int pos=cp.top().second;

        while(pos<L){
            cp.pop();
            if((int)cp.size()==0){
                cout << -1 << endl;
                return 0;
            }
            pos=cp.top().second;
            cost=cp.top().first;
        }
        cp.push(make_pair(cost+C,R));
    }
    while(cp.top().second<N){
        cp.pop();
        if((int)cp.size()==0){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << cp.top().first << endl;
}

Measured memory_bytes: 7800
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

N,M,V,P = LI()
A = LI()
A.sort()

def check(x):
    if (N-x)<=P:
        return True
    x_score = A[x] + M
    if (V-x-P) <= 0:
        return(A[N-P]<=x_score)

    total_v = (V-x-P)*M

    if(A[N-P]>x_score):
        return False

    for i in range(x+1,N-P+1):
        total_v -= min(M,(x_score - A[i]))
    if(total_v>0):
        return False
    return True

def main():
    if(check(0)):
        print(N)
        return

    isOK = N-1
    isNG = 0
    while(isOK-isNG>1):
        mid = (isOK+isNG)//2
        if(check(mid)):
            isOK = mid
        else:
            isNG = mid
    print(N-isOK)
    return


if __name__ == "__main__":
    main()



Measured memory_bytes: 58736
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}
 
const int maxn=100005;
//i_am_noob
int n,k;
string str;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> n >> k >> str;
	str[k-1]=str[k-1]-('A'-'a');
	print1(str);
	return 0;
}


Measured memory_bytes: 256
def solve(n, hhh, aaa):
    n2 = 1 << n.bit_length()
    offset = n2 - 1
    data = [0] * ((n2 << 1) - 1)

    def update(k, x):
        i = k + offset
        data[i] = max(data[i], x)
        while i:
            i = (i - 1) // 2
            data[i] = max(data[i], x)

    def get_max(k):
        i = k + offset
        ret = data[i]
        while i:
            if i % 2 == 0:
                ret = max(ret, data[i - 1])
            i = (i - 1) // 2
        return ret

    srt = sorted((h, i) for i, h in enumerate(hhh))
    for h, i in srt:
        update(i, get_max(i) + aaa[i])

    return data[0]


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))


Measured memory_bytes: 123856
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int main(void){
  int x,y,i,j,n,e,t;
  string s;
  vector<int> g[2];
  cin >> s >> x >> y;
  n=s.size();
  i=e=0;
  while (i<n){
    t=0;
    while (i<n && s[i]=='F'){
      i++;
      t++;
    }
    if (g[e].size()==0 || t>0) g[e].push_back(t);
    i++;
    e=1-e;
  }
   
  int xmin=8000,xmax=8000,ymin=8000,ymax=8000;
  bool xx[4010][16010]={false},yy[4010][16010]={false};
  xx[0][8000]=yy[0][8000]=true;
  for (i=0;i<g[0].size();i++){
    for (j=xmin;j<=xmax;j++) if (xx[i][j]){
      xx[i+1][j+g[0][i]]=xx[i+1][j-g[0][i]]=true;
      if (xmin>j-g[0][i]) xmin=j-g[0][i];
      if (xmax<j+g[0][i]) xmax=j+g[0][i];
    }
    if (i==0 && g[0][0]!=0) xx[1][8000-g[0][0]]=false;
  }
  for (i=0;i<g[1].size();i++){
    for (j=ymin;j<=ymax;j++) if (yy[i][j]){
      yy[i+1][j+g[1][i]]=yy[i+1][j-g[1][i]]=true;
      if (ymin>j-g[1][i]) ymin=j-g[1][i];
      if (ymax<j+g[1][i]) ymax=j+g[1][i];
    }
  }
  if (xx[g[0].size()][x+8000] && yy[g[1].size()][y+8000]){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}

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


int main(){
	int n,m,k;
	scanf("%d %d",&n,&m);
	if(m>(n-1)*(n-2)/2) return !puts("-1");
	k=n-1+(n-1)*(n-2)/2-m;
	printf("%d\n",k);
	for(int i=2; i<=n; i++){
		printf("1 %d\n",i);
	}
	k-=n-1;
	if(!k) return 0;
	for(int i=2; i<=n; i++){
		for(int j=i+1; j<=n; j++){
			printf("%d %d\n",i,j);
			k--;
			if(!k) return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

ll nums[300009];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;
    cin>>N;
    
    rep(i,3*N) cin>>nums[i];
    
    sort(nums,nums+3*N);
    reverse(nums,nums+3*N);
    
    ll ans=0;
    rep(i,N) ans+=nums[i*2+1];
    cout1(ans)
}

Measured memory_bytes: 2560
N = int(input())
A = list(map(int, input().split()))
B = [A[0]]
ans = 0
m = 10 ** 9 + 7
for i in range(1, N):
    B.append(B[i - 1] + A[i])
    ans += A[i] * B[i - 1]
    ans %= m
print(ans)
    

Measured memory_bytes: 31528
n,m,k = list(map(int, input().split()))
done = 0
for i in range(n+1):
    for j in range(m+1):
        r = i*(m-j)+j*(n-i)
        if r == k:
            print('Yes')
            done = 1
            break
    if done == 1:break
if done == 0:print('No')

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

int main() {
	// your code goes here
	int n;
	cin>>n;
	string s;
	cin>>s;
	int q;
	cin>>q;
	set<int>a[26];
	for(int i=0;i<n;i++)
	{
	    a[s[i]-'a'].insert(i+1);
	}
	while(q--)
	{
	    int t;
	    cin>>t;
	    if(t==1)
	    {
	        int p;
	        char c;
	        cin>>p>>c;
	        char x=s[p-1];
	        s[p-1]=c;
	        a[x-'a'].erase(p);
	        a[c-'a'].insert(p);
	    }
	    else
	    {
	        int l,r;
	        cin>>l>>r;
	        int cnt=0;
	        set<int>::iterator it;
	        for(int i=0;i<26;i++)
	        {
	            it=a[i].lower_bound(l);
	            if(it!=a[i].end() && *it<=r)
	            cnt++;
	            
	        }
	        cout<<cnt<<"\n";
	    }
	}
	
	return 0;
}


Measured memory_bytes: 24196
package main

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

func main() {
	var N,M,K int

	
	fmt.Scan(&N,&M,&K)

	As := make([]int, N+1)
	Bs := make([]int, M+1)

	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	var sum int
	for i := 0; i < N; i++ {
		sc.Scan()
		a, _ := strconv.Atoi(sc.Text())
		sum += a
		As[i+1] = sum		
	}

	sum = 0
	counter := 0
	for i := 0; i < M; i++ {
		sc.Scan()
		b, _ := strconv.Atoi(sc.Text())
		sum += b
		if sum > K {
			break
		}
		Bs[i+1] = sum
		counter = i+1
	}
	Bs = Bs[0:counter+1]

	var a, b int
	var max float64
	bLoc := len(Bs) -1
	for i := 0; i < len(As); i++ {
		a = As[i]
		if a > K {
			break
		}
		for j := bLoc; j >= 0; j-- {
			b = Bs[j]
			
			if a + b > K{
				continue
			}
			// fmt.Println(i,j,a,b, a+b)
			max = math.Max(max, (float64)(i + j))
			bLoc = j
			break
		}
	}
	fmt.Println(max)

}



Measured memory_bytes: 6180
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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 (b<a) { a = b; return 1; } return 0; }

void _main() {
  int H, W, h, w;
  cin >> H >> W >> h >> w;
  int ans = (H-h) * (W-w);
  cout << ans << "\n";
}

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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int ans[200010];

int main() {
  int N;
  cin >> N;
  int a[N];
  for (int i = 1; i < N; i++) cin >> a[i];

  for (int i = 1; i < N; i++) {
    ans[a[i]-1]++;
  }

  for (int i = 0; i < N; i++) {
    cout << ans[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 5152