akhauriyash/Code-Regression huggingface dataset:
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <time.h>
#include <random>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define LONG_INF 10000000000000000
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
map<string, int> looping;
int main() {
#define int long long
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	int reversed = 0;
	int erasing = 0;
	while (k != 0 && erasing < 2000000) {
		k--;
		if (reversed == true) {
			if (s[erasing] == 'A') {
				erasing++;
				reversed = false;
				s.push_back('A');
			}
			else {
				s[erasing] = 'A';
			}
		}
		else {
			if (s[erasing] == 'B') {
				erasing++;
				reversed = true;
				s.push_back('B');
			}
			else s[erasing] = 'B';
		}
	}
	if (k == 0) {
	ooh:;
		for (int i = erasing;i < s.length();++i) {
			if (reversed == true) {
				if (s[i] == 'A') {
					s[i] = 'B';
				}
				else s[i] = 'A';
			}
			cout << s[i];
		}
		cout << endl;
		return 0;
	}
	else {
		if (n % 2 == 0) {
			string ans;
			for (int i = 0;i < n;++i) {
				if (i % 2 == 0) {
					ans.push_back('A');
				}
				else ans.push_back('B');
			}
			for (int i = n - 1;i >= 0;--i) {
				cout << ans[i];
			}
			cout << endl;
			return 0;
		}
		else {
			string hoge;
			for (int i = erasing;i < s.length();++i) {
				if (reversed == true) {
					if (s[i] == 'A') {
						s[i] = 'B';
					}
					else s[i] = 'A';
				}
				hoge.push_back(s[i]);
			}
			int ptr = 0;
			while (k != 0) {
				if (looping[hoge.substr(ptr)] != 0) {
					k %= looping[hoge.substr(ptr)] - k;
				}
				if (k % 2 == 0) break;
				looping[hoge.substr(ptr)] = k;
				if (hoge[ptr] == 'A') {
					hoge[ptr] = 'B';
					k--;
				}
				else {
					hoge.push_back('A');
					for (int i = 0;i < hoge.length();++i) {
						if (hoge[i] == 'A') hoge[i] = 'B';
						else hoge[i] = 'A';
					}
					k--;
					ptr++;
				}
			}
			cout << hoge.substr(ptr) << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 6020
void main()
{
    dchar[] s = rdDchar;
    dchar[] t = rdDchar;

    long pos = t.length - 1;
    bool ok;
    foreach_reverse (long i, x; s)
    {
        if (x == t[pos] || x == '?')
        {
            bool check;
            if (i - pos >= 0)
            {
                check = true;
                foreach (j; 0 .. pos)
                {
                    if (s[i-pos+j] != t[j] && s[i-pos+j] != '?')
                    {
                        check = false;
                        break;
                    }
                }
            }

            if (check)
            {
                ok = true;
                foreach (j; 0 .. pos+1)
                {
                    s[i-pos+j] = t[j];
                }
                foreach (j; 0 .. s.length)
                {
                    if (s[j] == '?') s[j] = 'a';
                }
                break;
            }
        }
    }

    writeln(ok ? s.to!string : "UNRESTORABLE");
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.mathspecial;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;
import core.bitop;

Measured memory_bytes: 256
'''
Created on 2020/08/20

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N,K=map(int,pin().split())
  t=0
  if N%2==0:
    t=N//2
  else:
    t=N//2+1
  if t>=K:
    print("YES")
    return 
  print("NO")
  return 

main()

Measured memory_bytes: 9176
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod=1000000007;
int main() {
	ll i,j,k,l,m,n,t;
	ios_base::sync_with_stdio(false);
  cin.tie(NULL);

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

  vector<ll> dp(k + 1, 1);

  for (i = 1; i <= k; i++)
  {
    for (j = 0; j < n; j++){
      if(i<a[j]){
        continue;
      }
      if(dp[i-a[j]]==1){
        dp[i] = 0;
      }
    }
  }

  if(dp[k]==1){
    cout << "Second" << endl;
  } else {
    cout << "First" << endl;
  }

  return 0;
}

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

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int l=1,r=m;l<r;l++,r--) printf("%d %d\n",l,r);
    for(int l=m+1,r=2*m+1;l<r;l++,r--) printf("%d %d\n",l,r);
    return 0;
}

Measured memory_bytes: 3840
#include<bits/stdc++.h>
using namespace std;
int main() {
  int n,i;
  cin>>n;
  vector<long> a(n);
  for (i=0;i<n;i++) cin>>a.at(i);
  sort(a.begin(),a.end());
  for (i=1;i<n;i++) if (a.at(i-1)==a.at(i)) break;
  if (i==n) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}

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

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

int main()
{
    long long int n,modd=1000000007,i,x[200005],y[200005],mn1,mn2,mx1,mx2,ans;
    cin>>n;
    mn1=1000000000000;
    mx1=-1000000000000;
    mn2=1000000000000;
    mx2=-1000000000000;
    for(i=0;i<n;i++)
    {
        cin>>x[i]>>y[i];
        mn1=min(mn1,x[i]+y[i]);
        mn2=min(mn2,x[i]-y[i]);
        mx1=max(mx1,x[i]+y[i]);
        mx2=max(mx2,x[i]-y[i]);
    }
    // ans=max ( (max(xi+yi)-min(xi+yi)), (max(xi-yi) - min(xi-yi)) );
    ans=max ( (mx1-mn1), (mx2 - mn2) );
    cout<<ans<<endl;
    

}

Measured memory_bytes: 6736
#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
using namespace std;

int main()
{
	int A, B, C;
	while (cin >> A >> B >> C)
	{
		if (C >= A && C <= B)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}




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

int main(int argc, char const *argv[])
{
    string s;
    cin >> s;
    int x = stoi(s);
    int d[4];
    int op[3];
    for (int i=3;i>=0;--i){
        d[i]=x%10;
        x/=10;
    }
    int ret =0;
    for (int i=0;i<=7;++i){
        ret = d[0];
        for (int j=1;j<4;++j){
            op[j-1]=i>>(j-1)&1;
            if(op[j-1]){
                ret += d[j];
            }
            else{
                ret -= d[j];
            }
        }
        if (ret == 7){
            for (int i=0;i<3;++i)cout << d[i] << (op[i] ? "+":"-");
            cout << d[3] << "=7";
            return 0;
        }
        ret =0;
    }
    return 0;
}


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

const int dx[] = {0,1,0,-1,0,1,-1,-1,1,2,0,-2,0};
const int dy[] = {0,0,1,0,-1,1,1,-1,-1,0,2,0,-2};
const int num[3] = {5,9,13};
const int wx[3] = {0,1,0};
const int wy[3] = {1,1,2};
const int R = 10;
const int MAXN = 12;
const int MAXSUM = 13*12+1;

int N;
int G[R][R];
int sum;
int X[MAXN], Y[MAXN], S[MAXN];
bool can[MAXSUM];

bool draw(int x, int y, int s, int c) {
  for(int i = 0; i < num[s]; ++i) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(nx < 0 || nx >= R) return false;
    if(ny < 0 || ny >= R) return false;
    if(G[ny][nx]+c < 0) return false;
  }
  for(int i = 0; i < num[s]; ++i) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    G[ny][nx] += c;
  }
  return true;
}

bool rec(int k, int m, int x, int y) {
  if(k == N) {
    if(m == sum) {
      for(int i = 0; i < N; ++i) {
        cout << X[i] << " " << Y[i] << " " << S[i] << endl;
      }
      return true;
    } else { 
      return false;
    }
  }

  if(!can[sum-m]) return false;
  if(m+(N-k)*num[0] > sum) return false;

  for(; y < R; ++y) {
    for(x %= R; x < R; ++x) {
      if(G[y][x] != 0) {
        for(int s = 0; s < 3; ++s) {
          int px = x + wx[s];
          int py = y + wy[s];
          if(draw(px,py,s,-1)) {
            X[k] = px;
            Y[k] = py;
            S[k] = s+1;
            if(rec(k+1, m+num[s], x, y)) return true;
            draw(px,py,s,1);
          }
        }
        return false;
      }
    }
  }
  return false;
}

int main() {
  can[0] = true;
  for(int i = 0; i < MAXSUM; ++i) {
    if(!can[i]) continue;
    for(int j = 0; j < 3; ++j) {
      if(i+num[j] >= MAXSUM) break;
      can[i+num[j]] = true;
    }
  }

  cin >> N;
  for(int i = 0; i < R; ++i) {
    for(int j = 0; j < R; ++j) {
      cin >> G[i][j];
      sum += G[i][j];
    }
  }
  rec(0,0,0,0);
  return 0;
}

Measured memory_bytes: 1164
a, b = map(int, input().split())
s = input()

p = 0
for i in range(len(s)):
    if a == i:
        if s[i] == "-":
            p = 1
    else:
        if s[i] == "-":
            print("No")
            exit()

if p == 0:
    print("No")
else:
    print("Yes")

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

int main() {
  int n;
  string s, t;
  cin >> n;
  cin >> s >> t;
  string ans;
  rep(i, n) {
    ans += s[i];
    ans += t[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 764
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

char s[111111];
char t[111111];
vector<int> idx[26];

int main() {
    scanf("%s", &s);
    scanf("%s", &t);
    int n = strlen(s);
    int m = strlen(t);
    for (int i = 0; i < n; i++) {
        idx[s[i] - 'a'].push_back(i);
        idx[s[i] - 'a'].push_back(i + n);
    }

    for (auto &v : idx) {
        sort(v.begin(), v.end());
    }

    using int64 = long long;
    int64 ans = 0;
    int pos = -1;

    for (int i = 0; i < m; i++) {
        int ch = t[i] - 'a';
        const auto &v = idx[ch];
        auto it = lower_bound(v.begin(), v.end(), pos + 1);
        if (it == v.end()) {
            ans = -1;
            pos = -1;         
            break;
        }
        int next = *it;
        if (next >= n) {
            pos = next - n;
            ans += n;
        } else {
            pos = next;
        }
    }

    printf("%lld\n", ans + pos + 1);
    return 0;
}

Measured memory_bytes: 1536
a = int(input())
b = int(input())
c = int(input())
d = int(input())

ans = 0

for i in range(a + 1):
    for j in range(b + 1):
        for k in range(c + 1):
            if i * 500 + j * 100 + k * 50 == d:
                ans += 1
                
print(ans)

        



Measured memory_bytes: 3060
A, B, C, X, Y = map(int, input().split())
ans = []
ans.append(A * X + B * Y)
tmp = min(X, Y) * C * 2
if X > Y:
    tmp += abs(X - Y) * A
elif X < Y:
    tmp += abs(X - Y) * B
ans.append(tmp)
ans.append(max(X, Y) * C * 2)
print(min(ans))

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


using namespace std;
double pi=3.14159265358979323846264338;

string s;
long long ans;
int main(){
	cin>>s;
	ans=0;
	int lnth=s.length();
	int fr,ls;
	int lnth2;

	long long num=stoll(s);
	for(int i=0;i<(1<<lnth-1);i++){
		long long cur=0;
		fr=0;
		lnth2=0;
		ls=0;
		while(ls<lnth){
			if(i&(1<<ls)){
				cur+=stoll(s.substr(fr,ls-fr+1));
				fr=ls+1;
			}
			ls++;
		}
		cur+=stoll(s.substr(fr,lnth-fr+1));
		ans+=cur;
	}
	cout<<ans<<endl;
			
	return 0;
}


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

using namespace std;

int n;

long long GCD(long long a, long long b)
{
    return b == 0 ? a : GCD(b, a % b);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    long long Sum = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int x = GCD(i, j);
            for (int k = 1; k <= n; k++)
            {
                Sum = Sum + GCD(x, k);
            }
        }
    }
    cout << Sum;
    return 0;
}

Measured memory_bytes: 3636
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

inline int calc(int x,int y)
{
	if(x>y)
	{
		int tmp = x/y, res = 0;
		while(tmp>=4)
			res+=2, tmp>>=2;
		return -res;
	}
	else
	{
		int res = 0;
		while(x<y)
			++res, x<<=1;
		return res + (res&1);
	}
}

int a[MAXN];
int p[MAXN], q[MAXN];
ll pre_p[MAXN], suf_q[MAXN];

int main(void)
{
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
	
	stack<pii> sta;
	sta.push(make_pair(0, inf));
	
	for(int i=1; i<n; ++i)
	{
		p[i] = calc(a[i], a[i+1]);
		pre_p[i] = pre_p[i-1];
		
		if(p[i] < 0){ sta.push(make_pair(i, -p[i])); continue;}
		
		while(p[i])
		{
			int cur = min(p[i], sta.top().second);
			pre_p[i] += cur * (i - sta.top().first);
			
			p[i] -= cur;
			sta.top().second -= cur;
			if(!sta.top().second) sta.pop();
		}
	}
	
	while(!sta.empty()) sta.pop();
	sta.push(make_pair(n+1, inf));
	
	for(int i=n; i>=2; --i)
	{
		q[i] = calc(a[i], a[i-1]);
		suf_q[i] = suf_q[i+1];
		
		if(q[i] < 0){ sta.push(make_pair(i, -q[i])); continue;}
		
		while(q[i])
		{
			int cur = min(q[i], sta.top().second);
			suf_q[i] += cur * (sta.top().first - i);
			
			q[i] -= cur;
			sta.top().second -= cur;
			if(!sta.top().second) sta.pop();
		}
	}
	
	ll ans = linf;
	for(int i=0; i<=n; ++i)
	{
		ll res = 0;
		if(i>=1) res += pre_p[i-1] + i;
		if(i+1<=n) res += suf_q[i+2];
		
		ans = min(ans, res);
	}
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 8668
import heapq

max_v,m = input().split()
max_v = int(max_v)
m = int(m)

class Edge(object):
	def __init__(self, to, cost):
		self.to = to
		self.cost = cost


edges = [[] for j in range(max_v)]
for i in range(m):
  a, b = input().split()
  a = int(a)
  b = int(b)
  edges[a-1].append(Edge(b-1,1))
  edges[b-1].append(Edge(a-1,1))

d = [float("inf")]*max_v
fire = [-1]*max_v
#fire = [[[]for j in range(max_v)] for i in range(max_v)]
def dijkstra(s):
	h = []
	d[s] = 0
	heapq.heappush(h, [0,0])
	while(len(h) != 0):
		p = heapq.heappop(h)
		v = p[1]
		if d[v] < p[0]:continue
		for i in range(len(edges[v])):
			e = edges[v][i]
			if d[e.to] > d[v] + e.cost:
				d[e.to] = d[v] + e.cost
				heapq.heappush(h, [d[e.to], e.to])
				fire[e.to] = v
dijkstra(0)
if 2 <= fire.count(-1):
  print("No")
else:
  print("Yes")
  for i in range(1, max_v):
    print(fire[i]+1)

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

class ketasu
{
public:
	void SET()
	{
		cin >> N >> K;
	}
	void calculate()
	{
		int cnt = 1;
		while (pow(K, cnt) <= N)
		{
			cnt++;
		}
		cout << cnt << endl;
	}
private:
	int N;
	int K;
};

int main()
{
	ketasu k;
	k.SET();
	k.calculate();

	return 0;
}

Measured memory_bytes: 512
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x[] = new int[n];
		int y[] = new int[n];
		for(int i=0; i<n; i++){
			x[i] = sc.nextInt();
            y[i] = x[i];
        }
		Arrays.sort(x);
		for(int i=0; i<n; i++){
			System.out.println(y[i]<=x[(n-1)/2]? x[(n-1)/2+1]:x[(n-1)/2]);
		}
	}
}

Measured memory_bytes: 94116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp(a, b) make_pair(a, b)
#define ls (rt << 1)
#define rs (rt << 1 | 1) 
typedef pair<int, int> pii; 
const ll mod = 1e9 + 7;
template <class T> T lowbit(T x){return ((x)&(-(x)));}
const int maxn = 2e5 + 10;
bool vis[maxn];
int main()
{
	int n, k;
	cin >> n >> k;
	int ans = n;
	for(int i = 1; i <= k; ++i)
	{
		int d;
		cin >> d;
		while(d--)
		{
			int v;
			cin >> v;
			vis[v] = 1;
		}
	}
	for(int i = 1; i <= n; ++i) ans -= vis[i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3624
function Main(input) {
  // 1行目がinput[0], 2行目がinput[1], …に入る
  input = input.split("\n");
  
  //入力データ取得
  var tmp0 = input[0].split(" ");
  var N = tmp0[0] - 0;
  var K = tmp0[1] - 0;
  var tmp1 = input[1].split(" ");
  
  var point = {r:tmp1[2]-0,s:tmp1[0]-0,p:tmp1[1]-0};
  var str = input[2];
  var sum = 0;
  
  for(var i=0; i<N; i++){
    var char = str[i];
    var charBK = "";
    if(i-K >= 0){
      charBK = str[i-K];
    }
    if(char == charBK){
      str = str.slice(0,i) + 'B' + str.slice(i+1);
      continue;
    }
    sum += point[char];
  }
  //出力
  console.log(sum);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 42808
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int m = sc.nextInt();
		int a[] = new int[n+1];
		for(int i = 0; i < m; i++){
		    a[sc.nextInt()] = 1;
		}
		// 計算
		long result = 0;
		long[] dp = new long[n+1];
		for(int i = 1; i < n+1; i++){
		    if(a[i] == 1){
		        dp[i] = 0;
		    }else if(i == 1){
		        dp[i] = 1;
		    }else if(i == 2){
		        dp[i] = dp[i-1] + 1;
		    }else{
		        dp[i] = dp[i-1] + dp[i-2];
		        dp[i] %= 1000000007;
		    }
		}
		result = dp[n];
		// 出力
		System.out.println(result);
		
	}
}


Measured memory_bytes: 49824
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}

void No(){
	cout<<"No"<<endl;
	exit(0);
}

int main(){
  ll N,x; cin>>N>>x;
  vector<ll> A;
  rep(i,N){
    ll a; cin>>a;
    A.push_back(a);
  }
  vector<ll> ad;
  rep(i,N-1){
    ll d=A[i+1]+A[i];
    ad.push_back(d);
  }
  
  ll count=0;
  rep(i,N-1){
    if(i==N-1){
      if(ad[N-1]>x) count+=ad[N-1]-x;
      break;
    }
    else{
      if(ad[i]<=x) continue;
      else{
      ll v1=ad[i]-x;
      ll v2=A[i+1];
      if(v1<v2){
        ad[i+1]-=v1;
        count+=v1;
      }
      else{
        ad[i+1]-=v2;
        count+=v1;
      }
      }
    }
  }
  
  cout<<count<<endl;
}
      

Measured memory_bytes: 2548
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct Node { int p, l, r; };
struct Node T[MAX];
int n;

void preparse(int u) {
	if ( u == NIL ) return;
	printf(" %d", u);
	preparse(T[u].l);
	preparse(T[u].r);
}

void inParse(int u) {
	if ( u == NIL ) return;
	inParse(T[u].l);
	printf(" %d", u);
	inParse(T[u].r);
}

void postParse(int u) {
	if ( u == NIL ) return;
	postParse(T[u].l);
	postParse(T[u].r);
	printf(" %d", u);
}

int main() {
	int i, v, l, r, root;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		T[i].p = NIL;
	}

	for (i = 0; i < n; i++ ) {
		scanf("%d %d %d", &v, &l, &r);
		T[v].l = l;
		T[v].r = r;
		if ( l != NIL ) T[l].p = v;
		if ( r != NIL ) T[r].p = v;
	}

	for (i = 0; i<n; i++ ) if ( T[i].p == NIL ) root = i;

	printf("Preorder\n"); 
	preparse(root);
	printf("\n");
	printf("Inorder\n");
	inParse(root);
	printf("\n");
	printf("Postorder\n");
	postParse(root);
	printf("\n");

	return 0;
}


Measured memory_bytes: 2100
//header
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<stdlib.h>
#include<time.h>

//main
int main(void)
{
	char s[4];

	scanf("%s", s);

	if (strlen(s) == 2) {
		printf("%s\n", s);
	}
	if (strlen(s) == 3) {
		for (int i = 0; i<3; i++) {
			printf("%c", s[2 - i]);
		}
		printf("\n");
	}

	return 0;
}




Measured memory_bytes: 128
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), K = sc.nextInt();
		int R = sc.nextInt(), S = sc.nextInt(), P = sc.nextInt();
		String T = sc.next(); 
		sc.close();
		
		char ans[] = new char[N];
		for(int i=0;i<T.length();i++) {
			if(T.charAt(i)=='r')ans[i]='p';
			else if(T.charAt(i)=='s')ans[i]='r';
			else ans[i]='s';
		}
		for(int i=0;i<N;i++) {
			if(i+K<N && ans[i]==ans[i+K]) {
				ans[i+K]='z';
			}
		}
		
		long res = 0;
		for(int i=0;i<N;i++) {
			if(ans[i]=='r')res+=R;
			if(ans[i]=='s')res+=S;
			if(ans[i]=='p')res+=P;
		}
		System.out.println(res);
	}
}


Measured memory_bytes: 28076
using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using LayoutKind = System.Runtime.InteropServices.LayoutKind;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;


static class P
{
    static void Main()
    {
        var nx = Console.ReadLine().Split().Select(int.Parse).ToArray();
        long X = nx[1];
        //ちゅーごくじょーよてーり
        //オーダーによってSの終端が決定する
        //まず影響するのは降順のみなことは自明に分かって、
        //で、「次」を選ぶことができる順番は
        //「確率」「期待値」
        //aを取り除いた場合、その後に適用できるのはそれ以前全て。

        List<int> s = Console.ReadLine().Split().Select(int.Parse).OrderByDescending(x => x).ToList();
        ModInt[] dp = new ModInt[X + 1];
        dp[X] = 1;
        long remain = s.Count - 1;
        foreach (var mod in s)
        {
            ModInt[] newDP = new ModInt[X + 1];

            for (int i = 0; i < dp.Length; i++)
            {
                newDP[i % mod] += dp[i];
                newDP[i] += dp[i] * remain;
            }
            remain--;
            dp = newDP;
        }
        ModInt res = 0;
        for (int i = 0; i < dp.Length; i++)
        {
            res += dp[i] * i;
        }
        Console.WriteLine(res);
    }
}

struct ModInt
{
    static int MOD = 1000000007;
    long Data;
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public ModInt(long data) { if ((Data = data % MOD) < 0) Data += MOD; }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static implicit operator long(ModInt modInt) => modInt.Data;
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static implicit operator ModInt(long val) => new ModInt(val);
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static ModInt operator +(ModInt a, ModInt b)
    {
        long res = a.Data + b.Data;
        return new ModInt() { Data = res >= MOD ? res - MOD : res };
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static ModInt operator +(ModInt a, long b) => new ModInt(a.Data + b);
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static ModInt operator -(ModInt a, ModInt b)
    {
        long res = a.Data - b.Data;
        return new ModInt() { Data = res < 0 ? res + MOD : res };
    }
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static ModInt operator -(ModInt a, long b) => new ModInt(a.Data - b);
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static ModInt operator /(ModInt a, ModInt b) => a * Power(b, MOD - 2);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static ModInt Power(ModInt n, long m)
    {
        ModInt res = 1;
        while (m > 0)
        {
            if ((m & 1) == 1) res *= n;
            n *= n;
            m >>= 1;
        }
        return res;
    }
}


Measured memory_bytes: 31928
#include<bits/stdc++.h>
using namespace std;
 
long long n,a[10005],b[10005],op;
long long sumpierdut,sumcastigat,k,sum;
int main(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> b[i];
    for(int i=1;i<=n;i++){
        if(a[i]<b[i]){  op+=(b[i]-a[i]+1)/2; a[i]+=((b[i]-a[i]+1)/2)*2;}
    }
    for(int i=1;i<=n;i++){
        if(b[i]<a[i] && a[i]-b[i]<=op) op-=(a[i]-b[i]),b[i]=a[i];
        else if(b[i]<a[i] && a[i]-b[i]>op){cout<<"No"; return 0;}
    }
    cout<<"Yes";
}

Measured memory_bytes: 384
#include <cstdio>
#include <cctype>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)
#define mid ((l+r)>>1)
using namespace std;

typedef long long LL;
int n,fa[132000],v[132000],son[132000][2],tot[132000];
struct data
{
    LL x,y;
    bool operator<(const data &t) const
    {
        return x<t.x;
    }
} pool[2000000],*tp,*a[132000];

int getint()
{
    char ch;
    while (!isdigit(ch=getchar()));
    int x=ch-'0';
    for (; isdigit(ch=getchar()); x=x*10+ch-'0');
    return x;
}

int find(data *a,int n,LL w)
{
    int l=1,r=n+1;
    while (l<r)
        a[mid].x>w?r=mid:l=mid+1;
    return l-1;
}

bool check(LL m)
{
    tp=pool;
    repd(i,n,1)
        if (son[i][0])
        {
            int x=son[i][0],y=son[i][1];
            if (tot[x]>tot[y])
                swap(x,y);
            static data b[132000];
            int cnt=0;
            repu(j,1,tot[x])
            {
                int t=find(a[y],tot[y],m-a[x][j].x);
                if (t)
                {
                    b[++cnt]=(data){a[x][j].y,a[y][t].y};
                    b[++cnt]=(data){a[y][t].y,a[x][j].y};
                }
            }
            if (!cnt)
                return 0;
            sort(b+1,b+1+cnt),tot[i]=0,a[i]=tp;
            repu(j,1,cnt)
                if (!tot[i] || b[j].y<a[i][tot[i]].y)
                    a[i][++tot[i]]=b[j];
            tp+=tot[i];
            repu(j,1,tot[i])
                a[i][j].x+=v[i],a[i][j].y+=v[i];
        }
        else
            tot[i]=1,a[i]=tp++,*tp=(data){v[i],v[i]};
    return 1;
}

int main()
{
    LL l=0,r=0;
    n=getint();
    repu(i,2,n)
    {
        fa[i]=getint(),r+=v[i]=getint();
        (son[fa[i]][0]?son[fa[i]][1]:son[fa[i]][0])=i;
    }
    while (l<r)
        check(mid)?r=mid:l=mid+1;
    printf("%lld\n",l);
    return 0;
}

Measured memory_bytes: 26752
#include <stdio.h>
#include <math.h>
int main(){
    int n;
    scanf("%d",&n);
    int i,j;
    int max=0;
    for(i=0;i<=n;i++)
        for(j=2;j<9;j++){
            if(pow(i,j)<=n)
               if(pow(i,j)>max)
                   max=pow(i,j);
               }
    printf("%d",max);
}


Measured memory_bytes: 384
from collections import OrderedDict, deque

n = int(input())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
tree = [[] for _ in range(n)]  # こうしないとすべて同じリストObjになる.
coloring = OrderedDict()
for e in edges:
    a, b = e[0] - 1, e[1] - 1
    tree[a].append(b)
    tree[b].append(a)
    coloring[(a, b)] = 0

q = deque()
q_append = q.append
q_popleft = q.popleft
seen = [False] * n
q_append(0)
col_count_by_v = [set() for _ in range(n)]
while len(q):
    new_v = q_popleft()
    seen[new_v] = True
    color_i = 1  # One-based index.
    for adj in tree[new_v]:
        if seen[adj]:
            continue
        q_append(adj)
        while color_i in col_count_by_v[new_v]:
            color_i += 1
        coloring[(new_v, adj)] = color_i
        col_count_by_v[new_v].add(color_i)
        col_count_by_v[adj].add(color_i)
        color_i += 1

print(len(set(coloring.values())))
for c in coloring.values():
    print(c)


Measured memory_bytes: 95120
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

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


	string S;
	cin >> S;

	ll kotae = 0;
	int kazu = 0;
	rep(i, S.size()) {
		if (S[i] == 'W') {
			kotae += i - kazu;
			kazu++;
		}
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 720
#include <bits/stdc++.h>
 
using namespace std;
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; 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; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
bool dp[100100];


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

    set<string>S;
    rep(i,N){
        string s;
        cin >> s;
        S.insert(s);
    }

    int ans = 0;
    for(auto x : S){
        ans +=1;
    }
    cout << ans << endl;
    


}

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


def solve(N: int, A: int, B: int):
    res = N // (A + B) * A
    res += min(N % (A + B), A)
    print(res)
    return


# Generated by 1.1.6 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()
    N = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(N, A, B)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	if(s=="SSS") cout<<0;
	if(s=="SSR" || s=="SRS" || s=="RSS" || s=="RSR") cout<<1;
	if(s=="RRS" || s=="SRR") cout<<2;
	if(s=="RRR") cout<<3;
	return 0;
} 

Measured memory_bytes: 3592
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(),a.end()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forr(i,n) for(int i=int(n-1);i>=0;i--)
#define fora(i,a,b) for(int i=int(a);i<=int(b);i++)
#define forb(i,a,b) for(int i=int(a);i>=int(b);i--)
#define mod 998244353 
using namespace std;
using ll=long long int;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<ll> vii;
typedef pair<ll ,ll> pii;

void solve()
{
	ll n;
	ll ans=0;
	cin>>n;
	n--;
	fora(i,1,n)
	{
		ans+=floor((double)n/i);
	}
	cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
    int t=1;
    //cin>>t;
	//init();
    while(t--)
	solve();
    return 0;
}


Measured memory_bytes: 3660
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const int N = 1e6 + 20;

int go[N][26];
int leaf[N];

int sz = 1;

void add_string(string s) {
  int v = 0;
  for (auto c : s) {
    if (!go[v][c - 'a']) {
      go[v][c - 'a'] = sz++;
    }
    v = go[v][c - 'a'];
  }
  leaf[v] = 1;
}

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector <string> a;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    add_string(s);
    a.push_back(s);
  }
  ll ans = 0;
  for (int i = 0; i < (int) a.size(); i++) {
    string s = a[i];
    vector <int> cnt(26);
    for (auto c : s) {
      cnt[c - 'a']++;
    }
    int v = 0;
    for (int i = 0; i + 1 < (int) s.size(); i++) {
      for (int x = 0; x < 26; x++) {
        if (cnt[x] && go[v][x]) {
          ans += leaf[go[v][x]];
        }
      }
      cnt[s[i] - 'a']--;
      if (!go[v][s[i] - 'a']) break;
      v = go[v][s[i] - 'a'];
    }
  }
  cout << ans << '\n';
}


Measured memory_bytes: 109236
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

res = []

for i in range(N):
    a, b = input().split()
    b = -int(b)
    res.append([a,b,i+1])

res.sort()

for i in range(N):
    print(res[i][2])

Measured memory_bytes: 38256
#include <iostream>
#include <cmath>
#define _USE_MATH_DEFINES
#include <math.h>
#include <string>
#include <iomanip>
#include <valarray>
#include <vector>


int main(int argc, char *argv[])
{
    std::cout << std::fixed << std::setprecision(0);
    int h,w;
    while(1){
        std::cin >> h >> w;
        if(h+w == 0)break;

        std::string out = "";
        for(int i = 0; i < h; ++i){
            if(i == 0 || i == h-1){
                for(int j = 0; j < w; ++j){
                    out += "#";
                }
            }
            else{
                out += "#";
                for(int j = 1; j < w-1; ++j){
                    out += ".";
                }
                out += "#";

            }
            out += "\n";
        }
        std::cout << out << std::endl;
    }

    return 0;
}

Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

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

    ll x;
    ll p = 100;
    ll cnt=0;
    cin>>x;
    while(p<x){
        p += p/100;
        cnt++;
    }

    cout<<cnt<<"\n";

    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,pair<ll,ll>> pii;
typedef pair<ll,ll> pi;
typedef vector<ll> vl;

#define matrix vector<vector<ll>>
#define llmax LLONG_MAX
#define llmin LLONG_MIN
#define rep(i,n) for(ll (i)=0;(i)<n;++(i))
#define crep(i,m,n) for(ll (i)=m;(i)<n;++(i))
#define zero(a) memset((a),0,sizeof((a)))
#define minus(a) memset((a),-1,sizeof((a)));
#define sq(a) ((a)*(a))
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define ff first
#define ss second

ll global=0;

// return nCr value
long long C(int n, int r) {
	if(r>n) return 0;
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;
    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }
    return ans;
}

// return whether number is prime or not
vector<ll> sieve(ll n){
    vector<ll> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i] && (long long)i * i <= n) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return is_prime;
}


void test_case();
int main(){
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    ll t=1;
    // cin >> t;
    for(ll T=0;T<t;T++){
        test_case();
    }
    //**************************************************************************//
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

void test_case(){
    ll n,W;cin>>n>>W;
    std::vector<ll>wt(n),val(n);
    rep(i,n){cin>>wt[i]>>val[i];}
    vector<vector<ll>>dp(n+1, vector<ll>(W+1,0));
    crep(i,1,n+1){
        crep(j,1,W+1){
            if(wt[i-1]>j){
                dp[i][j] = dp[i-1][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j], val[i-1]+dp[i-1][j-wt[i-1]]);
            }
        }
    }
    
    cout<<dp[n][W];
}


Measured memory_bytes: 83044
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int m, d;
    cin >> m >> d;
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= d; ++j) {
            int d1 = j%10, d10 = j/10;
            if(d1 < 2 || d10 < 2) continue;
            if(d1*d10 == i) {
                ans++;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define maxn 100010
int head[maxn]={0},e[maxn*2][2],w[maxn],a[maxn],c[maxn],l=1,r=0,n,m,x,y,i,t=0,ans=0;
bool mark[maxn];
void addedge(int x,int y)
{
	e[++t][1]=y;
	e[t][0]=head[x];
	head[x]=t;
}
void dfs(int x)
{
	int i;
	mark[x]=false;
	a[++r]=x;
	c[w[x]]=t;
	for (i=head[x];i;i=e[i][0])
		if (mark[e[i][1]]) dfs(e[i][1]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		scanf("%d",&w[i]);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	t=0;
	memset(mark,true,sizeof(mark));
	for (i=1;i<=n;i++)
		if (mark[i])
		{
			t++;
			dfs(i);
			for (;l<=r;l++)
				if (c[a[l]]==t) ans++;
		}
	printf("%d",ans);
	return 0;
}

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

int main() {
  vector<int> A(3);
  for(int i = 0; i < 3; i++)
    cin >> A.at(i);
  sort(A.begin(), A.end());
  cout << (A.at(1) - A.at(0)) + (A.at(2) - A.at(1)) << endl;
}

Measured memory_bytes: 256
a0,b0,a1,b1=map(int,input().split())
[x,y]=[a1-a0,b1-b0]
print("U"*y+"R"*x+"D"*y+"L"*x+"D"+"R"*(x+1)+"U"*(y+1)+"LU"+"L"*(x+1)+"D"*(y+1)+"R")

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

const int MAX = 1000000;
const int MOD = 1000000007;

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;
}

template <class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
const long long INF = 1LL << 60;

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) { cin >> A[i]; }
    sort(A.begin(), A.end());
    vector<ll> sum(N);
    sum[0] = A[0];
    ll tmpIndex = 0;
    rep(i, N - 1) { sum[i + 1] = sum[i] + A[i + 1]; }
    rep(i, N - 1) {
        if (2 * sum[i] < A[i + 1]) {
            tmpIndex = i + 1;
        };
    }
    cout << N - tmpIndex << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <cstdlib>
#define mem(i,a) memset(i,a,sizeof(i))
#define PI acos(-1.0)
#define DMAX 200000+5
#define eps 1e-8
#define mp make_pair
#define INF 1000000000+9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline void read(ll &f){
    f=0;
    ll x=1;
    char ch=getchar();
    while(ch<48 || ch>57) {
        if(ch=='-') {
            x=-1;
        }
        ch=getchar();
    }
    while(ch<=57 && ch>=48) {
        f=f*10+ch-'0';
        ch=getchar();
    }
    f*=x;
}
ll cnt[10005];
string s;
ll f[DMAX];
ll n,p;
ll ans=0;
ll pol=1;
int main(){
    mem(cnt,0);
    read(n),read(p);
    cin>>s;
    if(p==2 || p==5){
        for(int i=0;i<s.size();i++){
            ll pos=ll(s[i]-'0');
            if(pos%p==0){
                ans+=(i+1);
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    reverse(s.begin(),s.end());
    f[0]=0;
    for(ll i=0;i<n;i++){
        ll pos=ll(s[i]-'0');
        f[i+1]=(f[i]+pol*pos)%p;
        pol=pol*10%p;
    }
    cnt[0]++;
    for(ll i=0;i<n;i++){
        ans+=cnt[f[i+1]];
        cnt[f[i+1]]++;
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 2180
import sys
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline

N,M = map(int,input().split())
XY = [[] for m in range(N)]
for l in range(M):
    x,y = map(int,input().split())
    XY[x-1].append(y-1)

dp = [-1 for k in range(N)]
def search(i):
    if dp[i] != -1:
        return dp[i]
    c = 0
    start = XY[i]
    for s in start:
        c = max(c,search(s)+1)
    dp[i] = c
    return dp[i]

a = 0
for i in range(N):
    a = max(a,search(i))
print(a)


Measured memory_bytes: 59116
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
// using namespace atcoder;
void Main()
{
    ll a, b, x;
    cin >> a >> b >> x;

    ld theta = 0;
    if(2 * x < a * a * b) {
        ld tan = (ld)a * b * b / (2 * x); 
        theta = atanl(tan);
    }
    else {
        ld tan = (ld)(2 * a * a * b - 2 * x) / (a * a * a);
        theta = atanl(tan);
    }

    ld rad = theta / M_PI * 180;
    printf("%.10Lf\n", rad);

}
signed main(){ Main();return 0;}

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

using namespace std;
#define MP(x, y) make_pair(x, y);
#define PB(v, x) v.push_back(x);
typedef pair<int, int> ii;

const int MAX = 18;

int N;
ii dp[(1 << MAX)+10];

ii add(ii a, ii b) {
  vector<int> v;
  PB(v,a.first);
  PB(v,a.second);
  PB(v,b.first);
  PB(v,b.second);
  sort(v.begin(), v.end());
  return MP(v[2], v[3]);
}

int result(ii p) {
  return p.first + p.second;
}

int main() {

  cin >> N;
  for (int i = 0; i < (1<<N); i++) {
    int x;
    cin >> x;
    dp[i] = MP(-1, x);
  }
  for (int j = 0; j < N; j++) {
    for (int i = (1<<N)-1; i >= 0; i--) {
      if (i & (1<<j))
        dp[i] = add(dp[i], dp[i&~(1<<j)]);
      else
        dp[i] = dp[i];
    }
  }
  int ans = 0;
  for (int i = 1; i < (1<<N); i++) {
    ans = max(ans, result(dp[i]));
    cout << ans << endl;
  }
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main() {
int a,b;
std::cin >> a;
std::cin >> b;

if (a<=8 && b<=8) {
  printf("Yay!\n");
}else{
  std::cout << ":(" << '\n';
}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,e) for(int i=0;i<(e);i++)
#define reps(i,s,e) for(int i=(s);i<(e);i++)

int main(){
  int H,W; cin >> H >> W;
  const int INF = H+W+5;
  const vector<vector<int>> dx{{-1,0},{1,0},{0,-1},{0,1}};
  string str;
  vector<vector<int>> table(H+2,vector<int>(W+2,INF));
  queue<tuple<int,int>> q;
  reps(i,1,H+1){
    cin >> str;
    reps(j,1,W+1){
      if(str[j-1]=='#'){
        q.push(make_tuple(i,j));
        table[i][j] = 0;
      }else{
        table[i][j]--;
      }
    }
  }
  int m = 0;
  while(!q.empty()){
    int i = get<0>(q.front());
    int j = get<1>(q.front());
    int c = table[i][j] + 1;
    rep(k,4){
      int f = table[i+dx[k][0]][j+dx[k][1]];
      if(f<INF&&f>c){
        table[i+dx[k][0]][j+dx[k][1]] = c;
        q.push(make_tuple(i+dx[k][0],j+dx[k][1]));
      }
    }
    q.pop();
    m = c-1;
  }
  cout << m << endl;
  return 0;
}

Measured memory_bytes: 12432
import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        int n = Integer.parseInt(br.readLine());
      		String[] strs = new String[52];
	        Boolean[] judes = new Boolean[52];
	        String[] suit = {"S","H","C","D"};
	        for(int i = 0; i < suit.length; i++){
			for(int l = 1; l <= 13; l++){
                		strs[i * 13 + l - 1] = suit[i] + " " + l;
                		judes[i * 13 + l - 1] = false;
           		}
       		}
        	for(int i = 0; i < n; i++){
        		String str = br.readLine();
          		for(int l = 0; l < strs.length; l++){
                		if(str.equals(strs[l])){
                   			judes[l] = true;
          	          		break;
                		}
            		}
        	}
        	for(int i = 0; i < judes.length; i++){
        		if(!judes[i]){
                		System.out.println(strs[i]);
            		}
        	}
    	}
}

Measured memory_bytes: 16876
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, a, b;
    cin >> n >> a >> b;
    if(abs(a - b) % 2 == 0){
        cout << "Alice" << endl;
    }else{
        cout << "Borys" << endl;
    }
}

Measured memory_bytes: 256
n = int(input())
info = [tuple(map(int, input().split())) for _ in range(n)]
nonzeroinfo = []
for x, y, h in info:
    if h > 0:
        nonzeroinfo.append((x, y, h))
zeroinfo = []
for x, y, h in info:
    if h == 0:
        zeroinfo.append((x, y, h))
def checknonzero(x, y, h):
    for a, b, c in nonzeroinfo:
        if h != abs(x-a) + abs(y-b) + c:
            return False
    return True
def checkzero(x, y, h):
    for a, b, _ in zeroinfo:
        if abs(x-a) + abs(y-b) < h:
            return False
    return True
for x in range(101):
    for y in range(101):
        x1, y1, h1 = nonzeroinfo[0]
        h = abs(x-x1) + abs(y-y1) + h1
        ret1 = checknonzero(x, y, h)
        ret2 = checkzero(x, y, h)
        if ret1 and ret2:
            print(x, y, h)
            exit()

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

int main(){
  int a,b,count=0;
  cin >> a >> b;
  for(int i = a; i<=b ; i++){
    string s1 = to_string(i);
    string s2 = s1;
    reverse(s2.begin(),s2.end());
    if(s1==s2)count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 256