akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

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

using namespace std;
const long long MOD = 998244353;
const long long INF = 1LL << 61;

int main() {
	int X, Y, A, B, C;
	cin >> X >> Y >> A >> B >> C;

	priority_queue<int, vector<int>, greater<int>> pqA;
	rep(i, A) {
		long long num;
		cin >> num;
		pqA.push(num);
	}
	rep(i, A - X)pqA.pop();
	/*while (!pqA.empty()) {
		cout << pqA.top() << endl;
		pqA.pop();
	}*/
	priority_queue<int, vector<int>, greater<int>> pqB;
	rep(i, B) {
		long long num;
		cin >> num;
		pqB.push(num);
	}
	rep(i, B - Y)pqB.pop();
	/*while (!pqB.empty()) {
		cout << pqB.top() << endl;
		pqB.pop();
	}*/
	priority_queue<int> pqC;
	rep(i, C) {
		long long num;
		cin >> num;
		pqC.push(num);
	}

	while (!pqC.empty()) {
		int difA = pqC.top() - pqA.top();
		int difB = pqC.top() - pqB.top();
		/*cout << pqA.top() << endl;
		cout << pqB.top() << endl;*/
		if ((difA >= difB) && (difA > 0)) {
			pqA.pop(); pqA.push(pqC.top());
		}
		else if ((difA <= difB) && (difB > 0)) {
			pqB.pop(); pqB.push(pqC.top());
		}
		pqC.pop();
	}

	long long ans = 0;
	while (!pqA.empty()) {
		ans += (long long)pqA.top();
		pqA.pop();
	}
	while (!pqB.empty()) {
		ans += (long long)pqB.top();
		pqB.pop();
	}

	cout << ans;
	
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  	int a,ans;
  	cin >> a;
  	ans = a+a*a+a*a*a;
  	cout << ans;
    return 0;
}

Measured memory_bytes: 3596
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var XKD = ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray();
        var (X, K, D) = (XKD[0], XKD[1], XKD[2]);

        X = Math.Abs(X);

        var d = X / D;
        var r = X % D;

        if(K <= d)
        {
            WriteLine(X - (D * K));
            return;
        }

        K -= d;

        if(K % 2 == 0)
        {
            WriteLine(X - (D * d));
            return;
        }
        else
        {
            WriteLine(Math.Abs(X - (D * (d + 1))));
            return;
        }
    }
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,k;
int a[125];
ll dp[125][125252]; // dp[i][j] := i-th, rest j candies
ll sum[125252];

int main(){
  scanf("%d%d",&n,&k);
  REP(i,n)scanf("%d",a+i);
  dp[0][k] = 1;
  // // kubaru dp
  // REP(i,n){
  //   int v = a[i];
  //   REP(j,k+1){
  //     REP(u,min(v,j)+1){
  //       (dp[i+1][j-u] += dp[i][j]) %= MOD;
  //     }
  //   }
  // }

  // morau dp
  REP(i,n){
    REP(j,k+1)sum[j+1] = (sum[j] + dp[i][j]) % MOD;
    int v = a[i];
    REP(j,k+1){
      dp[i+1][j] = (sum[j+min(v,k-j)+1] - sum[j] + MOD) % MOD;
      // REP(u,min(v,k-j)+1){
      //   dp[i+1][j] += dp[i][j+u];
      // }
    }
  }
  printf("%lld\n",dp[n][0]);
  return 0;
}


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

#define INF_LL 1e18
#define INF 1e9

#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()

#define fst first
#define snd second

using namespace std;

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

vector<int> G[5005];
vector<int> standings;
bool used[5005] = {};
int kind = 0;

void visit(int v){
	if(used[v]) return;
	used[v] = 1;
	int cnt = 0;
	REP(i, G[v].size()){
		visit(G[v][i]);
		cnt++;
	}
	if(cnt > 1)
		kind++;
	standings.push_back(v);
}

int main(void){
	int n, m;
	cin >> n >> m;
	REP(i, m){
		int a,b;
		cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
	}
	REP(i, n){
		visit(i);
	}
	reverse(all(standings));
	REP(i, n){
		cout << standings[i]+1 << endl;
	}
	REP(i, n-1){
		bool there = true;
		REP(j, G[standings[i]].size()){
			if(G[standings[i]][j] == standings[i+1])
				there = false;
		}
		if(there){
			cout << 1 << endl;
			return 0;
		}
	}
	cout << 0 << endl;
}

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





int main(){
    int N;
    cin >> N;
    if(N==1)cout << "Hello World" <<endl;
    else{
    int A,B;
    cin >> A >> B;
    cout << A+B << endl;
    }
}


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

int main(){
    unordered_map<int, int> mp;
    int S;
    
    cin >> S;
    mp[S]++;
    int i = 2;
    int a = 0;
    int preva = S;
    
    while(1){
        if((preva) % 2 == 0){
            a = preva / 2;
        }else{
            a = 3 * preva + 1;        
        }
        
        mp[a]++;
        if(mp[a] == 2){
            break;
        }else{
            i++;
            preva = a;
        }
    }
    cout << i << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<string.h>
#include<set>
#include<map>
#define LL long long
#define pr pair<int,int>
#define fr first
#define sc second
//#define mp make_pair
using namespace std;
LL read( ){LL sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) return -sum;return sum;}
void read(int &sum){sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) sum=-sum;}
void read(LL &sum){sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) sum=-sum;}
int A[30],B[30],C[30];
int main( )
{
  int i,n=read( ),c=0;
  for(i=1;i<=n;i++) read(A[i]);
  for(i=1;i<=n;i++) read(B[i]),c+=B[i];
  for(i=1;i<n;i++) read(C[i]);
  for(i=2;i<=n;i++)
    {
      if(A[i]==A[i-1]+1) c+=C[A[i]-1];
    }
  printf("%d",c);
  return 0;
}


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

#define PB push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define per(i,n) for(int i = (n)-1; i >= 0; --i)
#define rng(i,a,b) for(int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

const int inf = 1e9;
int D;
vl c, ans;
vvl s;

void init() {
    cin >> D;
    ans.assign(D, 0);
    c.resize(26);
    s.assign(D, vl(26));
    rep(t, 26) cin >> c[t];
    rep(d, D) rep(t, 26) {
        cin >> s[d][t];
    }
}

ll evaluate(vl typeOfDays, int numDays = D) {
    ll score = 0;
    vl lasts(26, 0);
    rep(d, numDays) {
        score += s[d][typeOfDays[d]];
        lasts[typeOfDays[d]] = d + 1;
        rep(t, 26) {
            score -= c[t] * (d - lasts[t] + 1);
        }
    }
    return score;
}

void solve() {
    rep(d,D) {
        ll mx = -inf;
        vl cand = ans;
        rep(t,26) {
            cand[d] = t;
            ll sc = evaluate(cand,d+1);
            if (sc > mx) {
                mx = sc;
                ans = cand;
            }
        }
    }
    cerr << evaluate(ans) << endl;
}

void output() {
    rep(d,D) cout << ans[d]+1 << endl;
}

int main() {
    init();
    solve();
    output();
    return 0;
}


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

void solve()
{
	int n;
	cin>>n;
	map<string,int> m;
	for (int i = 0; i < n; ++i)
	{
		string s;
		cin>>s;
		m[s]++;
	}
	cout<<"AC x "<<m["AC"]<<endl;
	cout<<"WA x "<<m["WA"]<<endl;
	cout<<"TLE x "<<m["TLE"]<<endl;
	cout<<"RE x "<<m["RE"]<<endl;

}

int main()
{
	ll t = 1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
}



Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int> >;
#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(int i = m; i < (int)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum accumulate
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
typedef long long ll;
const int INF = 2000000000;
const ll INF64 = 9223372036854775806ll;
const int mod = 1000000007ll;
const ll  MOD = 1000000007LL;
/*メモ 
*/
int main(){
    int n;
    std::cin >> n;
    vvector(f,ll,n,10,0);
    vvector(p,ll,n,11,0);
    rep(i,n)rep(j,10)std::cin >> f[i][j];
    rep(i,n)rep(j,11)std::cin >> p[i][j];
    ll ans=-INF64;
    brep(10){
        if(bit==0)continue;
        ll dum=0;
        rep(i,n){
            int c=0;
            rep(j,10)if((bit&(1<<j))&&f[i][j])c++;
            dum+=p[i][c];
        }
        ans=max(ans,dum);
    }
    
    std::cout << ans << std::endl;
}

Measured memory_bytes: 256
n = int(input())
a = [0]+list(map(int,input().split()))
money = 1000
stock = 0

for i in range(1,n+1):
  if i==n:
    money += stock *a[i]
    stock = 0    
  else:
    if a[i] < a[i+1]:
      stock += money//a[i]
      money -= money//a[i]*a[i]
    elif a[i] == a[i+1]:
      pass
    else:
      money += stock *a[i]
      stock = 0

#  print(i,'money:',money,'stock:',stock)
print(money)

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

int main() {
    while(true) {
        int h, w; cin >> h >> w;
        if (h == 0 && w == 0)
            break;
        rep(i, h) {
            rep(j, w){
                if ((i + j) % 2 == 0) {
                    cout << "#";
                }
                else
                    cout << ".";
            }
            cout << endl;
        }
        cout << endl;
    }
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp setprecision
#define pb(x) push_back(x)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e8;
const ll INF = 1e16;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    ll N;
    cin >> N;
    ll a[N], b[N];
    rep(i, N) cin >> a[i];
    rep(i, N) cin >> b[i];
    ll ans = 0;
    if(N%2 == 1){
        rep(i, N){
            ans ^= a[i];
            ans ^= b[i];
        }
    }
    //2進数で表したときの下から(i+1)桁目の繰り上がりの回数を調べる
    rep(i, 30){
        //繰り上がりの回数
        ll cnt = 0;
        //A[i]:=a[i]の下i桁、B[i]:=b[i]の下i桁
        ll A[N], B[N];
        fill(A, A+N, 0), fill(B, B+N, 0);
        rep(j, N){
            //下(k+1)桁目を足す
            rep(k, i){
                if(a[j] & (1ll<<k)) A[j] += (1ll<<k);
                if(b[j] & (1ll<<k)) B[j] += (1ll<<k);
            }
        }
        sort(B, B+N);
        rep(j, N){
            cnt += B+N - lower_bound(B, B+N, (1ll<<i)-A[j]);
        }
        if(cnt%2 == 1) ans ^= (1ll<<i);
    }
    cout << ans << endl;
}

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

int main() {
    int64_t n;
    cin >> n;
    vector<int64_t> t(n);
    for (auto& e : t) cin >> e;
    for (int64_t i = 0; i + 1 < n; i++) {
        t[i+1] = t[i] / __gcd(t[i], t[i+1]) * t[i+1]; 
    }
    cout << t.back() << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
char s[2001][2001];
int a[2001][2001]= {0};
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++){
        scanf("%s",s[i]);
    }
    int j;
    for(int i=0; i<n; ++i)
    {
        int num=0;
        for(j=1; j<m; ++j)
        {
            if(s[i][j-1]!='#'&&s[i][j]=='.')
            {
                num++;
                a[i][j]+=num;
            }
            else
                num=0;
        }
        num=0;
        for(j=m-2; j>=0; --j)
        {
            if(s[i][j+1]!='#'&&s[i][j]=='.')
            {
                num++;
                a[i][j]+=num;
            }
            else
                num=0;
        }
    }
    int maxnum=-1;
    for(int i=0; i<m; ++i)
    {
        int num=0;
        for(j=1; j<n; ++j)
        {
            if(s[j-1][i]!='#'&&s[j][i]=='.')
            {
                num++;
                a[j][i]+=num;
            }
            else
                num=0;
        }
        num=0;
        for(j=n-2; j>=0; --j)
        {
            if(s[j+1][i]!='#'&&s[j][i]=='.')
            {
                num++;
                a[j][i]+=num;
            }
            else
                num=0;
            //maxnum=max(maxnum,a[j][i]);
        }
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
            if(s[i][j]=='.')
            maxnum=max(maxnum,a[i][j]+1);
    }
    printf("%d\n",maxnum);
    return 0;
}


Measured memory_bytes: 19840
#include <iostream>
#include <queue>

using namespace std;

int main(){
    int Q;
    cin >> Q;
    priority_queue<int, vector<int>, greater<int>> que2;
    priority_queue<int, vector<int>> que1;
    long sum1 = 0;
    long sum2 = 0;
    long sumb = 0;
    int cnt = 0;
    for(int i = 0; i < Q; i++){
        int t;
        cin >> t;
        if(t == 1){
            cnt++;
            int a, b;
            cin >> a >> b;
            sumb += b;
            if(cnt <= 2) {
                que1.push(a);
                sum1 += a;
            }
            else{
                long t1 = que1.top();
                long t2 = que2.top();
                if(t2 < a) {
                    que2.push(a);
                    sum2 += a;
                }else{
                    que1.push(a);
                    sum1 += a;
                }
            }
            if(que1.size() > (cnt+1)/2){
                long top = que1.top();
                que1.pop();
                que2.push(top);
                sum1 -= top;
                sum2 += top;
            }
            if(que2.size() > cnt/2){
                long top = que2.top();
                que2.pop();
                que1.push(top);
                sum2 -= top;
                sum1 += top;
            }
        }else{
            long m = que1.top();
            long ans = 0;
            ans = -(sum1-que1.size()*m)+(sum2-que2.size()*m)+sumb;
            cout << m << ' ' << ans << endl;
        }
    }
}

Measured memory_bytes: 3452
def main():
    import sys

    readline = sys.stdin.readline

    N, W = map(int, readline().split())
    lst = [list(map(int, readline().split())) for _ in [0] * N]

    # 配るDP
    # dp[n][sum_w]はn個目までの品物でsum_w以下の重量での価値の最大値
    dp = [[0] * (W + 1) for _ in [0] * (N + 1)]
    
    for n in range(N):
        v, w = lst[n]
        for sum_w in range(W + 1):
            res = sum_w - w
            if res >= 0:
                dp[n + 1][sum_w] = max(dp[n + 1][sum_w], dp[n][res] + v)
            dp[n + 1][sum_w] = max(dp[n + 1][sum_w], dp[n][sum_w])
    print(dp[N][W])


main()



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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm(a, b) (a)/__gcd((a),(b))*(b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

vector<int> Div(int n) {
    vector<int> ret;
    for(int i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);

            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) {
        cin >> v[i];

    }

    vector<LL> sum;
    for(int i = 0; i < n - 1; ++i) {
        LL s = v[i];
        sum.pb(s);
        for(int j = i + 1; j < n; ++j) {
            s += v[j];
            sum.pb(s);

        }
    }
    sum.pb(v[n - 1]);
    sort(all(sum), greater<LL>());

    LL res = 0;
    for(int i = 45; i >= 0; --i) {
        int c = 0;
        LL t = res + (1ll << i);
        for(int j = 0; j < sum.size(); ++j) {
            if((t & sum[j]) == t) {
                ++c;

            }
        }
        if(c >= k) {
            res += (1ll << i);

        }
    }
    cout << res << endl;
    return 0;
}



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

#define FOR(i,l,r) for(int i = int(l);i < int(r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N;

int main()
{
	scanf("%d",&N);
	if(N % 10 == 9 || N / 10 == 9){
		puts("Yes");
	}
	else{
		puts("No");
	}

	return 0;
}


Measured memory_bytes: 768
#include<stdio.h>
int c;
char s[100010];
int f(int i){
  c++;
  if(s[i]=='n'){
    if(s[i+5]==0)return 0;
    return f(i+5)*2-90;
  }
  if(s[i+4]==0)return 90;
  return f(i+4)*2+90;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
  int i,a,b;
  while(scanf("%s",s),s[0]-'#'){
    a=f(c=0);
    c--;
    b=gcd(a,1<<c);//printf("%d %d %d\n",a,b,c);
    if((1<<c)==b)printf("%d\n",a/b);
    else         printf("%d/%d\n",a/b,(1<<c)/b);
  }
  return 0;
}
      

Measured memory_bytes: 536
#include<stdio.h>
void sort(int *x,int *y);
int GCD(int x,int y);
int main(void){
    int x,y;
    scanf("%d %d",&x,&y);
    sort(&x,&y);
    printf("%d\n",GCD(x,y));
    return 0;
}
void sort(int *x,int *y){
    if(*x<*y){
        int temp=*x;
        *x=*y;
        *y=temp;
    }
}
int GCD(int x,int y){
    while(x!=y){
        if(x<y)
            y=y-x;
        else
            x=x-y;
    }
    return x;
}

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

const int N=3040; 
string s,f[N],g[N];
int cnt1=0,cnt2=0,n,id1[2*N],id2[2*N],a[N],b[N];

int main(){
	cin>>n>>s;
	for(int i=0;i<2*n;++i){
		id1[i]=cnt1;id2[i]=cnt2;
		if(s[i]=='a')a[cnt1++]=i;
		else b[cnt2++]=i;
	}
	f[n]=g[n]="";
	for(int i=n-1;i>=0;--i){
		g[i]=g[i+1];
		int u=a[i],v=b[i];
		if(u<v)f[i]="ab"+g[id1[v]];
		else{
			int j=i+1;for(;j<n&&b[j]<a[j-1];++j);
			for(int p=i,q=i;p!=j||q!=j;)
				if(p!=j&&(q==j||a[p]<b[q]))f[i]+='a',++p;
				else f[i]+='b',++q;
			f[i]+=g[j];
		}
		g[i]=max(f[i],g[i+1]);
	}
	cout<<g[0]<<endl;
	return 0;
}

Measured memory_bytes: 16256
#include <stdio.h>

int main(void) { 
	int x, y, i, tmp;
	for (i = 0; i < 10000; i++) {
		scanf("%d %d", &x,&y);
		if (x == 0 && y == 0) {
			break;
		}
		if (x > y) {
			tmp = x;
			x = y;
			y = tmp;
		}
		printf("%d %d\n", x, y);
	}
	return 0;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  ll n, m;
  cin >> n >> m;
  ll ans = 0;

  if (n > 2 && m > 2)
    ans = (n - 2) * (m - 2);
  else if (n == 2 || m == 2)
    ans = 0;
  else if (n == 1 && m == 1)
    ans = 1;
  else
    ans = max(n, m) - 2;

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


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**5)

k = int(input())

a = [str(i) for i in range(1,10)]


def lunlun(s):
    a = int(s[-1])
    if a == 0:
        l = [0,1]
    
    elif a == 9:
        l = [8,9]
    
    else:
        l = [a-1,a,a+1]
    
    ret = []
    for i in l:
        ret.append(s+str(i))
        
    return ret

n_2 = []
for i in a:
    temp = lunlun(i)
    for i in temp:
        n_2.append(i)
 
n_3 = []
for i in n_2:
    temp = lunlun(i)
    for i in temp:
        n_3.append(i)

n_4 = []
for i in n_3:
    temp = lunlun(i)
    for i in temp:
        n_4.append(i)

n_5 = []
for i in n_4:
    temp = lunlun(i)
    for i in temp:
        n_5.append(i)

n_6 = []
for i in n_5:
    temp = lunlun(i)
    for i in temp:
        n_6.append(i)

n_7 = []
for i in n_6:
    temp = lunlun(i)
    for i in temp:
        n_7.append(i)

n_8 = []
for i in n_7:
    temp = lunlun(i)
    for i in temp:
        n_8.append(i)

n_9 = []
for i in n_8:
    temp = lunlun(i)
    for i in temp:
        n_9.append(i)

n_10 = []
for i in n_9:
    temp = lunlun(i)
    for i in temp:
        n_10.append(i)


a.extend(n_2)
a.extend(n_3)
a.extend(n_4)
a.extend(n_5)
a.extend(n_6)
a.extend(n_7)
a.extend(n_8)
a.extend(n_9)
a.extend(n_10)

print(str(a[k-1]))


Measured memory_bytes: 18796
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 2147483647;
const ll LLINF = 9223372036854775807;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
	ll n, m, v, p; cin >> n >> m >> v >> p;
	VI a(n); REP(i, n)cin >> a[i];
	sort(ALL(a), greater<ll>());
	int l = p - 1, r = n;
	while (r - l > 1) {
		int x = l + ((r - l) / 2);
		ll h = m * (v - p);
		for(int i = p - 1;i < n ;i++) {
			if (i == x)continue;
			h -= min(m, max(0LL, a[x] + m - a[i]));
		}
		if (h <= 0 && a[x] + m >= a[p - 1])l = x;
		else r = x;
	}
	cout << l + 1 << endl;
	return 0;
}

Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include  <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include <stdlib.h>
#include<stdio.h>
#include <queue>
#include<map>
#include <sstream>
#include<set>
#include<stack>

//#include<bits/stdc++.h>


using namespace std;



int main()
{
   
    long long int a, b;
    cin >> a >> b;
   if (a > b)swap(a, b);
    int x = a, y = b;
    for (int i = 0; i < y; i++)a *= 10, a += x;///cout << a ;
    for (int i = 0; i < x; i++)b *= 10, b += y;
    a /= 10, b /= 10;
    cout <<a<< endl;
    
    return 0;

}


Measured memory_bytes: 256
import copy

N = int(input())

def hoge(arg):
    return [arg[0], int(arg[1])]

A = list(map(hoge, map(str, input().split())))
A1 = copy.deepcopy(A)
A2 = copy.deepcopy(A)

def bsort(C, N):
    for i in range(N):
        for j in range(N-1, i, -1):
            if C[j][1] < C[j-1][1]:
                C[j], C[j-1] = C[j-1], C[j]

def ssort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N, 1):
            if C[j][1] < C[minj][1]:
                minj = j
        C[i], C[minj] = C[minj], C[i]

def judge(A, A1):
    for i in range(len(A) - 1):
        if A1[i][1] != A1[i+1][1]:
            continue
        a = A.index(A1[i])
        b = A.index(A1[i+1])
        if a > b:
            return 'Not stable'
    return 'Stable'

def toString(A):
    return A[0] + str(A[1])

bsort(A1, N)
print(' '.join(list(map(toString, A1))))
print(judge(A, A1))
ssort(A2, N)
print(' '.join(list(map(toString, A2))))
print(judge(A, A2))



Measured memory_bytes: 6344
#include<iostream>
#include<string>
using namespace std;
int main(){
  string a,b;
  cin >> a >> b;
  int c = a.size();
  int flag = 0;
  for(int i = 0;i < c;i++){
    if(a[i] != b[i]){
      flag += 1;
    }
  }
  if(flag == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3544
from typing import List
N = int(input())
AC = 0
WA = 0
TLE = 0
RE = 0
for i in range(N):
    x = input()
    if(x=='AC'):
        AC += 1
    elif(x=='WA'):
        WA += 1
    elif(x=='TLE'):
        TLE += 1
    else:
        RE += 1

print('AC', 'x', AC)
print('WA', 'x', WA)
print('TLE', 'x', TLE)
print('RE', 'x', RE)

Measured memory_bytes: 10284
#include<iostream>
#include<string>
#include<algorithm>

using namespace  std;
 int main(){
    int a,b,c,k,ans=0;
    cin >> a >> b >> c >> k;
    if(a >= k) ans = k;
    else{
        ans = a;
        k = k-a;
        if(b >= k) ans = ans;
        else{
            k = k-b;
            ans += -1*k;
        }
    }
    cout << ans << endl;
    return 0;
 }

Measured memory_bytes: 3512
using System;
using System.Linq;
namespace ABC156
{
    class A
    {
        static void Main(string[] args)
        {
            long[] input = Console.ReadLine().Split().Select(long.Parse).ToArray();
            //long[] input = Console.ReadLine().ToArray();
            long N = input[0];
            long R = input[1];

            if (10 <= N) Console.WriteLine(R);
            else { Console.WriteLine(R + 100 * (10 - N)); }

        }
    }
}


Measured memory_bytes: 13268
from collections import Counter

n = int(input())
v = list(map(int, input().split()))
v1 = Counter(v[::2]).most_common()
v2 = Counter(v[1::2]).most_common()
v1.append((0, 0))
v2.append((0, 0))
if v1[0][0] != v2[0][0]:
    print(n - v1[0][1] - v2[0][1])
else:
    print(min(n - v1[0][1] - v2[1][1], n - v1[1][1] - v2[0][1]))

Measured memory_bytes: 20700
#include<iostream>
#include<algorithm>

using namespace std;

int main(){

	long long N;

	cin >>N;

	long long A[110][2],res=0,temp=0;
		bool flag=0;


	for(int j=0; j<2; j++){
		for(int i=0; i<N; i++){

			cin >> A[i][j];

		}

	}

	res=-999999;

	for(int k=0; k<N; k++){
		flag=0;
	
		for(int i=0; i<N; i++){

			if(k == i && flag==0){

				temp += A[i][0];
				temp += A[i][1];
				flag=1;

			}

			else if(flag ==0)temp += A[i][0];

			else temp += A[i][1];

			//cout <<i <<" " <<k <<" "<<temp<< " "<<flag <<endl;

		}

		

		res =max(res,temp);
		
		temp=0;

	}
	cout <<res <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

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

    int h, w;
    string s[2010];

    cin >> h >> w;
    REP(i, h)
    cin >> s[i];

    int hm[2010][2010], wm[2010][2010];

    memset(hm, 0, sizeof(hm));
    memset(wm, 0, sizeof(wm));

    REP(j, w)
    {
        int cnt = 0;
        REP(i, h)
        {
            if (s[i][j] == '#')
            {
                cnt = 0;
                continue;
            }
            cnt++;
            hm[i][j] = cnt;
        }

        for (int i = h - 1; i >= 0; i--)
        {
            if (hm[i][j])
                hm[i][j] = max(hm[i][j], hm[i + 1][j]);
        }
    }

    REP(i, h)
    {
        int cnt = 0;
        REP(j, w)
        {
            if (s[i][j] == '#')
            {
                cnt = 0;
                continue;
            }
            cnt++;
            wm[i][j] = cnt;
        }

        for (int j = w - 1; j >= 0; j--)
        {
            if (wm[i][j])
                wm[i][j] = max(wm[i][j], wm[i][j + 1]);
        }
    }

    int res = 0;
    REP(i, h)
    REP(j, w)
    {
        res = max(res, hm[i][j] + wm[i][j] - 1);
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 36096
n = int(input())
s = []
for i in range(n):
  s.append(int(input()))
s.sort()
sum_score = sum(s)

if sum_score % 10 != 0:
  print(sum_score)
  exit()
for i in range(n):
  max_score = sum_score - s[i]
  if max_score % 10 != 0:
    print(max_score)
    exit()
print(0)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; 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 sz(x) (int)(x).size()
#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 newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;

vector<bool> sieve_of_eratosthenes(int n) {
  vector<bool> is_prime(n + 1, true);
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i * i <= n; ++i)
    if (is_prime[i])
      for (int k = 2 * i; k <= n; k += i)
        is_prime[k] = false;
  return is_prime;
}
  
int main() {
  int X;
  cin >> X;
  vector<bool> res = sieve_of_eratosthenes(200000);
  srep(k,X,200000){
    if(res[k]){
      cout << k << endl;
      return 0;
    }
  }
  return 0;
}

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

int min(int a, int b)
{
    if (a > b){
        return (b);
    }
    
    return (a);
}

int main(void)
{
    char message[3][30] = {"OK", "Cannot pay some amount", "Cannot use greedy algorithm"};
    int t;
    int i, j, k;
    int n, array[50];
    static int dp[10001], greedy[10001];
    char f;
    
    t = 0;
    while (1){
        scanf("%d", &n);
        
        if (n == 0){
            break;
        }
        f = 1;
        for (i = 0; i < n; i++){
            scanf("%d", &array[i]);
            if (array[i] == 1){
                f = 0;
            }
        }
        printf("Case #%d: ", ++t);
        
        if (f){
            printf("%s\n", message[1]);
            continue;
        }
        
        f = 0;
        
        memset(dp, 0, sizeof(dp));
        for (i = 0; i < n; i++){
            for (j = 0; j + array[i] <= 10000; j++){
                if (dp[j + array[i]] == 0){
                    dp[j + array[i]] = dp[j] + 1;
                }
                else {
                    dp[j + array[i]] = min(dp[j] + 1, dp[j + array[i]]);
                }
            }
        }
        memset(greedy, 0, sizeof(greedy));
        for (i = 0; i <= 10000; i++){
            k = i;
            for (j = n - 1; j >= 0; j--){
                greedy[i] += (k / array[j]);
                k -= array[j] * (k / array[j]);
            }
        }
        for (i = 0; i <= 10000; i++){
            if (dp[i] != greedy[i]){
                f = 1;
                break;
            }
        }
        if (f){
            printf("%s\n", message[2]);
        }
        else {
            printf("%s\n", message[0]);
        }
    }
    
    return (0);
}

Measured memory_bytes: 488
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
#define rep(i,n) for(int i=0; i<((int)n); i++)
#define REP(i,n) for(int i=0; i<=((int)n); i++)
#define srep(i,a,n) for(int i=a; i<((int)n); i++)
#define SREP(i,a,n) for(int i=a; i<=((int)n); i++)
#define rrep(i,n) for(int i=n-1; i>=0; i--)
#define RREP(i,n) for(int i=n; i>=0; i--)
#define INF 1000000000
const int mod = INF+7;

int binary(vector<int> array, int N, int k){
  int lb=-1;
  int ub=N;
  //arrayは降順。k未満で一番左を返す。
  while(ub-lb>1){
    int mid=(ub+lb)/2;
    if(k>array[mid]){
      ub=mid;
    }
    else{
      lb=mid;
    }
  }
  return ub;
}

int main(){
  // string temp="vnaeio";
  // temp.erase(temp.begin());
  // cout << temp << endl;

  int N;
  string S;
  cin >> N;
  cin >> S;
  int ans=0;
  int lenl=0;
  int lenu=N;

  while(lenu-lenl>1){
    int len=(lenl+lenu)/2;
    map<string, int> mp;
    string temp="";
    bool flag=false;
    rep(j,len){
      temp+=S[j];
    }
    mp[temp]=1;
    srep(j,1,N-len+1){
      temp.erase(temp.begin());
      temp.push_back(S[j+len-1]);
      if(mp[temp]==0){
        mp[temp]=j+1;
      }
      else if(mp[temp]!=0 && mp[temp]+len<=j+1){
        flag=true;
        break;
      }
    }
    if(flag==true){
      lenl=len;
    }
    else if(flag==false){
      lenu=len;
    }
  }

  printf("%d\n", lenl);

}


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

bool f[201010];
int num[201010];

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

    ll ac = 0, wa = 0;
    rep(i, M) {
        int p;
        string s;
        cin >> p >> s;
        if (!f[p]) {
            if (s == "AC") {
                ac++;
                f[p] = true;
                wa += num[p];
            }
            else {
                num[p]++;
            }
        }
    }

    cout << ac << " " << wa << endl;
    return 0;
}


Measured memory_bytes: 768
package main

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

const (
	defaultBufferSize = 1024
	maxBufferSize     = 1e6
	Mod               = 1e9 + 7
)

var sc = bufio.NewScanner(os.Stdin)

// sc.Buffer(make([]byte, defaultBufferSize), maxBufferSize)

func readInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func readString() string {
	sc.Scan()
	return sc.Text()
}

func readInt64() int64 {
	sc.Scan()
	i, err := strconv.ParseInt(sc.Text(), 10, 64)
	if err != nil {
		panic(err)
	}
	return int64(i)
}

func readfloat64() float64 {
	sc.Scan()
	f, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}
	return f
}

func abs(a int) int {
	if a < 0 {
		return a * -1
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func gcd(x, y int) int {
	if y == 0 {
		return x
	}
	return gcd(y, x%y)
}

func ModComb(n, k int) int {
	if k == 0 {
		return 1
	}
	x, y := n, k
	for i := 1; i < k; i++ {
		x = x * (n - i) % Mod
		y = y * (k - i) % Mod
	}
	inv := ModInv(y)
	return x * inv % Mod
}

func ModFact(x int) int {
	fact := 1
	for i := 1; i <= x; i++ {
		fact = fact * i % Mod
	}
	return fact
}

func ModInv(x int) int {
	return ModPow(x, Mod-2)
}

func ModPow(a, n int) int {
	res := 1
	for n > 0 {
		if n%2 != 0 {
			res = res * a % Mod
		}
		a = a * a % Mod
		n /= 2
	}
	return res
}

func pow(a, n int) int {
	if n == 0 {
		return 1
	}

	ans := 0
	if n%2 == 0 {
		ans = pow(a*a, n/2)
	} else {
		ans = a * pow(a*a, (n-1)/2)
	}
	return ans
}

func intSliceReverse(slice []int) []int {
	for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
		slice[i], slice[j] = slice[j], slice[i]
	}
	return slice
}

func stringReverse(str string) string {
	runes := []rune(str)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func primeFactorization(x int) map[int]int {
	result := make(map[int]int, 0)
	for i := 2; i*i <= x; i++ {
		for x%i == 0 {
			result[i]++
			x /= i
		}
	}
	if x != 1 {
		result[x]++
	}
	return result
}

func isPrime(x int) bool {
	if x == 1 {
		return false
	}
	for i := 2; i*i <= x; i++ {
		if i == x {
			continue
		}
		if x%i == 0 {
			return false
		}
	}
	return true
}

func main() {
	sc.Split(bufio.ScanWords)
	n := readInt()

	ans := ""
	for n > 0 {
		n -= 1
		ans += string('a' + n%26)
		n /= 26
	}
	fmt.Println(stringReverse(ans))
}


Measured memory_bytes: 1776
#include <stdio.h>


int main(void)
{

    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
      if(a<=b && b<=c){
         printf("%d %d %d\n",a,b,c);
      } else if (a<=c && c<=b){
         printf("%d %d %d\n",a,c,b);
      } else if (b<=a && a<=c){
         printf("%d %d %d\n",b,a,c);
      } else if (b<=c && c<=a){
        printf("%d %d %d\n",b,c,a);
      } else if (c<=a && a<=b){
        printf("%d %d %d\n",c,a,b);
      } else if (c<=b && b<=a){
        printf("%d %d %d\n",c,b,a);
      }

    return 0 ;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define lli long long int
#define tc int t;cin>>t;while(t--)
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define pb push_back
#define vi vector<int>
#define vll vector<lli>
#define maxn 505
#define mod 1000000007


int main(){
    fastio;
    int fr[10005]={0};
    for(int i=1;i<=100;i++)
    {
        for(int j=1;j<=100;j++)
        {
            for(int k=1;k<=100;k++)
            {
                lli cur=i*i+j*j+k*k+i*j+j*k+i*k;
                if(cur<=10000)
                fr[cur]++;
            }
        }
    }
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    cout<<fr[i]<<"\n";
    return 0;
}

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

const int64_t MOD = 998244353;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

template<typename T>
struct BIT {
    int n;
    vector<T> dat;

    BIT(int n=0){
        initialize(n);
    }

    void initialize(int nin){
        n = nin;
        dat.resize(n, 0);
    }

    T sum(int i){
        T s = 0;
        while(i >= 0){
            add(s, dat[i]);
            i = (i & (i+1)) - 1;
        }
        return s;
    }

    T sum_between(int i, int j){
        return (MOD + sum(j) - sum(i-1)) % MOD;
    }

    void plus(int i, T x){
        while(i < n){
            add(dat[i], x);
            i |= i+1;
        }
    }
};

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

int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

int main() {
    int N, K, A;
    cin >> N >> K >> A;
    BIT<int64_t> bit(N+K);
    int64_t c = A * inv_mod(100*N) % MOD;
    bit.plus(0, inv_mod(A) * 100 % MOD);
    for(int i=1; i<N+K; i++) bit.plus(i, bit.sum_between(max(0, i-N), min(K-1, i-1)) * c);
    int64_t ans = bit.sum_between(K, N+K-1);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4356
#include <stdio.h>

#define N 2000000

int main(){
	int n;
	scanf("%d",&n);
	int i;
	int A[N];
	for(i=1;i<=n;i++){
		scanf("%d",&A[i]);
	}
	for(i=1;i<=n;i++){
		printf("node %d: key = %d, ",i,A[i]);
		if(i/2>0)printf("parent key = %d, ",A[i/2]);
		if(i*2<=n)printf("left key = %d, ",A[i*2]);
		if(i*2+1<=n)printf("right key = %d, ",A[i*2+1]);
		printf("\n");
	}
	return 0;

}

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

using namespace std;

#define ll long long
#define ull unsigned long long
#define vll vector<ll>
#define pii pair<int, int>
#define vii vector<pii>
#define vs vector<string>
#define vb vector<bool>
#define vi vector<int>
#define vd vector<double>
#define vvi vector< vector<int> >
#define vvii vector< vector< pii > >
#define ld long double
#define mapii map<int, int>
#define mapsi map<string, int>
#define erep(i, x, n) for (auto i = x; i<=(ll)(n); i++)
#define rep(i, x, n) for(auto i = x; i<(ll)(n); i++)
//#define INF  LLONG_MAX
#define all(v) ((v).begin()), ((v).end())
#define sz(v) ((int)((v).size()))
#define pie  acos(-1)
#define mod(n,m) ((n % m + m) % m)
#define eps (1e-8)
#define reset(n, m) memset(n, m, sizeof n)
#define endl '\n'
#define output freopen("output.txt", "w", stdout)
#define mp(x, y, z) {{x, y}, z}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string x, y;
    cin >> x >> y;
    vs vec;
    erep(i, 1, sz(y))
        vec.push_back(y.substr(0, i));
    int mx = 0;
    rep(i, 0, sz(vec))
    {
        int pos = sz(x)-1-i;
        string temp = x.substr(pos, sz(vec[i]));
        if (temp == vec[i]) mx = sz(vec[i]);
    }
    cout << 2*n - mx;


    return 0;
}


Measured memory_bytes: 256
from collections import Counter
S = list(map(int, input()))
P = 2019

def solve(S,P):
    S = S[::-1]
    T = [0] * len(S)
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]
print(solve(S,P))


Measured memory_bytes: 19596
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int ans;
int N;
vector<ll>v;
void dfs(ll n, ll k) {
	if (k > 1e9)return;
	int f[10] = {}, t = n;
	while (t) {
		f[t % 10]++;
		t /= 10;
	}
	if (f[3] && f[5] && f[7])v.push_back(n);
	dfs(n + 3 * k, k * 10);
	dfs(n + 5 * k, k * 10);
	dfs(n + 7 * k, k * 10);
}
int main() {
	ans = 0;
	cin >> N;
	dfs(0, 1);
	sort(v.begin(), v.end());
	ll i = 0;
	for (; i < v.size(); ++i) {
		if (v[i] > N)break;
	}
	cout << i << endl;
	return 0;
}

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

typedef long long ll;

const int N = 2e5 + 5;
int n, q, a, b;
int cnt[N];
vector<int> e[N];
ll res;
void dfs(int x, int par) {
    for (int i : e[x]) {
        if (i == par) continue;
        cnt[i] += cnt[x];
        dfs(i, x);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    for (int i = 0; i < n - 1; ++i) {
        cin >> a >> b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for (int i = 0; i < q; ++i) {
        cin >> a >> b;
        cnt[a] += b;
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i) {
        cout << cnt[i] << ' ';
    }
    cout << endl;

    return 0;
}



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

using namespace std;

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

#define faster ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define read freopen("in.txt", "r", stdin)
#define write freopen("out.txt", "w", stdout)
#define mem(x, n) memset(x, n, sizeof(x))
#define all(x) x.begin(), x.end()
#define endl "\n"

int main() {
	faster;

	string s;
	cin >> s;
	int cnt = 0, curr = 0;
	for (int i = 0; i < 3; i++) {
		if (s[i] == 'R') {
			curr++;
		} else {
			curr = 0;
		}
		cnt = max(cnt, curr);
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 3608
def main():
    n=int(input())
    a=[0]*(n+1)
    ans=1
    for i in range(1,n+1):
        num=i
        for j in range(2,i+1):
            if num%j==0:
                while num>1 and num%j==0:
                    num//=j
                    a[j]+=1

    for i in a:
        ans=ans*(i+1)%(10**9+7)
    print(ans)
    return

main()

Measured memory_bytes: 39920