akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int H,W;
int c[11][11];
int V;
struct edge{int to,cost;};
vector<edge> G[SIZE];
int d[SIZE];

void dijkstra(int s){
	priority_queue<P, vector<P>, greater<P>> que;
	fill(d,d+V,INF);
	d[s] = 0;
	que.push(P(0,s));

	while(!que.empty()){
		P p = que.top();que.pop();
		int v = p.second;
		if(d[v] < p.first)continue;
		for(int i=0;i<G[v].size();i++){
			edge e = G[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
}

int main()
{
	cin >> H >> W;
	V = 10;
	int C;
	rep(i,0,10) rep(j,0,10){
		cin >> C;
		//Gは逆辺のグラフ
		G[j].push_back((edge){i,C});
	}
	dijkstra(1);
	int a,ans=0;
	rep(i,0,H) rep(j,0,W){
		cin >> a;
		ans += d[a];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4992
n, m = map(int, input().split())
h = list(map(int, input().split()))
ans = [1] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if h[a] <= h[b]:
        ans[a] = 0
    if h[b] <= h[a]:
        ans[b] = 0
print(sum(ans))


Measured memory_bytes: 20140
<?php
  fscanf(STDIN,'%d%d',$n,$m);
  $s=1e9;
  for($i=0;$i<$n;$i++){
    fscanf(STDIN,'%d',$a);
    $m-=$a;
    $s=min($s,$a);
  }
  echo $n+floor($m/$s);

Measured memory_bytes: 4084
#include "bits/stdc++.h"

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl
#define lint long long
#define yes "Yes"
#define no "No"

typedef pair<int, int> P;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, n; cin>>h>>n;
    vector<int> a(n);
    REP(i,n) cin>>a[i];
    lint wa = accumulate(all(a),0);
    //print(wa);
    if(h<=wa) print(yes);
    else print(no);
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <math.h>
using namespace std;

int main(){
	long long X, deposit = 100;
	cin >> X;

	int i = 0;
	while(X > deposit){
		deposit += deposit*0.01;
		i++;
	}
	cout << i << endl;
	return 0;
}


Measured memory_bytes: 3636
A,B,C,D=map(int,input().split())

def ans164(A, B, C, D):
    while True:
        C=C-B
        if A<=0:
            return"No"
            break
        A=A-D
        if C<=0:
            return "Yes"
            break

print(ans164(A,B,C,D))

Measured memory_bytes: 9040
import math
N,M = map(int,input().split())
mod = 10**9+7

if M == 1:
    print(1)
    exit()

m = M
A = []  #Mの素因数のリスト(今回は必要ない)
B = []  #各素因数で何回割り切れるか
for i in range(2,int(math.sqrt(M))+1):
    if m % i == 0:
        A.append(i)
        c = 0
        while m % i == 0:
            m = m // i
            c += 1
        B.append(c)

if m != 1:
    A.append(m)
    B.append(1)

def p(m,n):
    a = 1
    for i in range(n):
        a = a*(m-i) % mod
    return a

def c(m,n):
    return (p(m,n)*pow(p(n,n),mod-2,mod)) % mod

ans = 1
for i in range(len(B)):
    ans = (ans * c(N-1+B[i],B[i])) % mod

print(ans)

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

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int W,a,b; cin>>W>>a>>b;
	int diff=a-b;
	if(a+W<b) cout << b-a-W << endl;
	else if(b+W<a) cout << a-b-W << endl;
	else cout << 0 << endl;
	return 0;
}


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



int main() {
int N;
cin >> N;
int mon[200];
for(int i = 0; i < N; i++)cin >> mon[i];
int M;
cin >> M;
int drink[200][2];
for(int i = 0; i < M; i++){
cin >> drink[i][0] >> drink[i][1];
drink[i][0]--;
}
int mon2[200];

    for(int i = 0; i < N; i++)mon2[i] = mon[i];

for(int i = 0; i < M; i++){

int kari = 0;
mon2[drink[i][0]] = drink[i][1];
for(int j = 0; j<N; j++){
    kari += mon2[j];
}
cout << kari << endl;
mon2[drink[i][0]] = mon[drink[i][0]];
}




}



Measured memory_bytes: 3640
#include <iostream>
using namespace std;
int main(void){
    
    //変数の宣言
    int W, H, x, y, r;
    
    //h変数の入力
    cin >> W >> H >> x >> y >> r;
    
    //if：条件を与え判定する➡　判定は成立する or 成立しない
    if(x-r < 0 || y-r < 0 || W < x+r || H < y+r){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
    
    return 0;
    
}


/****************************************複数の条件式****************************************************


かつ・AND　➡　&&  ➡　　両方の条件が成立するときのみ成立の所へ行ける
またわ・OR　➡　||　➡　片方の条件が成立する　又は　　両方の条件が成立する　ときは成立の場所へ行ける
        
    
*********************************************************************************************************/


















Measured memory_bytes: 3104
from collections import deque

h, w = map(int, input().split())
a = ''.join(input() + '#' for _ in range(h))
n = len(a)
b = ['#'] * w
w += 1
q = deque()
r = 0
for i in range(n):
  if a[i] == '.':
    b[: 1 - w] = a
    b[i] = 0
    q.append(i)
    while(q):
      i = q.popleft()
      r = max(r, b[i])
      for j in (-1, 1, -w, w):
        j += i
        if b[j] == '.':
          b[j] = b[i] + 1
          q.append(j)
print(r)


Measured memory_bytes: 3316
#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<deque>
#include<vector>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<28)
#define MAX_N 21
#define MAX_M 101
using namespace std;
typedef pair<int,int> ii;


ii ps[MAX_N];
struct P
{
  int index;
  bool finish;
  P(int index=inf,bool finish=false):index(index),finish(finish){}
  bool operator < (const P& a)const
  {
    if(ps[index].second != ps[a.index].second)return ps[index].second > ps[a.index].second;
    return index < a.index;
  }
};


map<string,int> list;
string names[MAX_N];

ii order[MAX_M];
bool fin[MAX_M];
int ans[MAX_M];
vector<P> cust[MAX_M];
int N,M;

int main()
{
  bool f = true;
  while(cin >> N >> M,N|M)
    {
      if(!f)cout << endl;
      f = false;
      rep(i,N)
	{
	  cin >> names[i] >> ps[i].first >> ps[i].second;
	  list[names[i]] = i;
	}
      rep(i,M)cust[i].clear(),fin[i] = false,ans[i] = inf;
      rep(i,M)
	{
	  int k;
	  cin >> order[i].first >> k;
	  order[i].second = i;

	  rep(j,k)
	    {
	      string name;
	      cin >> name;
	      cust[i].push_back(P(list[name]));
	    }
	  sort(cust[i].begin(),cust[i].end());
	}

      sort(order,order+M);



      int phase = order[0].first;
      bool update = true;
      while(update)
	{
	  //cout << "phase : "<< phase << endl;
	  update = false;
	  int choice = inf;
	  rep(i,M)
	    {
	      int cur = order[i].second;
	      if(fin[cur])continue;
	      if(order[i].first > phase)continue;
	      rep(j,cust[cur].size())
		{
		  if(cust[cur][j].finish)continue;
		  update = true;
		  choice = cust[cur][j].index;
		  break;
		}
	      if(update)break;
	      fin[cur] = true;
	    }

    

	  if(!update)
	    {
	      rep(i,M)
		{
		  int cur = order[i].second;
		  if(fin[cur])continue;
		  phase = order[i].first;
		  update = true;
		  break;
		}
	      if(update)continue;
	      break;
	    }
	  //cout << "choice = " << names[choice] <<endl;
	  int S = ps[choice].first;


	  rep(i,M)
	    {
	      int cur = order[i].second;
	      if(fin[cur])continue;
	      if(order[i].first > phase)continue;
	      rep(j,cust[cur].size())
		{
		  if(!cust[cur][j].finish && S > 0 && cust[cur][j].index == choice)
		    {
		      cust[cur][j].finish = true;
		      S--;
		    }
		}
	      if(S <= 0)break;
	    }

	  phase += ps[choice].second;
	  rep(i,M)
	    {
	      int cur = order[i].second;
	      if(fin[cur])continue;
	      bool ok = true;
	      rep(j,cust[cur].size())
		{
		  if(!cust[cur][j].finish)
		    {
		      ok = false;
		      break;
		    }
		}
	      if(ok)ans[cur] = min(ans[cur],phase),fin[cur] = true;
	    }


	}

      rep(i,M)cout << ans[i] << endl;

    }
  return 0;
}

Measured memory_bytes: 1356
declare -r R4=(0 7 5 3 1 8 6 4 2) 

read N Y
(( Y /= 1000 ))

if (( Y >= N )); then
    y=${R4[(Y - N) % 9]}
    x=$(( (Y - N - 4 * y) / 9 ))
    if (( x >= 0 && y >= 0 && x + y <= N )); then
        echo $x $y $((N-x-y))
        exit
    fi
fi
echo -1 -1 -1


Measured memory_bytes: 376
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.Closeable;
import java.io.IOException;
import java.util.NoSuchElementException;
import java.io.InputStream;

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

    static class ASomethingOnIt {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            String S = in.next();
            int ans = 700;
            for (int i = 0; i < 3; i++) {
                if (S.charAt(i) == 'o') ans += 100;
            }
            out.println(ans);
        }

    }

    static class FastScanner implements Closeable {
        private final InputStream in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;

        public FastScanner(InputStream in) {
            this.in = in;
        }

        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte()) return buffer[ptr++];
            else return -1;
        }

        private static boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
            return hasNextByte();
        }

        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public void close() {
            try {
                in.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }
}



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

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

Measured memory_bytes: 3664
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)


int main()
{
    string s;
    int min;
    cin >> s;
    int n = s.length();
    string d[n];
    int f[n-2];
    rep(i,n){
        d[i]=s[i];
    }
    d[0]+=d[1];
    d[0]+=d[2];
    f[0]=atoi(d[0].c_str());
    min=abs(f[0]-753);

    rep(i,n-2){
        d[i]+=d[i+1];
        d[i]+=d[i+2];
        f[i]=atoi(d[i].c_str());
        if(min>abs(f[i]-753)){
            min=abs(f[i]-753);
        }else{
            ;
        }

    }
    printf("%d",min);
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  
  /* input data */
  int N,Y;
  cin >> N >> Y;
  
  /* Judge data */
  bool result = false;
  int xwk,ywk,zwk;
  int z;
  for(int x=0;x<=N;x++){
    for(int y=0;y<=N;y++){
      z=N-x-y;
      if(z>=0 && 10000*x+5000*y+1000*z == Y){
        result = true;
        zwk=z;
        xwk=x;
        ywk=y;
      }
    }
  }
  
  if(result)
    cout << xwk << " " << ywk << " " << zwk << endl;
  else
    cout << -1 <<" "<< -1 << " "<<-1 << endl;
 
  return 0;
}

Measured memory_bytes: 256
n, y = map(int, input().split())
flag = 0
for a in range(n+1):
    s = n-a
    for b in range(s+1):
        c = s-b
        if (a*1000 + b*5000 + c*10000) == y:
            print(c,b,a);    flag = 1
    if flag:
        break
else:
    print(-1,-1,-1)

Measured memory_bytes: 9052
#include<iostream>

using namespace std;
int main()
{

    int N, M, ai, sum = 0;
    cin >> N >> M;
    int i;
    for(i = 0; i < M ; i++)
    {
        cin >> ai;
        sum += ai;
    }
    int reserr = -1;
    int res = N - sum;
    if(res < 0){
        cout << reserr << endl;
    }
    else
    {

        cout << res << endl;
    }

    return 0;
}


Measured memory_bytes: 3612
n = int(input())
s = input()
change = s.count("E")
ans = change
i_o = "dum"
for i in s:
    #print(change)
    if i == "E":
        change -= 1
    if i_o == "W":
        change += 1
    ans = min(change,ans)
    i_o = i
print(ans)

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

int calc(int N) {
    int ret;
    for (ret = 0; 0 < N; ret++) {
        N /= 10;
    }
    return ret;
}

int main(void){
    int N; cin >> N;
    int ans = 0;
    for (int i = 1; i <= N; i++) if (calc(i) % 2) ans++;
    cout << ans << endl;
}


Measured memory_bytes: 256
string = gets.strip

left, right = -1, -1
string.size.times do |i|
  left, right = i + 1, i + 2 if string[i] == string[i + 1]
  left, right = i + 1, i + 3 if string[i] == string[i + 2]
end

puts "#{left} #{right}"


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

#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mk make_pair
#define mod 1000000007
#define mo 998244353
string str;
//map<int, int>::iterator itr; 
ull bin(ull a, ull n) {
    ull res = 1;
    while (n) {
        if (n & 1) res = 1LL * res * a % mo;
        a = 1LL * a * a % mo;
        n >>= 1;
    }
    return res;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;t=1;
    while(t--){
        int n,k;cin>>n>>k;
        int arr[n];
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        for(int i=k;i<n;i++){
            if(arr[i]>arr[i-k]){
                cout<<"Yes"<<"\n";
            }
            else{
                cout<<"No"<<"\n";
            }
        }
        }
    return 0;
}


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

int main() {

  int n;
  cin >> n;
  int ans = 0;
  for(int i=0;i<n;i++) {
    int s;
    cin >> s;

    int flg = 0;   
    for(int j=1;j*j<=s ;j++) {
      if( ((s-j)%(2*j+1) == 0 )){//&& 2*((s-j)/(2*j+1))*j+(s-j)/(2*j+1)+j == s ) {
	//	cout <<s<<" "<< j << endl;
	flg = 1;
	break;
      }
    }
    
    if(flg == 0) ans++;
  }
  cout << ans <<endl;

  return 0;
}

Measured memory_bytes: 1160
#!/usr/bin/env python3
import sys


def solve(A: int, B: int):
    return A * B


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    print(solve(A, B))

if __name__ == '__main__':
    main()


Measured memory_bytes: 9176
#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; 

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
  
#define int long long 
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define precise(x) fixed << setprecision(x) 

const int MOD = 1e9+7;

int mod_pow(int a,int b,int M = MOD)
{
    int res = 1;
    
    while(b)
    {
        if(b&1) res=(res*a)%M;
        a=(a*a)%M;
        b>>=1;
    }
    
    return res;
}

const int N = 2e3+10;
int xx[N];
int yy[N];
int res[N];

void solve()
{
    int n,x,y;
    cin >> n >> x >> y;
    
    for(int i=1;i<=x;i++) xx[i] = x-i;
    for(int i=y;i<=n;i++) yy[i] = i-y;
    
    xx[y] = yy[x] = 1;
    
    int btw = (y-1) - (x+1) + 1;
    
    for(int i=1;i<=(btw+1)/2;i++)
          xx[i+x] = i;
        
    for(int i=1;i<=(btw+1)/2;i++)
          yy[y-i] = i;
    
    for(int i=x+(btw+1)/2+1;i<=n;i++)
         xx[i] = min(i-x,yy[i] + 1);
    
    for(int i=y-(btw+1)/2-1;i>=1;i--)
        yy[i] = min(y-i,xx[i] + 1);
        
    
    for(int i=1;i<=n;i++) 
      for(int j=i+1;j<=n;j++)
    {
        int ans = j-i;
        //through x-y tunnel
        //through y-x tunnel
        ans=min(ans,xx[i]+1+yy[j]);
        ans=min(ans,yy[i]+1+xx[j]);
        res[ans]++;
    }
        
    for(int i=1;i<n;i++) cout << res[i] <<"\n";
}

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

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++) 
#define rep(i,n) for(int i = 0; i < (n); i++)
#define chmin(a,b) if((a)>(b)) (a)=(b); 
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a=a%b;}return max(a,b);
}
int dx[]={0,1,0,-1,1,-1,-1,1};
int dy[]={1,0,-1,0,1,1,-1,-1};
const int MOD = 1e9+7;
const int INF = 1e18+10;

/*----------------------------------------------*/


signed main(){
  int n;
  cin>>n;
  vi h(n);
  rep(i,n) cin>>h[i];
  rep(i,n-1){
    if(h[i]-h[i+1]<=0){
      continue;
    }
    else if(h[i]-h[i+1]==1) h[i+1]++;
    else{
      cout<<"No"<<endl;
      return 0;
    }

  }


  rep(i,n-1)if(h[i]-h[i+1]>0){
    cout<<"No"<<endl;
    return 0;
  }
 
  cout<<"Yes"<<endl;
  
  return 0;
}

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

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if(A + B + C > 21){
        cout << "bust" << "\n";
    } else{
        cout << "win" << "\n";
    }

    return 0;
}

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

using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);

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

    long long dp[n+2][k+1];
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = i == 0 ? 0 : 4e11;
            for (int x = 0; x <= j && x <= i - 1; x++) {
                dp[i][j] = min(dp[i][j], dp[i-x-1][j-x] + max(h[i] - h[i-x-1], 0));
            }
        }
    }

    cout << dp[n+1][k] << endl;

    return 0;
}


Measured memory_bytes: 1024
mod = 10**9+7
h,w = map(int, input().split())

a = [input() for _ in range(h)]
dp = [[0]*w for _ in range(h)]

dp[0][0] = int(a[0][0] == '.')

for i in range(1,h):
    dp[i][0] = int(a[i][0] == ".")*dp[i-1][0]
for j in range(1,w):
    dp[0][j] = int(a[0][j] == ".")*dp[0][j-1]

for i in range(1, h):
    for j in range(1, w):
        dp[i][j] = int(a[i][j] == '.') * (dp[i - 1][j] + dp[i][j - 1])
        dp[i][j] %= mod
# for i in dp:
#     print(*i)

print(dp[h-1][w-1] % mod)




Measured memory_bytes: 43632
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		 Scanner scan = new Scanner(System.in);
	        int A  = scan.nextInt();
	        int B  = scan.nextInt();
	        int C  = scan.nextInt();

	        if(A < B+C){
	        	System.out.println(C - (A-B));
	        }else {
	        	System.out.println(0);
	        }

	}
}


Measured memory_bytes: 21716
#include <stdio.h>
#include <string.h>
#define LEN 100005

typedef struct pp{          
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head, tail, n;

int min(int,int);
P dequeue(void);
void enqueue(P);


int main(){
  int elaps = 0, c;
  int i, q;
  P a ;
  
  
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }

  head = 1;
  tail = n+1;

  while(1){
    if(head == tail)break;
   a = dequeue();
    c = min(q,a.t);
    elaps += c;
    a.t -= c;
    if(a.t>0) enqueue(a);
    else printf("%s %d\n",a.name,elaps);
    }
  return 0;
}

void enqueue(P x){
  Q[tail]=x;
  if(tail+1==LEN)
  tail = 0;
  else tail++;
  }

P dequeue(){
  P x = Q[head];
  if(head+1==LEN)
    head = 0;
  else head++;
  return x;
}

int min(int x,int y){
  if(x>y)return y;
  else return x;
}



Measured memory_bytes: 11900
fn main() {
    let n = read::<usize>();
    let mut p = vec![];
    for i in 0..n {
        let v = read_vec::<i64>();
        let (a, b) = (v[0], v[1]);
        p.push((b, a));
    }
    p.sort();
    let ans = p[0].0 + p[0].1;
    println!("{}", ans);
}

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

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


Measured memory_bytes: 4220
n=int(input())
s=input()
a=[int(s[i])-1 for i in range(n)]

div=[0]*(n+1)
for i in range(1,n+1):
  div[i]+=div[i-1]
  x=i
  while not x&1:
    x>>=1
    div[i]+=1

XOR=0;one=False
for i in range(n):
  one|=a[i]==1
  if div[n-1]<=div[i]+div[n-1-i]:
    XOR^=a[i]
if XOR&1:print(1)
elif one:print(0)
elif XOR&2:print(2)
else:print(0)

Measured memory_bytes: 53192
#include<cstdio>
using namespace std;
#define N 205000
int head[N],cnt,dep[N],l,r,in[N],st[N],n,a,b,ct,st2[N],fg,as1[N],as2[N],is[N];
struct edge{int t,next;}ed[N*2];
void adde(int f,int t){ed[++cnt]=(edge){t,head[f]};head[f]=cnt;ed[++cnt]=(edge){f,head[t]};head[t]=cnt;in[f]++,in[t]++;}
void dfs(int u,int fa){dep[u]=dep[fa]+1;for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs(ed[i].t,u);}
void dfs2(int u,int t,int fa){if(!fg)st[++ct]=u;if(u==t)fg=1;for(int i=head[u];i;i=ed[i].next)if(ed[i].t!=fa)dfs2(ed[i].t,t,u);if(!fg)ct--;}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)scanf("%d%d",&a,&b),adde(a,b);
	dfs(1,0);int mx=0,vl;for(int i=1;i<=n;i++)if(dep[i]>mx)mx=dep[i],vl=i;
	dfs(vl,0);mx=0;int vl2=0;for(int i=1;i<=n;i++)if(dep[i]>mx)mx=dep[i],vl2=i;
	dfs2(vl,vl2,0);
	for(int i=1;i<=ct;i++)is[st[i]]=1;
	for(int i=1;i<=n;i++)if(!is[i]&&in[i]>1){printf("-1\n");return 0;}
	for(int i=1;i<=ct;i++)st2[i]=in[st[i]]-2+(in[st[i]]==1);
	int lb=0;
	for(int i=1;i<=ct;i++)
	{
		for(int j=1;j<=st2[i];j++)as1[lb+j]=lb+j+1;
		as1[lb+st2[i]+1]=lb+1;
		lb+=st2[i]+1;
	}
	lb=0;
	for(int i=ct;i>=1;i--)
	{
		for(int j=1;j<=st2[i];j++)as2[lb+j]=lb+j+1;
		as2[lb+st2[i]+1]=lb+1;
		lb+=st2[i]+1;
	}
	int fg2=0;
	for(int i=1;i<=n;i++)if(as1[i]<as2[i]){fg2=1;break;}else if(as2[i]<as1[i])break;
	if(!fg2)for(int i=1;i<=n;i++)as1[i]=as2[i];
	for(int i=1;i<=n;i++)printf("%d ",as1[i]);
}

Measured memory_bytes: 13696
def parent(i):
    return i//2
def left(i):
    return 2*i
def right(i):
    return 2*i+1

H = int(input())
A = [None] + list(map(int,input().split()))

for i in range(1,H+1):
    print('node {}: key = {}, '.format(i,A[i]), end='')
    if parent(i) >= 1:
        print('parent key = {}, '.format(A[parent(i)]), end='')
    if left(i) <= H:
        print('left key = {}, '.format(A[left(i)]), end='')
    if right(i) <= H:
        print('right key = {}, '.format(A[right(i)]), end='')
    print()



Measured memory_bytes: 5680
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
using ll = long long;

int main()
{
	int h,w,m;
	cin >> h >> w >> m;
	int ans = 0;
	vector<pair<int,int>> vp(m);
	for(int i = 0;i<m;i++)
	{
		cin >> vp[i].first >> vp[i].second;
		vp[i].first--;vp[i].second--;
	}
	vector<int> nowboms(h);	
	vector<int> tmp(w);
	vector<vector<int>> boms(h);
	multiset<int> yoko;
	{
		for(int i = 0;i<m;i++)
		{
			tmp[vp[i].second]++;
			nowboms[vp[i].first]++;
			boms[vp[i].first].push_back(vp[i].second);
		}
		for(int i = 0;i<w;i++)yoko.insert(tmp[i]);
	}
	for(int i = 0;i<h;i++)
	{
		multiset<int> onboms;
		for(int j =0;j<boms[i].size();j++)
		{
			onboms.insert(tmp[boms[i][j]]);
			yoko.erase(yoko.find(tmp[boms[i][j]]));
		}
		if(yoko.size())ans = max(ans,*yoko.rbegin()+nowboms[i]);
		if(onboms.size())ans = max(ans,*onboms.rbegin()+nowboms[i]-1);
		for(int j = 0;j<boms[i].size();j++)
		{
			yoko.insert(tmp[boms[i][j]]);
		}
	}

	cout<<ans<<endl;
}


Measured memory_bytes: 44208
#include <iostream>
#include <cstdlib>

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

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

    b[0]=0;
    b[1]=abs(a[0]-a[1]);

    for(int i=2;i<n;i++)
    {
        b[i]=min(b[i-1]+abs(a[i-1]-a[i]),b[i-2]+abs(a[i-2]-a[i]));
    }

    cout << b[n-1] << endl;
}


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

using namespace std;

#define sz(v)           ((int)((v).size()))
#define clr(v, d)       memset(v, d, sizeof(v))
#define rep(i, v)       for(int i=0; i<sz(v); ++i)
#define lp(i, n)        for(int i=0; i<(int)(n); ++i)
#define lpi(i, j, n)    for(int i=(j); i<(int)(n); ++i)
#define lpd(i, j, n)    for(int i=(j); i>=(int)(n); --i)
#define INF             1000000000

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

void init(){
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main()
{
	init();
	int ans = 1, n;
	string str;
	cin >> n >> str;
	lpi(i, 1, n){
		if(str[i-1] != str[i])
			++ans;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

inline int gi()
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

inline LL gl()
{
	LL f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 3003, mod = 998244353;

int n, m;
int a[N];
LL dp[N][N][3];

int main()
{
	//File("");
	n = gi(), m = gi();
	for (int i = 1; i <= n; i+=1) a[i] = gi();
	dp[0][0][0] = 1;
	for (int i = 1; i <= n; i+=1)
	    for (int j = 0; j <= m; j+=1)
	    {
	        dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][0]) % mod;
	        dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j][0] + dp[i - 1][j][1]) % mod;
	        dp[i][j][2] = (dp[i][j][2] + dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2]) % mod;
	        if (j + a[i] <= m)
	            dp[i][j + a[i]][1] = (dp[i][j + a[i]][1] + dp[i - 1][j][0] + dp[i - 1][j][1]) % mod,
	            dp[i][j + a[i]][2] = (dp[i][j + a[i]][2] + dp[i - 1][j][0] + dp[i - 1][j][1]) % mod;
	    }
	printf("%lld\n", dp[n][m][2] % mod);
	return 0;
}


Measured memory_bytes: 211456
/* I have already deleted My old account because somebody stole my code
and i have no idea how. If you are copying this code atleast make it look different 
Yours Faithfully
Shobhit Yadav */

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

ll X,Y,T;
/*ll freq[200005];*/
void solve(){
	 cin>>X>>Y;
	 bool flag = true;

	 if( ((Y-2*X)%2 != 0) || (Y<2*X) || (Y>4*X) || (4*X -Y)%2 != 0)
	 	flag = false;


	 if(flag)
	 	cout<<"Yes"<<'\n';

	 else
	 	cout<<"No"<<'\n';
}



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
 solve();

	return 0;
}

Measured memory_bytes: 3612
using System;
class P{
    static void Main(){
        int n = int.Parse(Console.ReadLine());
        if (n == 1){
            Console.WriteLine("Hello World");
            return;
        }
        int a, b;
        a = int.Parse(Console.ReadLine());
        b = int.Parse(Console.ReadLine());
        Console.WriteLine(a + b);
    }
}

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

int main() {
  int n;
  cin>>n;
  vector<int> p(n);
  for (int& x: p) cin>>x;
  sort(p.begin(), p.end());
  int res = std::accumulate(p.begin(),p.end(),0) - p.back()/2;
  cout<<res<<endl;
  return 0;
  
}

Measured memory_bytes: 3612
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


class Program
{
    static void Main(string[] args)
    {
        int K = int.Parse(Console.ReadLine());

        if(K % 2 == 1)
        {
            Console.WriteLine((K / 2) * (K / 2 + 1));
        }
        else
        {
            Console.WriteLine((K / 2) * (K / 2));
        }
    }
}



Measured memory_bytes: 11092
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;

int main() {
    int n, cnt = 0; string s; cin >> n >> s;
    rep(i, n-2) {
        if(s.substr(i, 3) == "ABC") cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;

class Seg {
  public:
  int N;
  vi segtree;
  Seg(int n) {
    N = 1;
    int len = 1;
    while(N < n) {
      N *= 2;
      len += N;
    }
    segtree = vi(len,0);
  }
  void build(int idx,int val) {
    int s = sz(segtree) - (N-idx);
    segtree[s] = val;
    while(1) {
      if(s == 0) break;
      s = (s-1)/2;
      segtree[s] = segtree[s*2+1]|segtree[s*2+2];
    }
  }
  int _query(int a,int b,int idx,int l,int r) {
    if(a <= l && r <= b) return segtree[idx];
    if(r <= a || b <= l) return 0;
    int vl = _query(a,b,idx*2+1,l,(l+r)/2);
    int rl = _query(a,b,idx*2+2,(l+r)/2,r);
    return vl|rl;
  }
  int query(int l,int r) {
    int k = _query(l,r+1,0,0,N);
    return __builtin_popcount(k);
  }
};
  
int main() {
  int N;
  cin >> N;
  string s;
  cin >> s;
  Seg seg(N);
  rep(i,N) {
    seg.build(i,1<<(s[i]-'a'));
  }
  int q;
  cin >> q;
  vi ans;
  rep(qi,q) {
    int t;
    cin >> t;
    if(t==1) {
      int i;
      char c;
      cin >> i >> c;
      i--;
      seg.build(i,1<<(c-'a'));
    } else {
      int l,r;
      cin >> l >> r;
      l--;
      r--;
      int k = seg.query(l,r);
      ans.push_back(k);
    }
  }
  rep(i,sz(ans)) {
    cout << ans[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 5124
#include <bits/stdc++.h>
#define INF 1000000007
#define rep(i, N) for(ll i = 0; i < N; i++)
#define rep2(i, j, k) for(ll i = j; i < k; i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define print(x) cout << x << "\n"
#define print2(x, y) cout << x << " " << y << "\n"
#define printv(vec) rep(lp, vec.size()) cout << vec[lp] << " "; print(""); 
#define show(x) cerr << #x << " = " << x << "\n";
#define ALL(v) v.begin(), v.end()
#define SUM(v) accumulate(ALL(v), 0)
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
#define pb(x) emplace_back(x)
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;

const int mod = 998244353;
class mint {
public:
	ll x;
	mint(ll x = 0) : x((x % mod + mod) % mod) {}
	mint operator-() const { 
	  return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}
	friend ostream& operator<<(ostream& os, const mint& m){
		os << m.x;
		return os;
	}
};

ll modpow(ll a, ll n){
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

ll N, M, X;
ll c[15];
ll a[15][15];

ll bit_all(ll bits, ll N){
	vl v(M);
	ll ret = 0;
	rep(i, N){
		if((1LL & bits >> i)){
			rep(j, M) v[j] += a[i][j];
			ret += c[i];
		}
	}
	rep(i, M) if(v[i] < X) return INF;
	return ret;
}

void Main(){
	
	cin >> N >> M >> X;
	rep(i, N){
		cin >> c[i];
		rep(j, M) cin >> a[i][j];
	}
	
	ll ans = INF;
	rep(i, 1 << N){
		ll ret = bit_all(i, N);
		chmin(ans, ret);
	}
	
	if(ans == INF) print(-1);
	else print(ans);

}

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll t = 1;
	//cin >> t;
	rep(i, t) Main();
	return 0;
	
}





Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define P pair<ll, ll>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

void print(Vl vec){
    rep(i, 0, sz(vec)){
        if(i) cout << " ";
        cout << vec[i];
    }
    coel;
}

////////////////////////////////////////////////////////


int main() {
    ll n; cin >> n;
    Vl a(n), b(n), c(n);
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, n) cin >> b[i];
    rep(i, 0, n) cin >> c[i];
    sort(ALL(a));
    sort(ALL(b));
    sort(ALL(c));

    Vl B(n);
    rep(i, 0, n){
        B[i] = c.end() - upper_bound(ALL(c), b[i]);
    }
    for(int i = n-1-1; i >= 0; i--){
        B[i] += B[i+1];
    }
    ll ans = 0;
    rep(i, 0, n){
        auto it = upper_bound(ALL(b), a[i]);
        ans += B[it - b.begin()];
    }
    co(ans);

    return 0;
}


Measured memory_bytes: 3328
n, k = map(int, input().split())
ans = max((n - k + 1) / n, 0)
for a in range(1, min(k, n + 1)):
    cnt = 0
    while k > a:
        a *= 2
        cnt += 1
    ans += 0.5 ** cnt / n
print('{:.12f}'.format(ans))

Measured memory_bytes: 3060
using System;
using System.Linq;

namespace ABC080_B
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = Console.ReadLine();
            var lN = long.Parse(N);
            var l = new int[N.Length];
            for (int i = 0; i < N.Length; i++)
                l[i] = int.Parse(N[i].ToString());
            Console.WriteLine(lN % l.Sum() == 0 ? "Yes" : "No");
        }
    }
}


Measured memory_bytes: 13268
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
 
typedef long long ll;
const ll MOD = 1e9+7;
const ll INF = 1e18;


#define PB push_back
#define MP make_pair
#define F first
#define S second

template<typename T,typename U>
bool chmax(T& max, const U& x){
	if(max<x){
		max = x;
		return true;
	}
	return false;
}

template<typename T,typename U>
bool chmin(T& min, const U& x){
	if(min>x){
		min = x;
		return true;
	}
	return false;
}


int main(){
  	ll x,tmp=100;
  	cin >> x;
	for(ll i=1;;i++){
    	tmp = tmp*1.01;
        if(x<=tmp){
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 3636
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"

typedef long long ll;
typedef tuple<int,int,bool> Tb;

int atcoder(){
    int n;
    cin >> n;
    int t[n],x[n],y[n];
    REP(i,n){
        cin >> t[i] >> x[i] >> y[i];
    }
    bool ans = true;
    
    REP(i,n){
        if(t[i]<x[i]+y[i]){
            ans = false;
            break;
        }
        if(t[i]%2 != (x[i]+y[i])%2){
            ans = false;
            break;
        }
    }    
    
    if(ans) cout << "Yes" <<ENT;
    else cout << "No" <<ENT;
    return 0;
}

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


Measured memory_bytes: 1408
def dif(*a)
  a.sort![-1]-a[0]
end

H,W=gets.split.map(&:to_i)
sH=H/3
sW=W/3
lH=(H+2)/3
lW=(W+2)/3

p [ lH * W - sH * W ,\
    dif(lH * W , ( H - lH ) * ( W >> 1 ) , ( H - lH ) * ( W + 1 >> 1 )) ,\
    dif(sH * W , ( H - sH ) * ( W >> 1 ) , ( H - sH ) * ( W + 1 >> 1 )) ,\
    lW * H - sW * H ,\
    dif(lW * H , ( W - lW ) * ( H >> 1 ) , ( W - lW ) * ( H + 1 >> 1 )) ,\
    dif(sW * H , ( W - sW ) * ( H >> 1 ) , ( W - sW ) * ( H + 1 >> 1 )) ,\
  ].min


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define N 400500
#define int long long
using namespace std;
int Ans, mx[3][3][N << 2], X, Y, m, n, num[N], cnt;
struct Data{int c, l, r;}d[N];
bool cmpl(Data a, Data b){return a.l < b.l;}
void pushup(int rt, int c){
	for(int i = 0; i < 3; i++)
		mx[c][i][rt] = max(mx[c][i][rt << 1], mx[c][i][rt << 1 | 1]);
}
void build(int rt, int l, int r){
	if(l == r){
		for(int i = 0; i < 3; i++){
			mx[i][0][rt] = 0;
			mx[i][1][rt] = X * (-1 - num[l]);
			mx[i][2][rt] = (X + X + Y) * (-1 - num[l]);
		}
		return ;
	}
	int mid = (l + r) >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
	pushup(rt, 0);pushup(rt, 1);pushup(rt, 2);
}
void update(int rt, int l, int r, int x, int y, int c){
	if(l == r){
		mx[c][0][rt] = max(mx[c][0][rt], y);
		mx[c][1][rt] = mx[c][0][rt] + X * (-1 - num[l]);
		mx[c][2][rt] = mx[c][0][rt] + (X + X + Y) * (-1 - num[l]);
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) update(rt << 1, l, mid, x, y, c);
	else update(rt << 1 | 1, mid + 1, r, x, y, c);
	pushup(rt, c);
}
int query(int rt, int l, int r, int x, int y, int c, int d){
	if(x <= l && r <= y) return mx[c][d][rt];
	int mid = (l + r) >> 1;
	if(y <= mid) return query(rt << 1, l, mid, x, y, c, d);
	if(x > mid) return query(rt << 1 | 1, mid + 1, r, x, y, c, d);
	return max(query(rt << 1, l, mid, x, y, c, d),
			   query(rt << 1 | 1, mid + 1, r, x, y, c, d));
}
signed main(){
	scanf("%lld%lld%lld%lld", &n, &m, &X, &Y);
	for(int i = 1; i <= m; i++){
		scanf("%lld%lld%lld", &d[i].c, &d[i].l, &d[i].r);
		d[i].c--;
		num[++cnt] = d[i].l;
		num[++cnt] = d[i].r;
	}
	sort(num + 1, num + cnt + 1);
	cnt = unique(num + 1, num + cnt + 1) - num - 1;
	sort(d + 1, d + m + 1, cmpl);
	for(int i = 1; i <= m; i++){
		d[i].l = lower_bound(num + 1, num + cnt + 1, d[i].l) - num;
		d[i].r = lower_bound(num + 1, num + cnt + 1, d[i].r) - num;
	}
	build(1, 0, cnt);
	for(int i = 1; i <= m; i++){
		int ans = LLONG_MIN;
		for(int j = 0; j < 3; j++){
			ans = max(ans, query(1, 0, cnt, 0, d[i].l - 1, j, 0));
			if(d[i].l < d[i].r){
				if(j == d[i].c) ans = max(ans, query(1, 0, cnt, d[i].l, d[i].r - 1, j, 1) + num[d[i].l] * X);
				else ans = max(ans, query(1, 0, cnt, d[i].l, d[i].r - 1, j, 2) + num[d[i].l] * (X + X + Y));
			}
		}
		ans += (num[d[i].r] - num[d[i].l] + 1) * X;
		update(1, 0, cnt, d[i].r, ans, d[i].c);
	}
	for(int i = 0; i < 3; i++)
		Ans = max(Ans, query(1, 0, cnt, 0, cnt, i, 0));
	printf("%lld\n", Ans);
	return 0;
}


Measured memory_bytes: 84848
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define TEMP_T template<typename T>
TEMP_T void sort(T& v){ sort(v.begin(), v.end()); }
TEMP_T void revs(T& v){ reverse(v.begin(), v.end()); }
TEMP_T void uniq(T& v){ sort(v); v.erase(unique(v.begin(), v.end())); }
TEMP_T T    cums(T& v){ T r; r.push_back(v[0]); for(int i=1; i<v.size(); i++) r.push_back(r[i-1] + v[i]); return r; }
TEMP_T void show(T& v, char delim=' ', char end='\n'){ for(int i=0; i<v.size()-1; i++) cout << v[i] << delim; cout << v[v.size()-1] << end; }

static inline int in(){ int x; scanf("%d", &x); return x; }

struct UF {
  vector<int> data;
  UF(int size) : data(size, -1) {}
  void merge(int x, int y){
    x = root(x), y = root(y);
    if (x != y){
      if (data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }
  int root(int x){
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x){
    return -data[root(x)];
  }
};

struct Solver {
  int w, h;
  vector<string> field;
  Solver(int w, int h) : w(w), h(h) {}
  int read_input(){
    for (int i = 0; i < h; i++){
      string s;
      cin >> s;
      field.push_back(s);
    }
    return (0);
  }

  int solve(){
    UF uf(w * h);
    int pos;
    for (int y = 0; y < h; y++){
      for (int x = 0; x < w; x++){
        if (field[y][x] == '#') continue;
        for (int d = 0; d < 4; d++){
          static const int dx[] = {0, 0, 1, -1};
          static const int dy[] = {1, -1, 0, 0};
          int nx = x + dx[d];
          int ny = y + dy[d];
          if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue;
          if (field[ny][nx] != '#') uf.merge(y * w + x, ny * w + nx);
        }
        if (field[y][x] == '@') pos = y * w + x;
      }
    }
    return uf.size(pos);
  }
};

int main()
{
  int w, h;
  while (w = in(), h = in()){
    Solver s(w, h);
    s.read_input();
    printf("%d\n", s.solve());
  }

  return (0);
}

Measured memory_bytes: 1244
import java.util.*

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

object Problem {
    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val C = mutableListOf(1)
        var c = 6
        while (c <= N) {
            C.add(c)
            c *= 6
        }
        c = 9
        while (c <= N) {
            C.add(c)
            c *= 9
        }
        C.distinct()
        C.sort()
        C.reverse()
        //dprint(C)

        val dp = IntArray(N + 1)
        dp[0] = 0
        for (i in 1..N) {
            val can = mutableListOf<Int>()
            C.forEach {
                if (i >= it) can.add(1 + dp[i - it])
            }
            dp[i] = can.min()!!
        }

        pw.println(dp[N])
    }
}


Measured memory_bytes: 38844
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val (T, A) = readLine()!!.split(" ").map { it.toInt() }
    val base = A - T
    println(readLine()!!.split(" ")
    .mapIndexed { index, it -> Pair(base + it.toDouble() * 0.006, index) }
    .minBy { Math.abs(it.first) }!!.second + 1)
}

Measured memory_bytes: 37764
#include<iostream>
#include<string>
using namespace std;
	int sq[60][60];
int main(){
	int w,h;
	scanf("%d%d",&h,&w);
	{
		string s;
		getline(cin,s);
	}
	for(int i1=1;i1<=h;i1++){
		string s;
	
		getline(cin,s);
	 for (int i2=1;i2<=w;i2++){
	  if(s[i2-1] =='.') sq[i1][i2]=2;
	  else sq[i1][i2]=1;
	 }
	 }
	 
	 for(int i1=1;i1<=h;i1++){
	
	 for (int i2=1;i2<=w;i2++){
	  int num=0;
	  if(sq[i1][i2]==1)cout<<"#";
	  else{
	   for(int a=-1;a<=1;++a){
	   	for(int b=-1;b<=1;++b){
	   		if(sq[i1+a][i2+b]==1)num++;
		   }
	   }
	   cout<<num;
	  }
	  }
	  cout<<endl;
	 
	 
}

return 0;
}
	


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[2010][2010],b[2010][2010],f[2010],st[2010],l[2010],r[2010];
int main()
{
	int n,m,top,ans=0;scanf("%d%d\n",&n,&m);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	{
		a[i][j]=(getchar()=='.')?1:2;
		if (j==m) scanf("\n");
	}
	ans=max(n,m);	
	for (int i=1;i<n;i++)
	for (int j=1;j<m;j++)
		b[i][j]=((a[i][j]^a[i+1][j]^a[i][j+1]^a[i+1][j+1])==0);
	for (int i=n-1;i>=1;i--)
	{
		for (int j=1;j<m;j++) f[j]=(b[i][j])?(f[j]+1):0;
		top=0;st[0]=0;
		for (int j=1;j<m;j++)
		{
			while ((top)&&(f[j]<=f[st[top]])) top--;
			l[j]=st[top]+1;st[++top]=j;
		}
		top=0;st[0]=m;
		for (int j=m-1;j>=1;j--)
		{
			while ((top)&&(f[j]<=f[st[top]])) top--;
			r[j]=st[top]-1;st[++top]=j;
		}
		for (int j=1;j<m;j++) ans=max(ans,(r[j]-l[j]+2)*(f[j]+1));
	}
	printf("%d\n",ans);
}
	

Measured memory_bytes: 31872
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
signed main() {
	int m; cin >> m;
	int a[123456], p = m - 2;
	for (int i = 0; i < m; i++)cin >> a[i]; sort(a, a + m, greater<int>());
	for (int i = 0; i < m - 1; i++) {
		if (a[i + 1] <= 0) {
			p = i;
			break;
		}
	}
	int ans = a[p + 1];
	for (int i = p; i > 0; i--) {
		ans -= a[i];
	}
	ans = a[0] - ans;
	for (int i = p + 2; i < m; i++)ans -= a[i];
	cout << ans << endl;
	ans = a[p + 1];
	for (int i = p; i > 0; i--) {
		cout << ans << ' ' << a[i] << endl;
		ans -= a[i];
	}
	cout << a[0] << ' ' << ans << endl;
	ans = a[0] - ans;
	for (int i = p + 2; i < m; i++) {
		cout << ans << ' ' << a[i] << endl;
		ans -= a[i];
	}
	cin >> m;
}

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

int main() {
    int a, b, c, n;
    std::cin >> a >> b >> c >> n;
    std::vector<int> vec = {a, b, c};
    std::sort(vec.begin(), vec.end());
    for (int i = 0; i < n; i++) {
        vec[2] *= 2;
    }
    int sum = 0;
    for (int i = 0; i < 3; i++) {
        sum += vec[i];
    }
    std::cout << sum << std::endl;

}


Measured memory_bytes: 256
N = gets.to_i
T, A = gets.split.map(&:to_i)
H = gets.split.map(&:to_i)

at = H.map {|h| (1000 * T - 6 * h - 1000 * A).abs}

ans = 0;
at.each_with_index {|x, i| ans = at[ans] < x ? ans : i}
print ans + 1, "\n"


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

using namespace std;

void solve(){
	int n; cin>>n;
	int a = 0, b = 0, c = 0, d = 0;
	while(n--){
		string s; cin>>s;
		if(s == "AC") a++;
		else if(s == "WA") b++;
		else if(s == "TLE") c++;
		else d++;
	}
	cout << "AC x " << a << "\nWA x " << b << "\nTLE x " << c << "\nRE x " << d;
}

int main(){
	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 3648