akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 100010
typedef long long ll;
const int mx=100000;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,qwq,w[N<<2],v[N<<2],Q,lim;
ll dp[1025][N];
void dfs(int u,int dep){
	if(u>n) return ;
	if(dep>qwq/2)return;
	lim=max(lim,u);
	for(int i=mx;i>=w[u];--i){
		dp[u][i]=max(dp[u>>1][i],dp[u>>1][i-w[u]]+v[u]);
	}
	for(int i=w[u]-1;i>=0;--i){
		dp[u][i]=dp[u>>1][i];
	}
	dfs(u<<1,dep+1);
	dfs(u<<1|1,dep+1);
	for(int i=1;i<=mx;++i){
		dp[u][i]=max(dp[u][i],dp[u][i-1]);
	}
}
int main(){
	n=read();
	for(int i=1;i<=n;++i){
		v[i]=read(),w[i]=read();
	}
	qwq=0;
	while((1<<qwq)<=n)qwq++;
	dfs(1,1);
	Q=read();
	while(Q--){
		int u=read(),L=read();
		if(u<=lim){
			printf("%lld\n",dp[u][L]);
			continue;
		}
		static int p[233],tot=0;
		tot=0;
		while(u>lim){
			p[++tot]=u;
			u>>=1;
		}
		ll ans=0;
		for(int i=0;i<(1<<tot);++i){
			ll d=0,sum=0;
			for(int j=1;j<=tot;++j){
				if((i>>(j-1))&1){
					d+=w[p[j]],sum+=v[p[j]];
				}
			}
			if(d>L)continue;
			ans=max(ans,dp[u][L-d]+sum);
		}
		printf("%lld\n",ans);
	}
	return 0;
}


Measured memory_bytes: 405064
n,k = map(int, input().split())
p = list(map(int, input().split()))
ep = [(i+1)/2 for i in p]
now = sum(ep[:k])
result = now
for i in range(n-k):
    now = now-ep[i]+ep[i+k]
    result = max(now, result)
print(result)

Measured memory_bytes: 25060
#include<bits/stdc++.h>
using namespace std;
int main(){
string S;
  cin>>S;
  
  int A=0;
  int B=0;
  int C=0;

  for(int i=0;i<S.size();i++){
    if(S.at(i)=='a'){
      A++;
    }
        else if(S.at(i)=='b'){
          B++;
          }
          else if(S.at(i)=='c'){
            C++;
          }
  }
  
  if(A==1&&B==1&C==1){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
    }
    }
    
    
  
   
    


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#define repp(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define repm(i,a,b) for(int i=(int)a;i>(int)b;--i)
using ll=long long;
static const ll mod=1e9+7;
static const ll INF=1LL<<50;
using namespace std;

int main() {
	int n,x;
  	cin>>n>>x;
  	vector<int>v(n);
  	repp(i,0,n)cin>>v[i];
  	int sum=0;
  	int i=0;
    for(i=0;i<n;++i){
      sum+=v[i];
      if(sum>x)break;
    }
  cout<<i+1<<endl;
}

Measured memory_bytes: 256
local mfl = math.floor
local mod = 1000000007

local function bmul(x, y)
  local x0, y0 = x % 31623, y % 31623
  local x1, y1 = mfl(x / 31623), mfl(y / 31623)
  return (x1 * y1 * 14122 + (x1 * y0 + x0 * y1) * 31623 + x0 * y0) % mod
end
local function badd(x, y) return (x + y) % mod end

local h, w, k = io.read("*n", "*n", "*n")
if w == 1 then
  print(1)
else
  local t = {1}
  for i = 2, w do t[i] = 0 end
  local tot = 2^(w - 1)
  local map = {}
  for i = 1, w do
    map[i] = {}
    for j = 1, w do
      map[i][j] = 0
    end
  end
  for it = 0, tot - 1 do
    local valid = true
    local flag = {}
    for i = 1, w - 1 do
      flag[i] = it % 2 == 1
      it = mfl(it / 2)
    end
    for i = 1, w - 2 do
      if flag[i] and flag[i + 1] then
        valid = false
      end
    end
    if valid then
      for i = 1, w do
        if i == 1 then
          if flag[1] then
            map[1][2] = map[1][2] + 1
          else
            map[1][1] = map[1][1] + 1
          end
        elseif i == w then
          if flag[w - 1] then
            map[w][w - 1] = map[w][w - 1] + 1
          else
            map[w][w] = map[w][w] + 1
          end
        else
          if flag[i] then
            map[i][i + 1] = map[i][i + 1] + 1
          elseif flag[i - 1] then
            map[i][i - 1] = map[i][i - 1] + 1
          else
            map[i][i] = map[i][i] + 1
          end
        end
      end
    end
  end
  for ih = 1, h do
    local nt = {}
    for i = 1, w do nt[i] = 0 end
    for src = 1, w do
      for dst = 1, w do
        nt[dst] = badd(nt[dst], bmul(t[src], map[src][dst]))
      end
    end
    for i = 1, w do t[i] = nt[i] end
  end
  print(t[k])
end


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(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);
  int X; cin >> X;
  if(X >= 30){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>

using namespace std;
long long n;
int main()
{
 scanf("%I64d",&n);
 long long x=800*n;
 long long y=n/15*200;
 cout<<x-y;
 return 0;
}


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

int main() {
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;

  rep(i, tx-sx) printf("R");
  rep(i, ty-sy) printf("U");
  rep(i, tx-sx) printf("L");
  rep(i, ty-sy+1) printf("D");
  rep(i, tx-sx+1) printf("R");
  rep(i, ty-sy+1) printf("U");
  printf("L");
  printf("U");
  rep(i, tx-sx+1) printf("L");
  rep(i, ty-sy+1) printf("D");
  printf("R");
  printf("\n");
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back



int main(){
    int n,t,a;
    cin >> n >> t >> a;
    int h[n];
    for(int i=0;i<n;i++){
        cin >> h[i];
    }

    int position=0;
    double min;

    for(int i=0;i<n;i++){
        double b=h[i]*0.006;
        double x=t-b;
        double s=abs(a-x);
        if(i==0){
            min=s;
            position=1;
        }
        if(s<min){
            position=i+1;
            min=s;
        }
    }
    cout << position << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <cstdlib>
#define N 2000005
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,m;
ll f[N],inv[N];
ll C(int n,int m){
	return f[n]*inv[m]%mod*inv[n-m]%mod;
}
ll solve(int n,int m){
	ll ans=0;
	for(int i=m&1;i<=m&&i<=n;i+=2){
		ll w=C(n,i);
		int res=m*3-i>>1;
		ans=(ans+w*C(res+n-1,n-1))%mod;
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	f[0]=f[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=2000002;i++) f[i]=f[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<=2000002;i++) inv[i]=inv[i-1]*inv[i]%mod;
	ll ans=(solve(n,m)-C(n+m-2,n-1)*n)%mod;
	ans=(ans+mod)%mod;
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 31488
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]

ab.sort()

i=0
ans = 0
while m>0:
    if ab[i][1]>m:
        ans += m*ab[i][0]
        break
    else:
        ans += ab[i][1]*ab[i][0]
        m-=ab[i][1]
        i+=1

print(ans)



Measured memory_bytes: 60760
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <queue>
#include <sstream>
#include <unordered_map>
#include <cstring>
#include <iomanip>

using namespace std;

typedef long long ll;

const ll INF=1e9+7;

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

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

int main(){
    int A,B,C,D;
    cin>>A>>B>>C>>D;
    int AB=A+B,CD=C+D;
    if(AB>CD)cout<<"Left"<<endl;
    else if(AB<CD) cout<<"Right"<<endl;
    else cout<<"Balanced"<<endl;
    return 0;
}

//a=97,z=122

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
const int INF = +100100100;
typedef pair<int,int> P;

#define MAX 100005
#define NIL -1
// 左子右兄弟表現
struct Node{
    int p,l,r;
};

Node T[MAX];
int D[MAX];

int getDepth(int u){
    int d = 0;
    while(T[u].p!=NIL){
        ++d;
        u = T[u].p;
    }
    return d;
}

// あるnodeの性質を書く
void setDepth(int u, int d){
    D[u]=d;
    // uの子がいる
    if(T[u].l!=NIL){
        setDepth(T[u].l,d+1);
    }
    // uの兄弟がいる
    if(T[u].r!=NIL){
        setDepth(T[u].r,d);
    }    
}

void printChildren(int u){
    vector<int> rel;
    if(T[u].l!=NIL){
        int x = T[u].l;
        while(x!=NIL){
            rel.push_back(x);
            x=T[x].r;
        }
    }
    cout << "node " << u<<":";
    cout << " parent = " << T[u].p << ", ";
    cout << "depth = " << D[u] << ", ";
    if(T[u].p==NIL){
        cout << "root,";
    }else if(T[u].l==NIL)cout << "leaf,";
    else{
        cout << "internal node,";
    }
    cout << " [";
    rep(i,rel.size()){
        if(rel.size()>1){
            if(i==0){
                cout<<rel[i];
            }else cout << ", "<<rel[i];
        }else{
            cout << rel[i];
        }
        
    }
    cout << "]"<<endl;;
    return;
}

int main(){
    int n,d,v,c,l,r;
    cin >> n;
    // 配列の初期化
    rep(i,n)T[i].l=T[i].r=T[i].p=NIL;

    rep(i,n){
        cin >> v >> d;
        // d個の子ができる
        rep(j,d){
            cin >> c;
            // vの子の一番目の場合
            if(j==0){
                T[v].l = c;
            }//二番目以降の場合
            else{
                T[l].r=c;
            }
            l=c;
            T[c].p = v;
        }
    }
    // 0番目が必ずしも根ではないので、根を探す
    int parent;
    rep(i,n){
        if(T[i].p==NIL)parent=i;
    }
    setDepth(parent,0);
    rep(i,n)printChildren(i);
    return 0;
}


Measured memory_bytes: 4988
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
Q,H,S,D = LI()
N = I()
min_1 = min(Q*4,H*2,S)
if 2*min_1<=D:
    ans = min_1*N
else:
    ans = N//2*D+(min_1 if N%2==1 else 0)
print(ans)


Measured memory_bytes: 3060
#!/usr/bin/env python3
n,a,b = map(int,input().split())
s = input()
cnt = 0
cnt_foreign = 0
for i in range(n):
    if s[i] == "a":
        if cnt < a+b:
            print("Yes")
            cnt += 1
        else: 
            print("No")
    elif s[i] == "b":
        if cnt < a+b and cnt_foreign < b:
            print("Yes")
            cnt += 1
            cnt_foreign += 1
        else: print("No")
    else: print("No")

       

Measured memory_bytes: 53080
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()

def lcm(N, M):
    return N * M // gcd(N, M)

L = lcm(N, M)
n = L // N
m = L // M
C = n * m

# print(N, M, L, n, m, S, T)

ans = True
for i in range(0, L, C):
    s = S[i // n]
    t = T[i // m]
    if s != t:
        ans = False
        break

if ans:
    print(L)
else:
    print(-1)


Measured memory_bytes: 65260
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		int A = int.Parse(Console.ReadLine());
		int B = int.Parse(Console.ReadLine());
		long ans = (N-A+1)*(N-B+1);
		Console.WriteLine(ans);
	}
}

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

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

	int h[100];

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

	int num = 1;
	for (int i = 1; i < n;i++) {

		int flag = 0;
		for (int j = 0; j < i;j++) {
			if (h[j] > h[i]) {
				flag = 1;
				break;
			}
		}

		if (flag == 0) {
			num++;
		}
	}

	cout << num;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
struct circ{
  vector<int> chil;
  int useless;
  bool done;
};
void Init();
void Tree();
int Solve();
circ BO[50];
double P[50][3];
char dp[(1<<24)];
vector< vector<int> > color(4);
int n;
int main(){
  while(cin >>n,n){
    Init();
    for(int i=0,c; i<n; i++){
      cin >>P[i][0]>>P[i][1]>>P[i][2]>>c;
      color[c-1].push_back(i);
    }
    Tree();
    cout <<Solve()<<endl;
  }
  return 0;
}
void Init(){
  for(int i=0; i<4; i++) color[i].clear();
  for(int i=0; i<(1<<24); i++) dp[i] = -1;
  for(int i=0; i<50; i++){
    BO[i].done = false;
    BO[i].useless = 0;
    BO[i].chil.clear();
    P[i][0] = P[i][1] = P[i][2] = 0;
  }
}
void Tree(){
  for(int i=0; i<n; i++){
    for(int j=i+1; j<n; j++){
      double dx = P[i][0]-P[j][0];
      double dy = P[i][1]-P[j][1];
      double rr = P[i][2]+P[j][2];
      if(dx*dx+dy*dy<rr*rr){
    BO[i].chil.push_back(j);
    BO[j].useless++;
      }
    }
  }
}
int Solve(){
  int ans = 0,A=0;
  for(int i=0; i<n; i++) if(BO[i].done) A|=(1<<i);
  if(dp[A] != -1) return (int)dp[A];
  for(int i=0; i<4; i++){
    for(int ii=0; ii<color[i].size(); ii++){
      for(int jj=ii+1; jj<color[i].size(); jj++){
    int a = color[i][ii];
    int b = color[i][jj];
    if(BO[a].useless || BO[b].useless) continue;
    if(BO[a].done || BO[b].done) continue;
    BO[a].done = BO[b].done = true;
    for(int j=0; j<BO[a].chil.size(); j++) BO[BO[a].chil[j]].useless--;
    for(int j=0; j<BO[b].chil.size(); j++) BO[BO[b].chil[j]].useless--;
    int ANS = Solve()+2;
    if(ans<ANS) ans = ANS;
    BO[a].done = BO[b].done = false;
    for(int j=0; j<BO[a].chil.size(); j++) BO[BO[a].chil[j]].useless++;
    for(int j=0; j<BO[b].chil.size(); j++) BO[BO[b].chil[j]].useless++;
      }
    }
  }
  dp[A] = (char)ans;
  return ans;
}

Measured memory_bytes: 17640
n = int(input())
if n <= 9:
  print(n)
elif n <= 99:
  print(9)
elif n <= 999:
  print(9+n-100+1)
elif n <= 9999:
  print(909)
elif n <= 99999:
  print(909+n-10000+1)
else:
  print(90909)

Measured memory_bytes: 2940
import java.util.*;
    public class Main{
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
          
            int a = n%1000;
          	int b = 0;
          	if(a!=0){
              b= 1000 -a;
            }
            System.out.println(b);
        }
    } 

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

int main(){
	int n,x;	cin >> n >>x;
	int l[n+1];
	for(int i=1;i<=n;i++)	cin >> l[i];
	int d[n+2];	d[1]=0;
	for(int i=2;i<=n+1;i++)	d[i]=d[i-1]+l[i-1];
	for(int i=1;i<=n+1;i++){
		if(x>=d[n+1]){
			cout << n+1 <<endl;	break;
		}
		if( x <d[i]){
			cout<<i-1 <<endl;	break;
		}
		else if(x==d[i]){
			cout <<i<<endl;	break;
		}
	}
	return 0;
}

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

void swap(int a[],int i,int j){
	int t=a[i];
	a[i]=a[j];
	a[j]=t;
}

void sort(int a[],int size){
	bool flag=true;
	while(flag){
		flag=false;
		for(int i=0;i<size-1;i++){
			if(a[i]<a[i+1]){
				swap(a,i,i+1);
				flag=true;
			}
		}
	}
}

int main(){
	int N;
	cin >> N;
	int a[N];
	for(int i=0;i<N;i++){
		cin >> a[i];
	}
	
	sort(a,N);
	int ans=0,k=1;
	for(int i=0;i<N;i++){
		ans+=k*a[i];
		k*=-1;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main() {
	int n,cnt=0;
	char s[11], ring[22],ss[11];
	fscanf(stdin, "%s", ss);
	fscanf(stdin, "%d", &n),getchar();
	while (n--) {
		memset(s, '\0', sizeof(s));
		memset(ring, '\0', sizeof(ring));
		fscanf(stdin, "%s", s);
		sprintf(ring, "%s%s", s, s);
		if (strstr(ring, ss) != NULL) cnt++;
	}
	fprintf(stdout, "%d\n", cnt);
	return 0;
}

Measured memory_bytes: 624
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

namespace MyMod {
  typedef long long ll;
  constexpr ll mod = 1e9+7;
  constexpr ll premax = 200020; std::array<ll, premax> f, rf; bool flag = false;

  ll power (ll e, ll x){
    if (x == 0) return 1LL; if (x % 2 != 0) return ((power(e, x-1) * e) % mod);
    ll temp = power(e, x / 2); return (temp * temp) % mod;
  }
  ll add ( ll a, ll b ) { return ((a%mod) + (b%mod))%mod; }
  ll sub ( ll a, ll b ) { return ( a%mod + mod - b%mod)%mod; }
  ll mul ( ll a, ll b ) { return ((a%mod) * (b%mod)) % mod; }
  ll div ( ll a, ll b ) { return ((a%mod) * power(b,mod-2)) % mod; }
  ll nCk (int n, int k) {
    if ( !flag ) {
      f[0] = 1; for(int i=1; i<premax; i++) f[i] = mul(f[i - 1],i);
      rf[premax-1] = power(f[premax-1], mod-2); for(int i=premax-2; i>=0; i--) rf[i] = mul(rf[i + 1], (i + 1));
      flag = true;
    }
    return mul(f[n], mul(rf[n-k], rf[k]));
  }
};

int main (void) {

  long long N, K; std::cin >> N >> K;

  // N-K i+1
  for(int i=1; i<=K; i++) {
    if ( i > N-K+1   ) std::cout << 0 << std::endl;
    else std::cout << MyMod::mul ( MyMod::nCk(N-K+1, i), MyMod::nCk(K-1, i-1)) << std::endl;
  }

  return 0;
}

Measured memory_bytes: 3328
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn adding(carry1: i64, residual1: i64, carry2: i64, residual2: i64) -> (i64, i64) {
    let added = residual1 + residual2;
    assert!(residual1 < 10);
    assert!(residual2 < 10);
    if added >= 10 {
        (carry1 + carry2 + 1, added % 10 + added / 10)
    } else {
        (carry1 + carry2, added)
    }
}

fn dfs(c: i64, d: i64) -> (i64, i64) {
    // (carried, residual)
    if c == 1 {
        return (0, d);
    }
    if c == 0 {
        return (0, 0);
    }
    let ans1 = dfs(c / 2, d);
    let ans1 = adding(ans1.0, ans1.1, ans1.0, ans1.1);
    let ans2 = dfs(c - 2 * (c / 2), d);
    adding(ans1.0, ans1.1, ans2.0, ans2.1)
}

fn main() {
    let n = read::<usize>();
    let mut d = vec![0i64; n];
    let mut c = vec![0i64; n];
    for i in 0..n {
        let v = read_vec::<i64>();
        d[i] = v[0];
        c[i] = v[1];
    }

    let mut ans = (0, 0);
    for i in 0..n {
        let temp = dfs(c[i], d[i]);
        ans = adding(ans.0, ans.1, temp.0, temp.1);
    }
    let ans = ans.0 + c.iter().sum::<i64>() - 1;
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 8444
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int check(vector<int>l);
long long int cal(vector<int>l){
	long long int sum=0;
	for(int i=0;i<l.size();i++){
		sum=sum*10;
		sum+=l[l.size()-i-1];
	}
	return sum;
}
int next(int a){
	if (a==0) return 3;
	else return a+2;
}
void pl(vector<int>&l){
	l[0]=next(l[0]);
	for(int i=0;i<l.size()-1;i++){
		if(l[i]==9){
			l[i]=3;
			l[i+1]=next(l[i+1]);
		}
	}
	if (check(l)==1) return;
	else {
		pl(l);
		return;
	}
}
int check(vector<int>l){
	bool a=0,b=0,c=0;
	for(int i=0;i<l.size();i++){
		if (l[i]==3) a=1;
		else if (l[i]==5) b=1;
		else if (l[i]==7) c=1;
	}
	return a*b*c;
}
int main(){
	int n;
	cin>>n;
	int cnt=0;
	vector<int> l(10,0);
	while(cal(l)<=n){
		pl(l);
		cnt++;
	}
	cout<<cnt-1<<endl;
	return 0;
}

Measured memory_bytes: 256
n = gets.to_i
hs = Array.new(n) { |i| gets.chomp.split.map(&:to_i) }
dp = Array.new(n) { Array.new(3){ - Float::INFINITY } }

dp[0] = hs[0]

1.upto(n - 1) do |i|
  0.upto(2) do |k|
    dp[i][k] = [dp[i - 1][k - 1], dp[i - 1][k - 2]].max + hs[i][k]
  end
end

puts dp[n - 1].max

Measured memory_bytes: 42492
n,m = map(int,input().split())
counter = [0] * m

for i in range(n):
    k = list(map(int,input().split()))
    first_k = k.pop(0)
    for j in range(m):
        counter[j] = counter[j] + k.count(j+1)
    k.clear

print(counter.count(n))
    

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define ll long long int
#define INF INT_MAX
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
int main()
{
	chutiyaap;
	ll d,r,x;
	cin>>r>>d>>x;
	ll sum=0;
	for(ll i=0;i<10;i++)
	{
		cout<<(r*x-d)<<endl;
		x=r*x-d;
	}
}


Measured memory_bytes: 256
N, K = map(int, input().split())
MOD = 1000000007

fact = [1]
for i in range(1, N):
  fact.append(fact[-1] * i)

def comb(n, k):
  return (fact[n] // (fact[n - k] * fact[k])) % MOD

def f2(n, k):
  return comb(n + k - 1, k - 1)

def f(n, k):
  if n < k:
    return 0
  if n == 0 and k == 0:
    return 1
  if k < 1:
    return 0
  return f2(n - k, k)

for i in range(1, K + 1):
  blue = f(K, i)
  red = (f(N - K, i - 1) + 2 * f(N - K, i) + f(N - K, i + 1)) % MOD
  ans = blue * red
  print(ans % MOD)

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

B = []
for idx, val in enumerate(A):
    B.append((val, idx+1))
B = sorted(B)


for i in range(len(B)):
    if i < N - 1:
        print(B[i][1], end=" ")
    else:
        print(B[i][1])

Measured memory_bytes: 19252
n = int(input())
a_list = list(map(int, input().split()))

_sum = 0

for e in range(len(a_list)):
    # print('aaa')
    if e != 0 :
        # print('bbb')
        if a_list[e] < a_list[e - 1] :
            # print('ccc')
            _sum = _sum + (a_list[e - 1] - a_list[e])
            a_list[e] = a_list[e] + (a_list[e - 1] - a_list[e])

print(_sum)

Measured memory_bytes: 32112
// include all standard library.
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(int argc, char const *argv[]) {
  int x, y;
  // xが動物の総数, yは足の総数
  cin >> x >> y;

  const int turu = 2;
  const int kame = 4;

  // ありえない時を除く
  if( y % 2 == 1 || x * 2 > y || x * 4 < y) {
      cout << "No" << endl;
      return 0;
  }
  
  // y = a * 2 + (x-a) * 4 (a: 鶴の数, 0<=a<=x)
  for( int a = 0; a <= x; a++) {
      if( a*2 + (x-a) * 4 == y) {
          cout << "Yes" << endl;
          return 0;
      }
  }
      cout << "No" << endl;
  

  return 0;
}

Measured memory_bytes: 3628
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int D_MAX_V=102;
const int D_v_size=102;
struct D_wolf{
	int t,c,r;
	D_wolf(){t=c=r=0;}
	D_wolf(int t1,int c1,int r1){
		t=t1;c=c1;r=r1;
	}
};
vector<D_wolf>D_G[D_MAX_V];
vector<int>D_sub[D_MAX_V];
int D_level[D_MAX_V];
int D_iter[D_MAX_V];

void add_edge(int from,int to,int cap){
	D_G[from].push_back(D_wolf(to,cap,D_G[to].size()));
	D_sub[from].push_back(1);
	D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1));
	D_sub[to].push_back(0);
}
void D_bfs(int s){
	for(int i=0;i<D_v_size;i++)D_level[i]=-1;
	queue<int> Q;
	D_level[s]=0;
	Q.push(s);
	while(Q.size()){
		int v=Q.front();
		Q.pop();
		for(int i=0;i<D_G[v].size();i++){
			if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){
				D_level[D_G[v][i].t]=D_level[v]+1;
				Q.push(D_G[v][i].t);
			}
		}
	}
}
int D_dfs(int v,int t,int f){
	if(v==t)return f;
	for(;D_iter[v]<D_G[v].size();D_iter[v]++){
		int i=D_iter[v];
		if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){
			int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c));
			if(d>0){
				D_G[v][i].c-=d;
				D_G[D_G[v][i].t][D_G[v][i].r].c+=d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
	int flow=0;
	for(;;){
		D_bfs(s);
		if(D_level[t]<0)return flow;
		for(int i=0;i<D_v_size;i++)D_iter[i]=0;
		int f;
		while((f=D_dfs(s,t,99999999))>0){flow+=f;}
	}
	return 0;
}
int g[60][60][60];
int res[60];
char in[1000];
int cur;
int val[60];
pair<int,int>fact(){
	int tmp=0;
	while('0'<=in[cur]&&in[cur]<='9'){
		tmp*=10;tmp+=in[cur]-'0';cur++;
	}
	if(tmp==0)tmp=1;
	if(in[cur]!='x')return make_pair(0,tmp);
	cur++;
	if(in[cur]!='^')return make_pair(1,tmp);
	cur++;
	int t2=0;
	while('0'<=in[cur]&&in[cur]<='9'){
		t2*=10;t2+=in[cur]-'0';cur++;
	}
	return make_pair(t2,tmp);
}
void expr(){
	pair<int,int> tmp=fact();
	val[tmp.first]+=tmp.second;
	while(in[cur]=='+'){
		cur++;
		tmp=fact();
		val[tmp.first]+=tmp.second;
	}
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<60;i++)for(int j=0;j<60;j++)for(int k=0;k<60;k++)
			g[i][j][k]=0;
		for(int i=0;i<b;i++){
			int p,q;
			scanf("%d%d%s",&p,&q,in);
			p--;q--;
			cur=0;
			for(int j=0;j<60;j++)val[j]=0;
			expr();
			for(int j=0;j<60;j++)g[j][p][q]=g[j][q][p]=val[j];
		}
		for(int i=59;i>=0;i--){
			for(int j=0;j<D_MAX_V;j++){
				D_G[j].clear();
				D_sub[j].clear();
				D_level[j]=D_iter[j]=0;
			}
			for(int j=0;j<a;j++)for(int k=0;k<a;k++){
				add_edge(j,k,g[i][j][k]);
			}
			res[i]=max_flow(0,a-1);
			for(int j=0;j<a;j++){
				for(int k=0;k<D_G[j].size();k++){
					if(D_sub[j][k]&&D_G[j][k].c){
						for(int l=i-1;l>=0;l--)g[l][j][D_G[j][k].t]=999999999;
					}
				}
			}
		}
		bool yet=true;
		for(int i=59;i>=0;i--){
			if(res[i]==0)continue;
			if(!yet)printf("+");
			yet=false;
			if(i==0||res[i]>1)printf("%d",res[i]);
			if(i)printf("x");
			if(i>1)printf("^%d",i);
		}
		if(yet)printf("0");
		printf("\n");
	}
}

Measured memory_bytes: 2020
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	int array1[] = new int[n];
        int array2[] = new int[n];
      	int ans = 0;
      	for(int i=0; i<n; i++){
          array1[i] = sc.nextInt();
        }
      	for(int l=0; l<n; l++){
          array2[l] = sc.nextInt();
        }
      	for(int m=0; m<n; m++){
          if(array1[m]>array2[m]){
            ans += array1[m]-array2[m];
          }
        }
      	System.out.println(ans);
    }
}
            

Measured memory_bytes: 22100
n, m = map(int, input().split())
A = []
B = []
for i in range(n):
    A.append(list(map(int, input().split())))
for i in range(m):
    B.append(int(input()))


for i in range(n):
    x = 0
    for j in range(m):
        x += A[i][j] * B[j]
    print(x)


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    string S;
    cin>>S;
    int ans=0;
    int st=0;
    rep(i,S.size()){
        if(S[i]=='T'){
            if(st)st--;
            else ans++;
        }
        else st++;
    }

    cout<<ans+st<<endl;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int alpha(char a);
int toarabic(char roman[]);
void toroman(int arabic);
int main(void) {
    int num,result,i;
    char op1[9],op2[9];
    scanf("%d",&num);
    for (i=0; i<num; i++) {
        result = 0;
        scanf(" %s %s",op1,op2);
        result = toarabic(op1) + toarabic(op2);
        toroman(result);
    }
    return 0;
}

int alpha(char a) {
    switch (a) {
        case 'm':
            return 1000;
        case 'c':
            return 100;
        case 'x':
            return 10;
        case 'i':
            return 1;
    }
}

int toarabic(char roman[]) {
    int i,result=0;
    for (i=0; i<strlen(roman); i++) {
        if (isalpha(roman[i])) {
            result+=alpha(roman[i]);
        } else {
            result+= (roman[i]-'0') * alpha(roman[i+1]);
            i++;
        }
    }
    return result;
}

void toroman(int arabic) {
    if (arabic/1000==1) {
        printf("m");
    } else if (arabic/1000>1) {
        printf("%dm",arabic/1000);
    }
    arabic%=1000;
    
    if (arabic/100==1) {
        printf("c");
    } else if (arabic/100>1) {
        printf("%dc",arabic/100);
    }
    arabic%=100;
    
    if (arabic/10==1) {
        printf("x");
    } else if (arabic/10>1) {
        printf("%dx",arabic/10);
    }
    arabic%=10;
    
    if (arabic/1==1) {
        printf("i");
    } else if (arabic/1>1) {
        printf("%di",arabic/1);
    }
    arabic%=1;
    
    printf("\n");
}

Measured memory_bytes: 612
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		SumOfThreeIntegers solver = new SumOfThreeIntegers();
		solver.readInput();
		solver.solve();
		solver.writeOutput();
	}

	static class SumOfThreeIntegers {
		private int k;
		private int s;
		private Scanner scanner;
		private int output;

		public SumOfThreeIntegers() {
			scanner = new Scanner(System.in);
			output = 0;
		}

		public void readInput() {
			k = scanner.nextInt();
			s = scanner.nextInt();
		}

		public void solve() {
			for(int x=0; x<=k;x++) {
				for(int y=0; y<=k;y++) {
					if(s-x-y <= k && s-x-y>=0) {
						output++;
					}
				}
			}

		}

		public void writeOutput() {
			System.out.print(output);
		}

	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
template<class T> inline bool amax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool amin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> ostream& operator << (ostream &os, const vector<T> &v) { os << "["; for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); it++) { os << (it != v.begin() ? ", " : "") << *it; } os << "]"; return os; }
template<class T> ostream& operator << (ostream &os, const set<T> &s) { os << "["; for (typename set<T>::const_iterator it = s.begin(); it != s.end(); it++) { os << (it != s.begin() ? ", " : "") << *it; } os << "]"; return os; }
template<class Key, class Val> ostream& operator << (ostream &os, const map<Key, Val> &m) { os << "{"; for (typename map<Key, Val>::const_iterator it = m.begin(); it != m.end(); it++) { os << (it != m.begin() ? ", " : "") << it->first << ":" << it->second; } os << "}"; return os; }
template<class T, class S> ostream& operator << (ostream &os, const pair<T, S> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <class T> istream& operator >> (istream &is, vector<T> &v) { for (size_t i = 0; i < v.size(); i++) is >> v[i]; return is; }
template <class Target, class Source> inline Target lexical_cast (const Source &s) { Target t; stringstream ss; ss << s; ss >> t; return t; }

//> v < ^ (clock wise)
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
const int INFI = 1<<28;
const long long int INFL = 1LL<<60;
const double INFD = 1e+300;
const float INFF = 1e+100;
const double EPS = 1e-8;
const long long int MOD = 1000000007;

int solve ();
int main () {
    cout.setf(ios::fixed); cout.precision(10);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

int solve () {
    int T;
    cin >> T;
    while (T--) {
        int table[27];
        table['R'-'A'] = 0;
        table['B'-'A'] = 1;
        table['G'-'A'] = 2;
        vector<pair<int,char>> card(9);
        for (int i = 0; i < 9; i++) {
            cin >> card[i].first;
            card[i].first--;
        }
        for (int i = 0; i < 9; i++) cin >> card[i].second;
        int exist[3][9] = {0};
        for (int i = 0; i < 9; i++) {
            int &a = exist[table[card[i].second-'A']][card[i].first];
            a = (a+1)%3;
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 7; j++) {
                while(exist[i][j] && exist[i][j+1] && exist[i][j+2]) {
                    exist[i][j]--;
                    exist[i][j+1]--;
                    exist[i][j+2]--;
                }
            }
        }
        bool ng = false;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 9; j++) {
                ng |= exist[i][j];
            }
        }
        cout << !ng << endl;
    }
    return 0;
}

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

const long long MAXprime=1000005;
bool bp[MAXprime];
vector<long long> p;
void boolprime()
{
	for (long long i = 0; i < MAXprime; ++i) bp[i]=1;
	bp[0]=0, bp[1]=0;
	for (long long i = 2; i*i < MAXprime; ++i)
	{
		if(bp[i])
		{
			p.push_back(i);
			for (long long j = 2; i*j < MAXprime; ++j) bp[i*j]=0;
		}
	}
	for (long long i = p.at(p.size()-1)+1; i < MAXprime; ++i) if(bp[i]) p.push_back(i);
}

int main(int argc, char const *argv[])
{
	boolprime();
	long long a,b;
	cin>>a>>b;
	int ans=1;
	for (auto v:p)
	{
		if (a%v==0&&b%v==0)
		{
			++ans;
		}
		while (a%v==0)
		{
			a/=v;
		}
		while (b%v==0)
		{
			b/=v;
		}
	}
	if (a>1&&b>1&&(a%b==0||b%a==0))
	{
		++ans;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 2424
#include<bits/stdc++.h>
using namespace std;
int ar[ 200009 ],br[ 200009 ];
int main()
{
    int n,k,i,j,c,c1,c2;
    string s;
    cin>>n>>k>>c;
    c1=c2=c;
    getchar();
    cin>>s;
    for(i = 0,j=n-1 ;i<n ;i++,j-- )
    {
        if(s[i]=='o' && c1>=c)
        {
            ar[i+1]=ar[i]+1;
            c1=0;
        }
        else{
            c1++;
            ar[i+1]=ar[i];
        }

        if(s[j]=='o' && c2>=c)
        {
            br[i+1]=br[i]+1;
            c2=0;
        }
        else{
            c2++;
            br[i+1]=br[i];
        }
    }
    for(i = 1 ;i<=n;i++)
    {
        //cout<<ar[i-1]<<"  "<<br[n-i]<<endl;
        if(ar[i-1]+br[n-i]<k && s[i-1]=='o')
            cout<<i<<endl;
    }

}


Measured memory_bytes: 3332
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var n = ReadInts()[0];
        var vals = ReadInts();
        var result = Coloc(n, vals);


        Console.WriteLine(result ? "Yes" : "No");
    }

    static bool Coloc(int n, int[] vals)
    {
        vals = (int[])vals.Clone();
        Array.Sort(vals, IntDisComparetor.Instance);

        var slimes = new List<int>(vals.Length);
        slimes.Add(vals[0]);
        vals[0] = int.MaxValue;
        for (int slimeNum = 1; slimeNum < vals.Length;)
        {
            var index = 0;
            for (int i = 0; i < slimeNum; i++)
            {
                var item = slimes[i];
                index = Utils.FindFirstIndex(vals, p => p < item, index + 1);
                if (index < 0)
                    return false;

                slimes.Add(vals[index]);
                vals[index] = int.MaxValue;
            }
            slimes.Sort(IntDisComparetor.Instance);
            slimeNum = slimes.Count;
        }
        return true;
    }

    #region Utils
    static int[] ReadInts()
    {
        return Console.ReadLine().Split().Select(int.Parse).ToArray();
    }
    #endregion
}

static class Utils
{
    public static int FindFirstIndex<T>(IList<T> source, Func<T, bool> func, int start)
    {
        for (int i = start; i < source.Count; i++)
        {
            if (func(source[i]))
            {
                var ret = source[i];
                return i;
            }
        }
        return -1;
    }
}

class IntDisComparetor : IComparer<int>
{
    public static IComparer<int> Instance { get; } = new IntDisComparetor();
    private IntDisComparetor()
    {

    }
    public int Compare(int x, int y)
    {
        return Comparer<int>.Default.Compare(y, x);
    }

}


Measured memory_bytes: 41128
n = int(input())
S = [input() for i in range(n)]
m = int(input())
T = [input() for j in range(m)]

ANS = []
for i in range(len(S)):
  p = 0
  q = 0
  for j in range(len(S)):
    if S[i]== S[j]:
      p += 1
  for k in range(len(T)):
    if S[i] == T[k]:
      q += -1
  ANS.append(p+q)

print(max(max(ANS),0))


Measured memory_bytes: 3064
#include <iostream>

using namespace std;

int main(void){
  char a;
  cin>>a;
  if(a=='A') cout << "T" << endl;
  if(a=='T') cout << "A" << endl;
  if(a=='C') cout << "G" << endl;
  if(a=='G') cout << "C" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int INF=999999;
int ans;
int main(){
 long long a,b,c,k[100005],l[10005];
cin>>a>>b>>c;
for(int i=0;i<a;++i){
  cin>>k[i]>>l[i];
if(k[i]>=b&&l[i]>=c)++ans;
}
cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;

/*

*/

ll n;

int main(void){
	cin>>n;
	if(n==7 || n==5||n==3){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
// BEGINNING WITH THE NAME OF ALMIGHTY GOD ALLAH
// AUTHOR:: MOHAMMAD FAISAL
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.flush();
	int a,b,c;
    cin >> a >> b >>c;
    if(a==b)
      cout<<c;
  	if(a==c)
      cout<<b;
    if(b==c)
      cout<<a;

	return 0;
	// BYE BYE 
}


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

using namespace std;
using p=pair<int,int>;
typedef long long ll;
const ll mod = 1000000007;

int main(){
  int n;
  cin >> n;
  int count = 0;
  rep(i,n){
    int d,e;
    cin >> d >> e;
    if(d==e){
      count++;
      if(count==3){
        cout << "Yes"<< endl;
        return 0;
      }
    }
    else{
      count=0;
    }
  }
  cout << "No" << endl;
  
}


Measured memory_bytes: 3620
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
#include <unordered_map>

#define fore(i,a,b) for(int i = a; i < (b); i++)
#define fr(i,a,b) for(int i = a - 1; i >= b; i--)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define N 200005
#define inf 2000000000
#define MOD 1000000007

using namespace std;

typedef long long ll;
typedef pair<int, pair<pair<int,int>, bool>> pr;
typedef pair<pair<int, int>, int> tup;

int sol(int i, int j, string &s1, string &s2, vector<vector<pr>> &dp)
{
	if (i >= s1.size() || j >= s2.size())
	{
		dp[i][j] = { 0, { {-1, -1}, 0 } };
		return 0;
	}
	if (dp[i][j].first != -1)
	{
		return dp[i][j].first;
	}

	if (s1[i] == s2[j])
	{
		int a = sol(i + 1, j + 1, s1, s2, dp);
		dp[i][j] = { a + 1, {{i + 1, j + 1}, 1} };
	}
	else
	{
		int a = sol(i, j + 1, s1, s2, dp);
		int b = sol(i + 1, j, s1, s2, dp);
		if (a >= b)
		{
			dp[i][j] = { a, dp[i][j + 1].second };
		}
		else
			dp[i][j] = { b, dp[i + 1][j].second };
	}
	return dp[i][j].first;
}

inline void solve()
{
	string s1, s2;
	cin >> s1 >> s2;
	vector<vector<pr>> dp(s1.size() + 1, vector<pr>(s2.size() + 1, { -1, {{-1, -1}, 0} }));
	sol(0, 0, s1, s2, dp);
	pair<pair<int, int>, bool> j = dp[0][0].second;
	int  g = dp[0][0].first;
	string res = "";
	while (g != 0)
	{
		if (j.second == 1)
			res += s1[j.first.first - 1];
		g = dp[j.first.first][j.first.second].first;
		j = dp[j.first.first][j.first.second].second;
	}
	cout << res;
}

int main()
{
	fast;
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	solve();
}

Measured memory_bytes: 141696
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

K_list = [0] * N
K_sum = 0

A_sum = 0

for i in range(N):
    A_sum += A[i]

if A_sum <= K:
    print(0)

else:
    left = 0
    right = A[N-1] * F[0]

    while right - left > 1:
        K_sum = 0
        mid = (right + left) // 2
        for i in range(N):
            if A[i] * F[i] > mid:
                K_list[i] = A[i] - mid // F[i]
                K_sum += K_list[i]

        if K_sum > K:
            left = mid
        else:
            right = mid
    print(right)


Measured memory_bytes: 120780
# Date [ 2020-09-19 21:04:27 ]
# Problem [ c.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class PrimeFactorization():
    def __init__(self, num):
        self.num = num
        self.factor_table = [0] * (num + 1)
        self.eratosthenes()

    def eratosthenes(self):
        for i in range(2, self.num + 1):
            if self.factor_table[i] == 0:
                self.factor_table[i] = i
                for j in range(i * i, self.num + 1, i):
                    if self.factor_table[j] == 0:
                        self.factor_table[j] = i
    
    def factorization(self, a):
        now = a
        ret = []
        while now > 1:
            cnt = 0
            prime = self.factor_table[now]
            while now % prime == 0:
                cnt += 1
                now //= prime
            ret.append((prime, cnt))
        return ret
def Main():
    n = read_int()
    prime = PrimeFactorization(n + 10)
    ans = 0

    for c in range(1, n):
        num = n - c
        tmp = prime.factorization(num)
        length = 1
        if not tmp:
            ans += 1
            continue
        for x, y in tmp:
            length *= (y + 1)
        if length == 1:
            ans += 1
        else:
            ans += length
    print(ans)

if __name__ == '__main__':
    Main()

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

#define el '\n'

typedef long long ll;

int n;

ll d;

ll x;

vector<ll> a;

ll tong;

void input()
{
    cin>>n;
    a.push_back(0);
    for (int i=0;i<n;i++)
    {
        cin>>x;a.push_back(x);
    }
    a.push_back(0);
    for (int i=0;i<a.size()-1;i++)
    {
        tong = tong + abs(a[i+1]-a[i]);
    }
    for (int i=1;i<a.size()-1;i++)
    {
        cout<<tong - abs(a[i-1]-a[i]) - abs(a[i+1]-a[i]) + abs(a[i+1]-a[i-1])<<el;
    }
}

int main ()
{
    ios_base::sync_with_stdio(0);
    //freopen("2.inp","r",stdin);
    //freopen("2.out","w",stdout);
    input();
}


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

int main() {
  int K, S;
  cin >> K >> S;
  
  int count = 0;
  for(int x = 0; x <= K; x++) {
    for(int y = 0; y <= K; y++) {
      int z = S - x - y;
        if(z >= 0 && z <= K) {
          count++;
        }
    }
  }
  cout << count << endl;
  
}
  

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N,K=list(map(int,input().split()))
if K%2 == 0:
    A = list(range(K//2,N+1,K))
    B = list(range(K,N+1,K))
else:
    A = list(range(K,N+1,K))
    B = []
print(len(A)**3+len(B)**3)

Measured memory_bytes: 16576
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int main(int argc, char *argv[])
{
    int n;
    cin>>n;
    int sum=0;
    int ma=0;
    while(n--)
    {
        int cost;
        cin>>cost;
        if(cost>ma)ma=cost;
        sum+=cost;
    }
    cout<<sum-ma/2<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main(void){
    string input;
    
    int n;
    getline(cin, input);
    sscanf(input.c_str(), "%d\n", &n);
    
    int *a = new int[n];
    
    getline(cin, input);
    const char *p = input.c_str();
    
    for(int i = 0; i < n; i++){
        sscanf(p, "%d", a + i);
        
        if(i == n - 1) break;
        while(*p != ' ') p++;
        p++;
    }
    
    long int min = a[0];
    long int max = a[0];
    long int sum = 0;
    
    for(int i = 0; i < n; i++){
        if(min > a[i]) min = a[i];
        if(max < a[i]) max = a[i];
        sum += a[i];
    }
    
    delete[] a;
    
    printf("%ld %ld %ld\n", min, max, sum);
    
    return(0);
}



Measured memory_bytes: 3408
#include <vector>
#include <list>
#include <map>
#include <string>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <utility>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll mod = 1000000007;

ll solve(void);

int main(void)
{
	while (solve())
	{
	}
	return 0;
}

ll power(ll n, ll p, ll m = mod) {
	if (n == 0) { return 0; }
	if (p == 0) { return 1; }
	if (p == 1) { return n % m; }
	if (p & 1) {
		ll y = power(n, (p - 1) / 2, m);
		y = (y*y) % m;
		return (n*y) % m;
	}
	else {
		ll y = power(n, p / 2, m);
		y = y * y%m;
		return y;
	}
}

ll inv_fact(ll x)
{
	if (x == 0) { return 1; }
	ll ret = 1;
	for (ll i = 1; i <= x; i++)
	{
		ret = (ret * power(i, mod - 2) % mod);
	}
	return ret;
}

ll fact(ll x)
{
	if (x == 0){ return 1;}
	ll ret = 1;
	for ( ll i = 1; i <= x; i++)
		ret = (ret * i) % mod;
	return ret;
}

ll solve(void)
{
	ll x, y;
	cin >> x >> y;

	ll c = (x + y) / 3;
	ll m = x - c;

	if ( (x + y) % 3 > 0 || m < 0 || c - m < 0) {
		cout << 0 << endl;
		return 0;
	}

	ll ans = (fact(c) * inv_fact(m)) % mod;
	ans = (ans * inv_fact(c-m)) % mod;

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    dead_code
)]
use proconio::input;
//use proconio::marker::Usize1;
// use proconio::marker::Chars;
use std::collections::HashSet;
//use std::cmp::*;

const M: i64 = 1000_000_007i64;
fn main() {
    input! {
        Q:usize,
        lr:[(usize,usize);Q]

    }
    let mut rmax = 0 as usize;
    for &(_, r) in &lr {
        rmax = std::cmp::max(rmax, r);
    }
    let mut sum = vec![0usize; rmax + 1];
    let primes: HashSet<usize> = makePrimes(rmax).into_iter().collect();
    //println!("{:?}", primes);
    let isPrime = |x| primes.contains(&x);
    // 1は素数ではない。
    sum[1] = 0;
    for i in 1..(rmax / 2 + 1) {
        sum[2 * i + 1] = sum[2 * i - 1]
            + if isPrime(2 * i + 1) && isPrime(i + 1) {
                1
            } else {
                0
            };
    }
    for (l, r) in lr {
        if l == 1 {
            println!("{}", sum[r]);
        } else {
            println!("{}", sum[r] - sum[l - 2]);
        }
    }
}
fn makePrimes(x: usize) -> Vec<usize> {
    let mut kouho = (2..x + 1).collect::<Vec<usize>>();
    let mut primes: Vec<usize> = Vec::with_capacity(x);
    while 0 < kouho.len() {
        let a = kouho[0];
        primes.push(a);
        kouho = kouho.into_iter().filter(|x| x % a != 0).collect();
    }
    primes
}


Measured memory_bytes: 6024
#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;
const int N_MAX=1e5*2+1;

signed main(){
  int n;
  cin>>n;
  int ans=0;
  int m=0;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    m=max(a,m);
    ans+=a;
  }
  cout<<ans-m/2<<endl;
}


Measured memory_bytes: 256