akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repr(i,n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
    int r, d, x;
    cin >> r >> d >> x;
    rep(i,10) {
        x = r * x - d;
        cout << x << endl;
    }
    return 0;
}

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

struct Edge {
    int u, v;
    bool dir;

    int other(int x)    {return x^u^v;}
};

const int N = 1e5+7;
vector<int> adj[N];
vector<Edge> edges;
bool deg[N];
bool vis[N];

void dfs(int u) {
    vis[u] = 1;
    for (int id: adj[u]) {
        int v = edges[id].other(u);
        if (vis[v])     continue;
        dfs(v);
        if (deg[v]) {
            edges[id].dir = 1;
            deg[v] = !deg[v];
            deg[u] = !deg[u];
        }
    }
}

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

    int n, m;
    cin>>n>>m;

    if (m%2) {
        cout<<-1<<endl;
        return 0;
    }

    for (int i=0; i<m; i++) {
        int u, v;
        cin>>u>>v;
        edges.push_back({u, v, 0});
        adj[u].push_back(edges.size()-1);
        adj[v].push_back(edges.size()-1);
        deg[u] ^= 1;
    }

    dfs(1);
    assert(deg[1] == 0);

    for (Edge e: edges)
        if (e.dir)  cout<<e.v<<" "<<e.u<<"\n";
        else        cout<<e.u<<" "<<e.v<<"\n";
}


Measured memory_bytes: 14516
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(){
//	freopen("in","r",stdin);

	string s; cin >> s;
	string l,r;
	bool flag = false;
	int q; cin >> q;
	for(int i = 0;i < q;i++){
		int t; cin >> t;
		if(t==1) flag = !flag;
		else {
			int f; 
			char c;
			cin >> f >> c;
			if(f==1) {
				if(flag) r.push_back(c);
				else l.push_back(c);	
			}else {
				if(flag) l.push_back(c);
				else r.push_back(c);
			}
		}
	}
	string res;
	if(flag){
		reverse(r.begin(),r.end());
		reverse(s.begin(),s.end());
		res = r + s + l;
	}else{
		reverse(l.begin(),l.end());
		res = l + s + r;
	}
	cout << res << endl;
}


Measured memory_bytes: 1348
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define D(x) cerr << #x << " = " << (x) << '\n'
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	ll n, k;
	cin >> n >> k;
	cout << min(n % k, k - n % k) << '\n';
}


Measured memory_bytes: 256
#include<math.h>
#include<iostream>
#include <algorithm>
#include <string>
#include<vector>
#include <array>
#include<tuple>
#include<queue>
#include<stack>
#include<iomanip>
#include<bitset>
//AtCoderC++.cpp

using namespace std;

vector<long long> comb = vector<long long>(100 * 100,-1);

long long combination(long long n, long long r) {
	if (n == 1 || n == 0)return 1;
	if (n == r)	return 1;
	else if (r == 0)return 1;
	else if (r == 1)return n;
	else if (comb[100 * (n - 1) + (r - 1)] != -1) return comb[100 * (n - 1) + (r - 1)];
	else {
		auto res = combination(n - 1, r - 1) + combination(n - 1, r);
		comb[100 * (n - 1) + (r - 1)] = res;
		return res;
	}
}




int main() {
	size_t n; cin >> n;
	auto min_count = vector<size_t>(26,10000);
	auto count = vector<size_t>(26, 0);
	string s;
	for (size_t i = 0; i < n; i++) {
		cin >> s;
		for (size_t i = 0; i < s.length(); i++) {
			count[s[i] - 'a']++;
		}
		for (size_t i = 0; i < 26; i++) {
			min_count[i] = min(min_count[i], count[i]);
			count[i] = 0;
		}
	}
	string answer = "";
	for (size_t i = 0; i < 26; i++) {
		for (size_t j = 0; j < min_count[i]; j++) {
			answer += (char)('a' + i);
		}
	}
	cout << answer << endl;
}


Measured memory_bytes: 384
"use strict"
const create = () => {
    const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
    const res = {
        "list": input, "index": 0, "max": input.length,
        "hasNext": function() {return this.index < this.max},
        "next": function() { if (!this.hasNext()) {throw "ArrayIndexOutOfBoundsException";}else{return this.list[this.index++];}}
    };
    return res;
}
const o = create();
const next = () => o.next()
const nextInt = () => parseInt(o.next())
const nextStrArray = () => o.next().split(" ")
const nextIntArray = () => o.next().split(" ").map(el => parseInt(el))
const nextCharArray = () => o.next().split("")
const hasNext = () => o.hasNext()
const myout = (...x) => console.log(...x)
const Main = () => {
    const X = nextInt()
    const max = 1000000
    const p = new Array(max).fill(true)
    for(let i = 4;i<max;i=i+2){
        p[i] = false
    }
    p[1] = false
    p[0] = false
    for(let i = 3; i<max; i=i+2){
        if(p[i] == false) continue
        for(let j=2;i*j<max;j++){
            p[j*i] = false
        }
    }
    for(let i = X; i<max;i++){
        if(p[i] == true){
            console.log(i)
            return
        }
    }
}
Main()


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

double a,b,c,r,size;
int n;

int main(){
	while(scanf("%lf %lf %lf",&a,&b,&c)*a*b*c){

		if(a<b){
			if(b<c)size=a*a/4+b*b/4;
			else size=a*a/4+c*c/4;
		}
		else{
			if(a<c)size=a*a/4+b*b/4;
			else size=b*b/4+c*c/4;
		}

		for(scanf("%d",&n);n>0;n--){
			scanf("%lf",&r);
			if(size<r*r)printf("OK\n"); else printf("NA\n");
		}

	}
	return 0;
}

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

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

  char w[n][11];
  int i,j,wlen[n];
  for(i=0;i<n;i++){
    scanf("%s",w[i]);
    wlen[i] = strlen(w[i]);
  }

  for(i=1;i<n;i++){
    for(j=0;j<i;j++)
      if(strcmp(w[i],w[j])==0){
        printf("No\n");
        return 0;
      }
    if(w[i][0]!=w[i-1][wlen[i-1]-1]){
      printf("No\n");
      return 0;
    }
  }

  printf("Yes\n");
  return 0;
}

Measured memory_bytes: 1620
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int main()
{
	int n;
	int a[100];
	while (cin >> n)
	{
		if (n == 0)
		{
			return 0;
		}
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			cin >> a[i];
		}

		for (int i = 0 ; i < n ; i++)
		{
			for (int j = 0; j < n - 1 - i; j++)
			{
				if (a[j] > a[j + 1])
				{
					int temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
					cnt++;
				}
			}
		}
		cout << cnt << endl;
	}

	sort(a, a + n);
	for (int i = 0; i < n; i++)
	{
		cout << a[i];
		if ( i != n - 1)
		{
			cout << " ";
		}
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1160
#include<stdio.h>

int main() {

    long cnt['z'+1]={};
    while( (cnt[1]=getchar())<='z' && cnt[1]>='a' ){
        cnt[0]++; cnt[cnt[1]]++;
    }
    cnt[0] = cnt[0]*(cnt[0]-1)/2;
    for( int i = 'a'; i < 'z'+1; i++){
        cnt[0] -= cnt[i]*(cnt[i]-1)/2;
    }
    printf ("%lld\n", cnt[0]+1 );

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <sstream>
#include <stdio.h>
//#define _USE_MATH_DEFINES
#include <math.h>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <bitset>
#include <stack>
#include <queue>
#include <ctype.h>

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
#define MOD 1000000007
#define more(a,b) (((a)>(b))?(a):(b))
#define less(a,b) (((a)<(b))?(a):(b))

using namespace std;


int main(void)
{
	string s; cin >> s;
	map<char, int> cnt; rep(i, 0, s.size())cnt[s[i]]++;
	int m = 100;
	for (map<char, int>::iterator it = cnt.begin(); it != cnt.end(); it++) {
		int tmp = 0, tmp_m = 0;
		rep(i, 0, s.size()) {
			if (s[i] == it->first) {
				tmp_m = max(tmp_m, tmp);
				tmp = 0;
			}
			else tmp++;
			if (i == s.size() - 1)tmp_m = max(tmp_m, tmp);
		}
		m = min(m, tmp_m);
	}
	cout << m << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = long long;

i64 gcd(i64 a, i64 b) { return b ? gcd(b, a % b) : a; }

int main() {
    i64 n;
    std::cin >> n;
    for (i64 i = 1; i <= 3500; i++) {
        i64 b = n - 4 * i, c = n * i;
        if (b >= 0) continue;
        i64 g = gcd(-b, c);
        b /= g, c /= g;
        for (i64 t = 1; t * -b <= 7000; t++) {
            for (i64 j = 1; j <= 3500; j++) {
                if (j * j + t * b * j + t * c == 0) {
                    std::cout << i << " " << j << " " << -b * t - j << std::endl;
                    return 0;
                }
            }
        }
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define vv(T) vector<vector<T>>
#define coa cout << ans << endl; return 0;
using namespace std;
using ll = long long;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using vll = vector<long long>;
using vvll = vector<vector<long long>>;
using vbool = vector<bool>;
using vvbool = vector<vector<bool>>;
using qint = queue<int>;
using sint = stack<int>;
using pii = pair<int, int>;


int main(){
    int n, k;
    cin >> n >> k;
    vector<int> l(n);
    rep(i, n) cin >> l[i];

    sort(l.begin(), l.end(), greater<int>());

    int ans = 0;
    for(int i = 0; i < k; i++){
        ans += l[i];
    }
    
    coa;
}


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

int main(){
    int m,f,r;

    while(1){
        cin >> m >> f >> r;
        if(m == -1 && f == -1 && r == -1){
            break;
        }else if(m == -1 || f == -1){
            cout << 'F' << endl;
        }else if((m + f) >= 80){
            cout << 'A' << endl;
        }else if(65 <=(m + f) && (m + f) < 80){
            cout << 'B' << endl;
        }else if(50 <=(m + f) && (m + f) < 65){
            cout << 'C' << endl;
        }else if(30 <=(m + f) && (m + f) < 50){
            if(r >= 50){
                cout << 'C' << endl;
            }else{
                cout << 'D' << endl;
            }
        }else if((m + f) < 30){
            cout << 'F' << endl;
        }
    }
}

Measured memory_bytes: 3076
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

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

    ll  a,b,c,d,e,n,k,maxi=0,f=0,mini=INF,sum=0,q;
	string str,stra,straa;
    ll x,y,z;
    char ca,cb,cc;
    cin>>n;
    cout<<n*n*n;
    return 0;
}


Measured memory_bytes: 3620
fun main(args: Array<String>) {
    abc150b()
}

fun abc150b() {
    val n = readLine()!!.toInt()
    val s = readLine()!!

    var answer = 0
    for (i in 0..s.lastIndex - 2) {
        if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') answer++
    }

    println(answer)
}


Measured memory_bytes: 33748
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

class Mod
{
    static const int MOD = 1000000007;
    long long a;
public:
    Mod(){
        a = 0;
    }
    Mod(long long x){
        a = (x % MOD + MOD) % MOD;
    }
    const Mod operator+(const Mod& x) const{
        return Mod(a + x.a);
    }
    const Mod operator-(const Mod& x) const{
        return Mod(a - x.a);
    }
    const Mod operator*(const Mod& x) const{
        return Mod(a * x.a);
    }
    const Mod operator/(const Mod& x) const{ //フェルマーの小定理、aとMODが互いに素の時のみ
        if(x.a == 0)return 0;
		if(a % x.a == 0)return Mod(a/x.a);
		long long b = MOD - 2;
        long long c = x.a;
        long long ret = 1;
        while(b > 0){
            if(b & 1){
                ret *= c;
                ret %= MOD;
            }
            c *= c;
            c %= MOD;
            b >>= 1;
        }
        return Mod(a * ret);
    }
    long long getValue(){
        return a;
    }
};

int dp[200010];

Mod combination(int n, int r)
{
	Mod a(dp[n]);
	Mod b(dp[r]);
	Mod c(dp[n-r]);
	b = b * c;
	a = a / b;
	return a;
}

int main()
{
	int h,w,a,b;
	cin >> h >> w >> a >> b;
	
	dp[0] = 1;
	for(ll i = 1;i < 200010;i++)
	{
		dp[i] = (dp[i-1] * i) % (ll)1000000007;
	}
	Mod ans;
	
	
	for(int i = 1;i <= h - a;i++)
	{
		ans = ans + ((combination(b+i-2,i-1) * combination((w-b-1)+(h-(i-1)-1),w-b-1)));
	}
	
	cout << ans.getValue() << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
const long long INF = 1ll << 60;



int main() {
  int n; cin >> n;
  int p[n];
  rep(i,n){
    cin >>p[i];
  }
  int cnt = 0;
  for(int i = 1; i < n-1; i++){
    if(p[i-1] < p[i] && p[i] < p[i+1])cnt++;
    if(p[i] < p[i-1] && p[i+1] < p[i])cnt++;
  }

  cout << cnt << endl;
	return 0;
}



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

const int N = 2e5 + 5;
const int mod = 998244353;

int n;
char s[N];
int dp[N][3][3][2];

set <int> st;
void solve(int dep = 0) {
	{
		int hsh = 0;
		for (int i = 0; i < n; ++ i)
			hsh = hsh * 23 + s[i] - 'a';
		st.insert(hsh);
	}
	if (dep == 20) return ;
	for (int i = 0; i + 1 < n; ++ i) {
		if (s[i] != s[i + 1]) {
			int c = 3 - (s[i] - 'a') - (s[i + 1] - 'a') + 'a';
			int osi = s[i], osi1 = s[i + 1];
			s[i] = s[i + 1] = c;
			solve(dep + 1);
			s[i] = osi; s[i + 1] = osi1;
		}
	}
}

int main() {
	cin >> s; n = strlen(s);
	if (n <= 3) {
		solve();
		cout << st.size() << endl;
		return 0;
	}
	bool ok = 0;
	for (int i = 1; i < n; ++ i) ok |= s[i] != s[0];
	if (!ok) return puts("1"), 0;
	dp[0][0][0][0] = 1;
	dp[0][1][1][0] = 1;
	dp[0][2][2][0] = 1;
	int wanted = 0;
	for (int i = 0; i < n; ++ i)
		(wanted += s[i] - 'a') %= 3;
	for (int i = 1; i < n; ++ i) {
		for (int lst = 0; lst < 3; ++ lst) {
			for (int sum = 0; sum < 3; ++ sum) {
				for (int f = 0; f < 2; ++ f) {
					for (int nw = 0; nw < 3; ++ nw) {
						(dp[i][nw][(sum + nw) % 3][f | (nw == lst)] += dp[i - 1][lst][sum][f]) %= mod;
					}
				}
			}
		}
	}
	bool eql = 1;
	for (int i = 1; i < n; ++ i) eql &= s[i] != s[i - 1];
	int ans = eql;
	for (int lst = 0; lst < 3; ++ lst)
		(ans += dp[n - 1][lst][wanted][1]) %= mod;
	cout << ans << endl;
	return 0;
}

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

int main(){
  int n;
  cin >> n;
  if ( n < 100 ){
    cout << min(9, n) << endl;
  } else if ( n < 10000){
    cout << 9 + min (999, n) - 99 << endl;
  } else {
    cout << 9 + 900 + min(99999, n ) - 9999 << endl;
  }


  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> cnt(3, 0);
    for(int i=0; i<n; ++i){
        int a;
        cin >> a;
        for(int j=2; ; --j){
            if(a % (1<<j) == 0){
                ++ cnt[j];
                break;
            }
        }
    }

    if(cnt[1] > 0)
        ++ cnt[0];
    if(cnt[0] - 1 <= cnt[2])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <tuple>
#include <numeric>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;
using ll = long long;
const int INF = 1e9;

int main() {
    ll a; double b;
    cin >> a >> b;
    ll b1 = b * 100 + 0.5;
    ll z = a * b1 / 100;
    printf("%lld\n", z);
}

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

using namespace std;
int a[100005],f[10005],n;
int main()
{
    cin >> n;
    for (int i=1;i<=n;i++)
        cin >> a[i];
    f[0]=0;
    f[1]=0;
    f[2]=abs(a[2]-a[1]);
    for (int i=3;i<=n;i++)
    f[i]=min(abs(a[i]-a[i-1])+f[i-1],abs (a[i]-a[i-2])+f[i-2]);
    cout << f[n];
    return 0;
}


Measured memory_bytes: 768
//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pb           push_back
#define ff           first
#define ss           second
#define gcd(a, b)    __gcd(a, b)
#define lcm(a, b)    ((a)*((b)/gcd(a,b)))
#define all(v)       v.begin(),v.end()
#define lllim        2147483648
#define Pi           2*acos(0.0)
#define sci(n)	     scanf("%d",&n)
#define scii(n,m)    scanf("%d%d",&n,&m)
#define scl(n)       scanf("%lld",&n)
#define scll(n,m)    scanf("%lld%lld",&n,&m)
#define pii          pair<int,int>
#define pll 	     pair<ll,ll>
#define mem(a,b)     memset(a, b, sizeof(a))
#define fill_(a,b)   fill(a,a+n,b);
#define MOD          1000000007
#define fast_cin     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define filein       freopen("input.txt","r", stdin)
#define D(x)         cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define case		 int t,cas=1;cin>>t;while(t--)
#define rep(i,a,n)   for(int i=a;i<n;i++)
#define rev(i,n,a)   for(int i=n;i>=a;i--)

/*------------------------------Graph Moves----------------------------*/
//const int fx[]= {+1,-1,+0,+0};
//const int fy[]= {+0,+0,+1,-1};
//const int fx[]= {+0,+0,+1,-1,-1,+1,-1,+1};  // Kings Move
//const int fy[]= {-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

template<class T> void ckmin(T& a, const T& b) {
    a= b < a? b:a;
}
template<class T> void ckmax(T& a, const T& b) {
    a= b > a? b:a;
}



template<class T> void read(T& a) {
    std::cin>>a;
}
template<class T> void read(T& a, int sidx,  int eidx) {
    for(int i=sidx; i<eidx; i++)
        std::cin>>a[i];
}



using namespace std;
using namespace __gnu_pbds;

const int maxn=100005;


vector<int>pr;
bool mark[maxn];

void si()
{
    mem(mark,0);
    for(int i=4; i<maxn; i+=2) mark[i]=1;
    for(int i=3; i*i<maxn; i+=2)
    {
        if(!mark[i])
            for(int j=i*i; j<maxn; j+=2*i)
                mark[j]=1;
    }

    pr.pb(2);
    for(int i=3; i<maxn; i+=2)
        if(!mark[i])
            pr.pb(i);
}


void solve()
{
    ll n;
    cin>>n;
    map<ll,ll>mpp;
    
    ll ara[n+2];
    ll sum=0;
    
    rep(i,0,n)
    {
		cin>>ara[i];
		mpp[ara[i]]++;
		sum+=ara[i];
	}
	int q;
	cin>>q;
	while(q--)
	{
		ll b,c;
		cin>>b>>c;
		//sum1=sum;
		
		ll cnt=mpp[b];
		sum-=(cnt*b);
		sum+=(cnt*c);
		mpp[b]=0;
		mpp[c]+=cnt;
		
		
		cout<<sum<<endl;
		//sum=sum1;
	}
    
	
}


int main()
{
    fast_cin;
    // si();

    //while(scanf("%d",&n)!=EOF)
//case
    {
		//cas=cas;
        //cout<<""<<cas++<<""<<endl;
        solve();
    }

    return 0;
}


Measured memory_bytes: 10200
void main() {
	auto N = readAs!ulong;
	ulong res = ulong.max;
	for(ulong i = 1; i*i <= N; i++) {
		auto b = div(N, i);
		if(b > 0) {
			res = min(res, max(b.to!string.length, i.to!string.length));
		}
	}
	//if(N <= 3) res = 1;
	res.writeln;
}

long div(ulong N, ulong a) {
	if(N%a != 0) return -1;
	return (N / a).to!long;
}

// ===================================

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int n;
  int total = 0;
  scanf("%d", &n);
  int v[n];

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

  for(int i = 0; i < n-1; ++i){
    for(int j = i+1; j < n; ++j){
      total += v[i]*v[j];
    }
  }
  printf("%d\n", total);
  return 0;
}


Measured memory_bytes: 128
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readNInts = readInt >>= flip replicateM readInt

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	n <- readInt
	[ xs, ys, hs ] <- transpose <$> replicateM n readInts
	let
		( x, y, h ) = head $ do
			cx <- [ 0 .. 100 ]
			cy <- [ 0 .. 100 ]
			let
				ch = head [ h + abs ( cx - x ) + abs ( cy - y ) | ( x, y, h ) <- zip3 xs ys hs, 0 < h ]
			if all ( check ( cx, cy,  ch ) ) ( zip3 xs ys hs )
				then return ( cx, cy, ch )
				else []
	printf "%d %d %d\n" x y h

check ( cx, cy, ch ) ( x, y, h ) = max 0 ( ch - abs ( cx - x ) - abs ( cy - y ) ) == h

Measured memory_bytes: 1020
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ABC097C - K-th Substring
  string s; cin >> s;
  int K; cin >> K;
  int N = s.size();
  set<string> setS;
  REP(i, N){
    for(int j = 1; j <= min(N - i, K); j++){
      setS.insert(s.substr(i, j));
    }
  }
  vector<string> vecS(setS.begin(), setS.end());
  sort(vecS.begin(), vecS.end());
  cout << vecS[K-1] << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define Max(a,b,c) max(a,max(b,c))
#define Min(a,b,c) min(a,min(b,c))
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define pc(x)  __builtin_popcount (x)
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define ld long double
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod 1000000007
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define gcd __gcd
#define primeDEN 727999983
#define nx_pe next_permutation(s.begin(),s.end())
#define cl cout<<"\n"
#define sp(x) setprecision(x)

void solve()
{
    ll x;
    cin>>x;
    if(x>=30)cout<<"Yes\n";
    else cout<<"No\n";
}


    
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin) ;
    freopen("ouput.txt", "w", stdout) ;
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL) ; cout.tie(NULL) ;
    std::ios::sync_with_stdio(false);
    ll te=1;
    // cin>>te;
    while(te--){
        solve();
    }
    
}


Measured memory_bytes: 3608
A, B, C, D = list(map(int, list(input())))

def int_to_pm(x):
    if x == 0:
        return '+'
    else:
        return '-'

for i in range(2):
    for j in range(2):
        for k in range(2):
            ans = A + (1-2*i)*B + (1-2*j)*C + (1-2*k)*D
            if ans == 7:
                print(str(A) + int_to_pm(i) + str(B) + int_to_pm(j) + str(C) + int_to_pm(k) + str(D) + '=7')
                break
        else:
            continue
        break
    else:
        continue
    break


Measured memory_bytes: 3064
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static void main (String[] args) throws IOException
    {
    	Scanner sc = new Scanner(System.in);
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		int c = sc.nextInt();
    		
    		if ((a==b) && (b==c)) {
    			System.out.println("1");
    		}
    			else {
    				if ((a != b) && (b != c) && (c != a)){
    					System.out.println("3");
    			}
    				else System.out.println("2");
    			}
    		 
    }	
}
    
   

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

int main() {
    string S;
    cin >> S;

    if (S == "Sunny") {
        cout << "Cloudy" << endl;
    } else if (S == "Cloudy") {
        cout << "Rainy" << endl;
    } else {
        cout << "Sunny" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
typedef struct data{
long long  a;
long long  b;
}Data;
int cmp(const void *p,const void *q){
if( *(long long*)q - *(long long*)p < 0 )
        return -1;
    if( *(long long*)q - *(long long *)p > 0 )
        return 1;
    return 0;
}
int cmpa(const void *p,const void *q){
if( ((Data*)q)->a - ((Data*)p)->a < 0 )
        return -1;
    if( ((Data*)q)->a - ((Data*)p)->a > 0 )
        return 1;
    return 0;
}
int main(){
    long long N,H,i,ans=0,max;
    scanf("%lld%lld",&N,&H);
    long long buf[2*N];
    Data d[N];
    
    for(i=0;i<N;i++)scanf("%lld%lld",&d[i].a,&d[i].b);
    qsort(d,N,sizeof(Data),cmpa);
    max=d[0].a;
    
    for(i=0;i<N;i++){
    buf[2*i]=d[i].a;
    buf[2*i+1]=d[i].b;
    }
    qsort(buf,2*N,sizeof(long long),cmp);
    
    i=0;
    while((i<(2*N))&&(buf[i]>=max)&&(H>0)){
    H-=buf[i];
    ans++;
    i++;
    }
    if(H>0){
    long long k=(H/max);
    ans+=k;
    if(H>k*max)ans++;
    }
    
    printf("%lld",ans);
}

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

using namespace std;

int main(){
    int n;
    cin>>n;
    int arr[n][3];
    for(int i = 0;i< n;i++){
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    }
    int markArr[n][3];
    memset(markArr, 0, sizeof(markArr));
    // int index= -1, num = 0;
    int sum  =0;
    for(int i = 0;i< n;i++){
        for(int j=0;j< 3;j++){
            if(i== 0){
                markArr[i][j] = arr[i][j];
            }
            else{
                int num =0;
                for(int k=0 ;k< 3;k++){
                    if(k!= j){
                        if(num < markArr[i-1][k]){
                            num = markArr[i-1][k];
                        }
                    }
                }
                markArr[i][j] = arr[i][j]+ num;
            }
        }
        // for(int j= 0;j< 3;j++){
            // if(num == arr[i][j])index = j;
        // }
    } 
    cout<<*max_element(markArr[n-1],markArr[n-1] +3);
}

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

using namespace std;

int n,w;

void solve(){
    cin >> n >> w;
    vector<long long> dp(w+1,0);
    vector<int> ww(n),v(n);
    for(int i = 0;i < n;i++) cin >> ww[i] >> v[i];
    for(int i = 0;i < n;i++){
        for(int j = w-ww[i];j >= 0;j--){
            dp[j+ww[i]] = max(dp[j+ww[i]],dp[j]+v[i]);
        }
    }
    cout << *max_element(dp.begin(),dp.end()) << endl;
}

int main(){
    solve();
}


Measured memory_bytes: 1024
#coding:UTF-8
a = int(input())
b = int(input())
c = int(input())
x = int(input())
count = 0
for aa in range(a+1):
  for bb in range(b+1):
    for cc in range(c+1):
      if aa*500+bb*100+cc*50 == x:
        count = count+1
print(count)  

Measured memory_bytes: 3060
from collections import deque
x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p_1 = deque(sorted(p))
q_1 = deque(sorted(q))
r_1 = sorted(r)
while len(p_1) > x:
  p_1.popleft()
while len(q_1) > y:
  q_1.popleft()
pqr = deque(sorted(list(p_1) + list(q_1) + r_1))
i = 0
ans = 0
while i < x+y:
  ans += pqr.pop()
  i += 1
print(ans)

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

const int INF = 1000000;
typedef pair<int,int> P;

char maze[20+1][20+1];
int h,w;
int sx,sy,gx,gy;
int d[20+1][20+1];

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

int bfs(){
  queue<P> que;
    
  for(int i=0;i<h+1;i++){
    for(int j=0;j<w+1;j++){
      d[i][j] = INF;
    }
  }
  
  que.push(P(sy,sx));
  d[sy][sx] = 0;
  
  while(que.size()){
    
    P p = que.front();
    que.pop();
    //cout << p.first << ' ' << p.second << endl;
    if(p.first == gy && p.second == gx) break;
    
    for(int i=0;i<4;i++){
      int ny = p.first + dy[i] , nx = p.second + dx[i];
      
      if(nx > 0 && nx <= w && ny > 0 && ny <= h && maze[ny][nx] == '.' && d[ny][nx] == INF){
        que.push(P(ny,nx));
        d[ny][nx] = d[p.first][p.second] + 1;
        //cout << ny << ' ' << nx << endl;
        //cout << d[ny][nx] << endl;
      }
    }
  }
  return d[gy][gx];
}  

int main(){
  int md = 0,temp = 0;
  cin >> h >> w;
    
  for(int i=1;i<h+1;i++){
    string s;
    cin >> s;
    for(int j=1;j<w+1;j++){
      maze[i][j] = s.at(j-1);
    }
  }
  
  for(sy=1;sy<=h;sy++){
    for(sx=1;sx<=w;sx++){
      if(maze[sy][sx] == '.'){
        for(gy=sy;gy<=h;gy++){
	      for(gx=0;gx<=w;gx++){
            if(maze[gy][gx] == '.' && (gx != sx || gy != sy)){
              temp = bfs();
              if(temp > md) md = temp;
              //cout << sx  << ' ' << sy << ' ' << gx << ' ' << gy << endl; 
            }
          }
        }
      }
    }
  }
  
  cout << md << endl;
  
}


Measured memory_bytes: 256
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx2,tune=native") // Auto-Vectorisation

#include "bits/stdc++.h"
#include "chrono"
#include "random"
using namespace std;

/*
//large integers
#include <boost/multiprecision/cpp_int.hpp>
__int128 s128; // pollard rho
__uint128_t u128;

//policy based data structures
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace boost::multiprecision; 
using namespace __gnu_pbds;
*/

typedef long long int ll;
typedef long double ld;
typedef double db;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef unsigned long long u64;
typedef vector<ll> vl;
typedef vector<pll> vpl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef unordered_set<ll> usl;
typedef set<ll> sl;
typedef multiset<ll> mul;
typedef unordered_map<ll,ll> umll;
typedef map<ll,ll> mll;

#define int long long int
#define sz(a) (ll)a.size()
#define lt(a) (ll)a.length()
#define tc(x) ll x; cin>>x; while(x--)
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define bac(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define print(a)  for (auto x : a) cout << x << " "; cout << endl
#define mt make_tuple
#define eb emplace_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define endl '\n'
#define all(a) a.begin(),a.end()
#define Sort(x) sort(all((x)))
#define setbits(a) __builtin_popcountll(a)
#define ps(x,y) fixed<<setprecision(y)<<x;
#define hhh cout<<"hello"<<'\n'
#define deb(x) cerr<<#x<<" = "<<x<<'\n'
#define F first
#define S second
#define teevra_gati ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //shuffle(all(v), rng);

const string alpha   =   "abcdefghijklmnopqrstuvwxyz";
const db EPS         =   1.22515e-06;
const db PI          =   3.14159265359;
const ll P           =   1e9 + 7; // 998244353; // 1e9 + 9 // 7340033 // 4294967296;
const ll Q           =   1e9 + 6; // 998244352; // 1e9 + 8 // 7340032;
const ll ninf        =   LONG_MIN;
const ll inf         =   1e18;
const ll M           =   2e3 + 5;
const ll N           =   1e5 + 5;

void solve(){
    ll k;
    cin>>k;
    string add = "ACL", ans= "";
    f(i,0,k) ans += add;
    cout<<ans;
}

signed main(){
    teevra_gati

    solve();

    //cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;



string t="ACGT";

int main(){
    string s;cin >> s;
    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < s.length(); i++) {
        bool flag = false;
        for (int j = 0; j < t.length(); j++) {
            if(s[i]==t[j]) flag =true; 
        }
        if(flag) cnt++;
        else{
            ans = max(ans,cnt);
            cnt = 0;
        }
    }
    ans = max(ans,cnt);
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
def main():
    S = str(input())
    t = 0
    diff = 0
    near = 10000
    for i in range(2, len(S)):
        t = int(S[i-2]) * 100 + int(S[i-1]) * 10 + int(S[i])
        if 753 < t:
            diff = t - 753
        else:
            diff = 753 - t
        if near > diff:
            near = diff
    print(near) 
main()  

Measured memory_bytes: 9020
'use strict'

const main = (input) => {
    input = input.split('\n')
    const odd = input[0].split('')
    const even = input[1].split('')
    
    let str = ''
    for(let i = 0; i <= even.length - 1; i++){
        str += odd[i]
        str += even[i]
    }

    if(odd.length > even.length){
        str += odd[odd.length - 1]
    }
    console.log(str)
}

main(require('fs').readFileSync('/dev/stdin', 'utf-8'))

Measured memory_bytes: 7500
#include <functional>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <math.h>
using namespace std;


int main() {
   int a,b,c;
 
   cin >> a >> b >> c;
  
   if(a+b+c<=21){
     cout << "win" << endl;
     
   }else{
     cout << "bust" << endl;
   }
   
  return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <deque>
#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <string>
#include <vector>
#include <vector>

using namespace std;

#define int long long

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

signed main(void)
{
  int n; cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];

  deque<int> b;
  for (int i = 0; i < n; ++i) {
    if (i % 2 == 0)
      b.push_back(a[i]);
    else
      b.push_front(a[i]);
  }

  if (n % 2 == 0) {
    for (auto it = b.cbegin(); it != b.cend(); ++it) {
      cout << *it << " ";
    }
  } else {
    for (auto it = b.crbegin(); it != b.crend(); ++it) {
      cout << *it << " ";
    }
  }
  
  cout << endl;
  
}


Measured memory_bytes: 5376
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int GCD(const int& a, const int& b){
   const int& _a = max(a,b);
   const int& _b = min(a,b);
   if(_a % _b == 0){
      return _b;
   }
   else{
      return GCD(_b, _a % _b);
   }
}

int LCM(const int& a, const int& b){
   const int& _a = max(a,b);
   const int& _b = min(a,b);
   return (_a*_b)/(GCD(_a, _b));
}

int main(){
   int a[3];
   cin >> a[0] >> a[1] >> a[2];
   sort(a,a+3);
   cout << abs(a[2] - a[0]) << endl;

   return 0;
}

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

// int/long:		-2147483648 - 2147483648 (-2^31 <= int < 2^31)
// long/long long:	-9223372036854775808 - 9223372036854775807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536870912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// bit: &/and, |/or, ^/xor, ~/not

#define	MOD 1000000007

int	main() {
	int N;
	cin >>N;
	vector<int> RATE(9, 0);
	for (int i=0; i<N; i++) {
		int a;
		cin >>a;
		a /=400;
		if (a>=8)
			RATE.at(8)++;
		else
			RATE.at(a)++;
	}
	int MIN=0;
	for (int i=0; i<8; i++)
		if (0<RATE.at(i))
			MIN++;
	int MAX=MIN+RATE.at(8);
	if (0==MIN)
		MIN++;
	cout <<MIN <<' ' <<MAX <<endl;
	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    long long int N, M;
    int i;
    long long int a = 0;
    long long int tmpa;
    scanf("%lld %lld", &N, &M);

    for (i = 0; i < M; i++)
    {
        scanf("%lld ", &tmpa);
        a += tmpa;
    }
    
    if (N < a)
        printf("-1");
    else
        printf("%lld", N - a);
    return (0);
}


Measured memory_bytes: 1728
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int LL;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define endl "\n"
#define SORT(v) sort(v.begin(),v.end())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

void mod_print(ll k){
    ll P=1000;
    rep(y,1,P){
        ll x=mod(y*k);
        if(x+P>=i_7){
            x-=i_7;
        }
        if(abs(x)<=P){
            cout<<x<<"/"<<y<<endl;
            return;
        }
    }
    cout<<"nun"<<endl;
}
//////////////////////////

struct shop{
    ll a,b;
    dd cmp;
};
bool comp(shop x,shop y){
    //return x.a*(y.b+1)>=y.a*(x.b+1);
    return x.cmp>y.cmp;
}

int main(){fastio
    ll n,t;cin>>n>>t;
    vector<shop>v;
    vector<ll>last;
    rep(i,0,n-1){
        shop s;cin>>s.a>>s.b;
        s.cmp=(dd)s.a/(dd)(s.b+1);
        if(s.a==0){
            last.pb(s.b);
        }else{
            v.pb(s);
        }
    }
    
    sort(v.begin(),v.end(),comp);
   // for(auto x:v)cout<<x.a<<" "<<x.b<<endl;
    ll M=32;
    ll vs=v.size();
    ll dp[2][M];
    rep(i,0,1)rep(j,0,M-1)dp[i][j]=inf;
    dp[0][0]=0;
    rep(i,0,vs-1){
        rep(j,0,M-1)dp[(i+1)&1][j]=inf;
        shop s=v[i];
        rep(j,0,M-1){
            if(dp[i&1][j]==inf)continue;
            chmin(dp[(i+1)&1][j],dp[i&1][j]);
            ll nxt=(dp[i&1][j]+1)*(s.a+1)+s.b;
            if(nxt<=t&&j+1<=M-1)chmin(dp[(i+1)&1][j+1],nxt);
        }
       // rep(j,0,M-1)cout<<dp[(i+1)&1][j]<<" ";cout<<endl;
    }
    ll ans=0;
    SORT(last);
    ll sz=last.size();
    vector<ll>a(sz+1);
    a[0]=0;
    rep(i,0,sz-1){
        a[i+1]=a[i]+(last[i]+1);
    }
    rep(j,0,M-1){
        ll res=t-dp[vs&1][j];
        if(res<0)continue;
        
        ll p=POSU(a,res)-1;
        chmax(ans,p+j);
    }
    cout<<ans<<endl;
    
    
    return 0;
}



Measured memory_bytes: 10476
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<int,int>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;

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

	ll n,m;
	cin >> n >> m;
	vector<ll> A(n);
	FOR(i,0,n)cin >> A[i];
	SORT(A);
	vector<P> BC(m);
	FOR(i,0,m){
		cin >> BC[i].second >> BC[i].first;
	}
	SORT(BC);
	REV(BC);
	int i=0,j=0;
	while(1){
		if(BC[j].second && BC[j].first>A[i]){
			A[i] = BC[j].first;
			i++;
			if(i==n)break;
			BC[j].second--;
			if(BC[j].second==0){
				j++;
				if(j==m)break;
			}
		}else{
			break;
		}
	}
	ll ans = 0;
	FOR(i,0,n){
		ans += A[i];
	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define fi first
#define se second
#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 srep(i, s, t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define limit(x, l, r) max(l, min(x, r))
#define lims(x, l, r) (x = max(l, min(x, r)))
#define isin(x, l, r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)), x.end())
#define show(x) cout << #x << " = " << x << endl;
#define PQ(T) priority_queue<T, v(T), greater<T>>
#define bn(x) ((1 << x) - 1)
#define dup(x, y) (((x) + (y)-1) / (y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
ll dp[110][10];
const ll MOD= 1000000007LL;
int main() { 
  int H, W, K;
  cin >> H >> W >> K;
  dp[0][0] = 1;

  auto check = [&](ll x){
    int cnt = 0;
    rep(i,W-1){
      if((x >> i )& 1)cnt++;
      else cnt = 0;
      if(cnt>=2)return false;
    }
    return true;
  };
  rep(i,H)rep(j,W){
    rep(k,1<<(W-1)){
      if(!check(k))continue;
      if((k>>(j-1))&1){
          dp[i+1][j-1] += dp[i][j];
          dp[i+1][j-1]%=MOD;
      }
      else if((k>>j)&1) dp[i+1][j+1] += dp[i][j];
      else dp[i+1][j]+=dp[i][j];
      dp[i+1][j]%=MOD;
      dp[i+1][j+1]%=MOD;
    }
  }
  cout<<dp[H][K-1]<<endl;
  return 0;
}

Measured memory_bytes: 3636
/// /* Bismillahir Rahmanir Rahim *\

/// S. M. Shakir Ahsan Romeo
/// Khulna University
/// CSE Discipline
#include <bits/stdc++.h>
using namespace std;
typedef long long lng;
const double eps = 1e-6;
const double PI = acos(-1.0);
const double ee = 2.71828182845904523536;
const long long inf = 1LL << 62;
lng Pow(lng b, lng p)
{
    if(p == 0) return 1;
    lng t = Pow(b, p >> 1);
    if(p & 1) return t * t * b;
    return t * t;
}
lng gcd(lng aa, lng bb)
{
    return bb == 0 ? aa : gcd(bb, aa % bb);
}
lng lcm(lng aa, lng bb)
{
    return aa / gcd(aa, bb) * bb;
}
double distance(double x1, double y1, double x2, double y2)
{
    x1 -= x2;
    y1 -= y2;
    return sqrt(x1 * x1 + y1 * y1);
}
string tostring(lng x)
{
    string r = "";
    while(x > 0)
    {
        r = (char)(x % 10 + 48) + r;
        x /= 10;
    }
    return r;
}
#define     rt0            return 0;
#define     FAST           ios_base::sync_with_stdio(0);cin.tie(0);
#define     endl           '\n'
#define     pb             push_back
#define     sf             scanf
#define     pf             printf
#define     all(x)         x.begin(), x.end()
#define     xx             first
#define     yy             second
#define     bin_sea(xx,yy) binary_search(all(xx),yy)
#define     dbg(x)         cout << x << " came here\n";
#define     si(x)          sf("%d", &x);
#define     mem(x, y)      memset(x, y, sizeof(x));
#define     rep(i, x)      for(int i = 0; i < x; ++i)
#define     rep1(i, x)     for(int i = 1; i <= x; ++i)
#define     repstl(it, xx) for(auto it = xx.begin(); it != xx.end(); it++)
#define     min3(aa,bb,cc) min(aa, min(bb,cc))
#define     RAD_TO_DEG     180.0/PI
#define     read(a)        freopen(a, "r", stdin);
#define     write(a)       freopen(a, "w", stdout);
#define     pr1(aa)        cout << aa << '\n';
#define     pr2(aa,bb)     cout << aa << ' ' << bb << '\n';
#define     pr3(aa,bb,cc)  cout << aa << ' ' << bb << ' ' << cc << '\n';
#define     pr4(aa,bb,cc,dd)  cout << aa << ' ' << bb << ' ' << cc << ' ' << dd << '\n';
#define     prv(x)         rep(iii, x.size()) cout << x[iii] << ' '; cout << '\n';
#define     repbstl(it,x)  for(auto it = x.rbegin(); it != x.rend(); it++)
#define     alen(x)        sizeof(x) / sizeof(x[0]);
#define     pra(xxx)       for(auto iii : xxx) cout << iii << ' '; cout << endl;
#define     pause          int ppause; cin >> ppause;
#define     gti(xx)        scanf("%d", &xx);
#define     gtl(xx)        scanf("%I64d", &xx);
#define     gts(xx)        getline(cin, xx);

pair<bool, int> has[200001];

int main()
{
    has[1].xx = true;
    has[1].yy = 1;
    int n, m, ans = 0;
    sf("%d %d", &n, &m);
    for(int i = 2; i <= n; ++i)
    {
        has[i].xx = false;
        has[i].yy = 1;
    }
    while(m--)
    {
        int x, y;
        sf("%d %d", &x, &y);
        ++has[y].yy;
        --has[x].yy;
        if(has[x].xx)
            has[y].xx = true;
        if(has[x].yy == 0)
            has[x].xx = false;
    }
    rep1(i, n)
        ans += has[i].xx;
    pf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef  long long ll;
ll gcd(ll x,ll y){
   if(y==0) return x;
   else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
   return x/gcd(x,y)*y;
}
using namespace std;
int main(){ 
   int n;
   cin>>n;
   vector<int> a(n);
   rep(i,n){
      cin>>a[i];
   }
   int count=0;
   int flag=0;
   rep(i,100000){
      for(int j=0;j<n;j++){
         int b=a[j]%2;
         if(b==1) flag=1;
         a[j]=a[j]/2; 
      }
      if(flag==1) {
         cout<<count;
         break;
      }
      count++;
   }
   



   
   return 0;
}

Measured memory_bytes: 256