akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int n;
ll wmax;
vector<ll> v[4];

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n >> wmax;
	// map<int, int> mp;

	ll w0, v0;
	cin >> w0 >> v0;
	// mp[0]++;
	v[0].push_back(v0);
	FOR(i, n-1) {
		ll we, va;
		cin >> we >> va;
		we -= w0;
		v[we].push_back(va);
		// mp[w]++;
	}
	FOR(i, 4) {
		sort(v[i].begin(), v[i].end());
		reverse(v[i].begin(), v[i].end());
	}
	FOR(i, 4) {
		for (int j = 1; j < v[i].size(); j++) {
			v[i][j] += v[i][j-1];
		}
	}

	// ll dp[mp[0]+1][mp[1]+1][mp[2]+1][mp[3]+1];
	ll ma = 0;
	FOR(j0, v[0].size()+1) {
		FOR(j1, v[1].size()+1) {
			FOR(j2, v[2].size()+1) {
				FOR(j3, v[3].size()+1) {
					ll ret = 0;
					if (j0) ret += v[0][j0-1];
					if (j1) ret += v[1][j1-1];
					if (j2) ret += v[2][j2-1];
					if (j3) ret += v[3][j3-1];
					if (j0*w0 + j1*(w0+1) + j2*(w0+2) + j3*(w0+3) <= wmax) ma = max(ma, ret);
				}
			}
		}
	}
	// int i0 = 0, i1 = 0, i2 = 0, i3 = 0;
	// for (i0 = 0; i0 <= mp[0]; i0++) {
	// 	if (i0 > 0) {
	// 		dp[i0][i1][i2][i3] = dp[i0-1][i1][i2][i3] + value[0].top();
	// 		value[0].pop();
	// 	}
	// 	for (i1 = 0; i1 <= mp[1]; i1++) {
	// 		if (i1 > 0) {
	// 			dp[i0][i1][i2][i3] = dp[i0][i1-1][i2][i3] + value[1].top();
	// 			value[1].pop();	
	// 		}
	// 		for (i2 = 0; i2 <= mp[2]; i2++) {
	// 			if (i2 > 0) {
	// 				dp[i0][i1][i2][i3] = dp[i0][i1][i2-1][i3] + value[2].top();
	// 				value[2].pop();	
	// 			}
	// 			for (i3 = 0; i3 <= mp[3]; i3++) {
	// 				if (i3 > 0) {
	// 					dp[i0][i1][i2][i3] = dp[i0][i1][i2][i3-1] + value[3].top();
	// 					value[3].pop();
	// 				}
	// 			}
	// 		}
	// 	}
	// }

	// FOR(i0, mp[0]+1) {
	// 	bool f0 = false;
	// 	FOR(i1, mp[1]+1) {
	// 		bool f1 = false;
	// 		FOR(i2, mp[2]+1) {
	// 			bool f2 = false;
	// 			FOR(i3, mp[3]+1) {
	// 				bool f3 = false;
	// 				if (i0 && !f0) {
	// 					dp[i0][i1][i2][i3] = dp[i0-1][i1][i2][i3] + value[0].top();
	// 					value[0].pop();
	// 					f0 = true;
	// 				}
	// 				if (i1 && !f1) {
	// 					dp[i0][i1][i2][i3] = dp[i0][i1-1][i2][i3] + value[1].top();
	// 					value[1].pop();	
	// 					f1 = true;
	// 				}
	// 				if (i2 && !f2) {
	// 					dp[i0][i1][i2][i3] = dp[i0][i1][i2-1][i3] + value[2].top();
	// 					value[2].pop();	
	// 					f2 = true;
	// 				}
	// 				if (i3 && !f3) {
	// 					dp[i0][i1][i2][i3] = dp[i0][i1][i2][i3-1] + value[3].top();
	// 					value[3].pop();
	// 					f3 = true;
	// 				}
	// 			}
	// 		}
	// 	}
	// }

	// ll ma = 0;
	// FOR(j0, mp[0]+1) {
	// 	FOR(j1, mp[1]+1) {
	// 		FOR(j2, mp[2]+1) {
	// 			FOR(j3, mp[3]+1) {
	// 				if (j0*w0 + j1*(w0+1) + j2*(w0+2) + j3*(w0+3) <= wmax) {
	// 					ma = max(ma, dp[j0][j1][j2][j3]);
	// 				}
	// 			}
	// 		}
	// 	}
	// }
	cout << ma << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  int a, b, c, n, i, sya, sum;
  scanf("%d",&n);
  for(i=0;i<n;i++){
  scanf("%d %d %d", &a, &b, &c);
    if(a > b && a > c){
      sya = a*a;
      sum = b*b + c*c;
    } else if(b > a && b > c){
      sya = b*b;
      sum = a*a + c*c;
    } else {
      sya = c*c;
      sum = a*a + b*b;
    }
    if(sya == sum){
      printf("YES\n");
    }else{
      printf("NO\n");
    }
  }
  return 0;
}

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

int N, M;
int D[1010], C[1010];
int memo[1010][1010];

int dfs(int idx = 0, int day = 0) {
  if (day >= M) return 0;
  if (memo[idx][day] != -1) return memo[idx][day];

  int &res = memo[idx][day];
  if (M - day == N - idx) {
    res = dfs(idx + 1, day + 1) + D[idx] * C[day];
  } else {
    res = min(dfs(idx, day + 1), dfs(idx + 1, day + 1) + D[idx] * C[day]);
  }

  return res;
}

int main() {
  cin >> N >> M;
  for (int i = 0; i < N; ++i) cin >> D[i];
  for (int i = 0; i < M; ++i) cin >> C[i];
  memset(memo, -1, sizeof(memo));
  cout << dfs() << endl;

  return 0;
}

Measured memory_bytes: 7100
#include <stdio.h>
#include <limits.h>

int main(void)
{
  long n,i;
  long goukei = 0;
  
  scanf("%ld",&n);
  
  for(i=1; i<=n; i++){
    if(i%3!=0 && i%5!=0){
      goukei += i;
      //printf("%d ",i);
    }
  }
  printf("%ld",goukei);
  return 0;
}

Measured memory_bytes: 1736
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();

    if((4 * a * b) < a * a + b * b + c * c + 2 * (a * b - b * c - c * a) && c - a - b > 0){
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}


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

int main(){

    int N, K;
    cin >> N >> K;
    int h[N];
    for(int i = 0; i < N; i++){
        cin >> h[i];
    }

    int cost[N];
    cost[0] = 0;
 //   cost[1] = abs(h[1] - h[0]);

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

        int MINCOST = cost[i-1] + abs(h[i] - h[i-1]);

        if(i < K){
            for( int j = 1; j < i; j++){
                MINCOST = min(MINCOST,cost[i-j-1] + abs(h[i] - h[i-j-1]));
            }
        }else{
            for( int j = 1; j < K; j++){
                MINCOST = min(MINCOST,cost[i-j-1] + abs(h[i] - h[i-j-1]));
            }
        }

        cost[i] = MINCOST;
    }
    
    cout << cost[N-1] << endl;
    
}

Measured memory_bytes: 1024
#include<iostream>
#include<stdio.h>
#include<string.h>
typedef long long LL;
using namespace std;
int main()
{
 char a[105],b[105],c[105];
 cin>>a>>b>>c;
    int la,lb,lc;  
    int flag=1;  
    int n1=strlen(a),n2=strlen(b),n3=strlen(c);    
    int x=-1,y=-1,z=-1;  
     while(1)  
        {  
            if(x==n1)  
            {  
                cout<<"A"<<endl;  
                break;  
            }  
            if(y==n2)  
            {  
                cout<<"B"<<endl;  
                break;  
            }  
             if(z==n3)  
            {  
                cout<<"C"<<endl;  
                break;  
            }  
            if(flag==1)  
            {  
                  x++;  
                flag=a[x]-'a'+1;  
               // cout<<x<<" "<<flag<<endl;
  
  
            }  
             if(flag==2)  
            {  
                 y++;  
                flag=b[y]-'a'+1;  
                // cout<<x<<" "<<flag<<endl;
  
            }  
            if(flag==3)  
            {  
                z++;  
                flag=c[z]-'a'+1;  
                // cout<<x<<" "<<flag<<endl;
  
            }  
        }  
      
    
    return 0;  
}  


Measured memory_bytes: 256
// abc079_d
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif
    int H, W;
    cin >> H >> W;
    vector<vector<int>> C(10, vector<int>(10, 0));
    REP(i, 10) REP(j, 10) cin >> C[i][j];

    vector<vector<int>> S(H, vector<int>(W, 0));
    REP(i, H) REP(j, W) cin >> S[i][j];

    REP(k, 10) REP(i, 10) REP(j, 10){
        C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
    }

//    REP(i, 10) print(C[i]);

    ll ans = 0;
    REP(i, H) REP(j, W){
        if (S[i][j] != -1){
            ans += C[S[i][j]][1];
        }
    }

    print(ans);


    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
#include<map>
using namespace std;
int a[300010];
int main()
{
	map<int,int>mp;
	int n,i,t=1;scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		mp[a[i]]++;
		if(mp[a[i]]>1)t=0;
	}
	if(t)printf("YES\n"); 
	else printf("NO\n");   
}

Measured memory_bytes: 10368
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <cmath>
#include <iterator>
#include <utility>
#include <set>
#include <random>
#include <map>
#include <stack>
#include <queue>
#include <list>
 
using namespace std;
 
int main() {
    int n, k, x, y;
    cin >> n >> k >> x >> y;
    if (n <= k)
    {
        cout << n*x << endl;
    }
    else
    {
        cout << k*x + (n - k)*y << endl;
    }
 
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define pb push_back
const int N = 100005;
vi con[N];
int g[N];
int dfs(int s, int p){
    int _g = 0;
    for(int v : con[s]) if(v != p) _g ^= (dfs(v, s) + 1);
    return g[s] = _g;
}
int main(){
    int n;
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        con[u].pb(v);
        con[v].pb(u);
    }
    cout << (dfs(1, 0) == 0 ? "Bob" : "Alice");
}

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

typedef long long ll;
typedef pair <int, int> pii;

const int N = 12 + 1 , inf = 2e9;

int n, m, a[N][N], cost[N], x, dp[(1 << N)];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> x;
	for (int i = 0; i < n; i++) {
		cin >> cost[i];
		for (int j = 0; j < m; j++)
			cin >> a[i][j];
	}
	int ans = inf;
	for (int mask = 0; mask < (1 << n); mask++) {
		dp[mask] = 0;
		vector <int> cur(m, 0);
		for (int i = 0; i < n; i++)
			if(mask & (1 << i)) {
				dp[mask] += cost[i];
				for (int j = 0; j < m; j++)
					cur[j] += a[i][j];
			}
		for (int j = 0; j < m; j++)
			if(cur[j] < x)
				dp[mask] = inf;
		ans = min(ans, dp[mask]);
	}
	cout << ((ans == inf)? -1 : ans) << "\n";
}


Measured memory_bytes: 3668
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int main()
{
    long long int N, C, K;
    if (scanf("%lld%lld%lld", &N, &C, &K) < 3) return 0;
 
    long long int lateT = 0;
    long long int busCnt = 0;
    long long int busPsn = 0;
 
    vector<long long int> vi;
 
    for (int i = 0; i < N; i++)
    {
        long long int T;
 
        if (scanf("%lld", &T) < 1) return 0;
 
        vi.push_back(T);
    }
 
    sort(vi.begin(), vi.end());
 
    for (int i = 0; i < N; i++)
    {
        if (0 < busPsn && K < vi[i] - lateT)
        {
            busCnt++;
            busPsn = 0;
            lateT = vi[i];
        }
        else if (busPsn == 0)
        {
            lateT = vi[i];
        }
 
        busPsn++;
 
        if (C == busPsn)
        {
            busCnt++;
            busPsn = 0;
        }
        else if (i == N - 1)
        {
            busCnt++;
        }
    }
 
    printf("%lld\n", busCnt);
    return 0;
}


Measured memory_bytes: 1400
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
p=list(map(int,input().split()))

dic={}
for i in range(n):
    dic[p[i]]=i
# print(dic)

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    # [1,i]の足し算
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    # [i,j]の足し算
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i-1)

bi=BIT(n+1)
ans=0
for i in range(n)[::-1]:
    bi.add(dic[i+1]+1,i+1)
    # print(bi.el)
    lsum=bi.get(1,dic[i+1])
    l,r=-1,dic[i+1]
    while r-l>1:
        half=(r+l)//2
        if bi.get(1,half)>=lsum:
            r=half
        else:
            l=half
    l1=r
    l2=-1
    if r!=0:
        lsum=bi.get(1,r-1)
        l,r=-1,r-1
        while r-l>1:
            half=(r+l)//2
            if bi.get(1,half)>=lsum:
                r=half
            else:
                l=half
        l2=r
    # print(l1,l2)
    rsum=bi.get(dic[i+1]+2,n)
    l,r=dic[i+1]+2,n+2
    while r-l>1:
        half=(r+l)//2
        if bi.get(half,n)>=rsum:
            l=half
        else:
            r=half
    # print(rsum,l,r)
    r1=l
    r2=n+1
    if r!=n+1:
        rsum=bi.get(r1+1,n)
        l,r=r1+1,n+2
        while r-l>1:
            half=(r+l)//2
            if bi.get(half,n)>=rsum:
                l=half
            else:
                r=half
        r2=l
    # print(l2,l1)
    # print(r1,r2)
    # print(bi.el)
    if i==n-1:
        continue
    if l1+l2==-1:
        ans+=(dic[i+1]+1-l1)*(r2-r1)*(i+1)
    elif r1+r2==2*n+3:
        ans+=(l1-l2)*(r1-dic[i+1]-1)*(i+1)
    elif l2+4==r2:
        ans+=2*(i+1)
    else:
        ans+=((l1-l2)*(r1-dic[i+1]-1)+(dic[i+1]+1-l1)*(r2-r1))*(i+1)
    # print(l1-l2,r1-dic[i+1]-1,dic[i+1]+1-l1,r2-r1)
    # print(ans)
print(ans)

Measured memory_bytes: 107836
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<vector<int> > edge;
int odeg[26], ideg[26];
int check[26];

int foo(int n) {
	if(check[n]<=0)
		return 0;
	check[n] = 0;
	for(int i = 0; i < edge[n].size(); i++)
		foo(edge[n][i]);
	return 1;
}

int main() {
	int n;
	while(cin >> n, n) {
		edge.clear();
		edge.resize(26);
		for(int i = 0; i < 26; i++) {
			odeg[i] = ideg[i] = check[i];
			check[i] = -1;
		}
		for(int i = 0; i < n; i++) {
			string s;
			cin >> s;
			int a, b;
			a = s[0]-'a'; b = s[s.size()-1] -'a';
			edge[a].push_back(b);
			odeg[a]++;
			ideg[b]++;
			check[a] = 1;
		}
		int a = 0;
		bool flg = true;
		for(int i = 0; i < 26; i++) {
			flg &= odeg[i] == ideg[i];
		}
		for(int i = 0; i < 26; i++) {
			a += foo(i);
		}
		if(flg && a == 1)
			cout << "OK" << endl;
		else
			cout << "NG" << endl;
	}
}

Measured memory_bytes: 1284
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define mod1 1000000007
#define ff first
#define ss second
#define INF INT_MAX
#define INFLL LLONG_MAX
typedef long long int ll;
// #define intLL unsigned long long int//used when x<2^64-1 && x>0
#define int long long//used when x<2^63-1
int fact[200005];
int power(int a, int b)
{
    int res=1;
    while(b)
    {
        if(b&1)
        {
            res*=a;
            res%=mod1;
        }
        a*=a;
        a%=mod1;
        b/=2;
    }
    return res;
}
int add(int a, int b)
{
    return (0LL+a+b)%mod1;
}
int sub(int a, int b)
{
    return add(a, mod1-b);
}
int mul(int a, int b)
{
    return (1LL*a*b)%mod1;
}
int inv(int x)
{
    return power(x, mod1-2);
}
int nCr(int n, int r)
{
    return mul(fact[n], inv(mul(fact[r], fact[n-r])));
}
int cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    return (a.ff>b.ff);
}
int32_t main()
{

    IOS;
    int n;
    cin>>n;
    vector<pair<int, int>> v;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        v.pb({x, i});
    }
    sort(v.begin(), v.end(), cmp);
    int dp[n+1][n+1];
    memset(dp, 0, sizeof(dp));//dp[i][j] means i elements have been placed with j elements on the left
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            dp[i][j+1]=max(dp[i][j+1], dp[i-1][j]+v[i-1].ff*abs(v[i-1].ss-(j+1)));//putting i th one at j+1
            dp[i][j]=max(dp[i][j], dp[i-1][j]+v[i-1].ff*abs(v[i-1].ss-(n-(i-1-j))));
        }
    }
    int mx=0;
    for(int i=1;i<=n;i++)
    {
        mx=max(mx, dp[n][i]);
    }
    cout<<mx<<"\n";
    return 0;
}

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

using namespace std;

#define ll long long
typedef complex<double> P;

int A[2000000];
int B[2000000];
int C[10001] = {0};
int k = 0;
int n;

void counting_sort() {
  // ????????°????¨????
  for (int i = 0; i < n; i++) {
    C[A[i]]++;
  }
  for (int i = 1; i <= k; i++) {
    C[i] += C[i-1];
  }

  for (int i = n-1; i >= 0; i--) {
    B[C[A[i]]-1] = A[i];
    C[A[i]]--;
  }
}

void show() {
  for (int i = 0; i < n; i++) {
    cout << B[i] << (i == n-1 ? '\n' : ' ');
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> A[i];
    k = max(k, A[i]);
  }

  counting_sort();

  show();
}

Measured memory_bytes: 18704
#include <iostream>                                                                                                       
#include <vector>
#include <algorithm>
#include <set>

int main(){
   int N;
   std::cin >> N;
   std::vector<std::pair<int, int> > R(N), B(N);
   int x, y;
   for(int i=0; i<N; ++i){
      std::cin >> x >> y;
      R[i] = std::make_pair(x, y); 
   }   
   for(int i=0; i<N; ++i){
      std::cin >> x >> y;
      B[i] = std::make_pair(x, y); 
   }   

   std::sort(R.begin(),R.end());
   std::sort(B.begin(),B.end());

   std::vector<int> cache;
   for(int i=0; i<N; ++i){
      int ymax = -1; 
      int index = -1; 
      for(int j=0; j<N; ++j){
         if(std::find(cache.begin(),cache.end(),j)!=cache.end()) continue;
         if(R[j].first<B[i].first && R[j].second<B[i].second){
            if(ymax<R[j].second){
               ymax = R[j].second;
               index = j;
            }   
         }
      }   
      if(index>=0) cache.push_back(index);
   }  
   std::cout << cache.size() << std::endl;
   return 0;

}

Measured memory_bytes: 256
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<climits>//long long型の最大値(LLONG_MAX)など
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

int main() {
    ll N,result=0;
    cin >> N;
    for(ll i=N;i>0;i--){
        if(i == 64){
            cout << 64 << endl;
            return 0;
        }else if(i == 32){
            cout << 32 << endl;
            return 0;
        }else if(i == 16){
            cout << 16 << endl;
            return 0;
        }else if(i == 8){
            cout << 8 << endl;
            return 0;
        }else if(i == 4){
            cout << 4 << endl;
            return 0;
        }else if(i == 2){
            cout << 2 << endl;
            return 0;
        }else if(i == 1){
            cout << 1 << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
n, m = map(int, input().split())
A = list(map(int, input().split()))

from collections import Counter
import heapq
Ad = dict(Counter(A))
keys = [-k for k in Ad.keys()]
heapq.heapify(keys)

tk = m
while tk > 0 and len(keys) > 0:
  key = -1 * keys[0]
  n = Ad[key]

  if n > tk:
    Ad[key] -= tk
    if Ad.get(key//2) != None:
      Ad[key//2] += tk
    else:
      Ad[key//2] = tk
    tk = 0
    break

  else:
    Ad[key] = 0
    heapq.heappop(keys)
    if Ad.get(key//2) != None:
      Ad[key//2] += n
    else:
      Ad[key//2] = n
      heapq.heappush(keys, -1 * (key//2))
    tk -= n

ans = 0
for kv in Ad.items():
  ans += kv[0] * kv[1]
print(ans)

Measured memory_bytes: 33160
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

ll binpow(ll a, ll b) {
    if (b == 0)
    {
        return 1;
    }
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
    {
        return res * a;
    }
    return res;
}

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

string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n,x;
    cin>>n;
    x=100;
    for (int i=1;1;++i)
    {
        x+=(x/100);
        if (x>=n)
        {
            cout<<i;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 3664
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int W = sc.nextInt();
		int[] dp=new int[W+1];
		for(int i=0; i<=W; i++) {
			dp[i]=-1;		//この重さでは価値がない（荷物を組み合わせてこの重さを作り出すことができない）
		}
		dp[0]=0;	//重さ0で価値0は作り出せる
		int[][] products=new int[N][2];
		for(int i=0; i<N; i++) {
			products[i][0]=sc.nextInt();//価値
			products[i][1]=sc.nextInt();//重さ
		}
		for(int i=0; i<N; i++) {
			for(int j=0; j<=W-products[i][1]; j++) {
				if(dp[j]==-1) {
					continue;
					//組み合わせても特定の重さにならないときは、商品の詰合せができないので0
				}
				else {
					dp[j+products[i][1]]=Math.max(dp[j+products[i][1]], dp[j]+products[i][0]);		//同じ商品を何個でも購入できるので、そのままDPテーブルを更新し続ければいいだけなので
					//わざわざ2次元のdpテーブルではなく、即時に更新できる1次元DPテーブルを使う.
				}
			}
		}
		int max=0;
		for(int i=0; i<=W; i++) {
			max=Math.max(max, dp[i]);
		}
		System.out.println(max);
	}
}



Measured memory_bytes: 27032
tmp = list(input().split())
H = int(tmp[0])
K = int(tmp[1])

tmp = list(input().split())

for i in range (H) :
    tmp[i] = int(tmp[i])

tmp = sorted(tmp)

sum = 0

for i in range (H - K) :
    sum += tmp[i]

print (sum)

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

bool check_pal(string s){
	int i = 0,j=s.size()-1;
	while(i<=j){
		if(s[i] != s[j]){
			return false;
		}
		i++;
		j--;
	}
	return true;
}

int main() {
	// your code goes here
	string s;
	cin>>s;
	bool full = check_pal(s);
	int indexlow = (s.size()-1)/2;
	string low = s.substr(0, indexlow);
	int indexhi = (s.size()+3)/2;
	int lenhi = s.size() - indexhi + 1;
	string high = s.substr(indexhi-1,lenhi);
	bool left = check_pal(low);
	bool right = check_pal(high);
	if(!full || !left || !right)
      cout<<"No";
  	else
      cout<<"Yes";
	return 0;
}

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

using namespace std;


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

    int n;
    cin >> n;

    vector<int> A(n-1);

    for(int &i : A)
        cin >> i;

    int sum = A[0];

    for(int i = 1; i < n-1; ++i)
    {
        sum += min(A[i], A[i-1]);
    }

    sum += A[n-2];

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
N,K = map(int,input().split())
X = list(map(int,input().split()))
m = 2*(abs(X[-1])+abs(X[0]))
for i in range(N-K+1):
    if X[i] > 0:
        d = X[i+K-1]
    elif X[i+K-1] < 0:
        d = -X[i]
    else:
        d = X[i+K-1]-X[i]+min(-X[i],X[i+K-1])
    m = min(m,d)
print(m)

Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define ll long long

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

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

    int row,col,k,black,ans=0;
    char c[7][7];

    cin>>row>>col>>k;

    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            cin>>c[i][j];
        }
    }

    for(int maskR = 0; maskR < (1<<row); maskR++){  //checking all formation of row
        for(int maskC = 0; maskC < (1<<col); maskC++){  //checking all formation for column
            black = 0;
            for(int i=0; i<row; i++){
                for(int j=0; j<col; j++){
                    if((maskR>>i & 1)==0 && (maskC>>j & 1)==0 && c[i][j] == '#')black++;    //if current cell is not in formation & its black
                }
            }
            if(black == k)ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
long long m,a,r,c,h;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		if(s[0]=='M')
		m++;
		if(s[0]=='A')
		a++;
		if(s[0]=='R')
		r++;
		if(s[0]=='C')
		c++;
		if(s[0]=='H')
		h++;
	}
	cout<<m*a*h+m*a*c+m*a*r+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h;
 } 

Measured memory_bytes: 3600
//#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define pb(a) push_back
#define print(x) cout<<(x)<<endl
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), n)
#define ub(v,n) upper_bound(v.begin(), v.end(), n)
#define int long long
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")

template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
//typedef pair<int, int>P;
const int MOD = 1e9 + 7; const int MAX = 3000020;
const double pi = acos(-1); const double EPS = 1e-12;
const ll INF = 1e16;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll add(ll x, ll y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
ll sub(ll x, ll y) {
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
ll mult(ll x, ll y) {
	return (x * y) % MOD;
}
ll bin_pow(ll x, ll p) {
	if (p == 0) return 1;
	if (p & 1) return mult(x, bin_pow(x, p - 1));
	return bin_pow(mult(x, x), p / 2);
}

void solve() {
	int X, Y; cin >> X >> Y;
	if (2 * X - Y < 0 || ((2 * X - Y) % 3 != 0)) {
		print(0); return;
	}
	int n = (2 * X - Y) / 3;
	int m = X - 2 * n;
	if (m < 0 || n < 0) {
		print(0); return;
	}
	COMinit();
	ll ans = mult(fac[m + n], finv[m]);
	ans = mult(ans, finv[n]);
	print(ans%MOD);
}

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

	solve();

}



Measured memory_bytes: 70528
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<map>
#define N 2000000
#define M 2000000
using namespace std;
struct node
{
  int x,y,id;
}b[M];
int c[N],ans[M],a[N];
map<int ,int >ma;
bool cmp(node a,node b)
{
  return a.y<b.y;
}
int lowbit(int x)
{
  return x&(-x);
}
void update(int x,int val)
{
   while(x<=N)
   {
     c[x]+=val;
     x+=lowbit(x);
   }
}
int sum(int x)
{
  int s=0;
  while(x)
  {
   s+=c[x];
   x-=lowbit(x);
  }
  return s;
}
int main()
{
   int n,i,m,pre,j;
   //freopen("a.txt","r",stdin);
   scanf("%d%d",&n,&m);
     for(i=1;i<=n;i++)
       scanf("%d",&a[i]);
      for(i=0;i<m;i++)
      {
        scanf("%d%d",&b[i].x,&b[i].y);
        b[i].id=i;
      }
      sort(b,b+m,cmp);  pre=1;
      memset(c,0,sizeof(c));
      for(i=0;i<m;i++)
      {
        for(j=pre;j<=b[i].y;j++)
        {
           if(ma.find(a[j])==ma.end())
                update(j,1);
            else
            {
               update(ma[a[j]],-1);
               update(j,1);
            }
            ma[a[j]]=j;
        }
        ans[b[i].id]=sum(b[i].y)-sum(b[i].x-1);
        pre=b[i].y+1;
      }
      for(i=0;i<m;i++)
        printf("%d\n",ans[i]);
   return 0;
}


Measured memory_bytes: 44844
import java.util.Scanner;

/**
 * Maximum Volume
 * 
 * https://atcoder.jp/contests/abc159/tasks/abc159_c
 */
public class Main {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) throws Exception {
        int L = sc.nextInt();

        System.out.println(String.format("%.6f", Math.pow(L / 3.0, 3)));
    }

}


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

int main(){
    vector<vector<int>> A(3, vector<int>(3));
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
    cin >> A.at(i).at(j);
    }
        }

    int n;
    cin >> n;
    int b;
    for(int i=0; i<n; i++){
        cin >> b;
        for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(A.at(i).at(j)==b)
            A.at(i).at(j)=0;
        }
    }
    }
    if(A.at(0).at(0)== A.at(0).at(1) && A.at(0).at(1)==A.at(0).at(2))
    cout << "Yes";
    else if(A.at(1).at(0)== A.at(1).at(1) && A.at(1).at(1)==A.at(1).at(2))
    cout << "Yes";
    else if(A.at(2).at(0)== A.at(2).at(1) && A.at(2).at(1)==A.at(2).at(2))
    cout << "Yes";
    else if(A.at(0).at(0)== A.at(1).at(0) && A.at(1).at(0)==A.at(2).at(0))
    cout << "Yes";
    else if(A.at(0).at(1)== A.at(1).at(1) && A.at(1).at(1)==A.at(2).at(1))
    cout << "Yes";
    else if(A.at(0).at(2)== A.at(1).at(2) && A.at(1).at(2)==A.at(2).at(2))
    cout << "Yes";
    else if(A.at(0).at(0)== A.at(1).at(1) && A.at(1).at(1)==A.at(2).at(2))
    cout << "Yes";
    else if(A.at(0).at(2)== A.at(1).at(1) && A.at(1).at(1)==A.at(2).at(0))
    cout << "Yes";
    else 
    cout << "No";
    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
llis=[]
rlis=[]
for i in range(m):
  l,r=map(int,input().split())
  llis.append(l)
  rlis.append(r)
llis.sort()
ok=True
for i in range(m):
  if llis[m-1]>rlis[i]:
    ok=False
if ok:
  print(min(rlis)-llis[m-1]+1)
else:
  print(0)

Measured memory_bytes: 11428
fn main() {
    let line = read::<i128>();
    let mut current_pos = line[0];
    let mut move_cnt = line[1];
    let move_distance = line[2];
    // skip
    let skip_cnt = current_pos.abs() / move_distance;
    let skippable_distance = move_distance * skip_cnt;
    if skip_cnt >= move_cnt {
        let tyouka = skip_cnt - move_cnt;
        let actual_distance = skippable_distance - tyouka * move_distance;
        println!("{}", current_pos.abs() - actual_distance);
        return;
    }
    move_cnt -= skip_cnt;
    current_pos -= skippable_distance;

    // move to nearest pos
    let mut prev_pos = current_pos;
    loop {
        if move_cnt == 0 {
            break;
        }
        if current_pos > 0 {
            current_pos = current_pos - move_distance;
        } else {
            current_pos = current_pos + move_distance;
        }
        move_cnt -= 1;
        if current_pos.abs() >= prev_pos.abs() {
            move_cnt += 1;
            current_pos = prev_pos;
            break;
        }
        prev_pos = current_pos;
    }
    if move_cnt == 0 {
        println!("{}", current_pos.abs());
        return;
    }
    // hanpukuyokotobi
    if move_cnt % 2 == 0 {
        println!("{}", current_pos.abs());
    } else {
        let current_pos = if current_pos > 0 {
            current_pos - move_distance
        } else {
            current_pos + move_distance
        };
        println!("{}", current_pos.abs());
    }
}

use std::io::{self, BufRead, Read};
use std::vec::Vec;
fn read<T: std::str::FromStr>() -> Vec<T> {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.lock().read_line(&mut buf).unwrap();
    parse_line(&buf)
}

fn read_lines<T: std::str::FromStr>(count: usize) -> Vec<Vec<T>> {
    let stdin = io::stdin();
    let mut stdin = stdin.lock();
    let mut result = Vec::<Vec<T>>::with_capacity(count);
    for _ in 0..count {
        let mut buf = String::new();
        stdin.read_line(&mut buf).unwrap();
        result.push(parse_line(&buf));
    }
    result
}

fn parse_line<T: std::str::FromStr>(string: &str) -> Vec<T> {
    string.trim().split(' ').map(|s| T::from_str(s).ok().unwrap()).collect()
}


Measured memory_bytes: 2140
#include <stdio.h>
#include <string.h>

#define MAX_P 1000001

char isprime[MAX_P];

int n, e, m[30];
char dp[2000002];

int max(int a, int b){
    return a > b ? a : b;
}

void sieve(void){
    int x, y;
    memset(isprime, 1, sizeof(isprime));
    isprime[0] = isprime[1] = 0;
    for(x = 2; x * x <= MAX_P; x++){
        if(isprime[x]){
           for(y = x * x; y < MAX_P; y += x){
               isprime[y] = 0;
           }
        }
    }
}

int main(void){
    int x, y;
    sieve();
    while(1){
        scanf("%d%d", &n, &e);
        if(n+e == 0) break;
        for(x = 0; x < n; x++){
            scanf("%d", m+x);
        }
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for(x = 0; x < e; x++){
            if(!dp[x]) continue;
            for(y = 0; y < n; y++){
                dp[x + m[y]] = 1;
            }
        }
        for(x = e; x >= 2; x--){
            if(dp[x] && isprime[x]){
                printf("%d\n", x);
                break;
            }
        }
        if(x < 2){
            printf("NA\n");
        }
    }
    return 0;
}

Measured memory_bytes: 3976
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n;
  m=n%10;
  if(m==3)cout<<"bon"<<endl;
  else if(m==0||m==1||m==6||m==8)cout<<"pon"<<endl;
  else cout<<"hon"<<endl;
}

Measured memory_bytes: 3596
#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template <class T> void corner(bool flg, T hoge) { if (flg) { cout << hoge << endl; exit(0); } }
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) { o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o; }
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) { o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o; }
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) { o << "{" << obj.first << ", " << obj.second << "}"; return o; }
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }
void print(void) { cout << endl; }
template <class Head> void print(Head&& head) { cout << head; print(); }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head << " "; print(forward<Tail>(tail)...); }
void YN(bool flg) { cout << ((flg) ? "YES" : "NO") << endl; }
void Yn(bool flg) { cout << ((flg) ? "Yes" : "No") << endl; }
void yn(bool flg) { cout << ((flg) ? "yes" : "no") << endl; }

int main() {
	int N; cin >> N;
	V<ll> a(N), b(N), c(N);
	REP(i, N) cin >> a[i] >> b[i] >> c[i];

	V<V<ll>> dp(N, V<ll>(3, 0));
	dp[0][0] = a[0];
	dp[0][1] = b[0];
	dp[0][2] = c[0];

	FOR(i,1,N){
		dp[i][0] = max(dp[i - 1][1] + a[i], dp[i - 1][2] + a[i]);
		dp[i][1] = max(dp[i - 1][2] + b[i], dp[i - 1][0] + b[i]);
		dp[i][2] = max(dp[i - 1][0] + c[i], dp[i - 1][1] + c[i]);
	}
	cout << *max_element(ALL(dp[N - 1])) << endl;
	return 0;
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;

template <typename T>
void read(T &x)
{
    static char ch;
    for (ch = getchar(); !isdigit(ch); ch = getchar()) ;
    for (x = 0; isdigit(ch); ch = getchar())
        x = (x<<3)+(x<<1)+ch-'0';
}

int n, k;
bool d[10];

bool check(int x)
{
    while (x)
    {
        if (d[x%10]) return false;
        x /= 10;
    }
    return true;
}

int main()
{
    read(n), read(k);
    for (int i = 1; i <= k; ++i)
    {
        int t;
        read(t), d[t] = true;
    }
    for (int i = n; i <= int(1e5); ++i)
    {
        if (check(i))
        {
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n int
	var s string
	fmt.Scan(&n, &s)

	sum := 1
	for i := 0; i < n-1; i++ {
		ft := s[i : i+1]
		sd := s[i+1 : i+2]
		if ft != sd {
			sum++
		}
	}
	fmt.Println(sum)
}


Measured memory_bytes: 1280
class UnionFind:
  def __init__(self, N):
    self.par=[i for i in range(N)]
    self.rank=[0 for _ in range(N)]
    self.size=[1 for _ in range(N)]
    
  def unite(self, x, y):
    x=self.getroot(x)
    y=self.getroot(y)
    if x!=y:
      if self.rank[x]<self.rank[y]:
        x, y=y, x
      if self.rank[x]==self.rank[y]:
        self.rank[x]+=1
      self.par[y]=x
      self.size[x]+=self.size[y]
      
  def united(self, x, y):
    return self.getroot(x)==self.getroot(y)
      
  def getroot(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x]=self.getroot(self.par[x])
      return self.par[x]

  def getsize(self, x):
    return self.size[self.getroot(x)]
  
N, M=map(int, input().split())
UF=UnionFind(N)
AB=[list(map(int, input().split())) for _ in range(M)]
ans=[0]*(M-1)+[N*(N-1)//2]
for i in range(M-1, 0, -1):
  if UF.getroot(AB[i][0]-1)!=UF.getroot(AB[i][1]-1):
    tmpa=UF.getsize(AB[i][0]-1)
    tmpb=UF.getsize(AB[i][1]-1)
    UF.unite(AB[i][0]-1, AB[i][1]-1)
    ans[i-1]=ans[i]-tmpa*tmpb
  else:
    ans[i-1]=ans[i]
print(*ans, sep='\n')
    

Measured memory_bytes: 37992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
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; }

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

    int N; cin >> N;
    ll x; cin >> x;
    vel a(N); rep(i,N) cin >> a[i];

    ll ans = 0;
    rep(i,N-1) {
        if(a[i] + a[i+1] > x) {
            ans += a[i] + a[i+1] - x;
            if(a[i+1] < a[i] + a[i+1] - x){
                a[i+1] = 0;
                a[i] -= a[i] - x;
            }
            else {a[i+1] -= a[i] + a[i+1] - x;}
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <numeric>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>

using namespace std;

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

typedef long long ll;
typedef unsigned long long ull;

int main(void) {
  int N; cin >> N;
  vector<int> A(N);
  rep(i, N) {
    cin >> A[i];
    A[i]--;
  }

  int ans = 0;
  for (int i = 0; i + 2 < N; i++) {
    if (A[i] == A[i+1] && A[i+1] == A[i+2]) {
      A[i+1] = (A[i+1] + 1) % 9999;
      ans++;
    }
  }

  for (int i = 0; i + 1 < N; i++) {
    if (!(A[i] == A[i+1]))
      continue;
    ans++;
  }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
long long dp[100005];
int n,w[105],W,v[105];
int main(){
	scanf("%d%d",&n,&W);
	for (int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);
	for (int i=1;i<=n;i++)
		for (int j=W;j>=w[i];j--)
			dp[j]=std::max(dp[j],dp[j-w[i]]+v[i]);
	printf("%lld\n",dp[W]);
} 

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<utility>
#include<tuple>
#include<cmath>

using namespace std;
typedef long long ll;

int main(){
    ll n;cin >> n;
    ll ans = n;
    for(ll i=1;i<=sqrt(n);i++){
        if(n%i == 0){
            ll j = n/i;
            ans = min((ll)ans,(ll)(i+j-2));
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
import { readFileSync } from "fs";

// eslint-disable-next-line @typescript-eslint/no-unused-vars
const range = (n: number | bigint) => [...Array(Number(n))].map((_, i) => i);
// eslint-disable-next-line @typescript-eslint/no-unused-vars
const tuple = <T extends unknown[]>(...ts: T) => ts;
// eslint-disable-next-line @typescript-eslint/no-unused-vars
const [cin, nCin, bCin] = (() => {
  const inputs = readFileSync("/dev/stdin", "utf-8").split(/[\n|\s]+/);
  let count = 0;
  const cin = () => inputs[count++];
  return tuple(
    cin,
    () => Number(cin()),
    () => BigInt(cin())
  );
})();
// eslint-disable-next-line @typescript-eslint/no-unused-vars
const isNumber = (x: unknown): x is number => typeof x === "number";
// eslint-disable-next-line @typescript-eslint/no-unused-vars
const isBigint = (x: unknown): x is bigint => typeof x === "bigint";
type NumberOrBigintOrElse<T> = number | bigint extends T
  ? undefined
  : T extends number
  ? number
  : T extends bigint
  ? bigint
  : undefined;
// eslint-disable-next-line @typescript-eslint/no-unused-vars
const max = <T extends number | bigint>(...ts: T[]) =>
  (ts.length === 0
    ? undefined
    : isNumber(ts[0])
    ? Math.max(...(ts as number[]))
    : (ts as bigint[]).reduce((acc, t) =>
        acc >= t ? acc : t
      )) as NumberOrBigintOrElse<T>;
// eslint-disable-next-line @typescript-eslint/no-unused-vars
const min = <T extends number | bigint>(...ts: T[]) =>
  (ts.length === 0
    ? undefined
    : isNumber(ts[0])
    ? Math.min(...(ts as number[]))
    : (ts as bigint[]).reduce((acc, t) =>
        acc <= t ? acc : t
      )) as NumberOrBigintOrElse<T>;
// eslint-disable-next-line @typescript-eslint/no-unused-vars
const abs = <T extends number | bigint>(t: T) =>
  (isNumber(t)
    ? Math.abs(t)
    : isBigint(t)
    ? t >= 0n
      ? t
      : -t
    : undefined) as NumberOrBigintOrElse<T>;

/**
 * Program
 */
const P = 10n ** 9n + 7n;
const addP = (x: bigint, y: bigint) =>
  ((((x % P) + P) % P) + (((y % P) + P) % P)) % P;
const subP = (x: bigint, y: bigint) =>
  ((((x % P) + P) % P) - (((y % P) + P) % P) + P) % P;
const prodP = (x: bigint, y: bigint) =>
  (((((x % P) + P) % P) * ((y % P) + P)) % P) % P;
const powP = (x: bigint, n: bigint): bigint => {
  let tmpN = n;
  const isEvens: boolean[] = [];
  while (tmpN !== 1n) {
    isEvens.push(tmpN % 2n === 0n);
    tmpN /= 2n;
  }
  return isEvens.reduceRight((acc, b) => {
    const tmp = prodP(acc, acc);
    return b ? tmp : prodP(x, tmp);
  }, x);
};
const getAns = (N: bigint): string =>
  addP(subP(powP(10n, N), prodP(2n, powP(9n, N))), powP(8n, N)).toString();
{
  const N = bCin();
  const ans = getAns(N);
  console.log(ans);
}


Measured memory_bytes: 29636
#include<bits/stdc++.h>
#define fastio     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(x)   cerr<<#x<<": "<<x<<endl;
#define all(x)     (x).begin() , (x).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define endl       '\n'
#define MAX        1000000
typedef long long int ll;
using namespace std;


const ll mod = 1e9+7;
const double eps = 1e-9;


string s;
int dp[2019];

void solve(){
    cin>>s;
    int n=(int)s.size();
    ll ans=0;
    for(int i=0;i<n;i++) {
        int tdp[2019];
        memset(tdp,0,sizeof(tdp));
        int d=(s[i]-'0');
        tdp[d%2019]=1;
        for(int j=0;j<2019;j++) {
            if(dp[j]>0) { 
                int rem=(10*j+d)%2019;
                if(rem==0)ans += dp[j];
                tdp[rem]+=dp[j];
            }
        }
        for(int i=0;i<2019;i++) {
            dp[i]=tdp[i];
        }
    }
    cout<<ans;
}





int main(){
    fastio
    int test=1;
    while(test--)
        solve();
    return 0;
}


Measured memory_bytes: 3756
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define endl "\n"
typedef long long ll;
#define traceV(v) for(auto x:v)cout<<x<<" ";cout<<endl
#define traceM(mp) for(auto x:mp)cout<<x.first<<" "<<x.second<<endl

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

  int A,B,C,D; cin>>A>>B>>C>>D;

  int res = 0;
  bool flg1=false, flg2=false, flg12=false;
  rep(t, max(B,D)+1) {
    flg1 = A<=t && t<=B;
    flg2 = C<=t && t<=D;

    if(flg1 && flg2) ++res;
  }

  cout << max(res-1,0) << endl;

  return 0;
}


Measured memory_bytes: 256