akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <tuple>
#include <cmath>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
using namespace std;

string s, t;
string ans = "";
int dp[3000 + 10][3000 + 10]; //dp[s][t]:sのs文字目までとtのt文字目まで見たときのLCSの長さ

int main(void) {
    cin >> s >> t;
    int s_len, t_len;
    s_len = int(s.size());
    t_len = int(t.size());
    REP(i, 0, s_len) {
        dp[i][0] = 0;
    }
    REP(i, 0, t_len) {
        dp[0][i] = 0;
    }
    
    REP(si, 1, s_len) {
        REP(ti, 1, t_len) {
            if (s[si-1] == t[ti-1]) {
                dp[si][ti] = dp[si-1][ti-1] + 1;
            } else {
                dp[si][ti] = max(dp[si-1][ti], dp[si][ti-1]);
            }
        }
    }
    
    // REP(si, 1, s_len) {
    //     REP(ti, 1, t_len) {
    //         cout << dp[si][ti] << " ";
    //     }
    //     cout << endl;
    // }
    
    int rest = dp[s_len][t_len];
    int si = s_len;
    int ti = t_len;
    while (si>=1) {
        // cout << "si=" << si << ", ti=" << ti << endl;
        if (dp[si-1][ti] == rest-1) {
            // cout << "si発見" << endl;
            while (ti>=1) {
                if (s[si-1] == t[ti-1]) {
                    // cout << "ti発見" << endl;
                    ans = s[si-1] + ans;
                    ti--;
                    break;
                }
                ti--;
            }
            rest--;
        }
        si--;
    }
    
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 35584
#include<bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);


using namespace std;

void solve(int n,double p[])
{
	int i,j,k;
	
	double dp[n+1][n+1];
	memset(dp,0,sizeof(dp));

	dp[0][0]=1;
	
	for(i=1;i<n+1;i++)
	{
		for(j=0;j<n+1;j++)
		{
			if(j==0)
				dp[i][j]=dp[i-1][j]*(1-p[i-1]);
			else
				dp[i][j]=dp[i-1][j-1]*p[i-1]+dp[i-1][j]*(1-p[i-1]);
		}
	}
	double ans=0;

	for(j=n/2+1;j<n+1;j++) ans+=dp[n][j];

	cout << setprecision(10) << ans;
	
}

int main()
{
	FIO
	
	int n;
	cin>>n;
	double p[n];
	for(int i=0;i<n;i++) cin>>p[i];

	//cout<<solve(n,p)<<endl;
	solve(n,p);

}

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

const long long B = 1000000007;
	
bool countOne(){
	int N, R;
	cin >> N;
	if(N==0) return false;
	cin >> R;
	int *counter = new int[N]();
	for(int r=0; r<R; r++){
		int s, t;
		cin >> s >> t;
		for(int i=t-1; i>=s; i--){
			int a = counter[i-1];
			int b = counter[i];
			if(a <= b){
				counter[i] = a;
				counter[i-1] = b+1;
			}
			else{
				counter[i] = a-1;
				counter[i-1] = b;
			}
		}
		for(int i=s+1; i<=t-1; i++){
			int a = counter[i-1];
			int b = counter[i];
			if(a <= b){
				counter[i] = a;
				counter[i-1] = b+1;
			}
			else{
				counter[i] = a-1;
				counter[i-1] = b;
			}
		}
	}
	
	long long fact = 1, index=0;
	for(int n=1; n<N; n++){
		index += counter[N-n-1]*fact;
		fact = ((n+1)*fact)%B;
		index = index%B;
	}
	cout << index << endl;
	delete[] counter;
	return true;
}

int main(){
	while(countOne()){}
	return 0;
}

Measured memory_bytes: 1580
n=int(input())
ans=[0]*n
for j in range(101):
	for k in range(101):
		for l in range(101):
			x=(j+1)**2+(k+1)**2+(l+1)**2+(j+1)*(k+1)+(k+1)*(l+1)+(l+1)*(j+1)
			if x<=n:
				ans[x-1]+=1
for s in ans:
	print(s)

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

#define REPI(i, n) for(int i = 0; i < n; i++)
#define REPJ(j, n) for(int j = 0; j < n; j++)

using ll = long long;
using namespace std;

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

    int n, ans = 0; cin >> n;
    int array[n]; REPI(i, n) cin >> array[i];

    REPI(i, n - 1)
        for(int j = i + 1; j < n; j++)
            ans += array[i] * array[j];

    cout << ans;
}


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

typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007;

int main(){
    
    ll W,H;cin>>W>>H;
    ll x,y;cin>>x>>y;
    cout<<setprecision(20)<<(W*H)/2.0<<" ";
    if(x*2==W&&y*2==H) cout<<1<<endl;
    else cout<<0<<endl;
}


Measured memory_bytes: 256
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
signed main(){
  ll a,b,c;
  cin >> a >> b >> c;
  if(a<=c&&c<=b) cout <<"Yes\n";
  else cout <<"No\n";
}


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


int main()
{
    int n,wt,w,v;
    cin>>n>>wt;
    ll dp[wt+1]={};
    for(ll i=0;i<n;i++)
    {
        cin>>w>>v;
        for(ll j=wt-w;j>=0;j--)
        {
            dp[w+j]=max(dp[w+j],dp[j]+v);
        }
    }
    ll res=0;
    for(ll i=0;i<=wt;i++)
        res=max(res,dp[i]);
    cout<<res;
}


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

int p,q,a,n;
int num;

void calc(int depth,vector<int> &hist,int max_l){
	if(depth>=n) return;
	int mul=1;
	for(int i=0;i<hist.size();i++) mul*=hist[i];

	for(int i=max_l;;i++){
		int next_mul=mul*i;
		if(next_mul>a) break;
		hist.push_back(i);
		int upper=0;
		for(int j=0;j<hist.size();j++){
			upper+=next_mul/hist[j];
		}
		if(upper*q==p*next_mul){
			num++;
		}
		if(upper*q<p*next_mul){
			calc(depth+1,hist,i);
		}
		hist.pop_back();
	}
}

int main()
{
	while(cin>>p>>q>>a>>n){
		if(p==0 && q==0 && a==0 && n==0) break;
		num=0;
		vector<int> hist=vector<int>();
		calc(0,hist,1);
		cout<<num<<endl;
	}
}

Measured memory_bytes: 1216
#include <stdio.h>
int L[200000];
int R[200000];
int p[100000];
int q[100000];
long int ans[100000];

long int dp[501][501];

int main() {
  int N,M,Q,i,j;

  scanf("%d%d%d",&N,&M,&Q );
  for ( i = 0; i< M; i++) {
    scanf("%d%d",L+i,R+i );
    dp[L[i]][R[i]] +=1;
  }
  for ( i = 0; i< Q; i++) scanf("%d%d",p+i,q+i );

 for (i = 0; i < N; i++) {
   for (size_t j = 0; j < N; j++) {
     dp[i+1][j+1] += dp[i+1][j];
   }
 }

  for (i = 0; i < Q; i++) {
    int pc,qc;
    pc = p[i];
    qc = q[i];
    for ( j = pc; j <= qc ; j++) {
      ans[i] += (dp[j][qc] - dp[j][pc-1]);
    }
  }

  for ( i = 0; i < Q; i++) {
   printf("%ld\n",ans[i] );
  }




  return 0;
}

Measured memory_bytes: 5888
using System;
    using System.Text;
    using System.Collections.Generic;
    using static System.Math;
    using System.Linq;
    using static System.Array;

    namespace ConsoleApp2
    {
        class Program
        {


            static void Main(string[] args)
            {
            //var S = Console.ReadLine().ToCharArray();
            //var T = Console.ReadLine().ToCharArray();
            var B = Console.ReadLine();

            if(B == "A")
            {
                Console.WriteLine("T");
            }else if (B == "T")
            {
                Console.WriteLine("A");
            }else if (B == "G")
            {
                Console.WriteLine("C");
            }
            else
            {
                Console.WriteLine("G");
            }

            
            }
        }
    }


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

using namespace std;
using ll = long long;

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    int ans = 0;
    for(int i = 1; i <= N; i++) {
        int temp = i/10000 + (i%10000)/1000 + (i%1000)/100 + (i%100)/10 + (i%10);
        //cout << i << ':' << temp << endl;
        if(temp >= A && temp <= B) {
            ans += i;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3592
n,m,c=map(int,input().split())
l_1=list(map(int,input().split()))
l_2=[list(map(int,input().split()))for n in range(n)]
c_1=0
for i in range(n):
    a=c
    for j in range(m):
        a+=l_1[j]*l_2[i][j]
    if a>0:
        c_1+=1
print(c_1)

Measured memory_bytes: 3060
#include <iostream>

int main(){
	int a, b, c, x;
	int n = 0;

	std::cin >> a >> b >> c >> x;

	for(int i = 0; i <= a; ++i){
		for(int j = 0; j <= b; ++j){
			for(int k = 0; k <= c; ++k){
				int p = 500 * i + 100 * j + 50 * k;
				if(p == x){
					++n;
				}
			}
		}
	}

	std::cout << n << std::endl;

	return 0;
}


Measured memory_bytes: 256
import itertools

n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))
for i, j in enumerate(itertools.permutations(range(1, n+1), n)):
  #print(j)
  if j == p:
    a=i
  if j == q:
    b=i
print(abs(a-b))

Measured memory_bytes: 73348
#include<bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define popcnt(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define watch(x) cout << (#x) << " is " << (x) << endl
#define rand() (rand() << 15 | rand())
using namespace std;
typedef long long  ll;
#define EPS 1e-9
#define PI acos(-1.0)

int main() {
   ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
   int n , k;
   cin >> n >> k;
   vector<int> a(n);
   for(int &x : a)
      cin >> x;

   vector<int> state(n , 0);
   for(int i = 0 ; i + 1 < n ; ++i){
      if(a[i] > a[i + 1]){
         state[i] = 1;
      }
   }


   int l = 0 , r = k - 1 , cur = 0;
   for(int i = 0 ; i <= r ; ++i)cur += state[i];
   int sorted = 0;
   while (r < n){
      sorted += (cur == 0 || (cur == 1 && state[r] == 1));
      if(r + 1 == n)break;
      cur -= state[l++];
      cur += state[++r];
   }

   l = 0 , r = k - 1 , cur = 0;
   set<int> s;
   for(int i = 0 ; i <= r ; ++i)s.insert(a[i]) , cur += state[i];
   int ans = 0;
   bool nxtFake = false;
   while (r < n){
      if(!nxtFake || (cur == 0 || (cur == 1 && state[r] == 1)))++ans;
      nxtFake = false;
      if(r + 1 == n)break;
      int nxtEle = a[++r];
      if(a[l] == *s.begin() && nxtEle > *s.rbegin())
         nxtFake = true;
      s.erase(a[l++]);
      s.insert(a[r]);
      cur -= state[l - 1];
      cur += state[r];
   }
   cout << ans - max(0 , sorted - 1) << '\n';
}

Measured memory_bytes: 11264
N,X,M = map(int,input().split())

is_appear = [-1]*M
a = []
_len = 0
while is_appear[X] == -1:
    a.append(X)
    is_appear[X] = _len
    _len += 1
    X = X*X % M

loop_len = _len-is_appear[X]
loop_total = 0
for i in range(is_appear[X], _len):
    loop_total += a[i]

ans = 0
if N <= _len:
    for i in range(N):
        ans += a[i]
    
    print(ans)
else:
    for i in range(is_appear[X]):
        ans += a[i]
        N -= 1
    
    ans += loop_total * (N // loop_len)
    
    for i in range(N%loop_len):
        ans += a[is_appear[X]+i]
    
    print(ans)


Measured memory_bytes: 69416
N = int(input())
X = list(map(int, input().split()))

import math

X_min = math.floor(min(X))
X_max = math.ceil(max(X))

c = [0] * (X_max - X_min + 1)

for i in range(X_min, X_max+1):
  for j in range(N):
    c[int(i)-X_min] += (X[j] - i)**2
    
d = min(c)
print(d)

Measured memory_bytes: 9044
#include<bits/stdc++.h>
using namespace std;
#define FAST ios_base:: sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;

int main(){
	FAST;
	ll a[5],k;
	for(auto &X:a)	cin >> X;
	cin >> k;
	
	if(a[4]-a[0]<=k)	cout << "Yay!";
	else 				cout << ":(";
}




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

int f(int x) {
	if (x == 0) return 0;
	return f(x % __builtin_popcount(x)) + 1;
	// return f(x % __builtin_popcountll(x)) + 1;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);

	int n; cin >> n;
	string s; cin >> s;
	vector<int> x(n);
	REP(i, n) x[i] = s[i] - '0';

	int pc = 0; // pc == pop_count
	REP(i, n) pc += x[i];

	vector<int> res(n);
	// 元の bit が 0 のところを1個だけ 1 にした場合と
	// 元の bit が 1 のところを1個だけ 0 にした場合とに分けて考えてる
	REP(bit, 2) {
		// 元の bit の popcount の変動をセットする
		int next_pc = pc;
		if (bit == 0) next_pc++;
		else next_pc--;
		// next_pc が 0 以下になった場合の例外処理
		if (next_pc <= 0) continue ;
		// 元の数を next_pc で割った余り(== rem0)を求める
		// これで1段回目が終わる
		int rem0 = 0;
		REP(i, n) {
			// 2進数を前から順番に見ていって10進数にしている
			rem0 = (rem0 * 2) % next_pc;
			rem0 += x[i];
		}
		// 1段回目が終わった後は，
		// 差分を足して，
		// その数を next_pc で割った余りを求める
		int k = 1;
		for (int i = n - 1; i >= 0; i--) {
			// i 桁目をフリップしたときの割った余りを求める
			if (x[i] == bit) {
				int rem = rem0;
				// i 番目の bit が 0 の時は，
				// i 番目の bit が 1 に変わるので，
				// 2^i を [next_pc で割った余り]に足してあげて，
				// next_pc で割った余りを求める
				if (bit == 0) rem = (rem + k) % next_pc;
				// i 番目の bit が 1 の時は，
				// i 番目の bit が 0 に変わるので，
				// 2^i を [next_pc で割った余り]から引いてあげて，
				// next_pc で割った余りを求める
				else rem = (rem - k + next_pc) % next_pc;
				// そして，popcount を求める
				res[i] = f(rem) + 1;
			}
			// 2^i の値
			k = (k * 2) % next_pc;
		}
	}

	REP(i, n)
		cout << res[i] << '\n';
	return 0;
}

Measured memory_bytes: 5156
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<string,int>> vpsi;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#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)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;

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

int n,k,r,s,p;
int ans=0;
string t;
cin >> n >> k;
cin >> r >> s >> p;
cin >> t;
rep(i,n){
    if(t[i]=='r'){
        if(i>=k){
            if(t[i]!=t[i-k]){
                ans+=p;
            }else{
                t[i] = 'n';
            }
        }else{
            ans+=p;
        }
    }
    if(t[i]=='s'){
        if(i>=k){
            if(t[i]!=t[i-k]){
                ans+=r;
            }else{
                t[i] = 'n';
            }
        }else{
            ans+=r;
        }
    }
    if(t[i]=='p'){
        if(i>=k){
            if(t[i]!=t[i-k]){
                ans+=s;
            }else{
                t[i] = 'n';
            }
        }else{
            ans+=s;
        }
    }
}
fin(ans);

//////////////////////////////////////////////////////
return 0;}

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

int main(){
    int n; cin>>n;
    vector<int> p(n);
    for(int i=0; i<n; i++)
        cin>>p.at(i);
    sort(p.begin(), p.end());
    
    int ans=0;
    for(int i=0; i<n; i++){
        if(i == n-1)
            ans += p.at(i)/2;
        else
            ans += p.at(i);
    }
    
    cout<<ans<<endl;
}


Measured memory_bytes: 256
def comb(n, k):
    k = min(k, n - k)
    ans = 1
    for i in range(n, n - k, -1):
        ans *= i
    for i in range(1, k + 1):
        ans //= i 
    return ans

def getNum(n,t) :
    s=0
    I=n
    R=n

    count = 1

    while s==0:
        for i in range(2,R+1):
            if I%i==0:
                I=I/i
                if I==1:
                    s=1
                if i in t:
                    t[i] = t[i] + 1
                else : 
                    t[i] = 1                
                count += 1
                break
    return count    

n = int(input())
t = {}

yaku = 1
for i in range(2,n+1):
    yaku = yaku + getNum(i,t)

#print(t)

ans = 0
n5 = 0
n3 = 0
for v in t.values():
    if v >= 4:
        n5 += 1
    if v >= 2:
        n3 += 1

if(n5 >= 2 and n3 >= 3):
    ans += comb(n5,2)*comb(n3-2,1)

n5 = 0
n3 = 0
for v in t.values():
    if v >= 14:
        n5 += 1
    if v >= 4:
        n3 += 1
#print(n5,n3)
ans += n5*(n3-1)

n5 = 0
n3 = 0
for v in t.values():
    if v >= 24:
        n5 += 1
    if v >= 2:
        n3 += 1
#print(n5,n3)
ans += n5*(n3-1)

n5 = 0
n3 = 0
for v in t.values():
    if v >= 74:
        n5 += 1
#print(n5)
ans += n5

print(ans)

Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))
x = []
for i in range(n):
    x.append(a[i]-i-1)
x.sort()
if n%2 == 1:
    b = x[n//2]
else:
    b = (x[n//2-1] + x[n//2])/2
sum = 0
for i in range(n):
    sum += abs(a[i]-(b+i+1))
print(int(sum))

Measured memory_bytes: 99796
#include <iostream>

using namespace std;

using ll =  long long;

constexpr ll MOD = 1000000007;

ll s[2001][2001];

void init(int n) {
    s[0][0] = 1;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j) {
            s[i][j] = (s[i-1][j-1] + s[i-1][j]) % MOD;
        }
    }
}

int main() {
    ll n, k;
    cin >> n >> k;
    init(n);

    for(ll g=1;g<=k;++g) {
        ll r = s[k][g];
        ll b = 0;
        for(ll i=g-1;i<=n-k;++i) {
            b += ((n-k-i+1) * s[i][g-1]) % MOD;
            b %= MOD;
        }
        // cerr << r << " " << b << endl;
        cout << (r * b) % MOD << endl;
    }
}

Measured memory_bytes: 31488
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
#include <numeric>
 
using namespace std;
 
int field[50][50];
int h, w;
 
void myfill(int src, int dst) {
	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) {
			if (field[y][x] == src) {
				field[y][x] = dst;
			}
		}
	}
}
 
int main(){
	cin >> h >> w;
	int gcnt = 0;
 
	for (int i = 0;i< h; ++i) {
		string s;
		cin >> s;
		for (int j = 0; j < w; ++j) {
			if (s[j] == '.') {
				field[i][j] = -1;
			}else{
				field[i][j] = gcnt;
				gcnt++;
			}
		}
	}
	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) {
			if (field[y][x] == -1) continue;
			int nx, ny;
			nx = x-1;
			ny = y;
			if (0 <= nx && nx < w && 0 <= ny && ny < h) {
				if (field[ny][nx] >= 0) {
					myfill(field[y][x], field[ny][nx]);
				}
			}
			nx = x;
			ny = y-1;
			if (0 <= nx && nx < w && 0 <= ny && ny < h) {
				if (field[ny][nx] >= 0) {
					myfill(field[y][x], field[ny][nx]);
				}
			}
		}
	}
	auto col = vector<int>(50 * 50 + 1, 0);
	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) {
			if (field[y][x] == -1) continue;
			col[field[y][x]]++;
		}
	}
	bool flag = true;
	for (int item : col) {
		if (item == 1) {
			flag = false;
		}
	}
	if (flag) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

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

int main() {
  int n; cin>>n;
  int d; 
  int t1=0, t2=0;
  rep(i,n){
    cin>>d;
    t1+=d;
    t2+=d*d;
  }
  int ans=(t1*t1-t2)/2;
  cout<<ans;
}

Measured memory_bytes: 256
n, k = [int(item) for item in input().split()]
a = sorted([int(item) for item in input().split()], reverse=True)

count = 0
asum = 0
for item in a:
    if asum + item < k:
        asum += item
        count += 1
    else:
        count = 0

print(count)

Measured memory_bytes: 3572
N,X,Y = map(int,input().split())
ans = [0] * (N-1)
for i in range(1,N):
    for j in range(i+1,N+1):
        min_distance = min(abs(i-j), abs(i-X)+abs(j-Y)+1, abs(j-X)+abs(i-Y)+1)
        ans[min_distance-1] += 1
for i in range(N-1):
    print(ans[i])

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
map<int,int> mp1;
int main()
{
    int n;scanf("%d",&n);
    mp1.clear();
    for(int i=1;i<=n;i++)
    {
        int x;scanf("%d",&x);
        mp1[x]++;
    }

    int m;scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int x;scanf("%d",&x);
        if(--mp1[x]<0)
            return !printf("NO\n");
    }
    return !printf("YES\n");


}

Measured memory_bytes: 9728
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793

int main(){
  string s;
  cin >> s;
  s.at(3)='8';
  cout << s << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << "\n"
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef complex<ld> Point;
typedef Point Vector;
typedef pair<Point, Point> Segment;
constexpr double EPS = (1e-9L);
ld dot(const Point& p1, const Point& p2) { return (conj(p1) * p2).real(); }
ld cross(const Point& p1, const Point& p2) { return (conj(p1) * p2).imag(); }
constexpr bool eq(ld a) { return abs(a) < EPS; }
Point project(Segment s, Point p) {
	Vector base = s.fi - s.se;
	ld r = dot(p - s.fi, base) / norm(base);
	return s.fi + base * r;
}
int main() {
	cout << setprecision(10) << fixed;
	int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
	Segment s = mp(Point(x1, y1), Point(x2, y2));
	int q; cin >> q;
	Point p, ap;
	int px, py;
	rep(i, 0, q) {
		cin >> px >> py;
		ap = project(s, Point(px, py));
		cout << ap.real() << " " << ap.imag() << "\n";
	}
	return 0;
}

Measured memory_bytes: 3360
def comb(n, r):
    _n = 1
    _r = 1
    for i in range(n - r + 1, n + 1):
        _n = _n * i % m
    for i in range(2, r + 1):
        _r = _r * i % m
    return _n * pow(_r, m - 2, m)


n, a, b = map(int, input().split())
m = pow(10, 9) + 7
a = comb(n, a) % m
b = comb(n, b) % m
print((pow(2, n, m) - 1 - a - b) % m)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main()
{
    int N;
    cin >> N;
    vector<int64_t>vec(N);
    vector<int64_t>vec2(N);
    for (int i=0; i<N; i++) {
        cin >> vec.at(i);
        vec2[i] = vec[i];
    }

    sort(vec.begin(), vec.end(), greater<int64_t>());
    int64_t medium = N / 2;
    for (int64_t i=0; i<N; i++) {
        int64_t num = vec2[i];
        if (num >= vec[medium-1]) {
            cout << vec[medium] << endl;
        } else {
            cout << vec[medium-1] << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 6428
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
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;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//-std=gnu++17
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    map<char,bool>m;
    string s;
    cin>>s;
    rep(i,s.size()){
        m[s[i]]=true;
    }
    for(char c='a';c<='z';c++){
        if(!m[c]){
            cout<<c<<"\n";
            return 0;
        }
    }
    cout<<"None"<<"\n";
}


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

int main(){
    bool cards[4][14];
    int n, rank;
    char suit;
    
    for ( int s = 0; s < 4; s++)
        for ( int r = 1; r <=13; r++)
            cards[s][r] = 0; //??¨??¨???????´????false??????
            
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> suit >> rank;
        if ( suit == 'S') cards[0][rank] = 1;
        if ( suit == 'H') cards[1][rank] = 1;
        if ( suit == 'C') cards[2][rank] = 1;
        if ( suit == 'D') cards[3][rank] = 1;
}
            
    for ( int s = 0; s < 4; s++){
        for ( int r = 1; r <= 13; r++){
            if ( cards[s][r] ) continue;
            if ( s == 0 ) suit = 'S';
            if ( s == 1 ) suit = 'H';
            if ( s == 2 ) suit = 'C';
            if ( s == 3 ) suit = 'D';
            cout << suit << " " << r << endl;
        }
    }
            
            
    return 0;
    
}

Measured memory_bytes: 3052
#include<bits/stdc++.h>
using namespace std;
const long double eps=1e-10;
int n,pos,cnt,xp,yp;
long long a[222222],mx;
int b[222222];
long double aa[222222],bb[222222],c[222222],ans[222222],res;
deque<pair<long double,long double> > q;
pair<long double,long double> cur,xx,yy;
long double slope(pair<long double,long double> x,pair<long double,long double> y)
{
	return (y.second-x.second)/(y.first-x.first);
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for (int i=1;i<=n;i++) scanf("%d",&b[i]);
	for (int i=1;i<=n;i++)
	{
		if (mx<a[i])
		{
			mx=a[i];
			pos=i;
		}
	}
	for (int i=pos;i<=n;i++)
	{
		aa[++cnt]=(long double)a[i];
		bb[cnt]=(long double)b[i];
	}
	for (int i=1;i<=pos;i++)
	{
		aa[++cnt]=(long double)a[i];
		bb[cnt]=(long double)b[i];
	}
	c[1]=c[2]=0.00;
	for (int i=3;i<=cnt;i++)
	{
		c[i]=(2.00*c[i-1]-2.00*bb[i-1]-c[i-2]);
	}
	for (int i=1;i<=cnt;i++) aa[i]+=c[i];
	for (int i=1;i<=cnt;i++)
	{
		cur=make_pair((long double)i,aa[i]);
		while(q.size()>1)
		{
			xx=q[(int)q.size()-1];yy=q[(int)q.size()-2];
			if (slope(yy,xx)<slope(xx,cur)-eps) q.pop_back();
			else break;
		}
		q.push_back(cur);
	}
	for (int i=0;i<(int)q.size()-1;i++)
	{
		xp=(int)(q[i].first+eps);yp=(int)(q[i+1].first+eps);
		for (int j=xp;j<=yp;j++)
		{
			ans[j]=(aa[xp]*(long double)(yp-j)+aa[yp]*(long double)(j-xp))/(long double)(yp-xp);
		}
	}
	for (int i=1;i<=cnt;i++) ans[i]-=c[i];
	for (int i=1;i<=n;i++) res+=ans[i];
	res/=(long double)n;
	printf("%.12Lf\n",res);
	return 0;
}

Measured memory_bytes: 24828
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: usize = read(&mut stdin_lock, &mut buf, b' ');
    let d: usize = read(&mut stdin_lock, &mut buf, b'\n');
    let mut xvv = vec![vec![0i32; d]; n];
    for i in 0..n {
        for j in 0..d - 1 {
            xvv[i][j] = read(&mut stdin_lock, &mut buf, b' ');
        }
        xvv[i][d - 1] = read(&mut stdin_lock, &mut buf, b'\n');
    }

    let mut ans = 0;
    for i in 0..n - 1 {
        for j in i + 1..n {
            let mut s = 0;
            for k in 0..d {
                s += (xvv[i][k] - xvv[j][k]).pow(2);
            }
            let a: f64 = f64::from(s);
            let b: f64 = a.sqrt().trunc();;
            if b * b == a {
                ans += 1;
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
A = $<.read.split.map(&:to_i).each_slice(2).to_a
H,N = A.shift
A.map! {|a,b| [1.0*b/a, b, a]}.sort!
M = Array.new(H+A[0][2])
A.each {|*,b,a|
  M[a] ||= b
  0.upto(M.size-a-1) {|i| M[i+a] ||= M[i]+b  if M[i]}
  break  if M[H]
}
p M[H..-1].compact.min


Measured memory_bytes: 3964
# ABC 138 C
# https://atcoder.jp/contests/abc138/tasks/abc138_c

n = gets.to_i
v = gets.split(/ /).map(&:to_i)

class Item
  def initialize(value, i)
    @value = value
    @i = i
  end

  attr_reader :value, :i

  def composed_value(n)
    j = i == 0 ? n - 1 : n - i
    value * 1.0 / (2 ** j)
  end
end

composed_values = v.sort.map.with_index(0) { |value, i| Item.new(value, i).composed_value(n) }
# puts composed_values
puts composed_values.reduce(0) { |acc, i| acc + i }


Measured memory_bytes: 1788
n,m = map(int,input().split())
h = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(m)]
gr=[[] for i in range(n)]
for i in range(m):
    gr[ab[i][0]-1].append(ab[i][1])
    gr[ab[i][1]-1].append(ab[i][0])
cnt=0
for i in range(n):
    for j in gr[i]:
        if h[i]<=h[j-1]:
            break
    else:
        cnt+=1
print(cnt)


Measured memory_bytes: 41164
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int mod = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};

int main() {
    cout << fixed << setprecision(10);
    
    int N, K; cin >> N >> K;

    // cout << "sum" << endl;
    vector<mint> rs(N+1);
    repr(i, 1, N+1) {
        rs[i] = rs[i-1] + i;
        // cout << i << " " << rs[i].x << endl;
    }
    mint ans;
    // cout << "count" << endl;
    repr(i, K, N+1) {
        // cout << i << endl;
        mint low, upp;
        low = rs[i-1];
        upp = rs[N] - rs[N - i];
        // cout << low.x << " " << upp.x << endl;
        ans += upp - low +1;
    }
    cout << ans.x +1 << endl;
    return 0;
}

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

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

    int cost = 0;
    for (int i = 1; i < N + 2; i++) cost += abs(A[i] - A[i - 1]);

    for (int i = 1; i <= N; i++) {
        int ans = cost - (abs(A[i] - A[i - 1]) + abs(A[i + 1] - A[i]));
        ans += abs(A[i + 1] - A[i - 1]);
        cout << ans << endl;
    }
}

Measured memory_bytes: 4024
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main(){
  int n,f;
  //mlÛ¶vÛ¶
  long long a,b,c;
  //aÔbP¿cÊ
  while(cin>>n,n){
		map<int,long long> m;
		vector<int> v;
		f=1;
    for(;n;n--){
      std::cin>>a>>b>>c;
      if(!m[a])v.push_back(a);
      m[a] += b*c;
    }
    
    for(int i=0;i<v.size();i++){
      if(m[v[i]]>999999){
				f=0;
				cout<<v[i]<<endl;}
    }
    if(f)cout<<"NA"<<endl;
  }
  return 0;
}

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

int main(void){
  int a,b,c,n;
  scanf("%d",&n);
  for(int i = 0; i < n; i++){
    scanf("%d",&a); scanf("%d",&b); scanf("%d",&c);
    if(pow(a,2) + pow(b,2) == pow(c,2))printf("YES\n");
    else if(pow(b,2) + pow(c,2) == pow(a,2))printf("YES\n");
    else if(pow(c,2) + pow(a,2) == pow(b,2))printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}


Measured memory_bytes: 2024
#include<iostream>
#include<string>
using namespace std;
int main()
{
	int a[105]={0},n,k;
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		int t,x;
		cin>>t;
		while(t--)
		{
			cin>>x;
			a[x]++;
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	if(!a[i])cnt++;
	cout<<cnt;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
  
using namespace std;
  
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  
#define pb push_back
#define mp make_pair
#define cotu cout
#define itn int
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
  
#define ordered_set tree<int , null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
  
const int inf = int(1e9);
const int mod = inf + 7;
const int N = 1e6 + 555; // TL MB
const double PI = acos(-1.0);
 
void mul(ll &x, ll y){
	x *= y;
	if(x >= mod) x %= mod;
}
 
void add(ll &x, ll y){
	x += y;
	if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}
ll bp(ll a, ll n){
	ll r = 1;
	while(n){
		if(n & 1) mul(r, a);
		mul(a, a);
		n >>= 1;
	}
	return r;
}		

ll s[N], p[N], res;
int get(int v){
	return v == p[v] ? v : p[v] = get(p[v]);
}
void un(int a, int b){
	a = get(a);
	b = get(b);
	if(a != b){
		res -= s[a] * s[b];
		p[b] = a;
		s[a] += s[b];
	}
}
void solve()
{
	int n, m;
	cin >> n >> m;
	vector<pii> px;
	rep(i, m){
		int x, y;
		cin >> x >> y;
		px.pb({x, y});
	}
	ll ans[m];
	res = (1ll * n * (n - 1)) / 2;
	for(int i = 1; i <= n; ++i) s[i] = 1, p[i] = i;
	for(int i = m - 1; i >= 0; --i){
		ans[i] = res;
		un(px[i].F, px[i].S);
	}
	rep(i, m) cout << ans[i] << '\n';
}



 
 
int main()
{
    Red;
  	// int T; cin >> T; while(T--)
    solve();
    return 0;
}

Measured memory_bytes: 7924
#include<bits/stdc++.h>
#include<iomanip>
#include<numeric>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int mo = 1e9+7;
constexpr int  mod = mo;
constexpr int inf = 1<<30;
constexpr ll infl = 1ll<<60;
vector<pair<int,int>> E[205];
vector<vector<ll>> dist(205,vector<ll>(205,infl));
int main(){
    int n,m;ll r;
    cin>>n>>m>>r;
    vector<int> to(r);
    for(auto &a : to){ cin>>a;a--;}
    for(int i=0;i<m;++i){
        int a,b; ll c;
        cin>>a>>b>>c;
        a--;b--;
        dist[a][b] = min(dist[a][b],c);
        dist[b][a] = min(dist[b][a],c);
    }
    for(int i=0;i<n;++i)dist[i][i] = 0;
    for(int k=0;k<n;++k)for(int i=0;i<n;++i)for(int j=0;j<n;++j)dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
    ll ret = infl;
    sort(to.begin(),to.end());
    do{
        ll tmp = 0ll;
        for(int i=0;i<r-1;++i){
            tmp += dist[to[i]][to[i+1]];
        }
        ret = min(tmp,ret);
    }while(next_permutation(to.begin(),to.end()));
    cout << ret  << endl;       
    return 0;
}



Measured memory_bytes: 640
import java.util.*;				
				
class Main {				
    public static void main(String[] args) {				
        Scanner sc=new Scanner(System.in);				
            String s = sc.nextLine();				
            String p = sc.nextLine();				
				
            int slen = s.length();				
            int plen = p.length();				
            int j = 0,i;				
            for( i = 0; i<slen; i++ ) {				
                if( p.charAt( 0 ) == s.charAt( i ) ) {				
                    int k = i;				
                    for( j = 0; j<plen; j++ ) {				
                        k = ( i+j ) % slen;				
                        if( p.charAt( j ) != s.charAt( k ) ) break;				
                    }				
                }				
                if( plen == j ) break;				
            }				
				
            if( plen == j ) {				
                System.out.println( "Yes" );            				
            } else {				
                System.out.println( "No" );				
            }				
    }				
}				
				


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

int kai(string s, int n)
{
    int flag = 0;
    for (int i = 0; i < n / 2; i++)
    {
        if (s[i] != s[n - i - 1])
        {
            flag += 1;
            break;
        }
    }
    if (flag == 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    string s;
    cin >> s;
    string j=s;
    reverse(j.begin(),j.end());
    if (kai(s, s.size()) == 1 && kai(s, (s.size() - 1) / 2) == 1 && kai(j, (s.size() - 1) / 2) == 1)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
}


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

int main() {
  int h, w, d;
  cin>>h>>w>>d;
  int a[h][w];
  for (int i=0; i<h; i++) {
    for (int j=0; j<w; j++) {
      cin>>a[i][j];
    }
  }
  pair<int, int> pos[h*w+1];
  for (int i=0; i<h; i++) {
    for (int j=0; j<w; j++) {
      pos[a[i][j]] = make_pair(i, j);
    }
  }
  int acc[h*w+1];
  for (int i=1; i<=d; i++) {
    acc[i] = 0;
    for (int j=i+d; j<=h*w; j+=d) {
      int y1, y2, x1, x2;
      tie(y1, x1) = pos[j-d];
      tie(y2, x2) = pos[j];
      acc[j] = acc[j-d] + abs(y2- y1) + abs(x2 - x1);
    }
  }
  int q;
  cin>>q;
  for (int i=0; i<q; i++) {
    int l, r;
    cin>>l>>r;
    cout<<acc[r] - acc[l]<<endl;
  }
}

Measured memory_bytes: 2560
#include<queue>
#include<iostream>
using namespace std;
typedef long long llong;

int main(){
    llong n;
    cin >> n;

    queue<llong> Q;
    for(llong i=1; i<=9; i++){
        Q.push(i);
    }

    llong d;
    for(int j=1; j<n; j++){
        d = Q.front(); Q.pop();
        // cout << j << " " <<  d << endl;
        llong m;

        if(d - d / 10 * 10 != 0){
            m = d * 10 + (d - d / 10 * 10) - 1;
            Q.push(m);
        }

        m = d * 10 + (d - d / 10 * 10);
        Q.push(m);

        if(d - d / 10 * 10 != 9){
            m = d * 10 + (d - d / 10 * 10) + 1;
            Q.push(m);
        }
    }
    
    d = Q.front(); Q.pop();
    cout << d << endl;
}

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

int main()
{
    int k;
    string s;
    cin>>k;
    
    cin>>s;
    int n;
    n=s.length();
    
    
    if(n<=k)
   cout<<s;
    
    
    else
    {
    for(int i=0;i<k;i++)
    {
            cout<<s[i];
    }
    cout<<"...";
    }
	return 0;
}

Measured memory_bytes: 3624
a=:+
puts [6484,a,0,1,3,:<,2,3,3]+[0,1].map{|x|[a,x,3,x]+(0..29).map{v=x+4;u=x*60+9+_1;[a,v,v,v,a,v,3,6,*[a,6,6,6]*(29-_1),:<,6,x,u,a,v,u,v]}}+(0..59).map{|t|[a,2,2,2]+(0...t).map{[a,8+t-_1,69+_1,5,:<,3,5,6,a,2,6,2]}}

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

#if defined(DEBUG)

#include <unistd.h>
#include <sys/fcntl.h>
#define DLOG(...)        cerr << dbgFormat(__VA_ARGS__) << endl
#define DCALL(func, ...) func(__VA_ARGS__)

template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}

#else  // defined(DEBUG)

#define DLOG(...)
#define DCALL(func, ...)

#endif // defined(DEBUG)
// ----------------------------------------------------------------------

template<typename F>
class FixPoint : private F {
public:
  explicit constexpr FixPoint(F&& f) noexcept : F(forward<F>(f)) {}

  template<typename... Args>
  constexpr decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, forward<Args>(args)...);
  }
};

template<typename F>
static inline constexpr decltype(auto) fix(F&& f) noexcept {
  return FixPoint<F>{forward<F>(f)};
}

// ----------------------------------------------------------------------
struct MyException : exception {};

int main(int argc, char *argv[]) {
#if defined(DEBUG)
  // GDB on Cygwin ignores redirection at run command.
  if (argc == 2) dup2(open(argv[1], 0), 0);
#else
  // For performance.  We should not use C-style stdio functions
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cout << setprecision(20);

  int N; cin >> N;
  vector<int> A(N-1), B(N-1);
  vector<vector<int>> nbr(N);

  for (int i = 0; i < N-1; i++) {
    int a, b; cin >> a >> b;
    A.at(i) = a;
    B.at(i) = b;
    nbr.at(a).push_back(b);
    nbr.at(b).push_back(a);
  }

  auto branch = [&](int nd) -> int {
    auto nxt = [&](int& node, int& source) -> void {
      for (int x : nbr.at(node)) {
	if (x != source) {
	  source = node;
	  node = x;
	  return;
	}
      }
      throw MyException();
    };
    int src = -1;
    while (nbr.at(nd).size() <= 2) nxt(nd, src);
    return nd;
  };

  vector<int> brnum(N);
  int ans = 0;
  try {
    for (int i = 0; i < N; i++) {
      if (nbr.at(i).size() > 1) continue;
      int j = branch(i);
      brnum.at(j)++;
    }
    for (int i = 0; i < N; i++) {
      if (brnum.at(i) >= 2) ans += brnum.at(i) - 1;
    }
  } catch(const MyException& e) {
    ans = 1;
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 7424
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
int main(){

  ll N;
  cin>>N;
  for(ll i=1;i<=3500;i++){
    
    if(4*i<=N){
    
      continue;
    }
    for(ll j=i;j<=3500;j++){
    
      if(4*i*j<=(i+j)*N){
        
        continue;
      }
      for(ll k=j;k<=3500;k++){
      
        if(4*i*j*k==N*(i*j+j*k+k*i)){
        
          cout<<i<<" "<<j<<" "<<k<<endl;
          return 0;
        }
      }
    }
  }
  return 0;
}

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


#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pf push_front
#define pb2 pop_back
#define pf2 pop_front
#define line printf("\n")
#define pq priority_queue
#define rep(k,i,j) for(int k = (int)i;k<(int)j;k++)
#define repd(k,i,j) for(int k = (int)i;k>=(int)j;k--)
#define ll long long
#define ALL(a) a.begin(),a.end()
#define vi vector<int>

using namespace std;

double EPS = 1e-9;
int INF = 1e9+7;;
long long INFLL = 1e17;
double pi = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

clock_t first_attempt = clock();
inline void cek_time(){
	clock_t cur = clock()- first_attempt;
	cerr<<"TIME : "<<(double) cur/CLOCKS_PER_SEC<<endl;
}
inline void OPEN (string s) {
	freopen ((s + ".in").c_str (), "r", stdin);
	freopen ((s + ".out").c_str (), "w", stdout);
}

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

using namespace __gnu_pbds;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> bbst;
//find_by_order(idx) : i-th index 
//order_of_key(val)  : val has which index

//end of template

int main() {
	ll n, m;
	cin >> n >> m;
	
	if (n > m) swap(n,m);
	
	if (n == 1){
		if (m > 1)
			cout << m - 2 << endl;
		else 
			cout << m << endl;
			
	}
	else{
		cout << (n-2)*(m-2) << endl;
	}
	
}

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;
#define PI  3.14159265358979323846
#define lp(i,n) for(int i = 0; i <n;i++)
#define rlp(i,n) for(int i = int(n);i >= 0;i--)
#define range1(i,a,b,c) for(int i = int(a);i <= int(b);i+=int(c))
#define range(i,a,b) for(int i = int(a);i <= int(b);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define sz(v) ((int)((v).size()))
#define sfi1(v) scanf("%d",&v)
#define sfi2(v1, v2) scanf("%d %d",&v1,&v2)
#define sfi3(v1, v2, v3) scanf("%d %d %d",&v1,&v2,&v3)
#define sfll1(v) scanf("%I64d",&v);
#define sfll2(v1, v2) scanf("%I64d %I64d",&v1,&v2)
#define sfll3(v1, v2, v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
typedef pair<int, int> pii;
template<class T> using ordered_set=tree<T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
const ll MOD = 1e9 + 7;
const int OO = (int)1e6;
const int N = (int)1e7;
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
void init(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
void _run(){
    ll x,k,d;
   cin>>x>>k>>d;
   x = abs(x);
   if(x<d){
       if(k%2==0){
           cout<<x<<endl;
       }else{
           cout<<abs(x-d)<<endl;
       }
   }else if(x==d){
       if(k%2==0){
           cout<<x<<endl;
       }else{
           cout<<0<<endl;
       }
   }else{
       ll rem = min(k,x/d);
       k-=rem;
       x-=d*rem;
       if(k){
            if(k%2==0){
                cout<<x<<endl;
            }else{
                cout<<abs(x-d)<<endl;
            }
       }else{
           cout<<x<<endl;
       }
   }
}
int main() {
	#   ifdef LOCAL_PROJECT
        freopen("in.txt", "r", stdin);
    #   endif
    int t=1;
    // scanf("%d",&t);
    while(t--)_run();
    
    return 0;
}

Measured memory_bytes: 3584
N = int(input())
A = list(map(int, input().split()))

dic = dict()

for a in A:
    if str(a) in dic:
        dic[str(a)] += 1
    else:
        dic[str(a)] = 1

res = 0
for i, cnt in dic.items():
    ii = int(i)
    if ii < cnt:
        res += cnt - ii
    elif ii > cnt:
        res += cnt

print(res)


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
  }
  
  int ans = 0;
  for(int i=0;i<n;i++){
    if(0 != (i+1) % 2 && !(0 == a.at(i) % 2) ){
      ans++;
    }
  }
  cout << ans <<endl;
}

Measured memory_bytes: 3532
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_bakc
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)


int main() {
	IO;
	ll n;
	cin>>n;
	ll sum=0;
	ll ans=0;
	const ll mod=1e9+7;
	for(int i=0;i<n;++i) {
		ll akt;
		cin>>akt;
		ans=(ans+sum*akt)%mod;
		sum=(sum+akt)%mod;
	}
	cout<<ans<<"\n";

	return 0;
}


Measured memory_bytes: 3688