akhauriyash/Code-Regression huggingface dataset:
use std::str::FromStr;
use std::io::stdin;

fn main() {
    let n: usize = read();
    let vec: Vec<u64> = read_vec();
    let mut count: u64 = 0;
    for i in 0..n {
        let mut v = vec[i];
        while v % 2 == 0 {
            count += 1;
            v /= 2;
        }
    }
    println!("{}", count);
}

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

fn read_vec<T: FromStr>() -> Vec<T> {
    let mut line = String::new();
    stdin().read_line(&mut line).ok();
    line.trim().split_whitespace()
        .map(|i| i.parse().ok().unwrap()).collect()
}

Measured memory_bytes: 4352
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<set>
using namespace std;

struct init{
	init(){
		cin.tie(0); ios::sync_with_stdio(false);
	}
}________init;
typedef vector<int> E;
typedef vector<E> Graph;
bool dfs2(int v, int p, int d, Graph &G, Graph &uE, Graph &rev, E &uV){
	int N = G.size();
	if (d == N / 2){
		return true;

	}
	else{
		int m = G[v].size();
		for (int i = 0; i < m; i++){
			int to = G[v][i];
			if (uE[v][i] == 0 && uV[to] == 0 && to != p){
				uV[to] = 1;
				uE[v][i] = 1;
				uE[to][rev[v][i]] = 1;
				if (dfs2(to, v, d + 1, G, uE, rev, uV))return true;
				uV[to] = 0;
				uE[v][i] = 0;
				uE[to][rev[v][i]] = 0;
			}
		}
	}
	return false;

}
bool dfs1(int v, int p, int d, Graph &G, Graph &uE, Graph &rev, E &uV, int u){
	int N = G.size();
	if (d == N / 2){
		if (dfs2(u, u, 1, G, uE,rev, uV))return true;
	}
	else{
		int m = G[v].size();
		for (int i = 0; i < m; i++){
			int to = G[v][i];
			if (uE[v][i] == 0 && uV[to] == 0&&to!=p){
				uV[to] = 1;
				uE[v][i] = 1;
				uE[to][rev[v][i]] = 1;
				if(dfs1(to, v, d + 1, G, uE, rev, uV, u))return true;
				uV[to] = 0;
				uE[v][i] = 0;
				uE[to][rev[v][i]] = 0;
			}
		}
	}
	return false;

}
int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	int  N,u,v;
	while (cin >> N >> u >> v) {
		u--, v--;
		Graph G(N),uE(N),rev(N);
		E uV(N, 0);
		for (int i = 0; i < N-1; i++){
			int a, b;
			cin >> a >> b;
			a--, b--;
			G[a].push_back(b);
			G[b].push_back(a);
			uE[a].push_back(0);
			uE[b].push_back(0);
			rev[a].push_back(G[b].size() - 1);
			rev[b].push_back(G[a].size() - 1);
		}
		int leaf = 0;
		for (int i = 0; i < N; i++){
			leaf += (G[i].size() == 1u);
		}
		if (leaf>4||N%2==1){
			cout << "No" << endl;
			continue;
		}
		else{
			uV[u] = 1;
			uV[v] = 1;
			if (dfs1(v, v, 1, G, uE,rev, uV, u))cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
	
	return 0;
}

Measured memory_bytes: 32172
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1LL << 60;
#define REP(i,n) for(ll i=0; i<n; i++)
#define FOR(i,a,n) for(ll i=a; i<n; i++)
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a[4]= {300000,200000,100000,0};
    int x,y;
    cin >> x >> y;

    if(x>3) x= 4;
    if(y>3) y= 4;
    int s=0;
    if(x==1&&y==1) s=400000;
    
    cout << s+a[x-1]+a[y-1] << endl;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] ni = scanner.nextLine().split(" ", 2);
        int n = Integer.parseInt(ni[0]);
        int i = Integer.parseInt(ni[1]);
        System.out.println(n - i + 1);
    }
}


Measured memory_bytes: 21716
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;

typedef long long LL;
class Team{
public:
	LL ac,time,id;
	vector<long long> wa;
	
	Team(int n,int _id){
		ac=time=0;
		id=_id;
		wa.resize(n);
	}
	bool operator< (const Team &t) const{
		if(ac>t.ac) return true;
		else if(ac==t.ac && time<t.time) return true;
		else if(ac==t.ac && time==t.time && id<t.id) return true;
		else return false;
	}

};

using namespace std;
int main(void) {
	int t,p,r;
	while ( cin >> t && t != 0 ) {
		cin>>p>>r;
		
		vector<Team> team;
		for(int i=0;i<t;i++) team.push_back(Team(p,i+1)) ;
		
		for(int i=0;i<r;i++){
			int tid,pid,time;
			string m;
			cin>>tid>>pid>>time>>m;
			tid--; pid--;
			
			if(m[0]=='C'){
				team[tid].ac++;
				team[tid].time+=time+team[tid].wa[pid]*1200;
			}else{
				team[tid].wa[pid]++;
			}
		}
		
		sort(team.begin(),team.end());
		
		for(int i=0;i<t;i++){
			cout<<team[i].id<<" "<<team[i].ac<<" "<<team[i].time<<endl;
		}

	}
	return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reps(i,a,b) for(int i= a; i < b; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int n;
  cin >> n;
  vector<int> vec(n);
  rep(i, n) cin >> vec.at(i);
  int ans = 0;
  rep(i, n-1) {
    if (vec.at(i) == i+1) {
      swap(vec.at(i), vec.at(i+1));
      ans++;
    }
  }
  if (vec.at(n-1) == n) {
    swap(vec.at(n-1), vec.at(n-2));
    ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
using ll = long long;
using P = pair<int,int>;
using PP = pair<int,pair<int,int>>;
using T = tuple<string,int,int>;
const ll INF = 1LL<<60;
const int ny[4] = {-1,1,0,0}, nx[4] = {0,0,-1,1};
int sy,sx,gy,gx;

int main(){
  int n,m; cin >> n >> m;
  vector<P> g(m);
  for(int i = 0; i < m; i++){
    int a,b; cin >> a >> b;
    g[i] = P(b,a);
  }
  sort(g.begin(), g.end());
  
  int left = g[0].first;
  int ans = 1;
  for(int i = 1; i < m; i++){
    if(left <= g[i].second){
      ans++;
      left = g[i].first;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int a,b,c,x,y;
  int result = 0;
  cin >> a >> b >> c >> x >> y;
  
  if(2 * c < a + b) {
    if(c < a && c < b){
    	result += std::max(x,y) * c * 2;
    }else{
      if(x > y){
      	result += 2 * c * y;
      	result += (x-y) * a;
      }else{
     	result += 2 * c * x;
     	result += (y-x) * b;
      }
    }
    
  }else{
  	result = std::min(a * x + y * b, std::max(x,y) * c * 2);
  }
  
  if(x > y){
  result = std::min({a * x + y * b,std::max(x,y) * c * 2,2 * c * y+(x-y)*a});
  }else{
  result = std::min({a * x + y * b,std::max(x,y) * c * 2,2 * c * x+(y-x)*b});
  }
  
  cout << result << endl;
  
  return 0;
}

Measured memory_bytes: 256
//#include<cstdio>
//#include<cassert>
//#include<iostream>
//#include<cstring>
//#include<algorithm>
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define MAX ((int)1e6 + 5)
#define MAXL ((ll)1e18 + 5)
#define MAX_X ((ll)1e5 + 2)
#define pi (2.0*acos(0))
#define M ((int)1e6 + 7)
#define MOD ((int)1e9 + 7)
#define NN ((int)62500 + 7)
#define N ((int)2e5 + 5)
#define eps (0)
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define logn 29
#define endl "\n"
#define mp make_pair
#define BUCK 105
#define LEF (idx<<1)
#define RIG ((idx<<1)|1)
//#define int ll


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;

/*fast io
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/




typedef tree < int,  null_type,  less < int >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;
//typedef tree < pair < int, int >,  null_type,  less < pair < int, int > >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;
/// o_set s;
/// s.order_of_key(k) : Number of items strictly smaller than k .
/// *(s.find_by_order(k)) : K-th element in a set (counting from zero).

int arr[N];


int main()
{
    fastio;
    int n , k;
    cin>>n>>k;
    for(int i = 1 ; i<=n ; i++) cin>>arr[i];
    for(int i = k+1 ; i<=n ; i++){
        if(arr[i]>arr[i-k]) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}


Measured memory_bytes: 4436
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
	string s;
	ll date1,date2;
	cin>>s;
	date1=(s[0]-'0')*10+(s[1]-'0');
	date2=(s[2]-'0')*10+(s[3]-'0');
	if(date1<=12&&date1>=1){
		if(date2<=12&&date2>=1) cout<<"AMBIGUOUS"<<endl;
		else cout<<"MMYY"<<endl;
	}else if(date2<=12&&date2>=1){
		cout<<"YYMM"<<endl;
	}else{
		cout<<"NA"<<endl;
	}
}

Measured memory_bytes: 256
read s
n=${#s}
a=Yes
for i in `seq $[n/2]`;do
 if [ ${s:i-1:1} != ${s:n-i:1} ];then
  a=No
 fi
 if [ ${s:i-1:1} != ${s:n/2-i:1} ];then
  a=No
 fi
done
echo $a

Measured memory_bytes: 540
#include<iostream>
#include<vector>
using namespace std;
int N,M;
string s;
vector<int>G[2<<17];
vector<int>H[4<<17];
int color[4<<17];
bool dfs(int u,int p)
{
	color[u]=1;
	for(int v:H[u])
	{
		if(p==v)continue;
		else if(color[v]==1)return true;
		else if(color[v]==0&&dfs(v,u))return true;
	}
	color[u]=2;
	return false;
}
main()
{
	cin>>N>>M>>s;
	for(int i=0;i<M;i++)
	{
		int a,b;cin>>a>>b;
		a--,b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for(int i=0;i<N;i++)
	{
		for(int v:G[i])
		{
			if(s[i]=='A')
			{
				if(s[v]=='B')H[i*2].push_back(v*2);
				else H[i*2+1].push_back(v*2);
			}
			else
			{
				if(s[v]=='B')H[i*2].push_back(v*2+1);
				else H[i*2+1].push_back(v*2+1);
			}
		}
	}
	for(int i=0;i<N*2;i++)
	{
		if(color[i]==0)
		{
			if(dfs(i,-1))
			{
				cout<<"Yes"<<endl;
				return 0;
			}
		}
	}
	cout<<"No"<<endl;
}

Measured memory_bytes: 40964
import java.util.*;
public class Main {
 
  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();
      long k = sc.nextLong();
      long[] sumA = new long[n];
      int idxA = -1;
      for(int i = 0; i < n; i++) {
        if(i == 0)
          sumA[i] = sc.nextLong();
        else
          sumA[i] = sumA[i-1] + sc.nextLong();
        if(sumA[i] <= k)
          idxA = i;
      }

      int idxB = -1;
      long[] sumB = new long[m];
      for(int i = 0; i < m; i++) {
        if(i == 0)
          sumB[i] = sc.nextLong();
        else
          sumB[i] = sumB[i-1] + sc.nextLong();
        if(sumB[i] <= k)
          idxB = i;
      }

      long max = Math.max(idxA, idxB) + 1;
      int j = 0;
      for(int i = idxA; i >= 0; i--) {
        while(j <= idxB && k - sumA[i] >= sumB[j]) {
          max = Math.max(max, i + 1 + j + 1);
          j++;
        }
      }

      System.out.println(max);
  }
}

Measured memory_bytes: 64304
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
ll MOD = 1e9 + 7;

int main() {
    int a, b, x;
    cin >> a >> b >> x;
    double theta;
    if (2 * x < a * a * b) {
        theta = atan(a * b * b / (2.0 * x)) * 180 / acos(-1);
    } else {
        theta = atan(2.0 * (a * a * b - x) / (a * a * a)) * 180 / acos(-1);
    }
    cout << setprecision(20) << theta << endl;
    return 0;
}

Measured memory_bytes: 3956
parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

div2(x)=div(x,2),mod(x,2)
function pow2(x)
    ret = 0
    while true
        x, rem = div2(x)
        if rem == 1 return(ret) end
        ret += 1
    end
end

function main()
    n = parseInt(readline())
    a = parseMap(split(readline()))

    ans = 0
    for i in 1:n
        ans += pow2(a[i])
    end

    println(ans)
end

main()


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

xx = [(X[i], i) for i in range(N)]
xx.sort()

ans = [0 for i in range(N)]

for i in range(N):
    x, idx = xx[i]
    if i < N // 2:
        ans[idx] = xx[N // 2][0]
    else:
        ans[idx] = xx[N // 2 - 1][0]

for i in range(N):
    print(ans[i])

Measured memory_bytes: 36224
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;

vector<pll> g[51];
ll dist[51][5001];
const ll INF=1000100010001000100;
int n,m,s;
const int x=100,y=5000;
ll C[51],D[51];
void dijkstra(int st){
    priority_queue<pll,vector<pll>,greater<pll> > pq;
    memset(dist,0x3f,sizeof(dist));
    dist[st][s]=0;
    pq.push({dist[st][s]*y+s,st});
    while(!pq.empty()){
        pll pi=pq.top();pq.pop();
        int t=pi.second;
        ll cost=pi.first/y,coin=pi.first%y;
        if(dist[t][coin]<cost) continue;

        ll nxb,nxa,nxv,nxco;
        for(auto it:g[t]){
            nxb=it.first/x,nxa=it.first%x,nxv=it.second;
            if(coin>=nxa&&dist[nxv][coin-nxa]>cost+nxb){
                nxco=coin-nxa;
                dist[nxv][nxco]=(cost+nxb);
                pq.push({dist[nxv][nxco]*y+nxco,nxv});
            }
        }
        nxco=coin+C[t];
        nxco=min(4999ll,nxco);
        if(dist[t][nxco]>cost+D[t]){
            dist[t][nxco]=cost+D[t];
            pq.push({dist[t][nxco]*y+nxco,t});
        }
    }
}
int main(){
    cin>>n>>m>>s;
    s=min(4999,s);
    ll ui,vi,ai,bi;
    rep(i,m){
        cin>>ui>>vi>>ai>>bi;
        --ui,--vi;
        g[ui].pb(bi*x+ai,vi);
        g[vi].pb(bi*x+ai,ui);
    }
    rep(i,n){
        cin>>C[i]>>D[i];
    }
    dijkstra(0);
    FOR(i,1,n){
        ll mn=INF;
        rep(j,5000) mn=min(mn,dist[i][j]);
        cout<<mn<<endl;
    }
    return 0;
}

Measured memory_bytes: 9460
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <cctype>
#include <iostream>
#include <set>
#include <string>
#include <queue>
#include <map>
using namespace std;
int size(string x){
	string::size_type size=x.size();
	return size;
}
#define fu(l,k) for(int i=l;i<k;i++)
#define fd(l,k) for(int i=l;i>k;i--)
#define fi first
#define se second
typedef  vector<string> vs;
typedef  vector<int> vi;
double pi(){
	return M_PI;
}
typedef set<int> set_i;
typedef set<string> set_s;
int INF=1000000;
int main(){
	double n;
	double min=INF,max=0;
	while(cin>>n){
		if(min>=n) min=n;
		if(max<=n) max=n;
	}
	cout<<max-min<<endl;
}

Measured memory_bytes: 1280
A, B, C = map(int, input().split())
 
num5 = 0
num7 = 0
ans = 'NO'
 
for num in [A, B, C]:
  if num == 5:
    num5+=1
  elif num == 7:
    num7+=1
  else:
    break
if num5 ==2 and num7 == 1:
  ans = 'YES'
print(ans)

Measured memory_bytes: 9048
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define ull unsigned long long
#define FI(i,a,n) for(int i=a; i<=n; i++)
#define RFI(i,n,a) for(int i=n; i>=a; i--)
#define FLL(i,a,n) for(ll i=a; i<=n; i++)
#define RFLL(i,n,a) for(ll i=n; i>=a; i--)
#define vi vector<int>
#define vll vector<ll>
#define all(v) v.begin(),v.end()
#define pll pair<ll,ll>
#define pi pair<int, int>
#define GCD(a,b) __gcd(a,b)
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define debug(x) cout << x << endl
#define MOD 1000000007
#define INF LLONG_MAX
#define PI 3.14159265359
using namespace std;


int main()
{
	fastio
  ll a, b, n;
  cin >> a >> b >> n;
  n = min(n, b-1);
  cout << (a*n)/b - a*(n/b);

	return 0;
}




Measured memory_bytes: 3636
n=int(input())

def dfs(s,mx):
  #print("s",s)
  if len(s)==n:
    print(s)
    return
  for i in range(ord("a"),mx+2):
    #print(i)
    #print(s+chr(i))
    dfs(s+chr(i),max(mx,i))

dfs("a",ord("a"))


Measured memory_bytes: 4340
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  MAX = 10**9 + 7
  
  n = int(input())
  lc = [int(input()) for _ in range(n)]
  dp = [0] * (n)
  
  last_is = [-1]*(2*10**5+1)
  dp[0] = 1
  last_is[lc[0]] = 0
  for i,c in enumerate(lc[1:], 1):
    last_i = last_is[c]
    dp[i] = dp[i-1]
    if last_i != -1 and last_i != i-1:
      dp[i] += dp[last_i]
      dp[i] %= MAX
    last_is[c] = i

  print(dp[-1])
  

if __name__=='__main__':
  main()



Measured memory_bytes: 22096
#include<stdio.h>
int main(){
  int x[5],y[5],dx,dy,area;
  scanf("%d %d %d %d",&x[0],&y[0],&x[1],&y[1]);
  dx = x[1] - x[0];
  dy = y[1] - y[0];
  x[2] = x[1] + dy;
  y[2] = y[1] - dx;
  area = x[0]*y[1]+x[1]*y[2]+x[2]*y[0]-x[1]*y[0]-x[2]*y[1]-x[0]*y[2];
  if(area < 0){
    x[2] = x[2] - 2*dy;
    y[2] = y[2] + 2*dx;
  }
  printf("%d %d %d %d\n",x[2],y[2],x[2]-dx,y[2]-dy);
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
 int n,a=0,w=0,t=0,r=0;
  cin>>n;
  string s;
  for(int i=0;i<n;i++){
    
    cin>>s;
    if(s=="AC")a++;
    if(s=="WA")w++;
    if(s=="TLE")t++;
    if(s=="RE") r++;
  }
  cout<<"AC x "<<a<<endl;
   cout<<"WA x "<<w<<endl;
   cout<<"TLE x "<<t<<endl;
   cout<<"RE x "<<r<<endl;
}


Measured memory_bytes: 3628
#include<cstdio>
#include<algorithm>
using namespace std;
int n,x,ans;
int a[102];
int main()
{
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<n;i++)
		if(x-a[i]>=0)
		{
			ans++;
			x-=a[i];
		}
	if(x==a[n])ans++;
	printf("%d",ans);
}

Measured memory_bytes: 128
T = 10**5+1
N, C = map(int, input().split())
h = [[] for _ in range(C)]
for i in range(N):
    s, t, c = map(int, input().split())
    s -= 1
    t -= 1
    c -= 1
    h[c].append([s, t])

v = [0]*T
for i in range(C):
    if len(h[i]) == 0:
        continue
    h[i].sort()
    c = h[i]
    if len(c) > 0:
        f = []
        f.append(c[0])
        for j in range(1, len(c)):
            if f[-1][1] != c[j][0]:
                f.append(c[j])
            else:
                f[-1] = [f[-1][0], c[j][1]]
        for s, t in f:
            v[s] += 1
            v[t+1] -= 1

ans = 0
use = 0
for i in range(T):
    use += v[i]
    ans = max(ans, use)
print(ans)


Measured memory_bytes: 89236
#include <iostream>
using namespace std;
int main(){
	string s;
	getline(cin,s);
	int pos=0;
	while(s.find("apple",pos)!=-1||s.find("peach",pos)!=-1){
		int a = s.find("apple",pos);
		int b = s.find("peach",pos);
		if(a==-1)a=s.length();
		if(b==-1)b=s.length();
		if(a<b) s=s.substr(0,a)+"peach"+s.substr(a+5);
		else s=s.substr(0,b)+"apple"+s.substr(b+5);
		pos=((a<b)?a:b)+5;
	}
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define rep(i,j,k) for(int i=j;i<k;i++)
#define all(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
#define mp make_pair
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
const int  COMMAX = 510000;

long long fac[COMMAX], finv[COMMAX], inv[COMMAX];

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcd(int a,int b){return a*b / gcd(a,b);}
// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < COMMAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

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

struct UnionFind {
  vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
  vector<int> rank;
  int num;
  UnionFind(int N) : par(N) , rank(N) { //最初は全てが根であるとして初期化
    num = N;
    for(int i = 0; i < N; i++){
      par[i] = i;
      rank[i] = 0;
    }
  }

  int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }

  void unite(int x, int y) { // xとyの木を併合
    int rx = root(x); //xの根をrx
    int ry = root(y); //yの根をry
    if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
    if(rank[rx] < rank[ry]){
      par[rx] = ry;  
    }else{
      par[ry] = rx;
      if(rank[rx] == rank[ry])rank[rx]++;
    }
    num--;
  }

  bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
    return root(x) == root(y);
  }
};

const int MS = 2;
const long long mod[] = {999999937LL, 1000000007LL}, base = 9973;
struct rolling_hash {
    int n;
    vector<long long> hs[MS], pw[MS];
    rolling_hash(){}
    rolling_hash(const string &s) {
        n = s.size();
        for (int i = 0; i < MS; i++) {
            hs[i].assign(n+1,0);
            pw[i].assign(n+1,0);
            hs[i][0] = 0;
            pw[i][0] = 1;
            for (int j = 0; j < n; j++) {
                pw[i][j+1] = pw[i][j]*base%mod[i];
                hs[i][j+1] = (hs[i][j]*base+s[j])%mod[i];
            }
        }
    }

    long long hash(int l, int r, int i) { return ((hs[i][r]-hs[i][l]*pw[i][r-l])%mod[i]+mod[i])%mod[i]; }

    bool match(int l1, int r1, int l2, int r2) {
        bool ret = 1;
        for (int i = 0; i < MS; i++) ret &= hash(l1,r1,i)==hash(l2,r2,i);
        return ret;
    }

    bool match(int l, int r, long long h[]) {
        bool ret = 1;
        for (int i = 0; i < MS; i++) ret &= hash(l,r,i)==h[i];
        return ret;
    }
};

int main(){
  int n,k;
  cin >> n >> k;
  int bus = 1;
  int res = 0;
  while(n >= bus){
    bus *= k;
    res++;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#include <string>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<n;++i)
#define mrep(i,n) for(ll i=n;i>=0;--i)
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define pl pair<ll,ll>
#define inf 1001001001001000
#define mod 1000000007
#define pi 3.1415926535
using namespace std;

int main(void){
    ll n;
    cin>>n;
    cout<<n/3<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
#include<random>
#include<ctime>
#include<set>
using namespace std;


const long long int mod=1000000007;
const long long int INF=99999999999999999;

long long int n,m,k,res=0,a[20],x[20][20],y[20][20],memo=0,two[20]={1};
string str;
int main() {
	cout << fixed << setprecision(18);
    for(int i=1;i<18;i++){
        two[i]=2*two[i-1];
    }
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        for(int j=0;j<a[i];j++){
            cin>>x[i][j]>>y[i][j];
            x[i][j]--;
        }
    }
    for(int i=0;i<two[n];i++){
        //cout<<i<<endl;
        for(int j=0;j<n;j++){
            
            if((i & two[j])!=0){
                
                for(int p=0;p<a[j];p++){
                    if((i & two[x[j][p]])!=y[j][p]*two[x[j][p]]){
                        //cout<<"a";
                        goto next;
                    }
                }

            }
            
        }
        memo=0;
        for(int j=0;j<n;j++){
            if((i & two[j])!=0){memo++;}
            //cout<<"bbb";
        }
        res=max(memo,res);
        next:
        i=i;
    }
    cout<<res;
} 


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> vec(N);
    REP(i,N)cin >> vec[i];

    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());

    int A,B=0;
    REP(i,N){
        if(i %2==0)A+=vec.at(i);
        else B+=vec.at(i);
    }
//    cout << B << endl;
    cout << max(A,B)-min(A,B);
    return 0;
    }

Measured memory_bytes: 256
N,K,Q = a = map(int,input().split())
a = list(map(int,input().split()))
inf = 10**10
ans = inf
for i in range(N):
    small = a[i]
    seq = []
    seqq = []
    for j in range(N):
        if a[j] < small:
            seq.append(seqq)
            seqq = []
        else:
            seqq.append(a[j])
    seq.append(seqq)
    aaa = []
    for s in seq:
        if len(s)>=K:
            s.sort()
            aaa += s[:len(s)-K+1]
    if len(aaa)>=Q:
        aaa.sort()
        ans = min(ans,aaa[Q-1]-aaa[0])
print(ans)

Measured memory_bytes: 50652
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <deque>
#include <stack>
#include <iomanip>
#include <cmath>


using namespace std;


typedef long long ll;
typedef long double ld;


const int MAXN = 101;


int N;
string s;


void input() {
  cin >> s;
  N = (int)s.size();
}


void preprocess() {
}


void solve() {
  int a = -1, b = -1;
  for (int i = 1 ; i < N ; i++) {
    if (s[i] == s[i-1]) {
      a = i, b = i+1;
    }
  }
  for (int i = 2 ; i < N ; i++) {
    if (s[i] == s[i-2]) {
      a = i-1, b = i+1;
    }
  }
  cout << a << " " << b << "\n";
}






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

  int T;
//  cin >> T;
  T = 1;

  for (int i = 0 ; i < T ; i++) {
    input();
    preprocess();
    solve();
  }

  return 0;
}


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

int main()
{
    string st;
    cin>>st;
    int ans=0;
    int l=0;
    int r=st.size()-1;
    while(l<=r)
    {
        if(st[l]==st[r])
        {
            l++;
            r--;
            continue;
        }
        if(st[l]=='x')
        {
            l++;
            ans++;
            continue;
        }
        if(st[r]=='x')
        {
            r--;
            ans++;
            continue;
        }
        cout<<"-1"<<endl;
        return 0;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

vector<ll> lbits, rbits;
ll dp[60][2][2][2];

void get_bits(ll n, vector<ll>& out){
    out.clear();
    for(int i = 0; n > 0; ++i){
        out.push_back(n % 2);
        n /= 2;
    }
}

ll calc(ll pos, bool x_gt_l, bool y_lt_r, bool has_top){
    if(pos < 0){
        return 1;
    }
    if(dp[pos][x_gt_l][y_lt_r][has_top] != -1){
        return dp[pos][x_gt_l][y_lt_r][has_top];
    }

    ll ret = 0;

    // x = 0, y = 0
    if((x_gt_l || lbits.at(pos) == 0)){
        ret += calc(pos - 1, x_gt_l, y_lt_r || rbits.at(pos) == 1, has_top);
    }

    // x = 0, y = 1
    if(has_top &&
       (x_gt_l || lbits.at(pos) == 0) &&
       (y_lt_r || rbits.at(pos) == 1)){
        ret += calc(pos - 1, x_gt_l, y_lt_r, has_top);
    }

    // x = 1, y = 1
    if(y_lt_r || rbits.at(pos) == 1){
        ret += calc(pos - 1, x_gt_l || lbits.at(pos) == 0, y_lt_r, true);
    }

    ret %= MOD;

    dp[pos][x_gt_l][y_lt_r][has_top] = ret;
    return ret;
}

int main(){
    ll l, r;
    cin >> l >> r;
    get_bits(l, lbits);
    get_bits(r, rbits);
    lbits.resize(60, 0);
    rbits.resize(60, 0);
    fill(
        &dp[0][0][0][0],
        &dp[0][0][0][0] + sizeof(dp) / sizeof(dp[0][0][0][0]),
        -1
    );
    ll ans = calc(59, 0, 0, 0);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=2e5+5;
const int mod=1e9+7;

int n,m,k,a[N],b[N];
signed main(){
    FastIO;
    cin>>n>>m>>k;
    rep(i,1,n) cin>>a[i];
    rep(i,1,m) cin>>b[i];
    reverse(a+1,a+n+1);
    reverse(b+1,b+m+1);
    int ans=0,curr=0,rem=k,l=n+1,r=m;
    repb(i,n,1){
        if(rem>=a[i]){
            rem-=a[i];
            l=i;
            curr++;
        } else break;
    }
    repb(i,m,1){
        if(rem>=b[i]){
            rem-=b[i];
            r=i-1;
            curr++;
        } else break;
    }
    ans=curr;
    rep(j,l,n){
        rem+=a[j];
        curr--;
        while(r and rem>=b[r]){
            rem-=b[r--];
            curr++;
        }
        ans=max(ans,curr);
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 5212
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.12f\n", x);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;
using P = pair<int, int>;


int main() {
	int a, b, k;
	cin >> a >> b >> k;

	int cnt = 0;
	vector<int> t;
	rrep (i, 100000) {
		if (a % i == 0 && b % i == 0) {
			t.pb(i);
		}
		
	}

	sort(rrng(t));
	cout << t[k - 1] << endl;
	return 0;
}

Measured memory_bytes: 256
//e4-e5-f4
//#include <boost/multiprecision/cpp_int.hpp> 
#include "bits/stdc++.h"
//#include "ext/pb_ds/assoc_container.hpp"
//#include "ext/pb_ds/tree_policy.hpp"
typedef long long int ll;
typedef double db;
// __int128 s128;
// __uint128_t u128;
typedef unsigned long long u64;
#define int long long int
#define PI 3.14159265359
#define sz(a) (ll)a.size()
#define lt(a) (ll)a.length()
#define pll pair<ll,ll>
#define tc(x) ll x; cin>>x; while(x--)
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define bac(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define print(a)  for (auto x : a) cout << x << " "; cout << endl
#define sl set<ll>
#define usl unordered_set<ll>
#define mll map<ll,ll>
#define umll unordered_map<ll,ll>
#define vl vector<ll>
#define vpl vector<pll>
#define vvl vector<vector<ll>>
#define mt make_tuple
#define eb emplace_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define setbits(a) __builtin_popcountll(a)
#define ps(x,y) fixed<<setprecision(y)<<x;
#define F first
#define S second
#define teevra_gati ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define P 1000000007
#define Q 1000000006
#define inf 1e18
#define N 100005
#define M 105
//using namespace boost::multiprecision; 
//using namespace __gnu_pbds;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //shuffle(all(v), rng);
vl adj[N];
ll vis[N], in[N], out[N], store[N];
ll n,m;
void indfs(ll s){
    //cout<<s<<endl;
    in[s]=1;
    vl ind,pre,post;
    for(auto u:adj[s]){
        if(!vis[u]){
            vis[u]=1;
            indfs(u);
            ind.pb(u);
            pre.pb(in[u]+1);
            post.pb(in[u]+1);
            (in[s] *= in[u]+1) %= m;
        }
    }
    ll n1 = sz(ind);
    f(i,1,n1) (pre[i] *= pre[i-1]) %= m;
    bac(i,n1-2,0) (post[i] *= post[i+1]) %= m;
    f(i,0,n1){
        ll p1=1,p2=1;
        if(i-1>=0) p1 = pre[i-1];
        if(i+1<n1) p2 = post[i+1]; 
        store[ind[i]] = (p1*p2)%m;
    }
}

void outdfs(ll s){
    for(auto u:adj[s]){
        if(!vis[u]){
            vis[u]=1;
            out[u] = (1 +  (out[s] * store[u]) % m) % m;
            //cout<<u<<" "<<out[u]<<endl;
            outdfs(u);
        }
    }
}
void solve(){
    cin>>n>>m;
    f(i,1,n){
        ll u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vis[1]=1;
    indfs(1);
    f(i,2,n+1) vis[i]=0;
    out[1]=1;
    outdfs(1);
    f(v,1,n+1){
        cout<<(in[v]*out[v])%m<<endl;
    }
    
}

signed main() {
    teevra_gati
        
    solve();

    return 0;
}

Measured memory_bytes: 25092
#include <stdio.h>
#include <stdlib.h>

void InputFrom(int *from, int num);
void InputTarget(int *target, int num);

int main(void)
{
    int i;

    int *from;
    int num_from;
    scanf("%d", &num_from);
    from = malloc(sizeof(int) * num_from);
    if (from == NULL) {
        printf("ERROR\n");
        return 1;
    }
    InputFrom(from, num_from);

    int *target;
    int num_target;
    scanf("%d", &num_target);
    target = malloc(sizeof(int) * num_target);
    if (target == NULL) {
        printf("ERROR\n");
        return 1;
    }
    InputTarget(target, num_target);

    int cnt = 0;
    for (i = 0; i < num_target; i++) {
        int first = 0, last = num_from;
        int mid;
        while (first <= last) {
            mid = (last + first) / 2;
            if (from[mid] < target[i]) {
                first = mid + 1;
            } else if (target[i] < from[mid]) {
                last = mid - 1;
            } else {
                cnt++;
                break;
            }
        }
    }

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

    return 0;
}

int cmp(const void *a, const void *b);

void InputFrom(int from[], int num)
{
    int i;

    for (i = 0; i < num; i++) {
        scanf("%d", from + i);
    }

    qsort((void *)from, num, sizeof(int), cmp);
}

int cmp(const void *a, const void *b)
{
    int diff = *(int *)a - *(int *)b;
    return diff;
}

void InputTarget(int target[], int num)
{
    int i;

    for (i = 0; i < num; i++) {
        scanf("%d", target + i);
    }
}

Measured memory_bytes: 720
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=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;
}

int main()
{
    ll dp[100100];
    for (int i=0; i<100100; ++i) dp[i]=longinf;
    
    int N,K;
    cin >> N >> K;
    vector<int> h;
    int tmp;
    for (int i=0; i<N; ++i)
    {
        cin >> tmp;
        h.push_back(tmp);
    }

    dp[0] = 0;

    for (int i=0; i<N; ++i)
    {   
        for (int k=1; k<K+1; ++k)
        {
            if(i+k<N)
            {
                if(dp[i+k]>dp[i]+abs(h[i]-h[i+k]))
                {
                    dp[i+k] = dp[i]+abs(h[i]-h[i+k]);
                }
            }
        }
    }

    cout << dp[N-1] << endl;
    return 0;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 1145141919
#define MOD 1000000007
#define ALL(a) begin((a)),end((a))
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
typedef vector<edge> edges;
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///
int n, w, v[15];

int main()
{
	while (cin >> n >> w, n)
	{
		MS(v, 0);
		int cnt = 0;
		REP(i, n)
		{
			int a; cin >> a;
			v[a / w]++;
			cnt = max(cnt, a / w);
		}
		cnt++;
		int mx = *max_element(ALL(v));
		double sum = 0.01;
		REP(i, cnt)
		{
			sum += (1.0 - double(i) / (cnt - 1))*v[i] / double(mx);
		}
		cout << D10 << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 2e5 + 11;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;


int t, n, k, l, r, ans;
vpii v1, v2;
vi g[N];

void solve (vpii v) {
	for (int i = 1; i <= n; ++i)
		g[i].clear();

	for (auto x : v)
		g[x.f].pb(x.s);

	int Sz = 0;
	multiset < int > q;

	for (int i = 1; i <= n; ++i) {
		for (auto j : g[i]) {
			q.insert(j); 
			++Sz;
			ans += j;
		}
		while (Sz > i) {
			--Sz;
			ans -= *q.begin();
			q.erase(q.begin());
		}
	}
}

main () {
	fastio
	cin >> t;
	while (t--) {
		ans = 0;
		cin >> n;
		v1.clear();
		v2.clear();

		for (int i = 1; i <= n; ++i)  {
			cin >> k >> l >> r; 
			ans += min(l, r);
			if (l >= r) 
				v1.pb({k, l - r});
			else
				v2.pb({n - k, r - l});
		}

		solve(v1);
		solve(v2);
		cout << ans << endl;
	}
}


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

using namespace std;

int main(){
    int n,k,min,f_cnt =0,b_cnt=0,ans =0;
    bool f = true,b = true;
    cin >>n >>k;
    vector<int> a(n);

    for(auto &e:a) cin >>e;
  
    if((n-1)%(k-1)==0){
        cout << (n-1)/(k-1) <<endl;
    }else{
        cout << (n-1)/(k-1) +1 <<endl;
    }
    



}

Measured memory_bytes: 640
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        LCS solver = new LCS();
        solver.solve(1, in, out);
        out.close();
    }

    static class LCS {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();

            while (n-- != 0) {
                final String x = in.next();
                final String y = in.next();

                out.printf("%d\n", lcs(x, x.length(), y, y.length()));
            }
        }

        private int lcs(final String a, final int alen, final String b, final int blen) {
            int[][] dp = new int[alen + 1][blen + 1];

            for (int i = 1; i < alen + 1; i++) {
                for (int j = 1; j < blen + 1; j++) {
                    if (a.charAt(i - 1) == b.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                    }
                }
            }

            return dp[alen][blen];
        }

    }
}




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

int main(){
  int N, K, s = 1;
  cin >> N >> K;
  for(int i = 0; i < N; i++){
    if(s + K < s * 2){
      s += K;
    }
    else{
      s *= 2;
    }
  }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;

struct Cube {
  int x,y,z;
  
  Cube(){}
  Cube(int x,int y,int z):x(x),y(y),z(z){}

  bool operator == (Cube that){
    return x == that.x && y == that.y && z == that.z;
  }
};

bool is_adjecent(Cube a, Cube b){
  for(int i=-1;i<=1;i++){
    if(a == Cube(b.x+i, b.y, b.z))return true;
    if(a == Cube(b.x, b.y+i, b.z))return true;
    if(a == Cube(b.x, b.y, b.z+i))return true;
  }
  return false;
}

int count_exposure(Cube cube,int a,int b,int c){
  return
  (cube.x == 0) + (cube.x == a-1) +
  (cube.y == 0) + (cube.y == b-1) +
  (cube.z == 0) + (cube.z == c-1);
}
  
int main(void){

  ll a,b,c,n;

  cin >> a >> b >> c >> n;

  vector<Cube>cubes(n);
  
  for(int i=0;i<n;i++)
    cin >> cubes[i].x >> cubes[i].y >> cubes[i].z;
  
  ll cnt=2*(a*b+b*c+c*a)+6*n;
  for(int i=0;i<n;i++){
    cnt -= 2*count_exposure(cubes[i],a,b,c);
    for(int j=i+1;j<n;j++){
      cnt -= 2*is_adjecent(cubes[i], cubes[j]);
    }
  }
  
  cout << cnt << endl;
  
  return 0;
}

Measured memory_bytes: 3120
#include<bits/stdc++.h>
    using namespace std;
    int main(){
    	string s;
      cin>>s;
      vector<int >ind(26,0);
      for(int i=0;i<s.length();i++)ind[s[i]-'a']=1;
    
      int i=0;
      for(i=0;i<26;i++){
      	if(ind[i]==0)break;
      }
      if(i==26)cout<<"None";
      else cout<<(char)(97+i);
    }

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

int main(){

  int n;

  cin >> n;

  long long int a[n];

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

  long long int dp[n];

  dp[0] = a[0];

  int count = 0;

  for(int i=1; i<n; i++){
    if(dp[count] < a[i]){
      dp[++count] = a[i];
    }
    else{
      for(int j=0; j<n; j++){
        if(dp[j] >= a[i]){
          dp[j] = a[i];
          break;
        }
      }
    }
  }

  cout << count + 1 << endl;




  return 0;
}

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

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<bool>> vvb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debugF(ostream &os) {os << endl;}
template <typename Head, typename... Tail>
void debugF(ostream &os, Head H, Tail... T) { os << " " << H; debugF(os, T...); }
#define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debugF(cout, __VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); os << (i>0 ? " ":"") << v[i++]); return os;}

void test(int cr, int x, int &ans){
    if(abs(cr - x) < abs(ans - x)){
        ans = cr;
    }else if(abs(cr - x) == abs(ans - x)){
        if(cr < ans) ans = cr;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x, n, i, j;
    cin >> x >> n;
    vi p(n); cin >> p;
    sort(all(p));
    int inf = 1e7;
    int ans = -inf;
    if(n == 0){
        cout << x << "\n";
        return 0;
    }
    if(x < p.front() || x > p.back()){
        ans = x;
    }
    for(i=0;i<n;i++){
        if(i == 0 || p[i-1] != p[i] - 1){
            test(p[i] - 1, x, ans);
        }
        if(i == n-1 || p[i+1] != p[i] + 1){
            test(p[i]+1, x, ans);
        }
    }

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 3660
#include<cstdio>

int main(){
   int n,i,a,b,min,max;
   long long sum;
   scanf("%d %d",&n,&a);
   min = a;
   max = a;
   sum = a;
   for(int i = 2;n >= i;i++){
       scanf("%d",&b);
       if(min >= b){
           min = b;
       }
       else{
           min = min;
       }
       if(max <= b){
           max = b;
       }
       else{
           max = max;
       }
       sum = sum + b;
       }
       printf("%d %d %lld\n",min,max,sum);
       return 0;
       
}


Measured memory_bytes: 2704
#include <stdio.h>

int main(void)
{
	int n, s;
	int i;

	while (1) {
		scanf("%d", &n);
		if (n == 0)
			break;
		s = 0;
		for (i = 1; i * i < n; i++)
			if (n % i == 0)
				s += i + n / i;
		s -= n;
		if (n == s)
			puts("perfect number");
		else if (n > s)
			puts("deficient number");
		else
			puts("abundant number");
	}

	return 0;
}

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

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<<endl

int main(){
    int n;
    cin >> n;
    int t0=0,x0=0,y0=0;
    bool flag = 1;
    for(int i=0;i<n;i++){
        int t,x,y;
        cin >> t >> x >> y;
        int dis = abs(x-x0)+abs(y-y0);
        int time = t-t0;
        if(time<dis) flag = 0;
        else if((time-dis)%2!=0) flag = 0;
        t0=t;x0=x;y0=y;
    }
    if(flag)COUT("Yes");
    else COUT("No");
    return 0;
} 


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int n = in.nextInt();
		int[] d = new int[n];
		for (int i = 0; i < n; i++)
			d[i] = in.nextInt();
		System.out.println(solve(d));
		in.close();
	}

	private static int solve(int[] d) {
		Arrays.sort(d);
		int m = d.length / 2;
		return d[m] - d[m - 1];
	}
}


Measured memory_bytes: 51200
const stdin = require('fs').readFileSync('/dev/stdin', 'utf8').trim()

const s = stdin.split('\n')[0]

const ans = () => {
  const uniq = new Set(s)

  if (uniq.size === 2) {
    const s0 = s[0]
    const len = s.split('').filter(e => e === s[0]).length

    if (len === 2) {
      return true
    }
  }
  return false
}

console.log(ans() ? 'Yes' : 'No')


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

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100000;

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

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

int main() {
	string l;
	cin >> l;
	int n = l.size();

	mint p_3[N];
	p_3[0] = 1;
	for(int i = 1; i < n; i++) p_3[i] = p_3[i - 1] * 3;

	mint ans = 0;
	mint p_2 = 1;
	for(int i = 0; i < n; i++) {
		if(l[i] == '1') {
			ans += p_2 * p_3[n - 1 - i];
			p_2 *= 2;
		}
	}
	ans += p_2;
	cout << ans.x << endl;
}


Measured memory_bytes: 1280