akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <stack>
#include <string>
#include <climits>
using namespace std;

#define MAX_N 101

int n, t;
vector<vector<int> > A(MAX_N, vector<int>(MAX_N, 0));
stack<int> S;
int d[MAX_N] = {};
int f[MAX_N] = {};

void df(int e)
{
    d[e] = t++;
    for (int i = 1; i <= n; i++) {
        if (A[e][i] && !d[i]) df(i);
    }
    f[e] = t++;
}

int main()
{
    int i, u, k, v;
    cin >> n;
    for (i = 0; i <= n; i++) A[0][i]++;
    for (i = 1; i <= n; i++) {
        cin >> u >> k;
        while (k--) {
            cin >> v;
            A[u][v]++;
        }
    }
    t = 0;
    df(0);
    for (i = 1; i <= n; i++)
        cout << i << " " << d[i] << " " << f[i] << endl;
    return 0;
}

Measured memory_bytes: 3188
#include <iostream>
using namespace std ;
int main()
{
  int num ;
  cin >> num ;
  
  double mat[num] ;
  
  for(int i=0; i<num; i++){
    cin >> mat[i] ;
  }
  
  for(int s=0; s<num-1; s++){
    for(int t=s+1; t<num; t++){
      if(mat[t] < mat[s]){
        int matt = mat[t] ;
        mat[t] = mat[s] ;
        mat[s] = matt ;
      }
    }
  }
  for(int j=1; j<num; j++){
    mat[j] =(mat[j-1] + mat[j])/2 ;
  }
  
  cout << mat[num-1]<<endl ;
  
  return 0 ;
}

Measured memory_bytes: 256
#include<iostream>
int main(){int s,t,d,n;std::cin>>n;while(n--){std::cin>>s>>t;d=(t<s&&s<6)?-1:1;while(t!=s){printf("%d ",s);s+=d;if(s==10){d=-1;s=5;}else if(s==-1){d=s=1;}}printf("%d\n",t);}return 0;}

Measured memory_bytes: 0
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const int N = 3e5 + 10;
int n , a[N];
ll Mx[N];

int main(){
    scanf("%d",&n);
    rep(i,1,3*n+1) scanf("%d",a + i);
    priority_queue<int> Q;
    ll s = 0;
    for(int i=n,j=1;i<=n+n;++i){
        for(;j<=i;++j){
            s += a[j];
            Q.push(-a[j]);
        }
        if(sz(Q) > n){
            s += Q.top();
            Q.pop();
        }
        Mx[i] = s;
    }
    while(sz(Q)) Q.pop();
    s = 0;
    ll ans = -1e18;
    for(int i=n+n+1,j=n*3;i>n;--i){
        for(;j>=i;--j){
            s += a[j];
            Q.push(a[j]);
        }
        if(sz(Q) > n){
            s -= Q.top();
            Q.pop();
        }
        ans = max(ans , Mx[i-1] - s);
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 2680
// Problem : A - A?C
// Contest : AtCoder - AtCoder Beginner Contest 166
// URL : https://atcoder.jp/contests/abc166/tasks/abc166_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

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

#define pb push_back
#define vi vector<int>


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string s;
	cin>>s;
	if(s=="ABC")cout<<"ARC\n";
	else	cout<<"ABC\n";
	
   	return 0;
}



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

const int maxn = 1e6 + 5;

int f[maxn];
int nope[maxn];
int a[maxn];

int main() {
	int n; scanf("%d", &n);

	for (int i = 1; i <= n; i++) scanf("%d", a+i);

	for (int i = 1; i <= n; i++) {
		int k = a[i];
		f[k]++;
		if (f[k] == 1)
			for (int j = k+k; j < maxn; j += k) nope[j] = 1;
	}
	
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += (f[a[i]] == 1) and !nope[a[i]];
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 12416
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int N = 105, V = 100005;

ll dp[N][V];
ll value[N];
ll weight[N];
int object_count, max_weight;

void solve() {
    for (int i = 1; i <= object_count; ++i) {
        for (int w = 0; w <= max_weight; ++w) {
            if (w >= weight[i]) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i]] + value[i]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
}

void debug() {
    for (int i = 0; i <= object_count; ++i, putchar('\n')) {
        for (int w = 1; w <= max_weight; ++w) {
            printf("%18lld", dp[i][w]);
        }
    }
}

int main() {
    scanf("%d%d", &object_count, &max_weight);
    for (int i = 1; i <= object_count; ++i) {
        scanf("%lld%lld", weight + i, value + i);
    }
    solve();
    printf("%lld\n", dp[object_count][max_weight]);
    return 0;
}

Measured memory_bytes: 79232
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

int dp[100010];

int main(){
   int n,k;
   cin >> n >> k;
   vector<int> v(n);
   rep(i,n){
      cin >> v[i];
   }
   rep(i,n){
      dp[i] = 1e9+7;
   }
   dp[0] = 0;
   rep(i,n){
      rep(j,k+1){
         if (i+j < n) dp[i+j] = min(dp[i+j],dp[i] + abs(v[i]-v[i+j]));
      }
   }
   cout << dp[n-1] << endl;
   

  
  return 0;
}


Measured memory_bytes: 4048
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    b = []
    for s in S:
        bottom = 0
        cur = 0
        for c in s:
            if c == '(':
                cur += 1
            else:
                cur -= 1
            bottom = min(bottom, cur)
        b.append((bottom, cur))

    bp = [_ for _ in b if _[1] > 0]
    bn = [_ for _ in b if _[1] <= 0]
    bp.sort(key=lambda x: x[0], reverse=True)
    bn.sort(key=lambda x: x[1]-x[0], reverse=True)

    cur = 0
    for bt, ct in bp:
        if cur + bt < 0:
            return 'No'
        cur += ct

    for bt, ct in bn:
        if cur + bt < 0:
            return 'No'
        cur += ct

    if cur != 0:
        return 'No'
    return 'Yes'



def main():
    N = read_int()
    S = [read_str() for _ in range(N)]
    print(slv(N, S))


if __name__ == '__main__':
    main()


Measured memory_bytes: 231944
from bisect import *
from math import *
N,D,A=map(int,input().split())
monsters=[list(map(int,input().split())) for _ in range(N)]
monsters.sort(key=lambda x:x[0])
killingrange=[0]*N
monsterspoint=[]
monstershp=[]
imos=[0]*N
for i in range(N):
    monsterspoint.append(monsters[i][0])
    monstershp.append(monsters[i][1])
for i in range(N):
    ind=bisect(monsterspoint,monsterspoint[i]+2*D)
    killingrange[i]=ind
#print(killingrange)
cnt=0
for i in range(N):
    monstershp[i]=monstershp[i]+imos[i]
    if (monstershp[i]>0):
        cnt=cnt+ceil(monstershp[i]/A)
        imos[i]=imos[i]-A*ceil(monstershp[i]/A)
        if killingrange[i]<N:
            imos[killingrange[i]]=imos[killingrange[i]]+A*ceil(monstershp[i]/A)
    if i<N-1:
        imos[i+1]=imos[i]+imos[i+1]
    #print(monstershp,imos)
print(cnt)

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

int main() {
  vector<int> V(5);
  for (int i = 0; i < 5; i++) cin >> V.at(i);
  int K;
  cin >> K;
  cout << ((V.at(4) - V.at(0) <= K) ? "Yay!" : ":(") << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define Rep(i,n) for((int) (i)=0;(i)<(int)(n);(i)++)
#define mp make_pair
#define pb push_back
#define x first
#define y second
using namespace std;
pair<int,int> a[100000];
int n,cnt=0,m;
long long ans;
int main(){
	cin>>n>>m;
	int i;
	for(i=0;i<n;i++){
		cin>>a[i].x>>a[i].y;	
	}
	sort(a,a+n);
	priority_queue<int> q;
	for(i=0;i<m;i++)
	{
		while(cnt<n&&a[cnt].x<=i+1)
		{
			q.push(a[cnt++].y);
		}
		if(!q.empty())
		{
			ans+=q.top();
			q.pop();	
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 1660
//Jai Bhole Ki
#include <bits/stdc++.h>
using namespace std;
#define fast static int fastline = []() { std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();
#define ll long long
#define LL unsigned ll
#define pb push_back
#define pi pair<ll,ll>
#define debug(x) cout<<x<<"\n";
#define debugg cout<<"debugged\n";
#define minval -2e9
#define maxval 2e9
long double PI =3.14159265358979323846;
 
const ll M=1e9+7;
const ll inf=1e18;
const ll ms=2e5+5;
fast;
ll ans,n,t;
void solve()
{
    cin>>n;
    for(int i=n;i<=999;i++)
    {
        ll nn=i;bool flag=1;
        ll dig=nn%10;
        nn/=10;
        while(nn)
        {
            if(dig!=nn%10)
                {flag=0;break;}
                nn/=10;
        }
        if(flag)
            {cout<<i<<endl;return;}
    }
}
int main()
{
 // freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
    //int t;cin>>t;while(t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int n,i,j;
    int eight_count = 0;
    int tmp = 0;
    scanf("%d",&n);
    
    for(int i = 1; i <= n ; i++){
        if(i%2 == 1){
            for(j = 1; j <= i ; j++){ //約数の数を数える
                if(i%j == 0) tmp++;
            }
            if(tmp == 8) eight_count++;
            tmp = 0;
        }
    }
    printf("%d\n",eight_count);
    return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
int main()
{
    int A,B,C;
    scanf("%d%d%d",&A,&B,&C);
    if(A>=1 && A<=9 && B>=1 && B<=9 && C>=1 && C<=9)
    {
    if(A==B && A==C)
        printf("No \n");
    else if((A==B && A!=C) || (A==C && A!=B) || (B==C && B!=A))
        printf("Yes\n");
    else
        printf("No \n");
    }
    else
        printf("Enter the values within the range \n");


    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
int n;
double t[110],v[110],sum[110];
main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>t[i+1];
		sum[i+1]=sum[i]+t[i+1];
	}
	for(int i=0;i<n;i++)cin>>v[i+1];
	double ans=0;
	double p=0;
	int f=0;
	for(double i=0.5;i<=sum[n];i+=0.5)
	{
		if(i>sum[f])f++;
		double now=v[f];
		for(int j=0;j<=n+1;j++)
		{
			double c=now;
			if(j<f)
			{
				c=v[j]+i-sum[j];
			}
			else if(j>f)
			{
				c=v[j]+sum[j-1]-i;
			}
			if(now>c)now=c;
		}
		ans+=(p+now)/4.0;
		p=now;
	}
	cout<<fixed<<setprecision(9)<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using LL = long long;
using namespace std;
class UnionFind{
private:
    vector<int> data;
    vector<LL> diff_weight;
public:
    UnionFind(int size) : data(size,-1), diff_weight(size, 0){}
    int root(int x){
        if(data[x] < 0){
            return x;
        }else{
            root(data[x]);
            diff_weight[x] += diff_weight[data[x]];
            return data[x] = root(data[x]);
        }
    }
    int weight(int x){
        root(x);
        return diff_weight[x];
    }
    bool connect(int x,int y, LL w){

        w += weight(x);w -= weight(y);
        x = root(x);y = root(y);
        if(x != y){
            if(data[x] > data[y])swap(x,y), w = -w;
            data[x] += data[y];data[y] = x;
            diff_weight[y] = w;
        }
        return x != y;
    }
    bool check(int x,int y){
        return root(x) == root(y);
    }
    int Size(int x){
        return -data[x];
    }
    int diff(int a, int b){
        return weight(b) - weight(a);
    }
};

int main(){
   int N,q;cin >> N >> q;
   UnionFind Uni(N);
   for(int a = 0;a < q;a++){
       int x;cin >> x;
       if(x == 0){
           int d,e,f;cin >> d >> e >> f;
           Uni.connect(d,e,f);
       }else{
           int d,e;cin >> d >> e;
           if(Uni.check(d,e))cout<<Uni.diff(d,e)<<endl;
           else cout<<"?"<<endl;
       }
   }
}



Measured memory_bytes: 3884
#include<stdio.h>

int main(void){
	
	char str;
	int num[26];
	int i;
		
		for(i = 0;i<26;i++){
			num[i] = 0;
		}
	  

    while(scanf("%c",&str) != EOF){

			if(str >= 'A' && str <= 'Z'){
				int a ;
				a = str - 'A';
				num[a] = num[a] + 1 ;

			}
			else if(str >= 'a' && str <= 'z'){
				int a ;
				a = str - 'a';
				num[a] = num[a] +1;

			}
		
    }
		
	for(i = 0;i<26;i++){
		printf("%c : %d\n",i+'a',num[i]);
	}
    
return 0;
}

Measured memory_bytes: 540
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
string s;
int main(){
  cin>>s;
  ll N=s.size();
  if(s[N-1]=='s'){
  s+="es";
    cout<<s<<endl;
  
  }else{
  s+="s";
    cout<<s<<endl;
  }
  return 0;
}
  

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 998244353;
const ld PI = acosl(-1);

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

    int N, K;
    cin >> N >> K;
    vector<pii> v(K);
    for (int i = 0; i < K; ++i) {
        cin >> v[i].first >> v[i].second;
    }

    vector<ll> dp(N + 1);
    vector<ll> dpsum(N + 2);
    dp[0] = 1;
    for (int i = 1; i < N; ++i) {
        dpsum[i] = (dpsum[i - 1] + dp[i - 1]) % MOD;
        for (int j = 0; j < K; ++j) {
            dp[i] += dpsum[max(i - v[j].first + 1, 0)] - dpsum[max(i - v[j].second, 0)];
            dp[i] %= MOD;
        }
    }

    if (dp[N - 1] < 0)
        dp[N - 1] += MOD;
    cout << dp[N - 1] << endl;

    return 0;
}


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

typedef long long int ll;

int main()
{
    ll h, a;
    cin >> h >> a;

    if(h % a == 0){
        cout << h / a;
    }
    else{
        cout << h / a + 1;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=2e5+1;
const ll INF=4e18;
void solve()
{
	char a;
	cin>>a;
	a=a+1;
	cout<<a<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll T=1,p=0;
	//cin>>T;
	do
	{
		solve();
		p++;
	}while(p<T);
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
unsigned gcd( unsigned a, unsigned b){
  
  if( !b ) return 0;
  if( a%b == 0 ) return b;
  else gcd( b, a%b );
  
}


int main(){
  
  int K;
  cin >> K;
  ll sum = 0;
  for( int i=1; i<= K; i++){
      for( int j=1; j<= K; j++){
        for( int l=1; l<= K; l++){
            sum += gcd(gcd( i,j ),l);

          }
      }
  }
  
  printf("%d\n",sum);
  return 0;
}

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
using ull = unsigned long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

template<class T>
bool ChangeMax(T&a,const T&b){
  if(a >= b) return false;
  a = b;    return true;
}

template<class T>
bool ChangeMin(T&a,const T&b){
  if(a <= b) return false;
  a = b;    return true;  
}

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T,class U>
istream& operator >> (istream&is, P<T,U>&p){
  is >> p.first >> p.second;
  return is;
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v){
    is >> e;
  }
  return is;
}

int main(){
  string s; cin >> s;
  int k; cin >> k;
  int n = (int)s.size();
  for(int i = 0; i < n && k > 0; ++i){
    int need = (26 - (s[i] - 'a'))%26;
    if(need <= k){
      k -= need;
      s[i] = 'a';
    }
  }
  s.back() = 'a'+(s.back()-'a'+k)%26;
  cout << s << endl;
}




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

ll N;


int main(){
	cin>>N;
	vector<ll> A(N);
	vector<ll> a(N);

	for(ll i=0;i<N;i++){
		cin>>A.at(i);
		A.at(i) *= 2;
	}


	a.at(0)=0;
	for(ll i=0;i<N;i++){
		if(i%2==0)
			a.at(0)+=A.at(i);
		else
			a.at(0)-=A.at(i);
	}

	a.at(0) /=2;

	for(ll i=1;i<N;i++)
		a.at(i)=A.at(i-1)-a.at(i-1);

	for(ll i=0;i<N;i++)
		cout<<a.at(i)<<endl;
}

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

int main(){
    int n, m, x;
    cin >> n >> m >> x;
    vector<vector<int>> a(n, vector<int>(m));
    vector<int> c(n);
    for(int i = 0; i < n; i++){
        cin >> c[i];
        for(int j = 0; j < m; j++)cin >> a[i][j];
    }
    int ans = 12345678;
    int all = 1<<n;
    for(int mask = 0; mask < all; mask++){
        vector<int> level(m);
        int cost = 0;
        for(int i = 0; i < n; i++){
            if((mask>>i)&1){
                cost += c[i];
                for(int j = 0; j < m; j++){
                    level[j] += a[i][j];
                }
            }
        }
        bool ok = true;
        for(int j = 0; j < m; j++){
            if(level[j] < x) ok = false;
        }
        if(ok) ans = min(ans,cost);
    }
    if(ans == 12345678) cout << -1 << endl;
    else cout << ans << endl;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long
#define ull unsigned long long
#define REP(i, n) for(int i=0; i<n; i++)

int a[100000];
int main(){
    int N;
    cin >> N;
    int inp;
    REP(i,N){
        cin >> inp;
        a[inp]++;
    }
    ll max = -1;
    ll sum = 0;

    REP(i,100000-2){
        sum = a[i] + a[i+1] + a[i+2];
        if(max < sum)
            max = sum;
    }
    cout << max << endl;

    return 0;
}


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

int k, m, n;
string s = "1122", t = "";
vector<int> v(4);

int main()
{
    for (int i = 0; i < 6; i++)
    {
        cin >> m;
        v[m - 1]++;
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < 4; i++)
        t = t + to_string(v[i]);
    cout << (s == t ? "YES" : "NO") << endl;
}


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

int main()
{
  ll a,b,c,d;
  cin >> a >> b >> c >> d;
  ll r1 = a*c;
  ll r2 = a*d;
  ll r3 = b*c;
  ll r4 = b*d;
  ll r = max({r1,r2,r3,r4});
  cout << r << '\n';
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

int main() {

    string s;
    bool isInverse = false;

    cin >> s;

    list<char> s_link;

    for(int i = 0; i < s.size(); ++i)
        s_link.emplace_back(s[i]);

    int q;


    cin >> q;

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

        int c;
        cin >> c;

        switch (c)
        {
        case 1:

            isInverse = !isInverse;
            break;
        
        case 2:

            int f;
            char ch;
            cin >> f >> ch;

            if( (!isInverse && f == 1) || (isInverse && f == 2))
                s_link.emplace_front(ch);
            else
                s_link.emplace_back(ch);

            break;
        
        }
    }


    if(isInverse) {

        for(auto itr = s_link.rbegin(); itr != s_link.rend(); itr++)
            cout << *itr;
        
    }
    else
    {
        for(auto itr = s_link.begin(); itr != s_link.end(); itr++)
            cout << *itr;
    }
    
    cout << endl;

    return 0;


}

Measured memory_bytes: 9984
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define pb push_back
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
#define mod (int)(998244353)
#define PI 3.14159265358979323846264338327950L
#define debug(vec) cout<<(#vec)<<": "; for (auto& i: vec) cout<<i<<" "; cout<<endl
#define trace(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout << endl; }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << "[ " << *it << " = " << a << " ] ";
    err(++it, args...);
}

signed main(){

    fastIO

    int n;
    cin >> n;
    unordered_map<int, int> mp;
    int sum = 0;
    for (int i = 0, a; i < n; i++) {
      cin >> a;
      mp[a]++;
      sum += a;
    }
    int Q;
    cin >> Q;
    while (Q--) {
      int a, b;
      cin >> a >> b;
      if (mp[a] != 0 && a != b){
        sum -= mp[a]*a;
        mp[b] += mp[a];
        sum += mp[a]*b;
        mp[a] = 0;
      }
      cout << sum << endl;
    }
    
    return 0;
}

Measured memory_bytes: 6992
import bisect

n = int(input())
k = sorted(map(int, input().split()))

hist = []
count = 0
for i in range(n):
    count += 1
    if i == n - 1 or k[i] != k[i + 1]:
        hist.append(count)
        count = 0
hist.sort()

sumh = [0]
for i in range(len(hist)):
    sumh.append(sumh[-1] + hist[i])

def ok(h, d):
    i = bisect.bisect_left(hist, h)
    s = sumh[i] + h * (len(hist) - i)
    return s >= h * d

def binary_search(d):
    lo, hi = 0, n // d + 1
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if ok(mid, d):
            lo = mid
        else:
            hi = mid
    return lo

for d in range(1, n + 1):
    print(binary_search(d))


Measured memory_bytes: 121116
#include <bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll MOD = 1000000007;
const ll INF = 10000000000000;
#define all(v) v.begin(), v.end()

int main(){
  ll N;
  cin >> N;
  if(N%1000==0) cout << 0 << endl;
  else cout << 1000-N%1000 << endl;
  
  
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (int i = (int)a; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define EPS 1e-12

int main(void)
{
  int n, l[205];
  cin >> n;
  REP(i, 2*n) {
    cin >> l[i];
  }
  sort(l, l+2*n);

  int ans = 0;
  for(int i=0; i<2*n; i+=2) {
    ans += l[i];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
use std::cmp::*;
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let I: usize = itr.next().unwrap().parse().unwrap();
    let O: usize = itr.next().unwrap().parse().unwrap();
    let _: usize = itr.next().unwrap().parse().unwrap();
    let J: usize = itr.next().unwrap().parse().unwrap();
    let L: usize = itr.next().unwrap().parse().unwrap();
    let _: usize = itr.next().unwrap().parse().unwrap();
    let _: usize = itr.next().unwrap().parse().unwrap();

    let mut ans = O + I / 2 * 2 + J / 2 * 2 + L / 2 * 2;
    if I > 0 && J > 0 && L > 0 {
        ans = max(
            ans,
            O + 3 + (I - 1) / 2 * 2 + (J - 1) / 2 * 2 + (L - 1) / 2 * 2,
        );
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

using P = pair<int, int>;

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

    int h, w, k;
    scanf("%d %d %d", &h, &w, &k);

    int si, sj, ti, tj;
    scanf("%d %d %d %d", &si, &sj, &ti, &tj);
    --si, --sj, --ti, --tj;

    const int inf = 1e9;
    int d[h][w];
    char s[w + 1];
    rep (i, h)
    {
        scanf("%s", s);
        rep (j, w)
        {
            d[i][j] = (s[j] == '@' ? -1 : inf);
        }
    }


    queue<P> q;
    q.emplace(si, sj);
    d[si][sj] = 0;
    int dy[] = {-1, 0, 1, 0};
    int dx[] = {0, -1, 0, 1};
    while (!q.empty())
    {
        auto from = q.front(); q.pop();
        int fi = from.first;
        int fj = from.second;
        rep (i, 4)
        {
            int ni = fi;
            int nj = fj;
            int dyy = dy[i];
            int dxx = dx[i];
            rep (j, k)
            {
                ni += dyy;
                nj += dxx;
                if (!(IN(0, h, ni) && IN(0, w, nj))) break;
                if (d[ni][nj] < d[fi][fj] + 1) break;
                if (d[ni][nj] != inf) continue;
                d[ni][nj] = d[fi][fj] + 1;
                q.emplace(ni, nj);
            }
        }
    }

    int ans = d[ti][tj];
    if (ans == inf) ans = -1;

    printf("%d\n", ans);
    return 0;
}



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

int main() {
  int N; cin >> N;
  string S; cin >> S;
  if ((N % 2 == 0) && (S.substr(0, N/2) == S.substr(N/2, N/2))) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

int main()
{
	int n;
	cin >> n;
	int ans=0,mx = 0;
	while(n--)
	{
		int x;
		cin >> x;
		ans += x;

		mx = max(x,mx);
	}
	if(ans-2*mx<=0)
	{
		cout<<"No"<<endl;
	}
	else
	{
		cout<<"Yes"<<endl;
	}
	
	return 0;
}

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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#else
#define TEST(n) ((void)0)
#endif

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	TEST(freopen("debug.txt", "w", stderr));
	int N, Q;
	string s;
	cin >> N >> s >> Q;
	for (; Q; Q--) {
		int K, D = 0, M = 0;
		long long DM = 0, ans = 0;
		cin >> K;
		for (int i = 0; i < K; i++) {
			if (s[i] == 'D') D++;
			else if (s[i] == 'M') {
				M++;
				DM += D;
			}
			else if (s[i] == 'C') ans += DM;
		}
		for (int i = K; i < N; i++) {
			if (s[i - K] == 'D') {
				D--;
				DM -= M;
			}
			else if (s[i - K] == 'M') M--;
			if (s[i] == 'D') D++;
			else if (s[i] == 'M') {
				M++;
				DM += D;
			}
			else if (s[i] == 'C') ans += DM;
		}
		cout << ans << '\n';
	}
	return 0;
}

Measured memory_bytes: 1948
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N;
    cin >> N;
    vector<string> S;
    int cnt = 0;
    for (int i = 1; i <= 9; i++) {
        cnt++;
        S.push_back(to_string(i));
        if (cnt == N) {
            cout << S[S.size() - 1] << '\n';
            return 0;
        }
    }
    while (true) {
        vector<string> tmp;
        for (string s : S) {
            int tail = s[s.size() - 1] - '0';
            for (int i = -1; i <= 1; i++) {
                if (tail + i >= 0 && tail + i <= 9) {
                    cnt++;
                    tmp.push_back(s + to_string(tail + i));
                    if (cnt == N) {
                    cout << s + to_string(tail + i) << '\n';
                    return 0;
                    }
                }
            }
        }
        S = tmp;
    }
}


Measured memory_bytes: 4384
#include <bits/stdc++.h>
using namespace std;
template <class T> inline void read(T &x) {
	x = 0; int c = getchar(), f = 1;
	for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
	for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-48);
}
int n, p[2][2005], c[2][2005][2005], f[2005][2005], tr[2][4005];
void inc(int col, int p) {for (; p <= (n<<1); p += (p&-p)) tr[col][p]++;}
int sum(int col, int p) {int ret = 0; for (; p; p -= (p&-p)) ret += tr[col][p]; return ret;}
int main() {
	read(n);
	for (int i = 1, col, val; i <= (n<<1); i++)
		col = getchar() == 'B', read(val), p[col][val] = i;
	memset(tr[0], 0, sizeof tr[0]);
	for (int i = 1; i <= n; i++) {
		memset(tr[1], 0, sizeof tr[1]);
		c[0][i][0] = i-1-sum(0, p[0][i]);
		for (int j = 1; j <= n; j++)
			inc(1, p[1][j]), 
			c[0][i][j] += i-1-sum(0, p[0][i]), 
			c[0][i][j] += j-sum(1, p[0][i]);
		inc(0, p[0][i]);
	}
	memset(tr[1], 0, sizeof tr[1]);
	for (int j = 1; j <= n; j++) {
		memset(tr[0], 0, sizeof tr[0]);
		c[1][0][j] = j-1-sum(1, p[1][j]);
		for (int i = 1; i <= n; i++)
			inc(0, p[0][i]), 
			c[1][i][j] += j-1-sum(1, p[1][j]), 
			c[1][i][j] += i-sum(0, p[1][j]);
		inc(1, p[1][j]);
	}
	memset(f, 0x3f, sizeof f), f[0][0] = 0;
	for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) {
		if (i) f[i][j] = min(f[i][j], f[i-1][j]+c[0][i][j]);
		if (j) f[i][j] = min(f[i][j], f[i][j-1]+c[1][i][j]);
	}
	return printf("%d\n", f[n][n]), 0;
}


Measured memory_bytes: 47360
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r))
                         for r in self.roots())


n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a - 1, b - 1)
maxSize = 0
for j in range(n):
    maxSize = max(maxSize, uf.size(j))
print(maxSize)


Measured memory_bytes: 14592
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cassert>
#include<numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
const int INF = 1001001001;
const long long LINF = 1001002003004005006ll;
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; }
typedef long long ll;
typedef pair<int,int> P;

vector<int> Zalgo(string str){
    int n = str.size();
    vector<int> a(n, 0);
    int from = -1, last = -1;
    for(int i = 1;i < n;i++){
        int &same = a[i];
        if(from != -1){
            same = min(a[i-from], last - i);
            same = max(0, same);
        }
        while(i + same < str.size() && str[same] == str[i+same])same++;
        if(last < i+same){
            last = i + same;
            from = i;
        }
    }
    a[0] = n;
    return a;
}

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int ans = 0;
  rep(i,n){
    auto a = Zalgo(s.substr(i));
    rep(j,n-i){
      chmax(ans,min(j,a[j]));
    }
  }
  cout << ans << endl;
}

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

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int n;cin>>n;
  ll x=0;
  ll y=0;
  ll res=-1;
  vector<ll> v(n);
  for(int i=0;i<n;i++){
    cin>>v[i];
    y += v[i];
  }
  for(int i=0;i<n-1;i++){
    x += v[i];
    y -= v[i];
    if(res==-1){
      res = abs(x-y);
    }else {
      res = min(res, abs(x-y));
    }
  }
  cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int prime[MAX_N];
int used[MAX_N];

void solve() {
	for(int i = 2; i <= 200000; i++) {
		if(used[i]) continue;
		prime[i] = 1;
		for(int j = i; j <= 200000; j += i) {
			used[j] = 1;
		}
	}
	int X; cin >> X;
	while(!prime[X]) X++;
	cout << X << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 1920
N, K, Q = gets.split.map(&:to_i)
A = Q.times.map{gets.to_i}

ret = Array.new(N, Q * -1 + K)

Q.times do |q|
  ret[A[q] - 1] += 1
end

ret.each do |r|
  puts r > 0 ? "Yes" : "No"
end

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

int main(){
    int N,X,i;
    int x[111111];
    cin >> N >> X;
    for(i=0;i<=N-1;i++)
        cin >> x[i];
    sort(x,x+N);
    for(i=0;i<=N-1;i++)
        x[i] -= X;
    int g = x[0];
    for(i=0;i<=N-1;i++)
        g = __gcd(g,x[i]);
    if(g < 0) g = (-1)*g;
    cout << g << endl;
}


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

typedef long long ll;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ANS(n) cout << (n) << endl

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(a);i>=(b);i--)

#define ALL(obj) (obj).begin(),(obj).end()

#define pii pair<int,int>

#define pb(a) push_back(a)
#define mp make_pair

int main()
{
	int x;
	cin >> x;
	int sum = 0;
	FOR(i,1,x+1){
		sum += i;
		if(sum >= x){
			ANS(i);
			return 0;
		}
	}
	return 0;
}


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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds; 
using namespace std;

template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
typedef long long  ll;
typedef vector<ll> VL;
typedef vector<int> VI;
typedef pair<ll,ll> PLL;
typedef pair<int,int> PII;
#define pb push_back

#define F first
#define S second
#define SZ(a) int((a).size())
#define ALL(a) a.begin(),a.end()
#define fr(i,x,y) for(ll i=x;i<y;i++)
#define frr(i,x,y) for(ll i=x-1;i>=y;i--)
#define inf 1e18+1
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const ll mod=1000000007;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll power(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;}a=a*a;b>>=1;}return ans;}
ll powerm(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;ans%=mod;}a=a*a;a%=mod;b>>=1;}return ans%mod;}
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();

void solve()
{
    ll n,k;
    cin>>n>>k;
    VL arr(n);
    fr(i,0,n)
        cin>>arr[i];
    sort(ALL(arr));
    ll sum=0;
    fr(i,0,k)
    {
        sum+=arr[i];
    }
    cout<<sum<<endl;
    return;
}
int main()
{
    IOS;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}
/* stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
*/
// BITMASK:
// 1)When some constrall is of the order of 15-20, think of bitmask DP.
// 2)When some constrall is around 40, try out meet in the middle
// 3) See Strings,palindromes,prefix,suffix etc -> KMP,Z algorithm

Measured memory_bytes: 3652
/*
ID: learnin7
TASK: test
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
        
    ios_base::sync_with_stdio(0);
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    //fin >> a >> b;
    //fout << a+b << endl;
    int n,m;
    cin>>n>>m;
    int a[n] = {0};
    while(m--){
        int x,y;
        cin>>x>>y;
        x--,y--;
        a[x]++;
        a[y]++;
    }
    for(int i=0;i<n;i++){
        cout<<a[i]<<endl;
    }
    return 0;
}



Measured memory_bytes: 256
import bisect
n=int(input())
p=list(map(int,input().split()))
idx=[0]*(n+1)

for i,p_i in enumerate(p):
    idx[p_i]=i

right_idx=list(range(1,n+1))+[n,n]
left_idx =list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=idx[p]
    r1=right_idx[x]
    r2=right_idx[r1]
    l1=left_idx[x]
    l2=left_idx[l1]

    ans+=p*( (x-l1)*(r2-r1) + (l1-l2)*(r1-x)  )
    right_idx[l1]=r1
    left_idx[r1]=l1
print(ans)

Measured memory_bytes: 20180
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
using ll = long long;

ll S;
long long MOD = 1000000007;
long long fac[2200], finv[2200], inv[2200];

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

// 二項係数計算
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main(void){

    cin >> S;

    COMinit();

    ll ans = 0;
    ll kumi = 0;
    ll times = S / 3;
//    cout << "times = " << times << endl;

    if (times > 0) {
       for (int i = 1; i <= times;i++){
            ll bunpai = S - 2 * i;
            if (i == 1) {
                kumi = 1;
//                cout << "kumi1 = " << kumi << endl;
            } else {
                kumi = COM(bunpai - 1,i - 1);
//                cout << "kumi3 = " << bunpai -1 << "," << i -1 << "," << kumi << endl;
            }
            ans = (ans + kumi) % MOD;
        }
    }

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

Measured memory_bytes: 3668
#include <stdio.h>

int main(void){
    int a[]={1,5,10,50,100,500},sum = 0,i,x;
    for(i = 0;i <= 5;i++){
        scanf("%d",&x);
        sum += a[i] * x;
    }
    if(sum >=1000)
        x = 1;
    else
        x = 0;
    printf("%d\n",x);
    return 0;
}

Measured memory_bytes: 1836
x = list(map(int,input().split()))
a = x[0]
b = x[1]
c = x[2]
if a < b:
    if b < c:
        print(a, b, c)
    if c < b:
        if a < c:
            print(a, c, b)
        else:
            print(c, a, b)
if b < a:
    if a < c:
        print(b, a, c)
    else:
        if c < a:
            if b < c:
                print(b, c, a)
            else:
                print(c, b, a)


Measured memory_bytes: 5596
#include <stdio.h>

int Dice(int [],int []);

int main(void){
    int D1[7],D2[7];
    int i;
    for(i=1;i<=6;i++){
        scanf("%d",&D1[i]);
    }
    for(i=1;i<=6;i++){
        scanf("%d",&D2[i]);
    }
    if(Dice(D1,D2)) printf("No\n");        
    else printf("Yes\n");

    return 0;
}

int Dice(int D1[],int D2[]){
    int a,i=0;
    for(;;){
        a=D1[1];
        D1[1]=D1[5];
        D1[5]=D1[6];
        D1[6]=D1[2];
        D1[2]=a;
        if(D1[2]==D2[2]) break;
        i++;
        if(i==4) break;
    }
    if(D1[2]!=D2[2]){
        a=D1[1];
        D1[1]=D1[3];
        D1[3]=D1[6];
        D1[6]=D1[4];
        D1[4]=a;
        if(D1[2]!=D2[2]){
            i=0;
            while(D1[2]!=D2[2]){
                a=D1[1];
                D1[1]=D1[5];
                D1[5]=D1[6];
                D1[6]=D1[2];
                D1[2]=a;
                i++;
                if(i==4) return 1;
            }
        }
    }

    if(D1[5]==D2[5]){
        if(D1[1]==D2[1]&&D1[3]==D2[3]){
            if(D1[6]==D2[6]&&D1[4]==D2[4]) return 0;
            else return 1;
        }
        else if(D1[3]==D2[1]&&D1[6]==D2[3]){
            if(D1[4]==D2[6]&&D1[1]==D2[4]) return 0;
            else return 1;
        }
        else if(D1[6]==D2[1]&&D1[4]==D2[3]){
            if(D1[1]==D2[6]&&D1[3]==D2[4]) return 0;
            else return 1;
        }
        else if(D1[4]==D2[1]&&D1[1]==D2[3]){
            if(D1[3]==D2[6]&&D1[6]==D2[4]) return 0;
            else return 1;
        }
    }
    return 1;
}



Measured memory_bytes: 2104
#include <cstdio>
#include <unordered_map>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    unordered_map<string, int> mp;
    for(int i=0; i<n; i++){
        char buf[16];
        scanf("%s", buf);
        if(*buf=='i'){
            scanf("%s", buf);
            mp[string(buf)]=1;
        } else{
            scanf("%s", buf);
            if(mp.find(string(buf))!=mp.end()){
                printf("yes\n");
            } else{
                printf("no\n");
            }
        }
    }
    return 0;
}

Measured memory_bytes: 32564
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		double t = sc.nextInt();
	
		t += 0.5;
		int count = 0;
		int s = 1;

		boolean flag = true;
		while(flag){
			if(a * s < t){
				count++;
				s++;
			}else{
				flag = false;
			}
		}
		System.out.println(count * b);
	}
}


Measured memory_bytes: 21716
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

auto & in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N;
int32_t graph[500][500];

void construct(int beg, int end, int level = 1) {
	if (end-beg <= 1) {
		return;
	}
	int mid = (beg + end) / 2;
	construct(beg, mid, level+1);
	construct(mid, end, level+1);
	for (int i = beg; i < mid; ++i)
		for (int j = mid; j < end; ++j)
	{
		graph[i][j] = level;
	}
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;

	construct(0, N);

	for (size_t i = 0; i < N-1 ; i++) {
		for (size_t j = i + 1; j < N-1; j++) {
			out << graph[i][j] << ' ';
		}
		out << graph[i][N-1] << '\n';
	}

	return 0;
}
#endif


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
    ll n,k;
    cin >> n >> k;
    ll ans=0;
    if(k==1){
        ans=n*n*n;
        cout << ans << endl;
        return 0;
    }
    for(ll i=1;i<=n;i++){
        ll j;
        ll ibai=i/k;
        j=k-(i-k*ibai);
        ll l=k-j;
        if(l==0) l+=k;
        ll lcopy=n-l;
        if((i+l)%k!=0) continue;
        ll lcnt=lcopy/k+1;
        ll jcopy=n-j;
        ll jcnt=jcopy/k+1;
        ans+=lcnt*jcnt;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3636
N, M, P = map(int,input().split())
dist = [0] + [float('inf')] * (N - 1)

a = []
b = []
c = []

for i in range(M):
    i,j,k = map(int,input().split())
    a.append(i)
    b.append(j)
    c.append(-1*(k - P))

INF = float('inf')

for i in range(N-1):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
        
ans = dist[N -1]

negative = [False] * N

for i in range(N):
    for j in range(M):
        if dist[a[j] - 1] == INF: continue
        if dist[b[j] - 1] > dist[a[j] - 1] + c[j]:
            dist[b[j] - 1] = dist[a[j] - 1] + c[j]
            negative[b[j] - 1] = True

        if negative[a[j] - 1] == True:
            negative[b[j] - 1] = True

if negative[N - 1]:
    print(-1)
else:
    print(max(-1 * ans, 0))


Measured memory_bytes: 53336
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		var sc = new Scanner(System.in);
		var n = sc.nextInt();
		var k = sc.nextLong();
		var a = new int[n];
		for (var i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		sc.close();

		var set = new HashSet<Integer>();
		var list = new ArrayList<Integer>();
		var tn = 1;
		var count = 0;
		for (var i = 0; i < n; i++) {
			count++;
			tn = a[tn - 1];
			if (count == k) {
				break;
			}
			if (set.contains(tn)) {
				var i2 = list.indexOf(tn);
				var index2 = (int)(i2 + (k - count) % (list.size() - i2));
				tn = list.get(index2);
				break;
			}
			set.add(tn);
			list.add(tn);
		}

		System.out.println(tn);
	}
}

Measured memory_bytes: 67028
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
	int iHigh[10];

	for( int i=0;i<10;i++ ){
		scanf("%d",&iHigh[i]);
	}

	sort( iHigh,iHigh+10,greater<int>() );

	for( int i=0;i<3;i++ ){
		printf("%d\n",iHigh[i]);
	}

	return 0;
}

Measured memory_bytes: 1044
<?php

$line = trim(fgets(STDIN));
$line = array_map(function($val){ return intval($val); }, preg_split("/\s/", $line));
$n = $line[0];
$x= $line[1];
$m = array_map(function($val){
    return intval(trim(fgets(STDIN)));
}, range(1, $n));
sort($m);
echo $n + floor(($x - array_sum($m)) / $m[0]);


Measured memory_bytes: 3828