akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int koyaku(a,b){
  if(a < b){
    int t = a;
    a = b;
    b = t;
  }
  int r = a % b;
  while(r != 0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

int main(){
  int N;
  scanf("%d",&N);
  int A[N];
  for(int i = 0;i < N;i++){
    scanf("%d",&A[i]);
  }
  for(int i = N - 2;i >= 0;i--){
    A[i] = koyaku(A[i],A[i + 1]);
  }
  printf("%d",A[0]);
  return 0;
}

Measured memory_bytes: 512
import sys
import queue
s = sys.stdin.readlines

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

for _ in range(m):
    a, b = [int(x) for x in input().split()]
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)


dist = [-1] * n
dist[0] = 0

def bfs():
    q = queue.Queue()
    q.put(0)

    while not q.empty():
        v = q.get()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = v + 1
            q.put(nv)
    
bfs()

if -1 in dist:
    print("No")
else:
    print("Yes")
    dist.pop(0)
    for s in dist:
        print(s)

Measured memory_bytes: 37144
#include<iostream>

using namespace std;

int main() {
	int N;
	cin >> N;
	int res = 0;
	while (true) {
		if (N == 1) {
			break;
		}
		N /= 2;
		res++;
	}

	int ans = 1;
	for (int i = 0; i < res; i++) {
		ans = ans * 2;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  int a, b;
  cin >> a >> b;

  cout << max(a - 2 * b, 0) << endl;
}


Measured memory_bytes: 3608
#include<cstdio>

int n,m;
int ti[105],t[105];
int p,x;

int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n; i++){
		scanf("%d",&ti[i]);
	}
	scanf("%d",&m);
	for(int i = 1;i <= m;i++){
		scanf("%d %d",&p,&x);
		for(int i = 1;i <= n; i++){
			t[i] = ti[i];
		}
		t[p] = x;
		int ans = 0;
		for(int i = 1;i <= n; i++){
			ans += t[i];
		}
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 128
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <limits>
#include <string>
#include <regex>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main()
{
    int a, b, h;
    cin >> a >> b >> h;
    cout << (a + b) * h / 2 << endl;
    return 0;
}


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

#define FOR0(i,n) for (int i = 0; i < n; i++)
#define FOR(i,j, n) for (int i = j; i < n; i++)
// bool isEven(ll n) {return (n%2!=0)?false:true;};
#define INF 1000000000 // 1 billion, safer than 2B for Floyd Warshall’s

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
// #define int ll

using namespace std;

//atcoder
// Dwango Programming Contest 6th
//a

int main()
{
    int n;
    string x;

    vector<pair<string, int> > v;

    cin>>n;

    string temp;
    int temp_t;
    for (int i = 0; i < n; ++i)
    {
        cin>>temp>>temp_t;
        v.push_back(make_pair(temp, temp_t));
    }

    cin>>x;

    int result = 0;

    int flag = 0;

    for (int i = 0; i < n; ++i)
    {
        if(flag)
            result+=v[i].second;
        if(v[i].first==x)
            flag = 1;
    }

    cout<<result<<endl;
}

Measured memory_bytes: 256
def ip():
    return int(input())
    
def ipp():
    return map(int,input().split())
    
def sar():
    return list(ipp())
    
def pars(a):
    print(''.join(list(map(str, a))))
    print('\r')
    
def parl(a):
    print('\r'.join(list(map(str, a))))
    print('\r')
    
#template ends   

if __name__=='__main__':
    T=1
    #T=int(input().strip())
    for _ in range(T):
        n = ip()
        k = []
        if n==0:
            print(0)
        i = 0
        while n is not 0:
            k.append((n%(-2)))
            n = n//(-2)
            if (k[-1] == -1):
                k[-1] = 1
                n+=1
            i+=1
        k = k[::-1]
        pars(k)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

const int INF = 1001001001;

// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

int N, M;
int d[400][400];

int main(){
    std::cin >> N >> M;
    
    REP(i, 400){
        REP(j, 400){
            if(i == j){d[i][j] = 0;}
            else{d[i][j] = -INF;}
        }
    }

    REP(i, M){
        int from, to, cost;
        std::cin >> from >> to >> cost;

        d[from][to] = cost;
    }

    REP(k, N){
        REP(i, N){
            REP(j, N){
                d[i][j] = std::max(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    std::cout << d[0][N-1] << std::endl;
}

Measured memory_bytes: 1784
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int sum = 0;
        for (int i = 0; i < 2; i++) {
            if (a >= b) {
                sum += a;
                a--;
            } else {
                sum += b;
                b--;
            }
        }
        System.out.println(sum);

    }
}

Measured memory_bytes: 21716
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;

 
int main() {
    string S; cin >> S;
    int N = S.size();
    vector<int> V(N);
    for(int i = 0; i < N; i++) V[i] = 1;

    for(int i = 0;i < N; i++){
        if(S[i] == 'R'){
            if(S[i+1] == 'R'){

                V[i+2] += V[i];
                V[i] = 0;
            }
            else if(S[i] == 'L'){
                continue;
            }
        }        
    }
    for(int i = N-1;i >= 0; i--){

        if(S[i] == 'L'){
            if(S[i-1] == 'L'){
                V[i-2] += V[i];
                V[i] = 0;
            }
            else if(S[i] == 'R'){
                continue;
            }
        } 
    }
    for(int i = 0; i < N; i++) cout << V[i] << " ";
    cout << endl;

    
}

Measured memory_bytes: 1152
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define N 400011
using namespace std;
int b[N],len,n,a[N],cnt[N],ans,maxx,minn;
int judge(int avr){
	b[0]=-1;
	for(int i=1;i<=len;i++){
		b[i]=(a[i]>=avr);
		if(b[i]==b[i-1]) cnt[i]=cnt[i-1]+1;
		else cnt[i]=1;
	}
	for(int i=0;i<n;i++){
		if(cnt[n+i]>=2) return b[n+i];
		if(cnt[n-i]>=2) return b[n-i];
	}
	return b[1];
}
void bin(){
	int head=minn,tail=maxx,mid;
	while(head<=tail){
		mid=(head+tail)/2;
		if(judge(mid)){
			ans=mid;
			head=mid+1;
		}
		else tail=mid-1;
	}
}
int main(){
//	freopen("triangle.in","r",stdin);
	scanf("%d",&n);len=2*n-1;
	for(int i=1;i<=len;i++) scanf("%d",&a[i]),minn=min(minn,a[i]),maxx=max(maxx,a[i]);
	bin();
	printf("%d",ans);
	return 0;
}

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

long long g(long long a,long long b);

long long l(long long a,long long b);

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    long long n;
    cin>>n;
    vector<long long> v(n+9);
    for(int i=0;i<n;i++){
        cin>>v.at(i);
    }
    for(int i=0;i<n-1;i++){
        v.at(i+1)=l(v.at(i),v.at(i+1));
    }
    cout<<v.at(n-1)<<'\n';
    return(0);
}

long long g(long long a,long long b){
    while(b!=0){
    long long r=a%b;
    a=b;
    b=r;
    }
    return(a);
}
long long l(long long a,long long b){
    return a/g(a,b)*b;
}



Measured memory_bytes: 3216
import sys
sys.setrecursionlimit(10000000)
H,N = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
mem = [0] * H
def dp(rem):
    global mem
    if rem <= 0:
        return 0
    elif mem[rem-1]:
        return mem[rem-1]
    else:
        a = min([dp(rem-AB[i][0]) + AB[i][1] for i in range(N)])
        mem[rem-1] = a
        return a
print(dp(H))

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


int main() {
int n;
cin >> n;
int sen = n % 1000;
if(sen == 0){
    cout << 0 << endl;
}
else{
    cout << 1000 - sen << endl;
}
}

Measured memory_bytes: 3632
n,m=map(int,input().split())
li = [list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
#n進数への変換関数の定義
#Python 3.7とかではデフォであるが，Python 3.4.3(AtCoder仕様)ではまだない
########10進法からn進法への変換関数部分##############
def format(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
############################

########10進法からn進法への変換関数(m桁埋める)部分##############
def format0(X, n, m):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    if len(out) < m:
        out = "0" * (m - len(out)) + out
    return out
############################
ans = 0
for i in range(2**n):
  i = format0(i,2,n)
  switch = [int(i[j]) for j in range(n)]
  on=0
  for j in range(m):
    if sum([switch[li[j][l+1]-1] for l in range(li[j][0])]) % 2 == p[j]:
      on += 1
  if on == m:
    ans += 1
print(ans)

Measured memory_bytes: 3064
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	int n, m;
	LinkedList<Integer>[] es;
	LinkedList<R> rs;
	int[] memo;

	void run(){
		for(;;){
			n=sc.nextInt();
			if(n==0){
				break;
			}
			rs=new LinkedList<R>();
			for(int i=0; i<n; i++){
				int h=sc.nextInt();
				int r=sc.nextInt();
				rs.add(new R(h, r));
			}
			m=sc.nextInt();
			for(int i=0; i<m; i++){
				int h=sc.nextInt();
				int r=sc.nextInt();
				rs.add(new R(h, r));
			}
			solve();
		}
	}

	@SuppressWarnings("unchecked")
	void solve(){
		n+=m;
		es=new LinkedList[n];
		memo=new int[n];
		Arrays.fill(memo, -1);
		for(int j=0; j<n; j++){
			es[j]=new LinkedList<Integer>();
			R rj=rs.get(j);
			for(int i=0; i<n; i++){
				R ri=rs.get(i);
				if(ri.h<rj.h&&ri.r<rj.r){
					es[j].add(i);
					// debug(j, i);
				}
			}
		}
		int ans=0;
		for(int i=0; i<n; i++){
			ans=Math.max(ans, dfs(i));
			// debug(i, dfs(i));
		}
		println(""+ans);
	}

	int dfs(int v){
		int ret=0;
		for(int u : es[v]){
			int d;
			if(memo[u]!=-1){
				d=memo[u];
			}else{
				d=memo[u]=dfs(u);
			}
			ret=Math.max(ret, d);
		}
		return ret+1;
	}

	class R{
		int h, r;

		R(int h, int r){
			this.h=h;
			this.r=r;
		}
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

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

int main(){
    int A, B;
    cin >> A >> B;
    int ans = 0;
    for(int i = A; i <= B; i++){
        string reverse_i = to_string(i);
        reverse(reverse_i.begin(), reverse_i.end());
        if(to_string(i) == reverse_i){
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
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(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod


#include <bits/stdc++.h>
using namespace std;
signed main(){
    int N,A,B; cin>>N>>A>>B;
    int ans;
    if(abs(A-B)%2==0) ans =abs(A-B)/2;
    else ans = min(N-B,A-1)+1+(B-A-1)/2;
    Out(ans);
}

Measured memory_bytes: 256
program sequence_sum
  implicit none
  integer(8) :: n, num, tmp, a(0:100000) = 0
  integer :: x, m, b(0:100000) = 0, period, offset, rem, i
  read(*,*) n, x, m
  tmp = m
  if (n <= 2 * m) then
    num = x
    rem = int(n)
    do i = 2, rem
      x = mod(int(x, 8) * x, tmp)
      if (x == 0) exit
      num = num + x
    end do
    write(*,'(i0)') num
    stop
  end if
  a(1) = x
  b(x) = 1
  do i = 2, m + 1
    x = int(mod(int(x, 8) * x, tmp))
    a(i) = a(i - 1) + x
    if (b(x) > 0) then
      offset = b(x) - 1
      period = i - offset - 1
      exit
    end if
    b(x) = i
  end do
  num = (n - offset) / period
  rem = int(n - offset - num * period)
  write(*,'(i0)') (a(offset + period) - a(offset)) * num + a(offset + rem)
end program sequence_sum

Measured memory_bytes: 3528
s=list(input())
i=0
while(i<len(s)):
    if s[i]=='?':
        if i-1>=0 and s[i-1]=='P':
            s[i]='D'
        elif i+1<len(s) and s[i+1]=='D':
            s[i]='P'
        elif i+1<len(s) and s[i+1]=='?':
            s[i]='P'
            s[i+1]='D'
        else:s[i]='D'
    i+=1
z=''.join(s)
print(z)

Measured memory_bytes: 73812
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll mod = 1000000007;
const int N = 200010;
ll fact[N], invf[N];

ll add(ll x, ll y){
    return (x+y)%mod;
}

ll mul(ll x, ll y){
    return (x%mod)*(y%mod)%mod;
}

ll powll(ll x, ll y){
    x %= mod;
    ll res = 1LL;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}

ll divll(ll x, ll y){
    x %= mod;
    return (x * powll(y,mod-2)) % mod;
}

ll nPr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(fact[n], invf[n-r]);
}

ll nCr(ll n, ll r){
    if (n < r || r < 0) return 0;
    return mul(mul(fact[n], invf[r]), invf[n-r]);
}

void init_f(){
    fact[0] = 1;
    FOR(i,1,N-1){
        fact[i] = (fact[i-1] * i) % mod;
    }
    invf[N-1] = divll(1, fact[N-1]);
    FORR(i,N-1,1){
        invf[i-1] = (invf[i] * i) % mod;
    }
}

int main(void){
    ll n, k;
    cin >> n >> k;
    init_f();
    ll ans = 0;
    REP(i,min(k,n)+1){
        if (k == 1 && i == 1) continue;
        ll a = n - i;
        ll x = nCr(n - 1, a - 1) * nCr(n, a);
        ans = (ans + x) % mod;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <map>

const int N = 400000 + 7;

int n;
std::vector<int> g[N];
int fa[N];
int h[N], q[N];
std::map<int, int> f[N];

void init(int s) {
	for (auto t : g[s]) if (t != fa[s]) fa[t] = s, init(t);
}
int get(int s, int y) {
	if (f[s].find(y) != f[s].end()) return f[s][y];
	int w = 1;
	for (auto t : g[s]) if (fa[t] == s && t <= y) w += get(t, y);
	return f[s][y] = w;
}
void dfs(int s) {
	h[s] = std::max(h[fa[s]], s);
	q[s] = q[fa[s]] + get(s, h[fa[s]]) - (s < h[fa[s]] && s < h[fa[fa[s]]]) * get(s, h[fa[fa[s]]]);
	for (auto t : g[s]) if (fa[t] == s) dfs(t);
}

int main() {
//	freopen("code.in", "r", stdin);
//	freopen("code.out", "w", stdout);

	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i)
		scanf("%d%d", &u, &v), g[u].push_back(v), g[v].push_back(u);
	init(1), dfs(1);
	for (int i = 2; i <= n; ++i) printf("%d ", q[i] - 1);
	return 0;
}


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

#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v,x) (std::find(v.begin(), v.end(), x) != v.end())
#define BIT_ON(bit, i) (bit & (1LL << i))

typedef long long LL;
template<typename T> using V = std::vector<T>;
template<typename T> using VV = std::vector<std::vector<T>>;
template<typename T> using VVV = std::vector<std::vector<std::vector<T>>>;
template<typename T> using VVVV = std::vector<std::vector<std::vector<std::vector<T>>>>;

template<class T> inline T ceil(T a, T b) { return (a + b - 1) / b; }
template<class T> inline void print(T x) { std::cout << x << std::endl; }
template<class T> inline void print_vec(const std::vector<T> &v) { for (int i = 0; i < v.size(); ++i) {  if (i != 0) {std::cout << " ";} std::cout << v[i];} std::cout << "\n"; }
template<class T> inline bool inside(T y, T x, T H, T W) {return 0 <= y and y < H and 0 <= x and x < W; }
template<class T> inline double euclidean_distance(T y1, T x1, T y2, T x2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
template<class T> inline double manhattan_distance(T y1, T x1, T y2, T x2) { return abs(x1 - x2) + abs(y1 - y2); }
template<class T> inline std::vector<T> unique(std::vector<T> v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v;
}

const int INF = 1 << 30;
const double EPS = 1e-9;
const std::string YES = "YES", Yes = "Yes", NO = "NO", No = "No";
const std::vector<int> dy4 = { 0, 1, 0, -1 }, dx4 = { 1, 0, -1, 0 };    // 4近傍（右, 下, 左, 上）
const std::vector<int> dy8 = { 0, -1, 0, 1, 1, -1, -1, 1 }, dx8 = { 1, 0, -1, 0, 1, 1, -1, -1 };

using namespace std;

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

    int N, D, X;
    cin >> N >> D >> X;
    VV<int> P(D, V<int>(N));
    FOR(i, 0, D) {
        FOR(j, 0, N) {
            cin >> P[i][j];
        }
    }

    int money = X;
    FOR(i, 0, D - 1) {

        // 個数制限なしのナップサック問題
        int next_moeny = 0;
        VV<int> dp(N + 1, V<int>(money + 1));
        FOR(j, 0, N) {
            int now = P[i][j];
            int next = P[i + 1][j];
            int price = next - now;

            FOR(k, 0, dp[0].size()) {
                // not use
                dp[j + 1][k] = max(dp[j + 1][k], dp[j][k]);
                next_moeny = max(next_moeny, dp[j + 1][k]);

                // use
                if (k + now <= money) {
                    dp[j][k + now] = max(dp[j][k + now], dp[j][k] + price);
                    next_moeny = max(next_moeny, dp[j][k + now]);
                }
            }
        }
        money = money + next_moeny;
    }
    print(money);

    return 0;
}


Measured memory_bytes: 4272
#coding:utf-8

import math

def enough(A, B, h_list, T):
    h_list = filter(lambda x: (x - B * T) > 0, h_list)
    h_list = map(lambda x : x - B * T, h_list)

    exp_num = 0
    for val in h_list:
        exp_num += math.ceil(val / (A - B))

    if exp_num <= T:
        return True
    else:
        return False

def binary_search(A, B, h_list, T_min, T_max):
    if T_min == T_max:
        return T_min
    else:
        T_mid = T_min + (T_max - T_min) // 2
        if enough(A, B, h_list, T_mid):
            return binary_search(A, B, h_list, T_min, T_mid)
        else:
            return binary_search(A, B, h_list, T_mid + 1, T_max)

if __name__ == "__main__":
    N, A, B = map(int, input().split(" "))

    h_list = []
    for i in range(N):
        h_list.append(int(input()))

    T_max = math.ceil(sum(h_list) / B)
    print(binary_search(A, B, h_list, 0, T_max))


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

void Main() {
    // input
    int A, B;
    cin >> A >> B;


    // translate
    int ans = A * B;

    // output
    cout << ans << endl;

}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define test int t; cin>>t; while(t--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
using namespace std;
int main()
{
    long long a,b,c,d;
    cin>>a>>b>>c;
   d=abs(b-a);
   if(a%c!=0&&b%c!=0)
   cout<<d/c<<endl;
   else
   {
       if(a%c==0||b%c==0)
        cout<<d/c +1<<endl;
   }
}


Measured memory_bytes: 3620
from collections import defaultdict
import sys
import time

sys.setrecursionlimit(2000)
N, M, K = [int(i) for i in input().split(" ")]

t = time.time()
class UnionNode():
    def __init__(self, number):
        self.number = number
        self.volume = 1
        self.master = None

    @property
    def root(self):
        if self.master:
            self.master = self.master.root
            return self.master
        else:
            return self

    def unite(self, target):
        seroot = self.root
        taroot = target.root
        if seroot.number == taroot.number:
            pass
        else:
            #print(f"unite {target.rootnum}({target.root.volume}), {self.rootnum}({self.root.volume})")
            if seroot.number < taroot.number:
                seroot.volume += taroot.volume
                taroot.master = seroot
            else:
                taroot.volume += seroot.volume
                seroot.master = taroot

nodes = [UnionNode(i) for i in range(N)]

outlist = defaultdict(lambda :[])

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    nodes[a].unite(nodes[b])
    outlist[a].append(b)
    outlist[b].append(a)

for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    outlist[a].append(b)
    outlist[b].append(a)

result = []
for i in range(N):
    rootnode = nodes[i].root
    ret = rootnode.volume - 1
    for out in outlist[i]:
        if nodes[out].root.number == rootnode.number:
            ret -=1
    result.append(ret)

#for i in range(100):
#    print(result[i])

print(" ".join([str(i) for i in result]))

#print(time.time() - t)

Measured memory_bytes: 66744
let () = Scanf.scanf "%d\n" @@ fun n ->
  let abs = Array.init n @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun a b -> a, b in
  Array.sort (fun (a, b) (a', b') -> compare (b, a) (b', a')) abs;
  print_endline @@ if
    fst @@
    Array.fold_left (fun (acc, t) (a, b) ->
      acc && t + a <= b, t + a) (true, 0) abs
  then "Yes"
  else "No"

Measured memory_bytes: 9600
def main():
    L, R = map(int, input().split())
    # [3, 673]
    if L + 672 <= R:
        print(0)
        return
    print(min(i * j % 2019 for i in range(L, R + 1)
              for j in range(i + 1, R + 1)))
    return


main()


Measured memory_bytes: 2940
#include <stdio.h>

int main (void){
   int N,K;
   scanf("%d %d",&N,&K);
   int high[N];
   int i;
   int count=0;
   for(i=0;i<N;i++){
       scanf("%d",&high[i]);
       if(high[i]>=K){
           count++;
       }
   }
   printf("%d",count);
   return 0;
}

Measured memory_bytes: 512
/**Bismillahir Rahmanir Raheem
    Author:Refatul Fahad**/

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

#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define pil pair<int,ll>
#define IOS  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
const int N = 1e5 + 5;
const ll M = (ll)1e9 + 7;
const double pi=2*acos(0.0);
const double esp=1e-9;
int Set(int N,int pos) {
    return N=N | (1<<pos);
}
int reset(int N,int pos) {
    return N= N & ~(1<<pos);
}
bool check(int N,int pos) {
    return (bool)(N & (1<<pos));
}

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

int main() {

    //IOS;
    /// freopen("input.txt","r",stdin);
    /// freopen("output.txt","w",stdout);

    int test=1;
    //cin>>test;
    for(int cs=1; cs<=test; ++cs) {
       int n;
       cin>>n;
       if(n<30){
        cout<<"No"<<endl;
       }
       else{
        cout<<"Yes"<<endl;
       }
    }
    return 0;
}



Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;
template <class T>
inline void chmin(T &a, const T &b) { a = min(a, b); }
template <class T>
inline void chmax(T &a, const T &b) { a = max(a, b); }
template <class T>
inline bool kbit(const T &x, const int &k) { return ((x >> k) & 1LL); }
inline int popcount(const int &n) { return __builtin_popcount(n); }
inline ll popcountll(const ll &n) { return __builtin_popcountll(n); }
template <class T>
void zip(V<T> &v) {
    sort(all(v));
    v.erase(unique(all(v)), v.end());
}
void dump() {
    cerr << '\n';
}
template <class Head, class... Tail>
void dump(Head &&head, Tail &&... tail) {
    cerr << head << (sizeof...(Tail) == 0 ? " " : " ");
    dump(std::move(tail)...);
}
template <class T>
void print(const vector<T> &v) {
    for (int i = 0; i < v.size(); i++) cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');
}
template <class T>
void read(vector<T> &v) {
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}
constexpr char sp = ' ';
constexpr char newl = '\n';
constexpr int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll MOD = 1e9 + 7;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    V<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int t = 0, mi = 0;
        for (int j = 0; j < s.length(); j++) {
            if (s[j] == '(') {
                t++;
            } else {
                --t;
            }
            chmin(mi, t);
        }
        a[i] = t, b[i] = mi;
    }
    int sum = 0;
    V<int> vis(n);
    int m = 1000000;
    V<V<int>> vs(m + 1);
    for (int i = 0; i < n; i++) {
        if (a[i] >= 0 && b[i] == 0) {
            sum += a[i];
            vis[i] = 1;
        } else if (a[i] >= 0) {
            vs[-b[i]].eb(i);
        }
    }
    for (int i = 0; i <= m; i++) {
        if (i > sum) break;
        for (auto &e : vs[i]) {
            vis[e] = 1;
            sum += a[e];
        }
    }
    V<P> v;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            if (a[i] >= 0) {
                cout << "No" << newl;
                return 0;
            }
            v.eb(abs(b[i]) - abs(a[i]), i);
        }
    }
    sort(all(v));
    reverse(all(v));
    for (int i = 0; i < v.size(); i++) {
        int id = v[i].se;
        if (sum + b[id] < 0) {
            cout << "No" << newl;
            return 0;
        }
        sum += a[id];
    }
    if (sum == 0) {
        cout << "Yes" << newl;
    } else {
        cout << "No" << newl;
    }
}

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


int main(){
	string tmp[16]={"KIHBR","KIHBRA","KIHBAR","KIHBARA","KIHABR","KIHABRA","KIHABAR","KIHABARA","AKIHBR","AKIHBRA","AKIHBAR","AKIHBARA","AKIHABR","AKIHABRA","AKIHABAR","AKIHABARA"};
	string s;
	cin>>s;

	for (int i = 0; i < 16; ++i){
		if(s==tmp[i]){
			cout<<"YES"<<endl;
			return 0;
		}
	}

	cout<<"NO"<<endl;


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <utility> 
#include <tuple>
#include <iterator>
#include <functional>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0; i<n; i++)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)



// union by size + path having
class UnionFind
{
public:
    vector<ll> par; // 各元の親を表す配列
    vector<ll> siz; // 素集合のサイズを表す配列(1 で初期化)
 
    // Constructor
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL)
    {
        for (ll i = 0; i < sz_; ++i)
            par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_)
    {
        siz.assign(sz_, 1LL); // assign: 再代入
        par.resize(sz_);      // resize: 再確保
        for (ll i = 0; i < sz_; ++i)
            par[i] = i; // 初期では親は自分自身
    }
 
    // Member Function
    // Find
    ll root(ll x)
    { // 根の検索
        while (par[x] != x)
        {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }
 
    // Union(Unite, Merge)
    bool merge(ll x, ll y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y])
            swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }
 
    bool issame(ll x, ll y)
    { // 連結判定
        return root(x) == root(y);
    }
 
    ll size(ll x)
    { // 素集合のサイズ
        return siz[root(x)];
    }
};



int main(){
  ll N, M;
    ll node1, node2;
    cin >> N >> M;
    vector<pair<ll,ll>> A(M);
    for (ll i = 0; i < M; i++)
    {
        cin >> node1 >> node2;
        --node1, --node2;
        A[i].first = node1;
        A[i].second = node2;
    }
 
    // calculation
    vector<ll> ans(M);
    ans[M - 1] = (N * (N - 1)) / 2; // 全ての頂点が孤立している状態
 
    UnionFind uf(N);
    for (ll i = M - 1; i >= 1; --i)
    {
        node1 = A[i].first, node2 = A[i].second;
        if (uf.issame(node1, node2))
        {
            ans[i - 1] = ans[i];
        }
        else
        {
            // 根が異なるとき，それぞれのサイズの積（頂点の組み合わせ）を引く．
            ans[i - 1] = ans[i] - (uf.size(node1) * uf.size(node2));
            uf.merge(node1, node2);
        }
    }
 
    REP(i, M)
    {
        cout << ans[i] << "\n";
    }
 
    return 0;
}


Measured memory_bytes: 5248
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

d, g = LI()
pc = [LI() for _ in range(d)]

ans = inf
for i in range(1<<d):
    rest = 1
    rest_count = 0
    score = 0
    count = 0
    for j in range(d):
        p, c = pc[j]
        if (i >> j) & 1:
            score += p * (j + 1) * 100 + c
            count += p
        else:
            if rest < (j + 1) * 100:
                rest = (j + 1) * 100
                rest_count = p
    if score >= g:
        ans = min(ans, count)
    else:
        if math.ceil((g - score) / rest) <= rest_count:
            count += math.ceil((g - score) / rest)
            ans = min(ans, count)
print(ans)

Measured memory_bytes: 40816
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
stack<int> s;
struct node{
	int t,x;
	bool operator <(const node& a)const{
		return x>a.x;
	}
}a[100005];
ll n,k,tp,sum,ans,b[100005];
int main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++)
		a[i].t=read(),a[i].x=read();
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)
		if(i<=k){
			if(b[a[i].t])s.push(a[i].x);
			else b[a[i].t]=1,tp++;
			sum+=a[i].x,ans=max(ans,sum+tp*tp);
		}
		else{
			if(s.empty())break;
			if(b[a[i].t])continue;
			int v=s.top();
			s.pop(),b[a[i].t]=1,tp++;
			sum=sum-v+a[i].x,ans=max(ans,sum+tp*tp);
		}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  a=(a+11)%13;
  b=(b+11)%13;
  if(a==b){
    cout<<"Draw"<<endl;
  }else if(a<b){
    cout<<"Bob"<<endl;
  }else{
    cout<<"Alice"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<set>
#include<map>
using namespace std;


int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int dif = a-b;
    if( c >= dif){
        cout << c - dif;
    }
    else
    {
        cout << 0;
    }
    
    cout << endl;
}


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

int main()
{
  bool list[100001];
  list[1] = true;
  for (int i = 2; i*i <= 100000; i++) {
    if (! list[i]) {
      for (int j = i + i; j <= 100000; j += i) {
        list[j] = true;
      }
    }
  }

  int number[100001];
  number[1] = 0;
  for (int i = 3; i <= 100000; i += 2) {
    if (!(list[i] || list[(i + 1) / 2])) {
      number[i] = number[i - 2] + 1;
    } else {
      number[i] = number[i - 2];
    }
  }

  int Q, l, r;
  cin >> Q;

  for (int i = 0; i < Q; i++) {
    cin >> l >> r;
    cout << number[r] - number[l - 2] << endl;
  }
  return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define all(a) (a).begin(),(a).end()

ll n;

vector<ll> calc(vector<ll> &a) {
    vector<ll> sum(n);
    stack<ll> stack;
    ll cnt = 0;
    rep1(i,n-1){
        ll pre = a[i-1], cur = a[i];
        if (pre >= cur) {
            while (pre >= cur*4) {
                cur *= 4;
                stack.push(i);
            }
        } else {
            while (pre < cur) {
                if (stack.empty()) {
                    cnt += i*2;
                } else {
                    ll k = stack.top(); stack.pop();
                    cnt += (i-k)*2;
                }
                pre *= 4;
            }
        }
        sum[i] = cnt;
    }
    return sum;
}

int main(void){
    cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    vector<ll> l = calc(a);
    reverse(all(a));
    vector<ll> r = calc(a);
    reverse(all(r));

    ll res_min = r[0];
    rep1(i,n-1){
        res_min = min(res_min, l[i-1] + i + r[i]);
    }
    cout << res_min << endl;
    return 0;
}


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

#define ln '\n'
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define FORR(i, a, b) for(int i = (a); i >= (int)(b); --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<P> VP;
typedef vector<PL> VPL;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int s;
    cin >> s;
    set<int> collatz_set;
    collatz_set.insert(s);
    FOR(m, 2, 1e8) {
        if(s % 2 == 0) s /= 2;
        else s = 3 * s + 1;
        if(collatz_set.count(s) > 0) {
            cout << m << ln;
            return 0;
        }
        collatz_set.insert(s);
    }
    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll> > P3;

const ll MOD = ll(1e9 + 7);
const ll LLINF = LLONG_MAX;
const int IINF = INT_MAX;
const int MAX_V = int(1e2) + 5;
const double EPS = 1e-8;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
string dir = "RDLU";
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define SORT(v) sort((v).begin(), (v), end())
#define SORTR(v) sort((v).rbegin(), (v), rend())
#define ALL(v) (v).begin(), (v).end()

struct UnionFindTree {
    int par[MAX_V];
    int rank[MAX_V];

    void init(int n) {
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;

        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y]) rank[x]++;
        }
    }

    bool same(int x, int y) { return find(x) == find(y); }
};

struct edge {
    int u, v;
    double cost;
};

bool comp(const edge &e1, const edge &e2) { return e1.cost < e2.cost; }

vector<edge> es;

double kruskal(int V) {
    sort(es.begin(), es.end(), comp);
    UnionFindTree a;
    a.init(V);
    double res = 0;
    for (int i = 0; i < es.size(); i++) {
        edge e = es[i];
        if (!a.same(e.u, e.v)) {
            a.unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int main() {
    while (1) {
        int n;
        cin >> n;
        if(n==0)break;
        vector<double> x(n),y(n),z(n),r(n);
        es.clear();
        REP(i,n){
            cin >> x[i] >> y[i] >> z[i] >> r[i];
        }
        REP(j,n){
            REP(i,j){
                double c;
                c = pow(pow(abs(x[i]-x[j]),2)+pow(abs(y[i]-y[j]),2)+pow(abs(z[i]-z[j]),2),0.5);
                c = max(0.0,c-r[i]-r[j]);
                es.push_back({i,j,c});
            }
        }
        printf("%.3lf\n",kruskal(n));
    }
    return 0;
}



Measured memory_bytes: 3548
K = int(input())
start = 1

DP = [[1 for i in range(10)] for j in range(12)]

# 下からの桁数
for j in range(1, 12):
    # その位の数
    for i in range(10):
        DP[j][i] = DP[j-1][i]
        if i != 0:
            DP[j][i] += DP[j-1][i-1]
        if i != 9:
            DP[j][i] += DP[j-1][i+1]
s = 0
# 後ろから考える
res = ""
for j in range(12):
    for i in range(1, 10):
        prev = s
        s += DP[j][i]
        if s >= K:
            res += str(i)
            # print(i, j)
            break
    if s >= K:
        break

top = i
keta = j
sa = K - prev
for k in range(keta-1, -1, -1):
    t = 0
    for j in range(max(0, top-1), min(9, top+1)+1):
        # print("kj", k, j)
        t_prev = t
        t += DP[k][j]
        if t >= sa:
            res += str(j)
            sa -= t_prev
            top = j
            break
print(res)


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

int main() 
{
	int n,m,a,b;
	cin>>n>>m;
	vector<int> v[n];
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		a--,b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=0;i<n;i++)
		cout<<v[i].size()<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <complex>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <stack>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <cassert>

using namespace std;

typedef long long ll;
typedef ll li;
typedef pair<int,int> PI;
#define EPS (1e-10L)
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define REP(i, n) rep (i, n)
#define F first
#define S second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset((a),0,sizeof(a))
#define FOR(it,a) for(__typeof(a.begin())it=a.begin();it!=a.end();++it)
template<typename T,typename U> ostream& operator<< (ostream& out, pair<T,U>& val){return out << "(" << val.F << ", " << val.S << ")";}
template<class T> ostream& operator<< (ostream& out, vector<T>& val){out << "{";rep(i,SZ(val)) out << (i?", ":"") << val[i];return out << "}";}
void pkuassert(bool t){t=1/t;};
int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,-1,1,1,-1};

int N;
int guy[100];
int Li[100];
bool vis[100][1<<16];
void solve(){
  CLR(vis);
  rep(i, N){
    int M;
    cin >> M >> Li[i];
    int sc=0;
    rep(j, M){
      int s,e;
      cin >> s >> e;
      for(int k=s;k<e;++k) sc |= 1 << (k-6);
    }
    guy[i] = sc;
  }

  priority_queue<pair<ll,PI> > q;
  q.push(mp(0,mp(0,0)));
  ll be=1LL<<40LL;
  while(!q.empty()){
    ll cc=-q.top().F;
    int ne=q.top().S.F;
    int sc=q.top().S.S;
    q.pop();
    if(ne==N){
      cout << be*N - cc << endl;
      return;
    }
    if(vis[ne][sc]) continue;
    vis[ne][sc] = true;
    //cout << cc << ' ' << ne << ' ' << sc << endl;
    q.push(mp(-cc-be,mp(ne+1,sc)));
    if((sc&guy[ne]) == 0)
      q.push(mp(-cc-(be-Li[ne]),mp(ne+1,sc|guy[ne])));
  }
}

int main(int argc, char *argv[])
{
  while(cin >> N && N) solve();
  return 0;
}

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

int main() {
	long long int n, k; cin >> n >> k;
	vector<long long int> a(n);
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	vector<int> cnt(40, 0);
	for(int i=0;i<n;i++){
		for(int j=0;j<40;j++){
			cnt[j] += a[i] >> j & 1;
		}
	}
	long long int sum = 0LL;
	for(int i=0;i<n;i++){
		sum += a[i];
	}
	long long int ans = 0LL;
	long long int now = 0LL;
	for(int i=40;i>=0;i--){
		int bit = k>>i & 1;
		if(bit){
			long long int d = 0LL;
			for(int j=i-1;j>=0;j--){
				d += max(0LL, (1LL << j)*(n-cnt[j]-cnt[j]));
			}
			ans = max(ans, sum+now+d);
			now += (1LL << i)*(n-cnt[i]-cnt[i]);
		}
	}
	ans = max(ans, sum+now);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long K;
  cin >> K ;
 if (K==1 || K==2||K==3||K==5||K==7||K==11||K==13|K==15|K==17||K==19||K==23||K==29||K==31) {cout << 1 << endl;}
 if (K==4 || K==6 ||K==9||K==10||K==14||K==21||K==22||K==25||K==26) {cout << 2 << endl;}
 if (K==28 ||K==30) {cout<<4<< endl;}
 if (K==8||K==12||K==18||K==20||K==27) {cout << 5<< endl;}
 if (K==16){cout << 14<< endl;}
 if (K==24){cout<<15<<endl;}
 if (K==32){cout <<51<< endl;}
 
 
}

Measured memory_bytes: 256
ARRAY = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k = int(input())

print(ARRAY[k - 1])

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define P pair<ll,ll>
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;cin>>s;
  if(s=="AAA"||s=="BBB") print("No");else print("Yes");
  return 0;
}


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

using namespace std;

#define INF 1000007
#define MOD 1000000007
#define int long long int
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
int mpow(int N, int P, int M) //繰り返し自乗法
{
    if (P == 0)
        return 1;
    if (P % 2 == 0)
    {
        int t = mpow(N, P / 2, M);
        return t * t % M;
    }
    return N * mpow(N, P - 1, M) % M;
}
signed main()
{
    string b;
    cin >> b;
    if (b == "A")
    {
        cout << "T" << endl;
    }
    else if (b == "T")
    {
        cout << "A" << endl;
    }
    else if (b == "C")
    {
        cout << "G" << endl;
    }
    else
    {
        cout << "C" << endl;
    }
}


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

int main(){
	string s;
	bool ans = false;
	cin >> s;
	if(s.length() > 2){
		for(int i=0; i<s.length()-2; i++){
			if(s[i] == s[i+1] || s[i] == s[i+2]){
				ans = true;
				cout << i+1 << " " << i+3 << endl;
				break;
			}
		}
	} else{
		if(s[0] == s[1]){
			ans = true;
			cout << 1 << " " << 2 << endl;
		} 
	}
	if(ans == false) cout << -1 << " " << -1 << endl;
	return 0;
}

Measured memory_bytes: 512
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		// 出力
        boolean cok = false;
        boolean fok = false;
        for(int i=0; i<s.length(); i++){
            if(String.valueOf(s.charAt(i)).equals("C")){
                if(cok == false){
                cok = true;
                }
            }
            else if(cok == true && String.valueOf(s.charAt(i)).equals("F")){
                fok = true;
            }
        }
        if(fok){
		System.out.println("Yes");
        }
        else{
System.out.println("No");
        }
	}
}

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

int main() {
  int n;
  cin>>n;
  vector<int> V;
  rep(i,n){
    int v;
    cin>>v;
    V.push_back(v);
  }
  vector<int> C;
  rep(i,n){
    int c;
    cin>>c;
    C.push_back(c);
  }
  
  int ans=0;
  rep(i,n)
    if(V[i]>C[i]) ans+=V[i]-C[i];
  
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int  main(){
	int n;
	int a[100];
cin>>n;
	for(int i=0;i<n;i++)
	cin>>a[i];
	for(int j=n-1;j>=0;j--){
		if(j!=0)
	cout<<a[j]<<' ';
		else cout<<a[j]<<endl;
	} 
	return 0;
}


Measured memory_bytes: 3092