akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        var qhsd = Array.ConvertAll(ReadLine().Split(' '), long.Parse);
        var num = ToInt32(ReadLine());
        var l2 = Calculation.Min(qhsd[3], 2 * qhsd[2], 4 * qhsd[1], 8 * qhsd[0]);
        var l1 = Calculation.Min(qhsd[2], 2 * qhsd[1], 4 * qhsd[0]);
        WriteLine((long)num / 2 * l2 + num % 2 * l1);
    }
}

public class Calculation
{
    public static long Min(params long[] nums)
    {
        var min = long.MaxValue;
        for (var i = 0; i < nums.Length; i++)
            min = Math.Min(min, nums[i]);
        return min;
    }
}


Measured memory_bytes: 13268
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

#include<unistd.h>
struct Buffer{
    int idx;
    enum { chunk = 1 << 16 };
    char buf[chunk];
    Buffer(){ init(); }
    void init(){ idx = 0; read(0, buf, chunk); }
    void check(){ if(idx == chunk){ init(); } }
    int next(){
        static char notDigits[256] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1, 0,0,0,0,0,0,0,0,0,0,};
        int ret = 0, sign = 1;
        while(check(), notDigits[(int)buf[idx]]){ idx++; }
        if(check(), buf[idx] == '-'){ sign = -1; idx++; }
        while(check(), !notDigits[(int)buf[idx]]){ ret = ret * 10 + buf[idx++] - '0'; }
        return sign * ret;
    }
};

const int lim = 1e5;
char prime[lim + 1];
int accs[lim + 1];
int main(){
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    Buffer buf;
    // vector<char> prime(lim + 1, true);
    prime[0] = prime[1] = true;
    for(int i = 2; i <= lim; i++){
        if(!prime[i]){
            for(int j = i + i; j <= lim; j += i){
                prime[j] = true;
            }
        }
    }
    // vector<int> accs(lim + 1);
    for(int i = 1; i <= lim; i++){
        accs[i] = accs[i - 1] + (i & 1 && !prime[i] && !prime[(i + 1) / 2]);
    }
    // int q; cin >> q;
    int q = buf.next();
    for(int i = 0; i < q; i++){
        // int l, r;
        // cin >> l >> r;
        int l = buf.next(), r = buf.next();
        cout << accs[r] - accs[l - 1] << '\n';
    }
}


Measured memory_bytes: 1152
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class Main
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int M = Integer.parseInt(st.nextToken());
         int A = Integer.parseInt(st.nextToken());
         int B = Integer.parseInt(st.nextToken());
         int C = Integer.parseInt(st.nextToken());
         int[] red = readArr(A, infile, st);
         int[] green = readArr(B, infile, st);
         int[] white = readArr(C, infile, st);
         sort(red);  sort(green);   sort(white);
         TreeMap<Integer, Integer> mset1 = new TreeMap<Integer, Integer>();
         TreeMap<Integer, Integer> mset2 = new TreeMap<Integer, Integer>();
         for(int i=0; i < N; i++)
            push(mset1, red[A-i-1]);
         for(int i=0; i < M; i++)
            push(mset2, green[B-i-1]);
         //white apples
         for(int i=C-1; i >= 0; i--)
         {
            if(Math.min(mset1.firstKey(), mset2.firstKey()) >= white[i])
               break;
            if(mset1.firstKey() < mset2.firstKey())
            {
               pull(mset1, mset1.firstKey());
               push(mset1, white[i]);
            }
            else
            {
               pull(mset2, mset2.firstKey());
               push(mset2, white[i]);
            }
         }
         long res = 0L;
         for(int k: mset1.keySet())
            res += (long)k*(long)mset1.get(k);
         for(int k: mset2.keySet())
            res += (long)k*(long)mset2.get(k);
         System.out.println(res);
      }
      public static void push(TreeMap<Integer, Integer> map, int k)
      {
         if(!map.containsKey(k))
            map.put(k, 1);
         else
            map.put(k, map.get(k)+1);
      }
      public static void pull(TreeMap<Integer, Integer> map, int k)
      {
         map.put(k, map.get(k)-1);
         if(map.get(k) == 0)
            map.remove(k);
      }
      //input shenanigans
      public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception
      {
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         return arr;
      }
      public static void sort(int[] arr)
      {
         //stable heap sort
         PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
         for(int a: arr)
            pq.add(a);
         for(int i=0; i < arr.length; i++)
            arr[i] = pq.poll();
      }
   }

Measured memory_bytes: 63136
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()
A.sort(reverse = True)
ans = A[0]
for i in range(N - 2):
    ans += A[1 + (i // 2)]
print(ans)

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

#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define int ll
#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;++i)
#define FOR(i,a,b) for(int i=(a),i##_cond=(b);i<i##_cond;++i)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;--i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second
using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using vs  = vector<string>;
using pii = pair<int,int>;
constexpr ll inf = 1ll<<61;
constexpr ll mod = 1e9+7;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>void add(T &a, const T &b){a += b; a %= mod;}

signed main(){
  int n, m; cin >> n >> m;
  vi a(n); rep(i,n) cin >> a[i];
  sort(all(a));
  dump(a);
  map<int,int> mp;
  rep(i,m){
    int b,c; cin >> b >> c;
    mp[c] += b;
  }
  vector<pii> b;
  for(auto x : mp){
    b.pb(pii(min(n,x.second),x.first));
  }
  int ans = 0;
  vector<pii> c(b);
  reverse(all(c));
  dump(c);
  int i = 0;
  rep(j,n){
    dump(j);
    if(i >= c.size()){
      ans += a[j];
    }else if(c[i].first > 0 and c[i].second > a[j]){
      dump(c[i]);
      c[i].first--;
      ans += c[i].second;
      if(c[i].first == 0) i++;
    }else{
      dump(c[i]);
      ans += a[j];
    }
    dump(ans);
  }
  cout << ans << endl;
}


Measured memory_bytes: 10484
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

int H, W;

vector<string> s;

vector<pair<int, int> > V;

vector<int> Adj[2600];

int d[55][55];
int C[55][55];

int NUM_B;

int main(void) {

	cin >> H >> W;

	for (int i = 0; i < H; i++) {
		string tmp;
		cin >> tmp; s.push_back(tmp);
	}

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			int k = i*W + j; 
			
			if (s[i].substr(j, 1) == ".") {
				//cout << "check" << endl;
				if (j < W - 1 && ( s[i].substr(j + 1,1) == ".") ) { Adj[k].push_back(i*W + j + 1); }
				if (j >= 1 && (s[i].substr(j - 1,1) == ".")) { Adj[k].push_back(i*W + j - 1); }
				if (i >= 1 && ( s[i - 1].substr(j,1) == ".")) { Adj[k].push_back((i - 1)*W + j); }
				if (i < H - 1 && (s[i + 1].substr(j,1) == ".")) { Adj[k].push_back((i + 1)*W + j); }
			}
		}
	}

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			d[i][j] = 99999;
		}
	}

	//cout << "CHECK" << endl;
	d[0][0] = 0;

	V.push_back(pair<int, int>(0, 0)); C[0][0] = 1;

	while (V.size() > 0) {
		//cout << V.size() << endl;
		sort(V.rbegin(), V.rend());
		int dis = V[V.size() - 1].first;
		int k = V[V.size() - 1].second; //cout << k << endl;
		V.pop_back();

		int j = k%W;
		int i = (k - j) / W;
		d[i][j] = dis;

		for (int m = 0; m < (int) Adj[k].size(); m++) {
			int K = Adj[k][m]; //cout << "Adj " << K << endl;
			int flag = 1;
			for (int h = 0; h < (int) V.size(); h++) {
				if (V[h].second == K) { flag = 0; }
			}
			//cout << "flag " << flag << endl;
			if (flag == 1 ) {  
				int J = K% W; int I = (K - J) / W; //cout << "C " << C[I][J] << endl;
				if (s[I].substr(J,1) == "." && C[I][J]==0) {
					V.push_back(pair<int, int>(dis + 1, K)); C[I][J] = 1; //cout << K << " 追加" << endl;
				}
			} //追加
		}

		for (int m = 0; m < (int) Adj[k].size(); m++) {
			int K = Adj[k][m];
			for (int h = 0; h < (int) V.size(); h++) {
				if (V[h].second == K) { if (V[h].first >= dis + 1) { V[h].first = dis + 1; } }//更新
			}

		}

	}//while -loop
	
	//cout << d[H - 1][W - 1] << endl;


	NUM_B = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (s[i].substr(j, 1) == "#") { NUM_B++; }
		}
	}

	if (d[H - 1][W - 1] >= 9999) { cout << -1 << endl; }
	else {
		cout << H*W - d[H - 1][W - 1]-1 - NUM_B << endl;
	         }

	//system("pause");

	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define int long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define mod 1000000007
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
void yes() { cout << "Yay!" << endl; }
void no() { cout << ":(" << endl; }
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y)* mod_pow(kai(y, y), mod - 2, mod) % mod;
}
struct edge { int to, cost; };
map<int, int>mp;
int n;
int a[114514];
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	rep(i, n)mp[a[i]]++;
	int ans = 0;
	for (auto x : mp) {
		if (x.second)ans++;
	}
	cout << ans << endl;
	ggr
}




Measured memory_bytes: 10064
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    k <- getInt
    as <- getIntList
    let (nmin,nmax) = foldr f (2,2) as
    putStrLn $ if nmin == -1 then "-1" else show nmin ++ " " ++ show nmax

f a (nmin,nmax) | nmin' > nmax' = (-1, -1)
                | otherwise = (nmin', nmax')
                    where nmin' = ((nmin - 1) `div` a + 1) * a
                          nmax' = (nmax `div` a + 1) * a - 1

Measured memory_bytes: 9864
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<stack>
#include<set>
#include<string.h>
#include<map>
#include<vector>
#define pb push_back
#define ins insert 
#define mp make_pair
#define ll long long 
#define max3(a,b,c) max(c,max(a,b))
#define min3(a,b,c) min(c,min(a,b))
#define M 10000007
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s1,s2,s="";
    cin>>s1>>s2;
    ll dp[s1.length()+1][s2.length()+1]={0};
    for (int i = 0; i <=s1.length(); ++i)
    {
        for (int j = 0; j <= s2.length(); ++j)
        {
            if(i==0 || j==0)
                dp[i][j]=0;
            else if(s1[i-1]==s2[j-1])
                dp[i][j]=1+dp[i-1][j-1];
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    ll i=s1.length(),j=s2.length();
    while(i>0 && j>0){
        if(s1[i-1]==s2[j-1]){
            s+=s1[i-1];
            i--;
            j--;
        }
        else if(dp[i-1][j]>=dp[i][j-1])
            i--;
        else
            j--;
    }
    for (int i = s.length()-1; i >=0; --i)
    {
        cout<<s[i];
    }
    return 0 ;
}


Measured memory_bytes: 70656
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define inc(i, n)  incID(i, 0, n)
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
#define bit(b, i) (((b) >> (i)) & 1)

// ---- ----

const int B = 40;
LL n, k, c[B][2], dp[2];
int main() {
	cin >> n >> k;
	inc(i, n) {
		LL a; cin >> a;
		inc(j, B) { c[j][1 - bit(a, j)]++; }
	}
	
	inc(i, B) {
		LL dp0 = exchange(dp[0], 0);
		LL dp1 = exchange(dp[1], 0);
		LL c0 = c[i][0] * (1LL << i);
		LL c1 = c[i][1] * (1LL << i);
		LL x = 1 - bit(k, i);
		setmax(dp[0], dp0 + c0);
		setmax(dp[x], dp0 + c1);
		setmax(dp[x], dp1 + c0);
		setmax(dp[1], dp1 + c1);
	}
	
	cout << dp[0] << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string nd;
int dp[10000100][2];

int main() {
    cin >> nd;
    string n = "0" + nd;

    int nlen = n.length();

    for(int i = 0; i <= nlen+2; ++i) {
        for(int j = 0; j < 2; ++j) {
            dp[i][j] = 0;
        }
    }

    int now = 0;
    for(int i = nlen-1; i >= 0; --i) {
        int check = n.at(i)-'0';
        if(now == 0) {
            dp[now+1][0] = dp[now][0] + check;
            dp[now+1][1] = dp[now][1] + (10-check);
        }else {
            dp[now+1][0] = min(dp[now][0] + check, dp[now][1] + (check+1));
            dp[now+1][1] = min(dp[now][0] + (10-check), dp[now][1] + (10-(check+1)));
        }
        now++;
    }

    cout << min(dp[nlen][0], dp[nlen][1]) << endl;

    /*for(int i = 0; i <= nlen; ++i) {
        for(int j = 0; j < 2; ++j) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }*/
}

Measured memory_bytes: 10500
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
f=int(input())
g=int(input())
h=int(input())
i=int(input())
j=int(input())

k=[a, b, c, d, e, f, g, h, i, j]

k.sort(reverse=True)
t=k[:3]

for i in t[0:]:
    print(i)


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

using namespace std;

int main() {

    char a[4];

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

    if(a[0] == a[1] && a[1] == a[2]) cout << "Yes" <<  endl;
    else if(a[1] == a[2] && a[2] == a[3]) cout << "Yes" <<  endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 384
# coding: utf-8

# In[118]:


data = list(map(int,input().split()))
data_diff = data[0] - data[1]


# In[119]:


trees = [1]
for i in range(2,1000):
    num = trees[-1] + i
    trees.append(num)


# In[120]:


differences = []
idx = -1
for i in range(len(trees)-1):
    diff = trees[i] - trees[i+1]
    if diff == data_diff:
        idx = i
        break
print(trees[idx] - data[0])



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

int main() {
  
  int a, b;
  cin >> a >> b;
  
  if(a+b < 10) cout << a+b << endl;
  else cout << "error" << endl;

}

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

int main()
{
  int sum = 0, D, N;

  scanf("%d %d", &D, &N);

  sum = pow(100, D) * N;
  if (log10(sum) / log10(100) == D + 1)
  {
    sum += pow(100, D);
  }

  cout << sum << endl;

  return 0;
};

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
    return string(1, val);
}

int check(string a, string b) {
    int cnt = 0;
    sort(all(a));
    sort(all(b));
    for(int i = 0; i < a.size(); ++i) {
        if(a[i] == a[i - 1]) continue;
        for(int j = 0; j < b.size(); ++j) {
            if(a[i] == b[j]) {
                cnt++;
                break;
            }
        }
    }
    return cnt;
}

int main(){
    int N; cin >> N;
    string S; cin >> S;

    int res = 0;
    for(int i = 1; i < N; ++i) {
        string suba = S.substr(0, i);
        string subb = S.substr(i);
        int cnt = check(suba, subb);
        if(res < cnt) res = cnt;
    }

    cout << res << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

const int MAXN = 55;
vector<int> G[MAXN];
int dp[MAXN];
bool done[MAXN][2*MAXN];
const int INF = 1e9;
int n, m;

void dfs(int now, int rest, set<int>& canvisit) {
    if (done[now][rest]) return;
    done[now][rest] = true;
    if (rest == 0) {
        canvisit.insert(now);
        return;
    }
    for (int v : G[now]) {
        dfs(v, rest-1, canvisit);
    }
}

set<int> canvisit[3][MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<int> a(3);
    cin >> n >> m >> a[0] >> a[1] >> a[2];
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
    }
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            memset(done, false, sizeof(done));
            dfs(j, a[i], canvisit[i][j]);
        }
    }
    for (int i = 0; i < n; i++) dp[i] = INF;
    dp[n-1] = 0;
    for (int t = 0; t < n; t++) {
        for (int i = 0; i < n; i++) {
            int ans = 0;
            for (int j = 0; j < 3; j++) {
                int tmp = INF;
                for (int u : canvisit[j][i]) {
                    tmp = min(tmp, 1+dp[u]);
                }
                ans = max(ans, tmp);
            }
            dp[i] = min(dp[i], ans);
        }
    }
    if (dp[0] == INF) cout << "IMPOSSIBLE" << endl;
    else cout << dp[0] << endl;
    return 0;
}

Measured memory_bytes: 3552
let k, a, b = Scanf.scanf " %d %d %d" @@ fun a b c -> a, b, c
let _ = Printf.printf "%d\n" @@ if a - 1 > k || b - a < 2 then k + 1 else a + (k - a + 1) / 2 * (b - a) + (k - a + 1) mod 2

Measured memory_bytes: 384
#include <stdio.h>

#define MAX 100000

typedef struct {
	int parent;
	int left;
	int right;
} node;

node nodes[MAX] = {0};

int n;



int getDepth(int num) {
	int d = 0;
	while (nodes[num].parent != -1) {
		num = nodes[num].parent;
		++d;
	}
	return d;
}

void printChilde(int num) {
	int c, flag = 0;
	c = nodes[num].left;

	while (c != -1) {
		if (flag) {
			printf(", ");
		}
		flag = 1;
		printf("%d", c);
		c = nodes[c].right;
	}
	printf("]\n");
	return;
}

void show_node(int num) {
	if (nodes[num].parent == -1) {
		printf("node %d: parent = %d, depth = %d, root, [", num, nodes[num].parent, getDepth(num));
	} else if (nodes[num].left == -1) {
		printf("node %d: parent = %d, depth = %d, leaf, [", num, nodes[num].parent, getDepth(num));
	} else {
		printf("node %d: parent = %d, depth = %d, internal node, [", num, nodes[num].parent, getDepth(num));
	}
	printChilde(num);
}

int main(void) {
	int i, j, tmp, right, left, num;
	int m;
	node init_node;
	init_node.parent = init_node.left = init_node.right = -1;

	for (i = 0; i < MAX; ++i) {
		nodes[i] = init_node;
	}
	
	scanf("%d", &n);	

	for (i = 0; i < n; ++i) {
		scanf(" %d", &num);
		scanf(" %d", &m);
		for (j = 0; j < m; ++j) {
			scanf(" %d", &tmp);
//			printf("j = %d, tmp = %d\n", j, tmp);
			nodes[tmp].parent = num;
			if (j == 0) {
				nodes[num].left = tmp;
				left = tmp;
			} else {
				nodes[left].right = tmp;
				left = tmp;
//				printf("tmp = %d, right = %d\n", tmp, nodes[tmp].right);
			}
		}
	}
//	printf("test\n");

	for (i = 0; i < n; ++i) {
		show_node(i);
	}
	return 0;
}

Measured memory_bytes: 1784
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#include<iomanip>
#include<functional>
using namespace std;
const int maxn = 2 * (int)(1e5) + 10;
const int BN = 30;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
typedef long long LL;
typedef unsigned long long ull;
int main() {
	LL a, b, c, x, y;
	while (~scanf("%lld%lld%lld%lld%lld", &a, &b, &c, &x, &y)) {
		LL ans1 = a*x + b*y;
		LL ans2 = 0;
		if (x > y) {
			ans2 = 2 * c*y;
			ans2 += min(2 * c*(x - y), (x - y)*a);
		}
		else {
			ans2 = 2 * c*x;
			ans2 += min(2 * c*(y - x), (y - x)*b);
		}
		printf("%lld\n", min(ans1, ans2));
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  int N,count1,count2,max,sum,room;
  scanf("%d",&N);

  int L[N],sort[N];
  for(count1=0;count1<N;count1++){
    scanf("%d",&L[count1]);
  }

  for(count1=0;count1<N;count1++){
    sort[count1]=L[count1];
  }

  for(count1=0;count1<N;count1++){
    for(count2=0;count2<N;count2++){
      if(sort[count1]-sort[count2]<0){
        room=sort[count1];
        sort[count1]=sort[count2];
        sort[count2]=room;
      }
    }
  }

  max=sort[N-1];
  sum=0;
  for(count1=0;count1<N-1;count1++){
    sum+=sort[count1];
  }
  if(max<sum){
    printf("Yes\n");
  }else{
    printf("No\n");
  }

  return 0;
}


Measured memory_bytes: 128
"use strict";
function Main(input) {
    const args = input.trim().split(' ').map(Number);
    const r1 = Math.max(args[0] - args[2], 0);
    const r2 = Math.max(args[0] + args[1] - args[2] - r1, 0);
    console.log('%s %s', r1, r2);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

#define NIL -1

int kd_index = 0;

struct point {
	int id;
	int x;
	int y;
};

bool compare_x(const point& p, const point& q) { return p.x < q.x; }
bool compare_y(const point& p, const point& q) { return p.y < q.y; }

struct Node {
	int index;
	int x;
	int y;
	int left_child;
	int right_child;
};

int construct_kdtree(Node* kdtree, point* P, int left, int right, int depth)
{
	if (left>=right) return NIL;
	
	Node v;
	
	int mid = (left + right) / 2;
	
	if (left+1<right) {
		if ((depth&1)==0) {
			std::sort(P + left, P + right, compare_x);
		}
		else {
			std::sort(P + left, P + right, compare_y);
		}
		v.x = P[mid].x; v.y = P[mid].y;
		v.index = mid;
		v.left_child = construct_kdtree(kdtree, P, left, mid, depth+1);
		v.right_child = construct_kdtree(kdtree, P, mid+1, right, depth+1);
	}
	else {
		v.x= P[left].x; v.y= P[left].y;
		v.index = left;
		v.left_child = v.right_child = NIL;
	}
	
	kdtree[kd_index++] = v;
	return kd_index - 1;
}

void tab(int n)
{
	for (int i=0; i<n; i++) std::cout << " ";
}

void show_kdtree(Node* kdtree, int v_index, int depth)
{
	Node v = kdtree[v_index];
	tab(2*depth);
	std::cout << "x = " << v.x << ", y = " << v.y << ", index = " << v.index << std::endl;
	if (v.left_child != NIL) show_kdtree(kdtree, v.left_child, depth+1);
	if (v.right_child != NIL) show_kdtree(kdtree, v.right_child, depth+1);
}

void rsq(Node* kdtree, std::vector<int>& points, point* P, int v_index, int sx, int tx, int sy, int ty, int depth)
{
	Node v = kdtree[v_index];
	if (sx <= v.x && v.x <= tx && sy <= v.y && v.y <= ty) { // point is contained
		points.push_back(P[v.index].id);
		// std::cout << "index = " << v->index << ", ID = " << points.back() << std::endl;
	}
	if ((depth&1)==0) {
		if (v.x >= sx) if (v.left_child != NIL) rsq(kdtree, points, P, v.left_child, sx, tx, sy, ty, depth+1);
		if (v.x <= tx) if (v.right_child != NIL) rsq(kdtree, points, P, v.right_child, sx, tx, sy, ty, depth+1);
	} else {
		if (v.y >= sy) if (v.left_child != NIL) rsq(kdtree, points, P, v.left_child, sx, tx, sy, ty, depth+1);
		if (v.y <= ty) if (v.right_child != NIL) rsq(kdtree, points, P, v.right_child, sx, tx, sy, ty, depth+1);
	}
}

int main ()
{
	int n; //std::cin >> n;
	scanf("%d", &n);
	
	point* P = new point[n];
	for (int i=0; i<n; i++) {
		P[i].id = i;
		//std::cin >> P[i].x >> P[i].y;
		scanf("%d %d", &(P[i].x), &(P[i].y));
	}
	Node* kdtree = new Node[n];
	
	int root = construct_kdtree(kdtree, P, 0, n, 0);

	// show_kdtree(root, 0);
	
	int q; std::cin >> q;
	for (int i=0; i<q; i++) {
		int sx, tx, sy, ty;
		//std::cin >> sx >> tx >> sy >> ty;
		scanf("%d %d %d %d", &sx, &tx, &sy, &ty);
		std::vector<int> ans;
		rsq(kdtree, ans, P, root, sx, tx, sy, ty, 0);
		std::sort(ans.begin(), ans.end());
		for (std::vector<int>::iterator it = ans.begin(); it != ans.end(); ++it) {
			//std::cout << *it << std::endl;
			printf("%d\n", *it);
		}
		//std::cout << std::endl;
		printf("\n");
	}
	
	delete[] kdtree;
	delete[] P;
	
	return 0;
}



Measured memory_bytes: 18088
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
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; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

int main(){
  ll A,B,K;
  cin >> A >> B >> K;
  rep(i,K){
    if(i%2==0){
      if(A%2==1){
        A--;
      }
      B+=A/2;
      A/=2;
    }
    else{
      if(B%2==1){
        B--;
      }
      A+=B/2;
      B/=2;
    }
  }
  cout << A << " " << B << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include<string.h>
#include<set>
#include<map>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include <cstdio>
#include <cstdlib>
#include<stack>
#include<vector>
const long long MAX=1e6+10;
int mp[30];
char a[30];
int main()
{

    cin>>a+1;
    memset(mp,0,sizeof(mp));
    int len=strlen(a+1);
    if(len!=26)
    {
        for(int i=1;i<=len;i++)
        {
            mp[a[i]-'a']++;
        }
        cout<<a+1;
        for(int i=0;i<30;i++)
        {
            if(mp[i]==0)
            {
                cout<<(char)(i+'a')<<endl;
                break;
            }
        }
        return 0;
    }
    else
    {
        int flag=0;
        for(int i=len-1;i>=1;i--)
        {
            if(a[i]<a[i+1])
            {
                flag=1;
                for(int j=1;j<=i;j++)
                {
                    mp[a[j]-'a']++;
                }
                for(int j=0;j<26;j++)
                {
                    if(mp[j]==0&&a[i]<(char)(j+'a'))
                    {
                        //cout<<(char)(j+'a')<<endl;
                        a[i]=(char)(j+'a');
                        break;
                    }
                }
                for(int j=1;j<=i;j++)
                    cout<<a[j];
                cout<<endl;
                return 0;
            }
        }
    }
    cout<<"-1"<<endl;
    return 0;
}


Measured memory_bytes: 256
h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))

color = [[0 for _ in range(w)] for _ in range(h)]
c = 0
for i in range(h*w):
    x = i // w
    y = i % w
    if x % 2:
        y = w - 1 - y
    if a[c] == 0:
        c += 1
    color[x][y] = c+1
    a[c] -= 1
for i in range(h):
    print(*color[i])

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

class Program
{
    public static bool f = false, t = true;
    static void Main(string[] args)
    {
        int a = int.Parse(Console.ReadLine());
        int b = int.Parse(Console.ReadLine());
        int c = int.Parse(Console.ReadLine());
        int d = int.Parse(Console.ReadLine());
        Console.WriteLine(Math.Min(a,b)+Math.Min(c,d));
    }
    public static long gcd(long a, long b)
    {
        while (true)
        {
            if (a == 0) { return b; }
            if (b == 0) { return a; }
            if (a > b) { a -= b; }
            else { b -= a; }
        }
    }
    public static long lcm(long a, long b) { return a / gcd(a, b) * b; }
    public static string Reverse(string s)
    {
        return new string(s.Reverse().ToArray());
    }
    public static bool IsPrime(int num)
    {
        if (num < 2) return false;
        else if (num == 2) return true;
        else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

        double sqrtNum = Math.Sqrt(num);
        for (int i = 3; i <= sqrtNum; i += 2)
        {
            if (num % i == 0)
            {
                // 素数ではない
                return false;
            }
        }

        // 素数である
        return true;
    }
}
public static class Read
{
    public static void outl(string n = "") { Console.WriteLine(n); return; }
    public static long Long() { return long.Parse(Console.ReadLine()); }
    public static long[] longs() { return Console.ReadLine().Split().Select(long.Parse).ToArray(); }
    public static int Int() { return int.Parse(Console.ReadLine()); }
    public static int[] ints() { return Console.ReadLine().Split().Select(int.Parse).ToArray(); }
    public static string Str() { return Console.ReadLine(); }
    public static string[] Strs() { return Console.ReadLine().Split(); }
}

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

ll gcd(ll x, ll y)
{
	if (y == 0) return x;
	return gcd(y, x%y);
}

signed main(void)
{
	ll n, x;
	cin >> n >> x;
	vector<ll> v(n), diff(n);
	ll g;

	rep(i, n)
	{
		cin >> v[i];
		diff[i] = abs(v[i] - x);
	}
	g = diff[0];
	for(ll i = 1; i < n; i++)
	{
		g = gcd(g, diff[i]);
	}
	cout << g << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
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;}
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

int N;

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

    cin >> N;
    vector<ll> a(N);
    vector<ll> mn(N,INF);
    ll ans = -INF;
    REP(i,N) cin >> a[i];
    mn[0] = a[0];
    rep(i,1,N){
        mn[i] = min(a[i-1],mn[i-1]);
    }
    rep(i,1,N){
        ans = max(ans,a[i]-mn[i]);
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 6012
#include<bits/stdc++.h>
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define pii pair<int,int>
#define rep(i,a) for(int (i)=0; (i)<(a); (i)++)
#define rrep(i,a) for(int (i)=a-1; (i)>=(0); (i)--)
#define rep2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
typedef long long ll;

using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n,r; cin >> n >> r;
  int keta = 0;
  if(n >= 10) cout << r << endl;
  else{
    cout << r + 100*(10 - n) << endl; 
  }
  return 0;
}


Measured memory_bytes: 256
// AOJ 1275: And Then There Was One
// 2017.10.16 bal4u@uu

#include <stdio.h>

int main()
{
	int n, k, m;
	int a, off;

	while (scanf("%d%d%d", &n, &k, &m) && n > 0) {
		off = (m-k) % n; if (off < 0) off += n;
		for (a = 1; a <= n; a++) m = (m + k) % a;
		printf("%d\n", (m+off+n) % n + 1);
	}
	return 0;
}

Measured memory_bytes: 1744
#include <iostream>
#include <queue>

using namespace std;
static const int N = 100;
static const int INFTY = (1 << 21);


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

void bfs(int s){
    queue<int> q;
    q.push(s);
    for(int i = 0; i < n; i++) d[i] = INFTY;
    d[s] = 0;
    int u;
    while(!q.empty()){
        u = q.front(); q.pop();
        for(int v = 0; v < n; v++){
            if(M[u][v] == 0)
            continue;
            if(d[v] != INFTY)
            continue;
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
    for(int i = 0; i < n; i++){
        cout << i + 1 << " " << ( (d[i] == INFTY) ? (-1) : d[i]) << endl;
    }
    
}



int main(){
    int u, k, v;
    
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)
        M[i][j] = 0;
    }
    
    for(int i = 0; i < n; i++){
        cin >> u >> k;
        u--;
        for(int j = 0; j < k; j++){
            cin >> v;
            v--;
            M[u][v] = 1;
        }
    }

    bfs(0);
    return 0;
}

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

int main()
{  
    int N;
    string S;
    cin >> N;
    cin >> S;
    int ans = 0;
    for (size_t i = 0; i < N; i++)
    {
        if(S.substr(i,3) == "ABC") ans++;
    }
    cout << ans << endl;    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<ii> vec;

int color(ll x, ll y)
{
	int ans=0;
	int n=vec.size();
	for(int i=0;i<n;i++)
	{
		ll x2=vec[i].fi; ll y2=vec[i].se;
		ll d = x-x2;
		ll h = y2-y;
		if(d<0||d>h) continue;
		if((d&h)==d) ans^=1;
	}
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++)
	{
		ll x,y; cin>>x>>y; vec.pb({x,y});
	}
	const ll C = -((1LL<<61)-1);
	ll cur = -(1LL<<61);
	while(!color(cur,C)) cur+=(1LL<<60);
	for(int i=61;i>=0;i--)
	{
		if(color(cur-(1LL<<i),C)) cur-=(1LL<<i);
	}
	cout<<cur<<'\n';
}


Measured memory_bytes: 2420
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 23 22:00:37 2018
ABC110D
@author: maezawa
"""
import collections

def comb(n, r):
    if n == 0 or r == 0:
        return 1
    return comb(n, r-1)*(n-r+1)//r

n, m = list(map(int, input().split()))

mod = 10**9+7
np = int(10**4.5 + 10)
is_prime = [True]*(np+1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, np//2):
    if is_prime[i] == True:
        for j in range(2*i,np+1,i):
            is_prime[j] = False

prime_numbers = [i for i in range(np+1) if is_prime[i]]

pds = []
for i in prime_numbers:
    if i > m//2:
        break
    md = m
    while md%i == 0:
        pds.append(i)
        md = md//i
mul = 1
for i in pds:
    mul *= i
if m != mul:
    pds.append(m//mul)

#print(pds)
cpds = collections.Counter(pds)
#print(cpds)
ans = 1
for i in cpds.values():
    ans = ans*comb(n+i-1,i)%mod

print(ans)


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

using namespace std;
using namespace std;
#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

const ll inf = 1e9+7;
const ll mod = 1e9+7;

int main(){
    ll n,k;
    cin>>n>>k;

    vector<ll>h(n);
    rep(i,n)cin>>h[i];

    sort(h.begin(),h.end());

    ll sub=inf;

    rep(i,n-k+1)sub=min(sub,abs(h[i+k-1]-h[i]));

    cout<<sub<<endl;

}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int n;
int a[200010];

bool solve(int m){
	map<int,int> b;
	for(int i = 1 ; i <= n ; i ++){
		if(a[i-1] < a[i])continue;
		map<int,int>::iterator itr = b.end();
		if(itr == b.begin())goto f;
		itr--;
		while(1){
			if(itr->fr <= a[i])break;
			if(itr == b.begin()){
				b.erase(itr);
				break;
			}
			b.erase(itr--);
		}
		f:;
		b[a[i]] ++;
		int loc = a[i];
		while(b[loc] == m){
			if(loc == 1)return false;
			b[loc] = 0;
			b[loc-1] ++;
			loc --;
		}
	}
	return true;
}

int main(){
	scanf("%d",&n);
	a[0] = 0;
	for(int i = 1 ; i <= n ; i ++){
		scanf("%d",&a[i]);
	}
	
	bool one = true;
	for(int i = 1 ; i+1 <= n ; i ++){
		one &= a[i] < a[i+1];
	}
	if(one){
		puts("1");
		return 0;
	}
	
	int l = 2, r = 200000;
	while(l < r){
		int m = (l+r)/2;
		if(solve(m))r = m;
		else l = m+1;
	}
	cout << l << endl;
}


Measured memory_bytes: 1152
int main()
{
  int h1, m1, h2, m2, k;
  scanf("%d %d %d %d %d", &h1, &m1, &h2, &m2, &k);
  int tmp_h, tmp_m;
  int min;
  if (h2 - h1 > 0)
  {
    tmp_h = h2 - (h1 + 1);
    tmp_m = 60 - m1 + m2;
  }
  else if (tmp_m == 0)
  {
    tmp_h = 0;
    tmp_m = m2 - m1;
  }
  min = tmp_h * 60 + tmp_m;
  printf("%d", min - k);
}

Measured memory_bytes: 1680
#include<stdio.h>
int main(void){
	int a[4][3][10],n,l,i;
	int b,f,r,v;
	
	for(b=0; b<4; b++) for(f=0;f<3;f++) for(r=0; r<10; r++) a[b][f][r]=0;
	
	scanf("%d",&n);
	for(l=0; l<n; l++){scanf("%d%d%d%d",&b,&f,&r,&v); a[b-1][f-1][r-1]=a[b-1][f-1][r-1]+v;}
	for(b=0; b<4; b++){
		for(f=0; f<3; f++) {for(r=0; r<10; r++) printf(" %d",a[b][f][r]); printf("\n");}
		if(b!=3){for(i=0; i<20; i++)printf("#"); printf("\n");}
	}

	return 0;
}

Measured memory_bytes: 600
// F - Engines
#include <bits/stdc++.h>

using namespace std;

struct point {
	int x, y;
	double v;
	bool operator<(const point &p) const { return v < p.v; }
};

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	vector<point> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i].x >> p[i].y;
		p[i].v = atan2(p[i].y, p[i].x);
	}
	sort(p.begin(), p.end());
	vector<pair<long long, long long> > a(1);
	for (int i = 0; i < 2 * n; i++) {
		long long x = p[i % n].x, y = p[i % n].y;
		a.push_back(make_pair(a[i].first + x, a[i].second + y));
	}

	long long ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = i; j < i + n; j++) {
			long long x = a[j + 1].first - a[i].first, y = a[j + 1].second - a[i].second;
			ans = max(ans, x * x + y * y);
		}

	cout << setprecision(20) << sqrt(ans) << endl;

	return 0;
}


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

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;
const int MAX = 50;

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

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, p;
    cin >> n >> p;
    map<int, int> mp;
    rep (i, n) {
        int a;
        cin >> a;
        a %= 2;
        mp[a]++;
    }
    COMinit();
    ll res = 0;
    if (p) {
        for (int i = 1; i < mp[1] + 1; i += 2) {
            res += COM(mp[1], i);
        }

    } else {
        for (int i = 0; i < mp[1] + 1; i += 2) {
            res += COM(mp[1], i);
        }
    }
    rep (i, mp[0]) res *= 2;
    cout << res << endl;
    
    return 0;
}



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

char e[2002][2002];
int cnt[2002][2002];

int m, n;

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			cin >> e[i][j];
		}
	}
	for(int i = 1; i <= n; ++i) {
		int ct = 0, now = 1, last = 1;
		while(1) {
			if(e[i][now] == '.')
				++ct, ++now;
			else {
				for(int j = last; j <= now - 1; ++j)
					cnt[i][j] = ct;
				ct = 0;
				while(e[i][now] == '#') ++now;
				if(now >= m) break;
				else last = now;
			}
		}
	}
	for(int i = 1; i <= m; ++i) {
		int ct = 0, now = 1, last = 1;
		while(1) {
			if(e[now][i] == '.')
				++ct, ++now;
			else {
				for(int j = last; j <= now - 1; ++j)
					cnt[j][i] += ct;
				ct = 0;
				while(e[now][i] == '#') ++now;
				if(now >= n) break;
				else last = now;
			}
		}
	}
	cout << *max_element(&cnt[1][1], &cnt[n][m + 1]) - 1;
	return 0;
}

Measured memory_bytes: 19840
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mod 1000000007
const int N=200005;

ll modulo(ll num,ll MOD=mod){ return ((num%MOD)+MOD)%MOD;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),MOD-2,MOD); }

ll ans=0;

void go(int ind, string s, int n, vector <int> vec) {
    if(ind==n-1) {
        int pr=-1;
        ll tmp=0;
        for(auto it:vec) {
            string sr="";
            for(int j=pr+1;j<=it;j++) {
                sr+=s[j];
            }
            pr=it;
            tmp+=stoll(sr);
        }
        string sr="";
        for(int j=pr+1;j<n;j++) {
            sr+=s[j];
        }
        tmp+=stoll(sr);
        ans+=tmp;
        return;
    }
    vec.pb(ind);
    go(ind+1, s, n, vec);
    vec.pop_back();
    go(ind+1, s, n, vec);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   
    cout<<fixed<<setprecision(15);

    string s;

    cin>>s;

    int n=s.length();

    vector <int> vec;

    go(0, s, n, vec);

    cout<<ans;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n,capacity;
    cin>>n>>capacity;

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

    long long int dp[capacity+1];
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        for(int j=capacity;j>=weight[i-1];j--)
        dp[j]=max(dp[j],dp[j-weight[i-1]]+value[i-1]);

    }
    cout<<dp[capacity]<<"\n";


}
void tool() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
}
int32_t main() {
	tool();
	
		solve();
	return 0;
}

Measured memory_bytes: 4416