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

using namespace std;

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

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

using namespace std;

int n;
pair<int, int> in[110000];
int maxb[110000];
int mine[110000];
set<int> ep;

int maxbr[110000];
int miner[110000];

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

	int ans = 0;
	REP(i,n) {
		scanf("%d %d", &in[i].first, &in[i].second);
	}

	sort(in,in+n);

	maxb[n] = -1;
	mine[n] = 1000000001;

	for (int i = n-1; i >= 0; i--) {
		maxb[i] = max(maxb[i+1], in[i].first);
		mine[i] = min(mine[i+1], in[i].second);
	}

	maxbr[0] = -1;
	miner[0] = 1000000001;

	for (int i = 1; i <= n; i++) {
		maxbr[i] = max(maxbr[i-1], in[i-1].first);
		miner[i] = min(miner[i-1], in[i-1].second);
	}

	for (int i = 0; i < n; i++) {
		int allt = in[i].second - in[i].first + 1;

		int bb = max(maxbr[i], maxb[i+1]);
		int ee = min(miner[i], mine[i+1]);
		int rest = max(0, ee - bb + 1);
		ans = max(ans, allt + rest);
	}

	for (int i = 1; i <= n; i++) {
		int le = 0, ri = 0;
		le = max(0, miner[i] - maxbr[i] + 1);
		if (i != n) ri = max(0, mine[i] - maxb[i] + 1);
		ans = max(ans, le+ri);
	}

	printf("%d\n",ans);
}

Measured memory_bytes: 2560
#include<iostream>
#include <algorithm>
#include<string>
#include<math.h>
using namespace std;

int main(void) {
	int D[3],K;
	cin >> D[0] >> D[1] >> D[2] >>K;
	sort(D, D + 3);
	cout << D[1]+D[0] +pow(2.0,K)*D[2]<<endl;
	return 0;
}

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

import numpy

def main():
  n = int(input())
  la = sorted(list(map(int, input().split())))
  a_max = max(la)
  dp = numpy.ones(a_max + 1)
  counts = numpy.zeros(a_max + 1)
  for a in la:
    counts[a] += 1
    if counts[a] < 2:
      dp[2*a::a] = 0
  print(len([a for a in la if dp[a]==1 and counts[a] == 1]))

if __name__=='__main__':
  main()



Measured memory_bytes: 51468
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define PI 2 * acos(0.0)
#define MAX 1000000
#define INF 1000000 
#define M 1000000007
using namespace std;
set<ll> s1;
void dfs(ll s,ll ans,vector<ll> adj[],ll visited[]){
        if (visited[s]){
            return;
        }
        visited[s] = 1;
        s1.insert(s);
        for (auto u: adj[s]) {
             dfs(u,ans,adj,visited);
        }
} 
int main(){
    FAST
    ll N,m;
    cin>>N>>m;
    ll visited[N+1];
    memset(visited,0,sizeof(visited));
    vector<ll> adj[N+1];
    set< pair<ll,ll> > p;
    while(m--){
        ll x,y;
        cin>>x>>y;
        p.insert({x,y});
    }
    for(auto x : p){
        ll a = x.first;
        ll b = x.second;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    ll ans1 = 0;
    for(ll i = 1;i<=N;i++){
        ll x1 = 0;
        dfs(i,x1,adj,visited);
        ll y = s1.size();
        ans1 = max(ans1,y);
        s1.clear();
    }
    cout<<ans1<<endl;
}


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

#define ll long long
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define viit vector<int>::iterator
#define MOD 1000000007
#define endl "\n"
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define repe(i, a, b) for (int i = (a); i <= (b); i++)
#define repd(i, a, b) for (int i = (a); i >= (b); i--)
#define modm(a, m) (((a)%m + m) % m)
#define mod(a) modm(a, MOD)
#define inp(type, n) \
    type n;          \
    cin >> n
#define inp2(type, n, m) \
    type n, m;           \
    cin >> n >> m

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    inp2(int, H, W);
    ll a[H][W];
    char c;
    rep(i, 0, H) {
        rep(j, 0, W) {
            cin>>c;
            a[i][j] = c == '.';
        }
    }
    rep(i, 1, H) a[i][0] *= a[i - 1][0];
    rep(i, 1, W) a[0][i] *= a[0][i - 1];
    rep(i, 1, H) {
        rep(j, 1, W) {
            a[i][j] *= mod(mod(a[i-1][j]) + mod(a[i][j-1]));
        }
    }
    cout<<a[H-1][W-1];
    return 0;
}


Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define gcd __gcd
#define in(a) scanf("%d",&a)
#define in2(a,b) scanf("%d%d",&a,&b)
#define in3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define read(v,i,n) for(i=0;i<n;i++)in(v[i])
#define twod(mat,i,j,n,m) rep(i,n){rep(j,m)in(mat[i][j]);}
#define sc(ch) scanf("%c",&ch)
#define sstr(str) scanf("%s",str)
#define pr(n) printf("%d ",n)
#define out(n) printf("%d\n",n)
#define llin(a) cin >> a
#define llpr(a) cout << a << " "
#define llout(a) cout << a << "\n"
#define yes printf("YES\n")
#define no printf("NO\n")
#define lin printf("\n")
#define DEBUG(x) cout << #x << " : " << x << endl;
#define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
#define ck printf("continue\n")
#define all(vec) vec.begin(),vec.end()
#define asc(vec) sort(vec.begin(),vec.end())
#define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
#define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
#define tf(mytuple) get<0>(mytuple)
#define ts(mytuple) get<1>(mytuple)
#define tt(mytuple) get<2>(mytuple)
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define viii vector<pair<pair<int,int>,int> >
#define vvii vector<vector<pair<int,int> > >
#define lp(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define M 1000000007
//check the limits, man
// read the constraint properly (ll vs int)
const int N = (1<<12);
typedef long long int ll;
int dp[N],key[N],v[N];
int main()
{
    int n,m,k,a,b,i,x;
    in2(n,m);
    rep(i,m)
    {
        in2(a,b);
        v[i]=a;
        while(b--)
            in(x),x--,key[i]=(key[i]|(1<<x));
    }
    k=(1<<n);
    int mask;
    fill(dp+1,dp+k,M);
    rep(mask,k)
    {
        rep(i,m)
        {
            a=(mask|key[i]);
            dp[a]=min(dp[a],dp[mask]+v[i]);
        }
    }
    if(dp[k-1]==M)
        dp[k-1]=-1;
    out(dp[k-1]);
}





Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

const int mod=1000000007;

void calc(int index,int *edge,int w,int *now,int *next){
  if(index>=w-1){
    int i;
    for(i=0;i<w;i++){
      if(i+1<w && edge[i]){
	next[i]+=now[i+1];
      } else if(i-1>=0 && edge[i-1]){
	next[i]+=now[i-1];
      } else {
	next[i]+=now[i];
      }
      next[i]%=mod;
    }
    return;
  }
  calc(index+1,edge,w,now,next);
  edge[index]=1;
  calc(index+2,edge,w,now,next);
  edge[index]=0;
  return;
}

void run(void){
  int h,w,k;
  scanf("%d%d%d",&h,&w,&k);
  int *dp=(int *)calloc(2*w,sizeof(int));
  int now=0;
  dp[0]=1;
  for(int i=1;i<=h;i++){
    int next=now^w;
    for(int j=0;j<w;j++) dp[next+j]=0;
    int edge[8]={0,0,0,0,0,0,0,0};
    calc(0,edge,w,dp+now,dp+next);
    now=next;
  }
  printf("%d\n",dp[now+k-1]);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 128
import numpy as np
# 複数個格納
# A B = map(int, input().split())
# 行列化
# A = np.array(A)
# A=A.reshape(1,-1)
# A=A.T
#行列の比較
#C=((A%2 == vector0).all())


A = int(input())
B = int(input())
C = int(input())
X = int(input())

gohyaku=(np.arange(0,500*A+1,500)).reshape(1,-1)
hyaku=(np.arange(0,100*B+1,100)).reshape(1,-1)
goju=(np.arange(0,50*C+1,50)).reshape(1,-1)


gohyaku1=X-(gohyaku+hyaku.T)
count=0
for i in range(A+1):
    for k in range(B+1):
        if 0 <= gohyaku1[k,i] <= C*50:
            count=count+1

print(count)



Measured memory_bytes: 12500
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
char s[N][5];
int main(){
	int n,a,b,c;
	cin>>n>>a>>b>>c;
	for(int i=1;i<=n;i++)	scanf("%s",s[i]+1); 
	string ans="";
	
	for(int i=1;i<=n;i++){
		if(s[i][1]=='A'&&s[i][2]=='B'){
			if(a>b){
				a--;b++;
				ans+='B';
			}
			else if(a<b){
				a++;b--;
				ans+='A'; 
			}
			else {
				if(s[i+1][1]=='A'){
					a++;b--;
					ans+='A';
				}
				else{
					a--;b++;
					ans+='B';
				}
			}
		}
		else if(s[i][1]=='A'&&s[i][2]=='C'){
			if(a>c){
				a--;c++;
				ans+='C';
			}
			else if(a<c){
				a++;c--;
				ans+='A'; 
			}
			else {
				if(s[i+1][1]=='A'){
					a++;c--;
					ans+='A';
				}
				else{
					a--;c++;
					ans+='C';
				}
			}
		}
		else {
			if(b>c){
				b--;c++;
				ans+='C';
			}
			else if(b<c){
				b++;c--;
				ans+='B'; 
			}
			else {
				if(s[i+1][2]=='C'){
					b--;c++;
					ans+='C';
				}
				else{
					b++;c--;
					ans+='B';
				}
			}
		} 
		if(a<0||b<0||c<0) return cout<<"No"<<endl,0;
	}
	puts("Yes");
	int t=ans.size();
	for(int i=0;i<t;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 4312
#include<cstdio>
#include<cstring>

using namespace std;

int a[200011];

inline int Max(int a,int b){
	return a>b?a:b;
}

int main(){
	int n;long long ans=0;scanf("%d",&n);
	int lst=0;//所有在前面都比他矮 
	for(int i=1;i<=n;i++) {
		int x;scanf("%d",&x);
		ans+=Max(0,lst-x);
		lst=Max(x,lst);
	}
	return printf("%lld",ans),0;
}


Measured memory_bytes: 1728
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve():
    N, M = map(int, input().split())
    if N == M:
        print("Yes")
    else:
        print("No")


def main():
    solve()


if __name__ == '__main__':
    main()


Measured memory_bytes: 9988
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		ArrayList <Deque<Integer>> deques = new ArrayList <Deque<Integer>>();  //DequeのArrayListを生成
		try (Scanner sc = new Scanner (System.in)){
			int n = sc.nextInt();
			for (int i=0; i<n; i++) {
				deques.add(new ArrayDeque<Integer>());  //n個のdequeを追加
			}
			int times = sc.nextInt();
			for (int i=0; i<times; i++) {
				int request = sc.nextInt();  //命令 0 push 1 top 2 pop
				int deq = sc.nextInt();  //何個目のdeque
				switch (request) {
				//push(deq,x)
				case 0:
					int x = sc.nextInt();
					deques.get(deq).addFirst(x);
					break;
				//top(deq)
				case 1:
					if (deques.get(deq).size() != 0) { //空じゃなかったら
						System.out.println(deques.get(deq).peek());
					}
					break;
				//pop(deq)
				case 2:
					if (deques.get(deq).size() != 0) { //空じゃなかったら
						deques.get(deq).pop();
					}
					break;

				}
			}
		}
	}
}



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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N, Q;
    string S;
    vector<ll> ruiseki;
    cin >> N >> Q;
    cin >> S;
    ruiseki.resize(N);
    rep2(i, 1, N) {
        ruiseki[i] = ruiseki[i - 1] + (S[i - 1] == 'A' && S[i] == 'C');
    }
    rep(i, Q) {
        ll l, r;
        cin >> l >> r;
        cout << ruiseki[r - 1] - ruiseki[l - 1] << endl;
    }
    return 0;
}


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

#define ll long long
const int N=2e5+5;
int ar[N],br[N];
int main() {
    int n;
    cin>>n;
    for(int i=1; i<=n; ++i) {
        cin>>ar[i]>>br[i];
    }
    sort(ar+1,ar+n+1);
    sort(br+1,br+n+1);
    if(n%2) {
        int x=(n+1)/2,y=(n+1)/2;
        cout<<br[y]-ar[x]+1<<endl;
    } else {
        int x=n/2,y=(n/2)+1,ans;

        if(ar[x]+br[y]>=ar[y]+br[x]) {
            ans=br[y]-ar[y]+1;
            ans+=(br[x]+br[y])-(ar[x]+br[y]+1)+1;
        } else {
            ll d=min(br[y]-ar[y]+1,br[x]-ar[x]+1);
            ans=d+max(br[y]-ar[y],br[x]-ar[x]);
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 5176
#include <bits/stdc++.h>
using namespace std;
signed main() {
	long long L, R;
	cin >> L >> R;
	long long a, b;
	a = 999999999999;
	for (long long i = L; i < R; i++) {
		for (long long j = i+1; j <= R; j++){
			b = (i * j) % 2019;
			if (b == 0) {
				cout << 0 << endl;
				return 0;
			} 
			else if (a > b) {
				a = b;
			}
		}
	}
	cout << a << endl;
	return 0;
}

Measured memory_bytes: 256
/**
 *      ABc 107 C
 *      author  : kyomukyomupurin
 *      created : 2018-09-19 08:45:45
**/

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, K; cin >> N >> K;
    int x[N] = {};
    for (int i = 0; i < N; ++i) cin >> x[i];

    int answer = 1000000000;
    

    if (N == K){
        cout << min(abs(x[N - 1] - x[0]) + abs(x[0]), abs(x[N - 1] - x[0]) + abs(x[N - 1])) << '\n'; return 0;
    }

    for (int i = 0; i <= N - K; ++i) {
        int left = x[i]; int right = x[i + K - 1];

        int sum1 = abs(right - left) + abs(left);
        int sum2 = abs(right - left) + abs(right);
        /*
        int sum1 = abs(x[i + K - 1] - x[i]) + abs(x[i + K - 1]);
        int sum2 = abs(x[i + K - 1] - x[i]) + abs(x[i]);
        */
        int min1; sum1 > sum2 ? min1 = sum2 : min1 = sum1;
        //ll min1 = min(sum1, sum2);
        if (min1 < answer) answer = min1;
    }
    cout << answer << '\n';

    return 0;
}


Measured memory_bytes: 640
def main():
    alphabet = list(chr(i)for i in range(97, 123))
    n = int(input())
    ans = ''
    while n > 0:
        n -= 1
        ans = chr(ord('a') + (n % 26)) + ans
        n = n//26

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9040
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi#, gcd
from fractions import gcd
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))


def stoli(s, sep = ''):
    """ 文字列と区切り文字(列)を受け取り、
    整数のリストにして返す """
    if sep == None or sep == '':
        return list(map(int, list(s)))

    ls = []
    for e in s.split(sep):
        if e is None or e == '':
            continue
        else:
            ls.append(e)

    return list(map(int, ls))


def seg_count_all(A: list) -> dict:
    """ 整数リスト A を受け取り、
    リスト中の任意の整数 A[i] で挟まれた区間の数を辞書として返す """
    assert A is not None, "S は None でない"
    N = len(A)
    cnt = {}  # これまでに出現した A[i] の数
    res = {}  # A[i] で囲まれた区間の数
    for i in range(N):
        if A[i] in cnt:
            res[A[i]] += cnt[A[i]]  # 今回出現した A[i] を右端として、左端の候補が cnt 個ある
            cnt[A[i]] += 1
        else:
            res[A[i]] = 0
            cnt[A[i]] = 1

    return res


def main():
    N, P = ILI()
    S = IS()

    d = stoli(S)
    
    # 下 1 桁目の数字を d[0] に変更
    d.reverse()

    if 10%P == 0:
        assert P == 2 or P == 5
        ans = 0
        for l in range(N):
            # 部分文字列の末尾の数字で判定
            if d[l] % P == 0:
                ans += N-l  # l を固定して r を [l,N) の N-1 箇所から選ぶ
        print(ans)
        return 0

    # 各桁の数を P で割った余り md を求める
    # md[i] := (d[i] * 10^i) % P
    md = [0] * N
    ten = 1
    for i in range(N):
        md[i] = (d[i] * ten) % P
        ten *= 10
        ten %= P  # 10 と P は互いに素
    
    # md の mod P の塁積和を求める
    sum = [0] * N
    sum[0] = md[0]
    for i in range(1,N):
        sum[i] = (sum[i-1] + md[i]) % P

    # mod P の塁積和の数字が同じ区間は、差が 0 なので P の倍数となる
    ans = 0    
    cnt = seg_count_all(sum)  # sum[i] ごとにグメントを数え上げる
    for k in cnt:
        ans += cnt[k]
    ans += sum.count(0) # sum[i] == 0 のときは 1 文字で成り立つ

    print(ans)
    return 0


if __name__ == '__main__':
    main()


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

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

int main(void) {
    int K;
    cin>>K;

    vector<string> ans;

    for(int i = 1;i <= 9;i++) {
        char num = '0';
        string s = "";
        ans.push_back(s+char(num+i));
    }

    for(int i = 0;ans.size() <= K;i++) {
        string prefix = ans[i];
        char num = prefix[prefix.size()-1];
        if(num == '0') {
            ans.push_back(prefix+num);
            ans.push_back(prefix+char(num+1));
        } else if(num == '9') {
            ans.push_back(prefix+char(num-1));
            ans.push_back(prefix+num);
        } else {
            ans.push_back(prefix+char(num-1));
            ans.push_back(prefix+num);
            ans.push_back(prefix+char(num+1));
        }
    }

    cout<<ans[K-1]<<endl;

    return 0;
}





Measured memory_bytes: 4724
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b;
  cin >> a >> b;
  if(b==1)
    cout << 0 << endl;
  else{
   for(int i=0;i<20;i++){
     if(a*i-i+1>=b){
      cout << i << endl;
      break;
     }
   }
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

    cin >> n;
    ans = 1000 * (n / 500) + 5 * ((n % 500) / 5);
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(500000)
 
N = int(input())
ABC = [list(map(int, input().split())) for i in range(N-1)]
Q, K = map(int, input().split())
D = [0] * (N+1)
L = [[] for i in range(N+1)]
for a, b, c in ABC:
    L[a].append([b, c])
    L[b].append([a, c])
 
 
def dfs(n, np):
    for nc in L[n]:
        if nc[0] == np:
            continue
        else:
            D[nc[0]] = D[n] + nc[1]
            dfs(nc[0], n)
 
 
dfs(K, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(D[x] + D[y])


Measured memory_bytes: 152280
#include <iostream>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e18;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 20000;
constexpr ll nx[8] = {1,0,-1,0,-1,-1,1,1};
constexpr ll ny[8] = {0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b;
    cin >> a >> b;
    if (a*b%2) PRINT("Odd");
    else PRINT("Even");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define range(i, l, r) for(int (i) = (l); (i) < (r); (i)++)
#define reversed_range(i, l, r) for (int (i) = (r) - 1; (i) >= l; (i)--)
using namespace std;
template <typename T>
using vec = vector<T>;
using lint = long long;
using ulint = unsigned long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;

template <typename S, typename T>
ostream& operator <<(ostream& os, pair<S, T> p) {
    os << "(";
    os << p.first << ", " << p.second;
    return os << ")";
}

template <typename T>
ostream& operator <<(ostream& os, vec<T> v) {
    os << "[";
    for (int i = 0; i < v.size() - 1; i++) {
        os << v.at(i) << ", ";
    }
    return os << v.at(v.size() - 1) << "]";
}

template <typename T>
ostream& operator <<(ostream& os, set<T>& s) {
    os << "{";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename T>
ostream& operator <<(ostream& os, unordered_set<T>& s) {
    os << "{";
    auto it_first_item = s.begin();
    cout << *it_first_item;
    for (auto it = ++it_first_item; it != s.end(); it++) {
        cout << ", " << *it;
    }
    return cout << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, map<K, V> m) {
    os << "{";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

template <typename K, typename V>
ostream& operator <<(ostream& os, unordered_map<K, V> m) {
    os << "{";
    auto it_first_item = m.begin();
    cout << it_first_item->first << ": " << it_first_item->second;
    for (auto it = ++it_first_item; it != m.end(); it++) {
        cout << ", " << it->first << ": " << it->second;
    }
    return os << "}";
}

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    lint N, H;
    cin >> N >> H;
    vec<lint> b_list;
    lint max_a = 0;
    range(i, 0, N) {
        lint a, b;
        cin >> a >> b;
        max_a = max(max_a, a);
        b_list.emplace_back(b);
    }
    sort(b_list.begin(), b_list.end(), greater<lint>());
    // cout << b_list << "\n";
    lint min_num_steps = H / max_a + (H % max_a ? 1 : 0);
    lint curr_pref_sum = 0;
    range(i, 0, N) {
        lint b = b_list.at(i);
        curr_pref_sum += b;
        lint num_steps;
        if (curr_pref_sum >= H) {
            num_steps = i + 1;
        }
        else {
            num_steps = (H - curr_pref_sum) / max_a + i + 1
                + ((H - curr_pref_sum) % max_a ? 1 : 0);
        }
        min_num_steps = min(min_num_steps, num_steps);
    }
    cout << min_num_steps << "\n";
    // cout << -10 / 4 << "\n";
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, M;
ll dp[2][3010][2];

void solve() {
	cin >> N >> M;
	rep(i, 1, N + 1) dp[0][i][0] = 1;
	dp[0][0][1] = 1;
	int now = 0, nex = 1;
	rep(i, 0, M) {
		memset(dp[nex], 0, sizeof(dp[nex]));
		if(N == 1) {
			ADD(dp[nex][1][1], dp[now][1][0]);
			ADD(dp[nex][0][1], dp[now][1][0]);
			ADD(dp[nex][1][1], dp[now][0][1]);
			ADD(dp[nex][0][1], dp[now][0][1]);
			ADD(dp[nex][1][1], dp[now][1][1]);
			ADD(dp[nex][0][1], dp[now][1][1]);
		}
		else {
			rep(j, 0, N + 1) {
				rep(k, 0, 2) {
					if(!dp[now][j][k]) continue;
					if(j == 0) {
						ADD(dp[nex][j][k], dp[now][j][k]);
						ADD(dp[nex][j + 1][k], dp[now][j][k]);
					}
					else if(j == N) {
						ADD(dp[nex][j][k], dp[now][j][k]);
						ADD(dp[nex][j - 1][k], dp[now][j][k]);
					}
					else {
						ADD(dp[nex][j + 1][k], dp[now][j][k]);
						if(j == 1) ADD(dp[nex][j][1], dp[now][j][k] % mod);
						else ADD(dp[nex][j][k], dp[now][j][k] % mod);
						ADD(dp[nex][j][k], dp[now][j][k] % mod);
						if(j == 1) ADD(dp[nex][j - 1][1], dp[now][j][k]);
						else ADD(dp[nex][j - 1][k], dp[now][j][k]);
					}
				}
			}
		}
		swap(now, nex);
	}
	ll res = 0;
	rep(i, 0, N + 1) {
		ADD(res, dp[now][i][1]);
	}
	cout << res << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<cstdio>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ppi pair<pii,int>
#define pip pair<int,pii>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define inf 1000000001
#define inf1 1000000000000000001
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 1000005
#define mid(l,r) l+(r-l)/2
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
void mad(ll &a,ll b){a=(a+b)%mod;if(a<0)a+=mod;}
ll gcd(ll a,ll b){ if(!a)return b;return gcd(b%a,a);}

void solve(){
	int n;
	cin>>n;
	int k;
	cin>>k;
	int a[n];
	rep(i,n)cin>>a[i];
	int l=1,r=1e9;
	while(l<r){
		int m=mid(l,r);
		int cur=0;
		for(int i=0;i<n;i++){
			if((a[i])<=m)continue;
			int c=(a[i]+m-1)/m-1;
			cur+=c;
		}
		//cout<<cur<<" "<<m<<"\n";
		if(cur<=k)r=m;
		else l=m+1;
	}
	cout<<l;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
}

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


void solve(long long N, std::vector<long long> a){
    int average = std::accumulate(a.begin(), a.end(), 0.0)/a.size();
    int cost = 0;
    int cost2 = 0;
    for (int i = 0; i < N; i++) {
	cost += pow(a[i]-average, 2);
	cost2 +=pow(a[i]-(average+1), 2);
    }
    cout << min(cost, cost2) << endl;
}

// Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&a[i]);
    }
    solve(N, std::move(a));
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int main(){
    LL N;
    cin>>N;
    LL M=N;
    LL A=0;
    while(M!=0){
          A+=(M%10);
          M/=10;
    }
    if(N%A==0){
       cout<<"Yes"<<endl;
    }else{
       cout<<"No"<<endl;
    }
	return(0);
}

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

class Dyce{
    int Top, Bottom, North, East, West, South;
    int temp;
public:
    Dyce(){
        reset(1,2,3);
    }
    Dyce(int iTop, int iSouth, int iEast){
        reset(iTop, iSouth, iEast);
    }
    void reset(int iTop, int iSouth, int iEast);
    int getTop(){return Top;}
    void printNow();
    void toNorth();
    void toEast();
    void toWest();
    void toSouth();
    void toRight();
    void toLeft();
};

void Dyce::reset(int iTop, int iSouth, int iEast){
    Top= iTop;//Top
    Bottom = 7-iTop;//Bottom
    South = iSouth;//South
    North = 7-iSouth;//North
    East = iEast;//East
    West = 7-iEast;//West
}

void Dyce::toNorth(){
    temp = Top;
    Top = South;
    South = Bottom;
    Bottom = North;
    North = temp;
}

void Dyce::toSouth(){
    temp = Top;
    Top = North;
    North = Bottom;
    Bottom = South;
    South = temp;
}

void Dyce::toEast(){
    temp = Top;
    Top = West;
    West = Bottom;
    Bottom = East;
    East = temp;
}

void Dyce::toWest(){
    temp = Top;
    Top = East;
    East = Bottom;
    Bottom = West;
    West = temp;
}

void Dyce::toRight(){
    temp = North;
    North = West;
    West = South;
    South = East;
    East = temp;
}

void Dyce::toLeft(){
    temp = North;
    North = East;
    East = South;
    South = West;
    West = temp;
}

void Dyce::printNow(){
    cout<<"Top"<<Top<<endl;
    cout<<"North"<<North<<endl;
    cout<<"Bottom"<<Bottom<<endl;
    cout<<"South"<<South<<endl;
    cout<<"East"<<East<<endl;
    cout<<"West"<<West<<endl;
}

int main(int argc, const char * argv[])
{
    
    Dyce oDyce(1,2,3);
    int sum;
    
    for(int n;cin>>n,n;){
        oDyce.reset(1,2,3);
        sum = 0;
        sum += oDyce.getTop();
        while(n--){
            string s;cin>>s;
            if(s=="North"){
                oDyce.toNorth();
            }else if(s=="South"){
                oDyce.toSouth();
            }else if(s=="East"){
                oDyce.toEast();
            }else if(s=="West"){
                oDyce.toWest();
            }else if(s=="Right"){
                oDyce.toRight();
            }else if(s=="Left"){
                oDyce.toLeft();
            }
            sum += oDyce.getTop();
        }
        cout<<sum<<endl;
    }
    return 0;
}

Measured memory_bytes: 1216
#include<stdio.h>
int main(void)
{
	int H, W, i, j;
	while(1){
		scanf("%d %d",&H,&W);
		if(H==0 && W==0){
			break;
		}
		for(i=1;i<=H;i++){
			for(j=1;j<=W;j++){
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
	
	return 0;
}
	

Measured memory_bytes: 572
for _ in range(100000):
    H,W = map(int, input().split())
    if H+W==0:
        exit()
    W_w = '#' + '.'*(W-2) + '#'
    W_f = '#' * W
    print(W_f)
    for i in range(H-2):
        print(W_w)
    print(W_f)
    print()


Measured memory_bytes: 5616
#include <stdio.h>

int main(void)
{
    int a,i,j,k,sum;
    sum=0;

    scanf("%d%d%d",&i,&j,&k);
    for(a=i;a<=j;a++)
    {
        if((k%a)==0)
        sum+=1;
    }
    printf("%d\n",sum);

    return 0;
}

Measured memory_bytes: 596
#include<cstdio>
#include<set>
using namespace std;
int n,k,f[2345678],ct,as,is,as2;
set<int> s;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&f[i]);
	for(int i=2;i<=k;i++)as+=f[i]<f[i-1];
	for(int i=1;i<=k;i++)s.insert(f[i]);
	if(as==0)is=1;else as2=1;
	for(int i=k+1;i<=n;i++)
	{
		int fg=0;
		if(*s.lower_bound(-100)!=f[i-k])fg=1;
		s.erase(f[i-k]);
		s.insert(f[i]);
		if(s.lower_bound(f[i]+1)!=s.end())fg=1;
		as-=f[i-k+1]<f[i-k];
		as+=f[i]<f[i-1];
		if(as==0)is=1;
		else as2+=fg;
	}
	printf("%d\n",as2+is);
}

Measured memory_bytes: 10368
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int a, b;
  cin >> a >> b;
  cout << a * b << endl;
}


Measured memory_bytes: 3560
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <sstream>
#include <fstream>

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

using namespace std;
typedef long long ll;
int N;

ll act[100010][3];

ll dp[100010][3];


int main() {
  cin >> N;
  
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 3; ++j) {
      cin >> act[i][j];
    }
  }
  
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
	if (j == k) continue;
	dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + act[i][k]);
      }
    }
  }

  ll ans = 0;
  for (int i = 0; i < 3; ++i) {
    ans = max(ans, dp[N][i]);
  }

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


Measured memory_bytes: 4992
function main()
  n,k=parse.(split(readline()))
  dp=zeros(Int,n,k)
  for j=1:k;dp[1,j]=1;end
  for i=2:n,j=1:k,l=1:k
    if j==l;continue;end
    dp[i,j]+=dp[i-1,l]
  end
  print(sum(dp[n,:]))
end
main()

Measured memory_bytes: 152328
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

def cmb(n, k):
    if k < 0 or k > n: return 0
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6  # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

N, K = lr()
K = min(K, N-1)
x = fact[N] * fact_inv[0:K+1] % MOD * fact_inv[N-K:N+1][::-1] % MOD
y = fact[N-1] * fact_inv[0:K+1] % MOD * fact_inv[N-K-1:N][::-1] % MOD
answer = (x * y % MOD).sum()
print(answer % MOD)


Measured memory_bytes: 53576
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define nl cout<<endl
 
#define pii pair<ll,ll>
#define vi  vector<ll>
#define vii vector<pii>
#define mi  map<ll,ll>
#define all(a)  (a).begin(),(a).end()
 
#define pb push_back
#define ff first
#define ss second
#define hell 1000000007
 
#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;
#define N 300009
 
ll power(ll a,ll b,ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}
int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll n;cin>>n;
	string a;cin>>a;
	ll cnt=0;
	for(ll i=0;i<=n-3;i++)
	{
		if(a[i]=='A' and a[i+1]=='B' and a[i+2]=='C')
		cnt++;
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

vector<int> v[225816];
priority_queue<int, vector<int>, greater<int> > pq;

int main(void){
	int h,w,n,i,j,x,y,ans,r=0;
	cin >> h >> w >> n;
	ans = h;
	for(i=0; i<n; ++i){
		cin >> x >> y; --x; --y;
		v[y].push_back(x);
	}
	for(i=0; i<w; ++i){
		v[i].push_back(h);
		sort(v[i].begin(),v[i].end());
	}
	for(j=(v[0].l_ength()-1); j>=0; --j){
		if(v[0][j]>0){
			pq.push(v[0][j]);
		}
	}
	for(i=0; i<h; ++i){
		if(pq.top()==i){
			ans = i;
			break;
		}
		if(!((!v[r+1].l_ength()) || (upper_bound(v[r+1].begin(),v[r+1].end(),i+1)-lower_bound(v[r+1].begin(),v[r+1].end(),i+1)))){
			++r;
			for(j=(v[r].l_ength()-1); j>=0; --j){
				if(v[r][j]>i){
					pq.push(v[r][j]);
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 12924
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  long long t[n];
  long long sum = 0;
  for(int i = 0; i < n; i++){
    cin >> t[i];
    sum += t[i];
  }
  int m; cin >> m;
  for(int i = 0; i < m; i++){
    int p;
    long long x;
    cin >> p >> x;
    cout << sum - t[p-1] + x << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main()
{
int a,b,c,d,i,j;
scanf("%d %d",&a,&b);
for(i=0;i<a;++i)  {j=pow(10,i);
                   c=c+b*j;}
for(i=0;i<b;++i)  {j=pow(10,i);
                   d=d+a*j;}
  if(c>d) printf("%d",c);
  else printf("%d",d);
return 0;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  int A[2][N];
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < N; j++) {
      cin >> A[i][j];
    }
  }
  int dp[2][N];
  dp[0][0] = A[0][0];
  dp[1][0] = A[0][0] + A[1][0];
  for (int i = 1; i < N; i++) {
    dp[0][i] = dp[0][i - 1] + A[0][i];
    dp[1][i] = max(dp[0][i], dp[1][i - 1]) + A[1][i];
  }
  cout << dp[1][N - 1];
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String S = sc.next();
        S = S.replaceAll("eraser", "");
        S = S.replaceAll("erase", "");
        S = S.replaceAll("dreamer", "");
        S = S.replaceAll("dream", "");
        if (S.length() == 0) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}



Measured memory_bytes: 28504
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
//typedef __int128_t lll;
using namespace std;

int main(int argc, char const *argv[]) {
  ll x, y, a, b, c;std::cin >> x >> y >> a >> b >> c;
  vll p(a), q(b), r(c);

  re(i, a) scanf("%lld", &p[i]);
  re(i, b) scanf("%lld", &q[i]);
  re(i, c) scanf("%lld", &r[i]);

  sort(all(p));reverse(all(p));
  sort(all(q));reverse(all(q));
  sort(all(r));reverse(all(r));

  multiset<ll> A, B, C;
  ll ans = 0, s = 0;
  for(int i=0;i<x;i++) s+=p[i], A.insert(p[i]);
  for(int i=0;i<y;i++) s+=q[i], B.insert(q[i]);
  ans = s;

  for(int i=0;i<min(c, x+y);i++){
    if(A.size()==0){
      s -= *B.begin();
      B.erase(B.begin());
    }else if(B.size()==0||*A.begin()<*B.begin()){
      s -= *A.begin();
      A.erase(A.begin());
    }else{
      s -= *B.begin();
      B.erase(B.begin());
    }
    s += r[i];
    ans = max(s, ans);
  }

  std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 11008
N, K = map(int, input().split())
H_list = list(map(int, input().split()))
INF = 1 << 100
dp = [INF] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, K + 1):
        if i - j < 0: break
        #print(dp,i,j)
        #print(abs(H_list[i] - H_list[i - j]))
        dp[i] = min(dp[i - j] + abs(H_list[i] - H_list[i - j]), dp[i])
print(dp[N-1])

Measured memory_bytes: 53472
n, q = map(int, input().split())
s = input()
x = [0] * (n + 1)
for i in range(n):
    x[i + 1] = x[i] + 1 * (s[i:i + 2] == 'AC')
for i in range(q):
    l, r = map(int, input().split())
    print(x[r - 1] - x[l - 1])


Measured memory_bytes: 7748
*XYZ,K = map(int,input().split())
ABC = [list(map(int,input().split())) for i in range(3)]
for a in ABC:
    a.sort(reverse=1)
import heapq
ans = [0]*K
for a in ABC[0]:
    for b in ABC[1]:
        for c in ABC[2]:
            if a+b+c>ans[0]:
                heapq.heappush(ans,a+b+c)
                heapq.heappop(ans)
            else:
                break
ans.sort(reverse=1)
for i in range(K):
    print(ans[i])

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

typedef long long int LL;
typedef long long int LLint;
typedef pair<int,int> intpair;
typedef pair<bool,bool> boolpair;
typedef pair<string,string> strpair;
typedef pair<LL,LL> LLpair;
typedef pair<double,double> doublepair;
typedef pair<float,float> floatpair;
typedef vector<int> intvector;
typedef vector<bool> boolvector;
typedef vector<string> strvector;
typedef vector<LL> LLvector;
typedef vector<double> doublevector;
typedef vector<float> floatvector;
#define wait(sec) usleep((sec) * 1000000)
#define ED return 0;
#define TEST cout << "OK" << endl;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) LL(pow(x,y))
#define INF 999999999
const long long mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<vector<long long int>> vec (M,vector<long long int> (3,0));
    for(long long int i = 0;i < M;i++){
        cin >> vec[i][1] >> vec[i][0];
        vec[i][2] = i;
    }
    vector<long long int> sum (N,1);
    SORT(vec);
//    cout << vec[0][0] << " " << vec[0][1] << endl;
    vector<pair<long long int,long long int>> ans (M,pair<long long int,long long int>(0,0));
    for(long long int i = 0;i < M;i++){
//        cout << sum[vec[i][1]-1] << vec[i][1] << endl;
        ans[i].first = vec[i][2];
        ans[i].second += vec[i][1] * 1000000;
        ans[i].second += sum[vec[i][1]-1];
        sum[vec[i][1]-1]++;
    }
    SORT(ans);
    for(long long int i = 0;i < M;i++){
//        cout << ans[i].second << endl;
        for(long long int j = 11;j > -1;j--){
            cout << (ans[i].second/ipow(10,j))%10;
        }
        cout << endl;
    }
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int, int> pii;
const int mod = (int)1e9 +7;

int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n, ans=0;
	cin >> n;
	
	vector<ll> a(n), b(n);
	rep(i,n) cin >> a[i] >>b[i];
	ll nm = 0;
	repr(i,n-1,0){
		ll ca=a[i] + nm , cb=b[i];
		if(ca % cb){
			nm += cb - (ca % cb);
		}
	}
	
	cout << nm <<endl;
	return 0;

}


Measured memory_bytes: 1792
#include <iostream>

int main(){
  int a1, a2, a3;
  std::cin >> a1 >> a2 >> a3;
  if(a1+a2+a3 > 21)
    std::cout << "bust" << std::endl;
  else
    std::cout << "win" << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<math.h>
#include<algorithm>
using namespace std;

int main() {
	int n,a,b,c,d;
cin>>n>>a>>b>>c>>d;
int ans=min(((n+a-1)/a)*b,((n+c-1)/c)*d);
cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3128
m, dp = gets.to_s.to_i, [0]
(1..m).each {|i|
  cans = (1..6).to_a.map{|j| [6 ** j, 9 ** j, 1] }.flatten.select {|j| i - j >= 0 }.map{|j| i - j }.uniq
  dp.push(cans.map{|j| dp[j] }.min + 1)
}
p dp.last

Measured memory_bytes: 3000