akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;



int main(){
	double n, m, sum = 0;
	cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
		sum += a[i];
	}
	double worst = (double)sum/(4*m);
	sort(a.begin(), a.end(), greater<int>());
	for (int i = 0; i < m; i++){
		if (a[i] < worst){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
 	return 0;
 }




Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String x = br.readLine();
		String[] cut = x.split(" ");
		String a = cut[0];
		String b = cut[1];
		String c = cut[2];

		String q = a.substring(0, 1);
		String w = b.substring(0, 1);
		String e = c.substring(0, 1);

		String p = q.toUpperCase();
		String o = w.toUpperCase();
		String i = e.toUpperCase();

		System.out.println(p + o + i);

	}

}

Measured memory_bytes: 21332
S = input()

MOD = 10 ** 9 + 7
dp, dp_a, dp_ab, dp_abc = 1, 0, 0, 0

for s in S:
    if s == 'A':
        dp_a += dp
    elif s == 'B':
        dp_ab += dp_a
    elif s == 'C':
        dp_abc += dp_ab
    else:
        dp, dp_a, dp_ab, dp_abc = dp * 3, dp_a * 3 + dp, dp_ab * 3 + dp_a, dp_abc * 3 + dp_ab
    dp %= MOD
    dp_a %= MOD
    dp_ab %= MOD
    dp_abc %= MOD
print(dp_abc)


Measured memory_bytes: 9264
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct E{
    int t;
    int d;
    E(int _t, int _d){
        t = _t;
        d = _d;
    }
};

struct V{
    int cost = -1;
    vector<E> es;
};

typedef vector<V> G;

typedef pair<int, int> P;


int main (int argc, char* argv[]){
    int v, e, r;
    cin >> v >> e >> r;
    G graph(v);
    for (int i = 0; i < e; i++) {
        int s, t, d;
        cin >> s >> t >> d;
        graph[s].es.push_back(E(t, d));
    }

    priority_queue<P> q;
    q.push(P(r, 0));
    graph[r].cost = 0;

    while (!q.empty()) {
        P next = q.top();
        q.pop();
        int v = next.first;
        int hereCost = next.second;
        for (auto e : graph[v].es) {
            int cost = e.d;
            int newCost = hereCost + cost;
            int oldCost = graph[e.t].cost;
            if (newCost < oldCost || oldCost == -1) {
                graph[e.t].cost = newCost;
                q.push(P(e.t, newCost));
            }
        }
    }

    for (auto v: graph) {
        int d = v.cost;
        if (d == -1) {
            cout << "INF" << endl;
        }else{
            cout << d << endl;
        }
    }

	return 0;
}

Measured memory_bytes: 20648
H, W, M = map(int, input().split())

hdic = {}
wdic = {}
hws_h = {}
hws_w = {}

for m in range(M):
    h, w = map(int, input().split())
    if h in hdic.keys():
        hdic[h] += 1
        hws_h[h].append(w)
    else:
        hdic[h] = 1
        hws_h[h] = [w]
    
    if w in wdic.keys():
        wdic[w] += 1
        hws_w[w].append(h)
    else:
        wdic[w] = 1
        hws_w[w] = [h]

hmax = max(hdic.values())
wmax = max(wdic.values())

hs = []
ws = []

hs = [k for k, v in hdic.items() if v==hmax]
ws = [k for k, v in wdic.items() if v==wmax]

f = 1

if len(ws) < len(hs):
    for h in hs:
        wlist = hws_h[h]
        for w in ws:
            if w not in wlist:
                f = 0
                break
        if f == 0:
            break
        
else:
    for w in ws:
        hlist = hws_w[w]
        for h in hs:
            if h not in hlist:
                f = 0
                break
        if f == 0:
            break

print(hmax + wmax - f)


Measured memory_bytes: 240604
#!/usr/bin/env python

def list_sum(a, b):
    n = len(a)
    c = [0] * n
    for i in range(n):
        c[i] = a[i] + b[i]
    return c

def skilled(ca_sum, x):
    m = len(ca_sum) - 1
    ret = True
    for i in range(1, m+1):
        ret = ret and ca_sum[i] >= x
    return ret

def main():
    n, m, x = map(int, input().split())
    ca = [list(map(int, input().split())) for _ in range(n)]
    c_list = []

    for i in range(2 ** n):
        ca_sum = [0] * (m+1)
        for j in range(n):
            if (i >> j) & 1:
                ca_sum = list_sum(ca_sum, ca[j])
        if skilled(ca_sum, x):
            c_list.append(ca_sum[0])

    if c_list == []:
        print(-1)
    else:
        c_list.sort()
        print(c_list[0])

if __name__ == '__main__':
    main()


Measured memory_bytes: 9320
import java.util.Scanner;
import java.util.HashSet;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    HashSet<String> set = new HashSet<>();
    int t = scan.nextInt();
    int ans = 0;
    for(int i = 0; i < t; i++){
        String s = scan.next();
        if(!set.contains(s)){
            set.add(s);
            ans++;
        }
    }
    System.out.println(ans);
  }
}

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


int main (){
    int N;
  cin>>N;
    if(N/1000==(N/100)%10||(N/100)%10==(N/10)%10||(N/10)%10==N%10){
        cout<<"Bad"<<endl;
    }
    else{
        cout<<"Good"<<endl;
    }
}

Measured memory_bytes: 256
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}


int main()
{

   fastread();

   ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,ans=0;

      bool flag=false;

      string str;

      cin>>a>>b;

      if(a>=13)
        cout<<b<<endl;

      else if(a>=6)cout<<b/2<<endl;

      else cout<<0<<endl;













}



Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;
const int INF = INT_MAX / 2;

int N; 

ll dfs(string s){
    ll num = stoll(s);
    if(num>N){
        return 0;
    }

    bool has_three, has_five, has_seven;
    has_three = has_five = has_seven = false;

    for (int i = 0; i < s.size(); i++)
    {
        if(s[i]=='3') has_three = true;
        else if(s[i]=='5') has_five = true;
        else if(s[i]=='7') has_seven = true;
    }
    ll cnt = 0;
    if(has_three&&has_five&&has_seven) cnt++;

    cnt += dfs(s+"3") + dfs(s+"5") + dfs(s+"7");
    return cnt;
}


int main(){
    cin >> N;
    ll ans = 0;
    ans += dfs("3");
    ans += dfs("5");
    ans += dfs("7");
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main()
{
	char S[10];
	scanf("%s",S);
	if(strcmp(S,"Sunny")==0)
		printf("Cloudy");
	if(strcmp(S,"Cloudy")==0)
		printf("Rainy");
	if(strcmp(S,"Rainy")==0)
		printf("Sunny");
	
	return 0;
}

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

void outPut(vector<int> work) {
    string alphabet = {"abcdefghijklmnopqrstuvwxyz"};
    string result = "";
    for (int w: work) {
        result.push_back(alphabet[w]);
    }
    cout << result << endl;
}

void dfs(vector<int> work, int max, int N) {
    if (work.size() == N) {
        outPut(work);
    } else {
        for (int i = 0; i <= max; ++i) {
            auto newWork = work;
            newWork.push_back(i);
            // i == max の場合maxが更新される
            dfs(newWork, i == max ? max + 1 : max, N);
        }
    }
}

int main(void){

    int N = 0;
    cin >> N;
    
    vector<int> work;
    dfs(work, 0, N);

    return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define cans cout << ans << endl
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
typedef long long ll;


int main(){
    int n,k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    sort(h.begin(),h.end());
    int ans = 1e9;
    for(int i=0; i<=h.size()-k; i++){
        int now = h[i+k-1]-h[i];
        ans = min(now,ans);
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
const ll mod = 1e9 + 7;
const int INF = 1e9;

int main() {
	cin.sync_with_stdio(false);
	int X, Y, Z;
	cin >> X >> Y >> Z;
	cout << X / (Y + Z) - (X % (Y + Z) >= Z ? 0 : 1) << endl;
	return 0;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    a = [int(an) for an in input().split()]
    divider = 10 ** 9 + 7
    ans = 0
    total = sum(a)
    tmp = 0
    for i in range(n - 1):
        ai = a[i]
        tmp += ai
        ans = (ans + a[i] * (total - tmp)) % divider
    print(ans)


if __name__ == '__main__':
    main()


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

int a[100001]={0};

int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;++i){
        int tmp;
        cin >> tmp;
        a[tmp-1]++;
        a[tmp]++;
        a[tmp+1]++;
    }
    int ans=0;
    for(int i=0;i<=100000;++i)
        ans = max(ans, a[i]);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vi=vector<int>;

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

template<class T> ll llpow(T x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int main(){
    int n,r;
    cin>>n>>r;
    if(n>=10)cout<<r<<endl;
    else {
        cout<<r+(100*(10-n))<<endl;
    }
    return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
// #define endl '\n'
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rf(i,a,b) for(int i=a;i>=b;i--) 
#define fast_io ios_base::sync_with_stdio(0);
#define show(x) cout<<x<<endl;
#define pret(x) cout<<x<<endl; return 0;
#define disp(x) cout<<x<<" ";
#define let(x,y) cout<<x<<" "<<y<<endl;
ll MOD=1e9+7;
ll MAX=9223372036854775807;

int f(int n){
	fo(i,1,n){
		int temp = i*(i+1);
		if(temp==n) return i;
		if(temp>n) break;
	}
	return 0;
}

int main(){
    fast_io;
    int n;
    cin>>n;
    int k=f(2*n);
    if(k==0) {
    	pret("No");
    }
    show("Yes");
    show(k+1);
    vi v[k+2];
    fo(i,1,k) v[1].emplace_back(i);
    int temp=k+1;
    fo(i,2,k+1){
    	int flag=0;
    	fo(j,1,i-1){
    		flag++;
    		v[i].emplace_back(v[j][i-2]);
    	}
    	while(flag<k){
    		v[i].emplace_back(temp);
    		temp++;
    		flag++;
    	}
    }
    fo(i,1,k+1){
    	disp(k);
    	for(auto j:v[i]){
    		disp(j);
    	}
    	cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 2304
import java.util.Scanner;
import java.util.TreeSet;


public class Main {
	static class Range implements Comparable<Range>{
		long start;
		long depth;
		Range(long s , long d){
			start = s;
			depth = d;
		}
		public Range(Range r) {
			start = r.start;
			depth = r.depth;
		}
		@Override
		public int compareTo(Range o) {
			int c = Long.compare(start, o.start);
			if(c == 0){
				return Long.compare(o.depth, depth);
			}
			return c;
		}
	}
	static class Reversi{
		long black;
		TreeSet<Range> tops;
		TreeSet<Range> lefts;
		public Reversi(int N) {
			long n = (long)N;
			tops = new TreeSet<Range>();
			lefts = new TreeSet<Range>();

			black = (n - 2) * (n - 2);
			Range r = new Range(2, n - 2);
			tops.add(r);
			lefts.add(r);
		}
		void put(int q, int x){
			if(q == 1){
				Range r = tops.lower(new Range(x , -1));
				Range t0 = tops.first();
				black -= r.depth;
				if(t0.start != r.start){
					return ;
				}else{
					Range t = new Range(tops.pollFirst());
					Range l = new Range(lefts.pollFirst());
					l.depth = x - 2;
					lefts.add(l);
					Range t2 = new Range(x + 1, t.depth);
					tops.add(t);
					tops.add(t2);
				}
			}else{
				Range r = lefts.lower(new Range(x , -1));
				Range t0 = lefts.first();
				black -= r.depth;
				if(t0.start != r.start){
					return ;
				}else{
					Range t = new Range(lefts.pollFirst());
					Range l = new Range(tops.pollFirst());
					l.depth = x - 2;
					tops.add(l);
					Range t2 = new Range(x + 1, t.depth);
					lefts.add(t);
					lefts.add(t2);
				}
				
			}
		}
		long black(){
			return black;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		Reversi r = new Reversi(N);
		int Q = sc.nextInt();
		for(int q = 0 ; q < Q ; ++q){
			int a = sc.nextInt();
			int x = sc.nextInt();
			r.put(a, x);
		}
		System.out.println(r.black());
	}
}


Measured memory_bytes: 81848
N = int(input())
a = list(map(int, input().split()))
b = []
for i in range(N):
    b.append([a[i], i+1])
b.sort(reverse = True)
ans = [0]*(N+1)
mini = N+1

for i in range(N-1):
    mini = min(mini, b[i][1])
    if b[i+1][0] - b[i][0] < 0:
        ans[mini] += (b[i][0] - b[i+1][0])*(i+1)

ans[1] += N*b[-1][0]
for i in range(N):
    print(ans[i+1])


Measured memory_bytes: 25580
#include<bits/stdc++.h>
    #include<climits>
    using namespace std;
    int main()
    {
         long long int n,i,flag=0;
        cin>>n;
       long long int ar[n];
        for(i=0;i<n;i++)
            cin>>ar[i];
        if(n==1)
            cout<<"0"<<endl;
        else{
            long long int mi=INT_MIN;
        for(i=0;i<n-1;i++)
        {
            if(ar[i]>=ar[i+1])
                {
                flag++;
                }
            else if(ar[i]<ar[i+1])
            {
                flag=0;
            }
            if(mi<flag)
            {
                mi=flag;
            }
        }
        cout<<mi<<endl;
        }
    }


Measured memory_bytes: 1024
// AOJ 2488 Tree Construction
// 2018.2.28 bal4u

#include <stdio.h>
#include <string.h>

#define ABS(a)  ((a)>=0?(a):-(a))
int x[1001], y[1001];
int dp[1001][1001];

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	do n = 10*n + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

int main()
{
	int n, i, j, l, t;

	n = in();
	for (i = 0; i < n; i++) x[i] = in(), y[i] = in();

	memset(dp, 0x10, sizeof(dp));
	for (i = 0; i < n; i++) dp[i][i] = 0;

	for (l = 0; l < n; l++) for (i = 0; i+l < n; i++) for (j = i; j-i < l; j++) {
		t = dp[i][j] + dp[j+1][i+l] + ABS(x[i]-x[j+1]) + ABS(y[j]-y[i+l]);
		if (t < dp[i][i+l]) dp[i][i+l] = t;
	}
	printf("%d\n", dp[0][n-1]);
	return 0;
}


Measured memory_bytes: 5764
#!/bin/sh
read n
read -d "" L
cnt=0
x=0
for i in `echo $L | awk '{for(i=1;i<=NF;i++)print $i}' | sort -n`
do
	if [ $cnt -eq 0 ]
	then
		x=$(( x + i ))
		cnt=1
	else
		cnt=0
	fi
done
echo $x


Measured memory_bytes: 2120
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main()
{
	for(int n;cin>>n,n;){
		vector<int> is(n),ps(n),qs(n),rs(n);
		for(int i=0;i<n;i++)
			cin>>is[i]>>ps[i]>>qs[i]>>rs[i];
		int P,Q,R,C; cin>>P>>Q>>R>>C;
		
		vector<int> res;
		for(int i=0;i<n;i++){
			if(ps[i]<=P && qs[i]<=Q && rs[i]<=R && ps[i]*4+qs[i]*9+rs[i]*4<=C)
				res.push_back(is[i]);
		}
		
		if(res.empty())
			cout<<"NA"<<endl;
		else
			for(int i=0;i<res.size();i++)
				cout<<res[i]<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 932
N, WE = list(map(int, input().split()))
V = []
W = []
for i in range(N):
    v, w = list(map(int, input().split()))
    V.append(v)
    W.append(w)

DP = [0] * (WE+1)
# DP = [0] * 20

# DP[j]: 重さjのときの価値の最大
DP[0] = 0

for i in range(N):
    for j in range(WE+1):
        if j + W[i] <= WE:
            DP[j+W[i]] = max(DP[j+W[i]], DP[j]+V[i])
    # print(DP)

print(DP[WE])


Measured memory_bytes: 5916
object Main {
	def nextAlphabet(c: Char) : Char = {
	  val list = "abcdefghijklmnopqrstuvwxyz".toList
	  val pos = list.indexOf(c)
	  if(list(pos) == 'z') return list(0)
	  else return list(pos+1)
	}

    def main(args:Array[String]) = {
        val sc = new java.util.Scanner(System.in)
        while(sc.hasNext){
	        val a = sc.nextLine
	        var c = a.toCharArray
            for(i <- 0 until 26){
                for(j <- 0 until c.length){
                     if (c(j) != ' ' && c(j) != '.'){
                         c(j) = nextAlphabet(c(j))
                     }
                }
                val s = new String(c)
                if(s.contains("the") || s.contains("this") || s.contains("that")) println(s)
            }
    	}
    }
}

Measured memory_bytes: 50752
function Main(input) {
  input=input.split("\n");
  var string=input[0].split(" ")[0];
  var output="";
  var hate=input[1].split(" ");
  var i=string-0;
  var temp;
  while(true){
    //console.log(i);
    temp=(i+"").split('');
    if(temp.every(e=>{return !hate.includes(e);})){
      console.log(i);
      return;
    }
    i++;
  }
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
  
  

Measured memory_bytes: 37088
#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(){
   ll K,N;
   cin >> K >> N;

   ll d;

   vector<ll> A(N);

   rep(i,N){
      cin >> A.at(i);
   }
   rep(i,N-1){
      ll m;
      m = A.at(N-i-1) - A.at(N-i-2);
      if(m > K/2)
      m = K - m;

      d = max(d,m);
   }
   ll o;
   o = A.at(N-1) - A.at(0);
   if(o > K/2)
   o = K - o;
   d = max(d,o);

   cout << K - d;

   return 0;  
}

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

using namespace std;

#define endl "\n"
typedef long long int ll;

#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
inline void setPrecision(int n){cout.precision(n);}

ll INF = 1e10;
ll MOD = 1e9+7;

int n;
int a[21][21];

ll done[1<<21];

ll pairs(int state){
    int idx = __builtin_popcount(state);
    if(idx == n) return 1;
    if(done[state] != -1) return done[state];
    ll ans = 0;
    for(int i=0;i<n;++i)
        if(a[idx][i] && !(state&(1<<i)))
            ans = (ans + pairs(state|(1<<i)))%MOD;
    done[state] = ans;
    return ans;
}

int main(){
    fastio;
    cin>>n;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            cin>>a[i][j];
    memset(done, -1, sizeof(done));
    cout<<pairs(0);
    return 0;
}


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

class maxheap{
    vector <int> H;
    int maxsize;
    int size;

public:
    maxheap(int maxsize) : maxsize(maxsize){
        H.resize(maxsize);
        size=0;
    }

    void Insert(int p){
        if (size==maxsize) return;
        size+=1;
        H[size-1]=p;
        SiftUp(size-1);
    }
    int parent(int i){
        return floor((i-1)/2);
    }
    int leftchild(int i){
        return 2*i+1;
    }
    int rightchild(int i){
        return 2*i+2;
    }
    void SiftUp(int i){
        while (i>0 && H[parent(i)]<H[i] ) {
            swap(H[parent(i)], H[i]);
            i=parent(i);
        }
    }
    void ChangePrioirty(int i,int p){
        int oldval=H[i];
        H[i]=p;
        if (H[i]>oldval) SiftUp(i);
        else SiftDown(i);
        
    }
    void SiftDown( int i){
        int maxi=i;
        int l=leftchild(i);
        if (l<size && H[l]>H[maxi]){
            maxi=l;
        }
        int r= rightchild(i);
        if (r<size and H[r]>H[maxi]){
            maxi=r;
        }
        if (i!=maxi){
            swap(H[i], H[maxi]);
            SiftDown(maxi);
        }
    }
    int getMax(int i){
        return H[0];
    }
    void printfinalsum(){
        long long sum=0;
        for (int i=0; i<maxsize; i++){
            sum+=H[i];
        }
        cout<<sum<<endl;
    }
    void printheapvalues(){
        cout<<"heap values are "<<endl;
        for (int i=0; i<maxsize; i++){
            cout<<H[i]<<" ";
        }cout<<endl;
    }
};

int main(){
    int n, m;
    cin>>n>>m;
    maxheap heap(n);
    for (int i=0; i<n; i++){
        int val;
        cin>>val;
        heap.Insert(val);
    }
    //heap.printheapvalues();
    while (m>0){
        int tobehalved= heap.getMax(0);
        //cout<<tobehalved<<" is tobehalved for m "<<m<<endl;
        heap.ChangePrioirty(0, tobehalved/2);
        m--;
    }
    heap.printfinalsum();
    return 0;
}

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


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

    int arr[n];
    //int arr[n] = {0};
    for (int i = 0; i < n; i++)
    {
        arr[i] = 0;
    }
    

    for(int i = 1;i <= k;i ++){
        int d;
        cin >> d;
        
        int num;
        for (int k = 0; k < d; k++)
        {
            cin >> num;
            arr[num - 1] = 1;
        }
        
    }

    int count = 0;

    for(int i = 0;i < n;i ++){
        if(arr[i] == 0){
            count ++;
        }
    }

    cout << count << endl;


    return 0;
    

}

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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri(), k = ri();
	int a[n];
	for (int i = 0; i < n; i++) a[i] = ri();
	int64_t sum = std::accumulate(a, a + n, 0LL);
	
	std::vector<int64_t> yaku;
	for (int i = 1; i * i <= sum; i++) if (!(sum % i)) yaku.push_back(i), yaku.push_back(sum / i);
	std::sort(yaku.begin(), yaku.end(), std::greater<>());
	
	for (auto i : yaku) {
		if (sum % i) continue;
		std::vector<int> ama;
		int64_t ama_sum = 0;
		for (int j = 0; j < n; j++) if (a[j] % i) ama.push_back(a[j] % i), ama_sum += a[j] % i;
		if (!ama.size()) {
			std::cout << i << std::endl;
			return 0;
		}
		std::sort(ama.begin(), ama.end(), std::greater<>());
		assert(ama_sum % i == 0);
		int64_t cost = 0;
		for (auto j : ama) {
			cost += i - j;
			ama_sum -= j;
			if (ama_sum == cost) break;
		}
		if (cost <= k) {
			std::cout << i << std::endl;
			return 0;
		}
	}
	assert(0);
	return 0;
}


Measured memory_bytes: 256
#ifdef __unix__
#include <bits/stdc++.h>
#else
#include <iostream>
#include <algorithm>
#include <math.h>
#include <functional>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <unordered_set>
#include <stack>
#include <bitset>
#endif

#define fastIO ios_base::sync_with_stdio(0), cin.tie(NULL)
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl '\n'
#define mkp make_pair
/*#define NUMTOSTR(x)  (unsigned char)((x) + 48);*/
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long  ull;
using namespace std;

int main(){
	fastIO;
	int a, b, n;
	cin >> a >> b >> n;
	bool t = true;
	while (n--)
	{
		if (t) {
			if (a & 1) a -= 1;
			b += a / 2;
			a /= 2;
		}
		else {
			if (b & 1) b -= 1;
			a += b / 2;
			b /= 2;
		}
		t ^= 1;
	}
	cout << a << ' ' << b;
	return 0;
}


Measured memory_bytes: 3600
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define of(i,l,r) for(int i=l;i>=r;i--)
#define fe(i,u) for(int i=head[u];i;i=e[i].next)
#define el putchar('\n')
#define ta putchar('	')
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline void open(const char *s)
{
	#ifndef ONLINE_JUDGE
	char str[20];
	sprintf(str,"%s.in",s);
	freopen(str,"r",stdin);
//	sprintf(str,"%s.out",s);
//	freopen(str,"w",stdout);
	#endif
}
inline int rd()
{
	static int x,f;
	x=0;f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return f>0?x:-x;
}
const int N=100010;
int n,d[N],head[N],tot=0;
ll a[N];
struct edge{int v,next;}e[N<<1];

inline void add(int u,int v){e[++tot]=edge{v,head[u]};head[u]=tot;++d[u];}

ll dfs(int u,int fat)
{
	if(d[u]==1)return a[u];
	ll sum=0,mx=0;
	fe(i,u){
		int v=e[i].v;if(v==fat)continue;
		ll hh=dfs(v,u);
		if(hh==-1)return -1;
		sum+=hh;mx=max(mx,hh);
	}
	if(sum<a[u])return -1;
	if(mx<sum-mx&&sum-a[u]>sum/2)return -1;
	if(mx>sum-mx&&sum-a[u]>sum-mx)return -1;
	return (ll)a[u]-(sum-a[u]);
}

int main()
{
	n=rd();fo(i,1,n)a[i]=rd();
	fo(i,2,n){
		int x=rd(),y=rd();
		add(x,y);add(y,x);
	}
	if(n==2)return puts(a[1]^a[2]?"NO":"YES"),0;
	int rt=0;
	fo(i,1,n)if(d[i]>1){rt=i;break;}
	puts(dfs(rt,0)==0?"YES":"NO");
	return 0;
}


Measured memory_bytes: 8704
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define Rep(i,n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout << endl;
#define prique(T) priority_queue<T,vector<T>,greater<T>>
struct edge { int to, cost; };
typedef pair<int, int> P;
typedef pair<P, int> PP;
const int mod = 1e9 + 7, inf = 1e16;

int modpow(int x, int n) {
	int ans = 1;
	while (n > 0) {
		if (n & 1) {
			if (mod <= ans * x) ans = ans * x % mod;
			else ans *= x;
		}
		if (mod <= x * x) x = x * x % mod;
		else x *= x;
		n >>= 1;
	}
	return ans;
}

int fact_memo[114514];
int fact(int n) {
	int ans = 1;
	if (fact_memo[n]) return fact_memo[n];
	rep(i, n) {
		ans *= (i + 1);
		if (mod <= ans) ans %= mod;
	}
	fact_memo[n] = (ans + mod) % mod;
	return (ans + mod) % mod;
}

int comb(int n, int r) {
	if (n < r) return 0;
	if (n - r < r) r = n - r;
	return (fact(n) * modpow(fact(n - r), mod - 2) % mod * modpow(fact(r), mod - 2) + mod) % mod;
}

int perm(int n, int r) {
	if (n < r) return 0;
	if (n - r < r) r = n - r;
	return (fact(n) * modpow(fact(n - r), mod - 2) % mod + mod) % mod;
}

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

bool pri(int p) {
	for (int i = 2; i * i <= p; i++) if (p % i == 0) return false;
	return p > 1;
}

int n, j;
int a[114514], l[114514], r[114514];
int ans = 0;
signed main() {
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}
	l[0] = a[0];
	r[n - 1] = a[n - 1];
	rep(i, n - 1) {
		l[i + 1] = gcd(l[i], a[i + 1]);
		j = n - 2 - i;
		r[j] = gcd(r[j + 1], a[j]);
	}
	rep(i, n) {
		if (i == 0) {
			ans = r[i + 1];
		}
		else if (i == n - 1) {
			ans = max(ans, l[i - 1]);
		}
		else {
			ans = max(ans, gcd(l[i - 1], r[i + 1]));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 2688
a=[]
h,w=map(int,input().split())
for i in range(h):
    a.append(input()+'#')
a.append('#'*(w+1))
b=[[0]*(w+1) for i in range(h+1)]
c=[[0]*(w+1) for i in range(h+1)]

for i in range(h+1):
    t=0
    for j in range(w+1):
        if a[i][j]=='#':
            for k in range(t):
                b[i][j-k-1]=t
            t=0
        else:
            t+=1

for j in range(w+1):
    t=0
    for i in range(h+1):
        if a[i][j]=='#':
            for k in range(t):
                c[i-k-1][j]=t
            t=0
        else:
            t+=1
ans=0
for i in range(h+1):
    for j in range(w+1):           
        ans=max(b[i][j]+c[i][j]-1,ans)
print(ans)

Measured memory_bytes: 123608
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}



signed main(){
	int k,a,b; cin>>k>>a>>b;
	for(int i=a; i<=b; i++){
		cerr<<i%k<<endl;
		if(i%k==0) return cout<<"OK"<<endl,0;
	}
	cout<<"NG"<<endl;
	return 0;
}


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

using namespace std;

int main() {
    int n, a;
    cin >> n;
    int res = 0;
    for (int i=0; i<n; ++i) {
        cin >> a;
        res += a-1;
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll n,a,b;
  cin >> n >> a >> b;
  if(a>b) cout << 0 << endl;
  else if(n == 1){
    if(a != b) cout << 0 << endl;
    else cout << 1 << endl;
  }else if(n == 2) cout << 1 << endl;
  else cout << (n-2)*b-(n-2)*a+1 << endl;
}


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

using namespace std;

#define dbg(x) { cerr << #x << " - " << x << endl; }

int main() {
	int n;
	cin >> n;
	vector<int> a(n), s(n);
	for(int i = 0; i < n; i++) cin >> a[i], s[i] = a[i];
	sort(s.begin(), s.end());
	int maxi = s[s.size() - 1], nxt = s[s.size() - 2];
	for(int i = 0; i < n; i++) {
		if(a[i] == maxi) cout << nxt << endl;
		else cout << maxi << endl;
	}
	return 0;
}


Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n,m,k;
  cin>>n>>m>>k;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  vector<Int> dp(a);
  for(Int i=1;i<k;i++){
    vector<Int> nx(n,0);
    deque<Int> d;
    for(Int j=i;j<n;j++){
      while(!d.empty()&&d.front()<j-m) d.pop_front();
      while(!d.empty()&&dp[d.back()]<=dp[j-1]) d.pop_back();
      d.emplace_back(j-1);
      nx[j]=dp[d.front()];
    }
    swap(dp,nx);
    for(Int j=0;j<n;j++) dp[j]+=(i+1)*a[j];
  }
  cout<<*max_element(dp.begin(),dp.end())<<endl;
  return 0;
}


Measured memory_bytes: 2656
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define bye return 0
#define Yes cout << "Yes" << "\n"
#define No  cout << "No" << "\n"
#define YES cout << "YES" << "\n"
#define NO cout << "NO" << "\n"
#define endl cout << "\n"
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    map<int, int> m;
    vector<int> v;
    int a, b, c;
    cin >> a >> b >> c;
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);

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

    if((v[0]+v[1])==v[2]) Yes;
    else No;

    // for(auto i: v) cout << i;
    // 	endl;
    bye;
}

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

int main(){
    int Q;
    cin >> Q;
    vector<int> l(Q), r(Q);
    for(int i = 0; i < Q; ++i) {
        cin >> l[i] >> r[i];
    }
    vector<int> isPrime(100001, 1);
    isPrime[0] = isPrime[1] = 0;
    for(int i = 2; i*i <= 100000; ++i) {
        if(isPrime[i] == 1)
            for(int j=2; i*j <= 100000; ++j)
                isPrime[i*j] = 0;
    }
    vector<int> sim2017(100001, 0);
    for(int i = 3; i <= 100000; ++i) {
        if(isPrime[i] == 1 && isPrime[(i+1)/2] == 1)
            sim2017[i] = 1;
    }
    for(int i = 3; i <= 100000; ++i) {
        sim2017[i] += sim2017[i-1];        
    }
    for(int i = 0; i < Q; ++i) {
        cout << sim2017[r[i]] - sim2017[l[i]-1] << endl;
    }
    return 0;
}

Measured memory_bytes: 2304
N = int(input())

c0 = 0
c1 = 0
c2 = 0
c3 = 0

for i in range(1, N+1) :
    s = input()
    if s == 'AC' :
        c0 = c0 + 1
    elif s == 'WA' :
        c1 = c1 + 1
    elif s == 'TLE' :
        c2 = c2 + 1
    elif s == 'RE' :
        c3 = c3 + 1

print("AC x " + str(c0))
print("WA x " + str(c1))
print("TLE x " + str(c2))
print("RE x " + str(c3))


Measured memory_bytes: 9188
N, M = map(int,input().split())
H = list(map(int, input().split()))
L = []
for i in range(M):
  L.append(list(map(int, input().split())))
  
H = [0] + H
A = [0] + [1] * N

for i in range(M):
  if H[L[i][0]] > H[L[i][1]]:
    A[L[i][1]] = 0
  elif H[L[i][0]] < H[L[i][1]]:
    A[L[i][0]] = 0
  else:
    A[L[i][0]] = 0
    A[L[i][1]] = 0
print(A.count(1))

Measured memory_bytes: 32824
package main
import (
   "fmt"
   "os"
   "bufio"
   "strconv"
)
var sc = bufio.NewScanner(os.Stdin)

func main() {
  sc.Split(bufio.ScanWords)
  n := nextInt()
  y := nextInt()

  re10000 := "-1"
  re5000 := "-1"
  re1000 := "-1"
  for i := 0; i <= n; i++ {
    for j := 0; j <= n; j++ {
      //for r := 0; r < n; r++ {
	  r := n - i - j
	  if r >= 0 && i * 10000 + j * 5000 + r * 1000 == y {
		  re10000 = strconv.Itoa(i)
		  re5000 = strconv.Itoa(j)
		  re1000 = strconv.Itoa(r)
	  }
      //}
    }
  }
  fmt.Println(re10000 + " " + re5000 + " " + re1000)

}

func arrayExist(element int, arr []int) (bool) {
	  for _, v := range arr {
		  if v == element {
			  return true
		  }
	  }
	  return false
}

func nextString() (string) {
	sc.Scan()
	v := sc.Text()
	return v
}

func nextInt() (int) {
	sc.Scan()
	v, e := strconv.Atoi(sc.Text())
    if e != nil { panic(e) }
    return v
}

func nextFloat() (float64) {
	sc.Scan()
	v, e := strconv.ParseFloat(sc.Text(), 64)
    if e != nil { panic(e) }
    return v
}


Measured memory_bytes: 640
n=int(input())
a=[[int(i) for i in input().split()] for j in range(n)]
dp=[[0 for i in range(3)] for j in range(n+1)]
for day in range(1,n+1):
    for i in range(3):
        for j in range(3):
            if i!=j:
                dp[day][j]=max(dp[day][j],dp[day-1][i]+a[day-1][j])
print(max(dp[n]))

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

using namespace std;

#define sz(x) (int)((x).size())
#define forn(i,n) for (int i=0; i < n; i++)
#define forse(i,s,e) for (int i=s; i < e; i++)
#define pb push_back
#define fi first
#define se second
#define all(vec) vec.begin(), vec.end()
#define time() ((double)clock() / CLOCKS_PER_SEC)

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

//Debug
string to_string(const string& s) { return '"' + s + '"';}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A, typename B>
string to_string(pair<A, B> p) {return "("+to_string(p.fi)+", "+to_string(p.se)+")";}
template <typename A>
string to_string(A v) {
	if(v.begin()==v.end()) return "";
	return accumulate(++v.begin(), v.end(), "{"+to_string(*v.begin()),
			[](const string& a, auto b){ return a + ", " + to_string(b);})+"}";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) false
#endif


double PI=3.141592653589793;

void solve(){
	int n=5;
	int ans=-1;
	forn(i,n){
		int k;cin >> k;
		if(!k) ans=i+1;
	}	
	cout << ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int T=1;
//	cin >> T;
	forse(c,1,T+1){
		//	cout << "Case #" << cid << ": ";
		solve();
	}
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
//typedef vector<unsigned int>vec;
typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
//const ll MOD = 998244353;
const double PI = acos(-1.0);
const double EPS = 1e-10;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << "square1001" << endl;
}


Measured memory_bytes: 3212
#include<algorithm>//everybody dies in their nightmares
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<string>
#include<vector>
#include<sstream>
#include<cmath>
//#include<unordered_set>
//#include<unordered_map>
#include<bitset>
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ff(i,a,b) for(register int i=a;i>=b;--i)
#define debug(x) cerr << #x << " : " << x << " " << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
const ll mod = 1e9 + 7;
const double tiaohe = 0.57721566490153286060651209;
ll oula(ll x) { ll res = x;f(i, 2, x / i) { if (x % i == 0) { res = res / i * (i - 1);while (x % i == 0) x /= i; } }if (x > 1) res = res / x * (x - 1);return res; }
ll quickmod(ll a, ll n, ll m) { ll s = 1;while (n) { if (n & 1) { s = s * a % m; }a = (a*a) % m;n = n / 2; }return s; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d) { if (!b) { d = a, x = 1, y = 0; } else { ex_gcd(b, a % b, y, x, d);y -= x * (a / b); } }
ll inv(ll t, ll p) { ll d, x, y;ex_gcd(t, p, x, y, d);return d == 1 ? (x % p + p) % p : -1; }
bool isPrime(ll x) { if (x == 2)return true;if (x % 2 == 0)return false;for (ll i = 2;i*i <= x;i++) if (x % i == 0)return false; return true; }
//double a = log(n) +tiaohe + 1.0 / (2 * n);
double eqa = (1 + sqrt(5.0)) / 2.0;

const int N = 6e5 + 5;
int t;
int fa[N], n, m,num[N],a[N];
vector<int> G[N];

int main()
{
	while (cin >> n >> m)
	{
		int x, y;
		f(i, 1, n)scanf("%d", &a[i]);
		//f(i, 1, n)fa[i] = i;
		f(i, 1, m)
		{
			scanf("%d%d", &x, &y);
			G[x].emplace_back(a[y]);
			G[y].emplace_back(a[x]);
		}
		//f(i, 1, n)G[forf(i)].emplace_back(a[i]);
		int ans = 0;
	//	f(i, 1, n)
		//	cout << forf(i) << endl;
		//f(i, 1, n)
		//{
		//	for (auto I : G[i])cout << I << " ";
		//	cout << endl;
		//}
		f(i, 1, n)
		{
			if (G[i].size() == 0)ans++;
			else
			{
				//G[i].emplace_back(a[i]);
				sort(G[i].begin(), G[i].end(), greater<int>());
				if ( a[i]>G[i][0])ans++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 21012
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
int main(void){
    int N , K ;
    cin >> N >> K ;

    int ans = 1;
    for(int i = 0;i < N;i++){
        if(ans<=K)
           ans = ans *2;
        else
           ans = ans + K ;
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define ull unsigned long long
#define ld long double
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rrep(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vvc vector<vector<char>>
#define vc vector<char>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define maxe(x) *max_element(all(x))
#define mine(x) *min_element(all(x))
#define Size(x) ((int)(x).size())
#define umap unordered_map
const long long INF = 1LL << 60;
const long double pi = 3.1415926535897932;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

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

//lis,modpow,uf,modncr,soinsubunkai,yakusurekkyo,gyakugen
//mint,dijkstra

    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        ll h,w,n;
        cin>>h>>w>>n;
        ll m=max(h,w);
        cout<<(n+m-1)/m<<endl;
    }

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    long long X;
    cin >> X;
    
    long long now = 100;
    int cnt = 0;
    while (now < X) {
        now += now / 100;
        ++cnt;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3632
//Name: Bowling
//Level: 2
//Category: シミュレーション
//Note: 

/**
 * 倒したピン数を監視しながらフレーム数を管理する。
 * スペアかストライクが出た場合、次以降の投球を見て追加点を決める。
 *
 * オーダーは O(NM + M log M)。
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>

using namespace std;

bool solve(bool first) {
    int M;
    if(!(cin >> M)) return false;
    if(!M) return false;

    cin.ignore();
    vector<pair<int,int>> v;
    while(M--) {
        string line;
        getline(cin, line);
        istringstream is(line);

        int id;
        is >> id;

        vector<int> history;
        int pin;
        while(is >> pin) history.push_back(pin);

        int frame = 1;
        int score = 0;
        int acc = 0, turn = 0;
        for(int i = 0; i < history.size(); ++i) {
            ++turn;
            score += history[i];
            acc += history[i];
            if(frame != 10) {
                if(acc == 10) {
                    if(turn == 1) score += history[i+1] + history[i+2];
                    else if(turn == 2) score += history[i+1];
                    turn = 2;
                }
                if(turn == 2) {
                    ++frame;
                    acc = 0;
                    turn = 0;
                }
            }
        }
        v.emplace_back(-score, id);
    }
    sort(begin(v), end(v));
    for(const auto &p : v) {
        cout << p.second << ' ' << -p.first << endl;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout.setf(ios::fixed);
    cout.precision(10);

    bool first = true;
    while(solve(first)) {
        first = false;
    }
    return 0;
}

Measured memory_bytes: 1244
#####segfunc######                                                              
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    for i in range(num-2,-1,-1):
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
    
def update(k,x):
    k+=num-1
    seg[k]=x
    while k+1:
        k=(k-1)//2
        seg[k]=segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p+=num-1
    q+=num-2
    res=ide_ele
    while q-p>1:
        if p&1==0:
            res=segfunc(res,seg[p])
        if q&1==1:
            res=segfunc(res,seg[q])
            q-=1
        p=p//2
        q=(q-1)//2
    if p==q:
        res=segfunc(res,seg[p])
    else:
        res=segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele=0
N,K=map(int,input().split())
n=300001
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
init([0]*300001)
for i in range(N):
    A = int(input())
    a = max(A-K, 0)
    b = min(A+K, 300000)
    tmp = query(a, b+1) + 1
    update(A, tmp)
print(query(0, 300000))


Measured memory_bytes: 118368
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;

#define INF   (1e9 + 7)
#define MAX_H (100)
#define MAX_W (100)

int H, W;
string line;

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

  for (int i = 0; i < H; i++) {
    cin >> line;
    cout << line << endl;
    cout << line << endl;
  }
  
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int x = scanner.nextInt();
		int[] a = new int[n];
		int min = 1001;
		int sum = 0;

		for (int i = 0; i < n; i++) {
			a[i] = scanner.nextInt();
			if (a[i] < min) {
				min = a[i];
			}
			sum += a[i];
		}

		System.out.println((x-sum)/min + n);
	}
}


Measured memory_bytes: 21204
#include <iostream>

using namespace std;

int gcd(int a, int b);

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

	long long ans = 0;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= k; j++) {
			for (int l = 1; l <= k; l++) {
				ans += gcd(i, gcd(j, l));
			}
		}
	}
	cout << ans << endl;

	return 0;
}

int gcd(int a, int b)
{
	if (a < b) {
		int t = a;
		a = b;
		b = t;
	}

	int r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}

	return b;
}

Measured memory_bytes: 3608
N, x = map(int, input().split())
L = list(map(int, input().split()))
res = 0
for i in range(N-1):
    if L[i] + L[i+1] > x:
        if L[i] <= x:
            res +=  L[i+1] - (x - L[i])
            L[i+1] =  x - L[i]
        else:
            res += L[i+1] + L[i] - x
            L[i] = x
            L[i+1] = 0
            
print(res)

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

using namespace std;

#define int long long


vector<int> x;
vector<vector<pair<int, int>>>g;

vector<int> used;
void dfs(int v) {
    used[v] = 1;
    for (auto l: g[v]) {
        int to = l.first;
        int w = l.second;
        if (x[to] != -1) {
            if (x[v] + w != x[to]) {
                cout << "No";
                exit(0);
            }
        }
        else {
            x[to] = x[v] + w;
            if (!used[to]) dfs(to);
        }
    }
}

void solve() {
    int n;
    cin >> n;
    x.assign(n, -1);
    g.resize(n);
    used.resize(n);
    int m;
    cin >> m;
    set<int> st;
    for (int i = 0; i < m; ++ i) {
        int l, r, d;
        cin >> l >> r >> d;
        l--;
        r--;
        g[l].push_back({r, d});
        st.insert(r);
    }
    for (int i = 0; i < n; ++ i) {
        if (st.count(i)) continue;
        if (!used[i]) dfs(i);
    }
    for (int i = 0; i < n; ++ i) {
        if (!used[i]) {
            cout << "No";
            return;
        }
    }
    cout << "Yes";


}

signed main() {
    //freopen
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}
/*
5 5
4 5 1
5 1 1
1 2 1
2 3 1
4 3 4

 */


Measured memory_bytes: 15104