akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

// [i][0] => 0.9 둘다 없음
// [i][1] => 0만 있음
// [i][2] => 9만 있음
// [i][3] => 0,9 둘다 있음
long long dp[1000001][4];

int main() {
	const int mod = 1e9 + 7;
	int n;
	cin >> n;

	if (n == 1)
	{
		cout << 0 << endl;
		return 0;
	}

	long long ans = 2;

	dp[1][0] = 8;
	dp[1][1] = 1;
	dp[1][2] = 1;

	for (int i = 2; i <= n; i++)
	{
		// ai 가 1-8
		dp[i][0] += dp[i - 1][0] * 8;
		dp[i][0] %= mod;
		dp[i][1] += dp[i - 1][1] * 8;
		dp[i][1] %= mod;
		dp[i][2] += dp[i - 1][2] * 8;
		dp[i][2] %= mod;
		dp[i][3] += dp[i - 1][3] * 8;
		dp[i][3] %= mod;
		// ai 가 0
		dp[i][1] += dp[i - 1][1] + dp[i - 1][0];
		dp[i][1] %= mod;
		dp[i][3] += dp[i - 1][3] + dp[i - 1][2];
		dp[i][3] %= mod;

		// ai 가 9
		dp[i][2] += dp[i - 1][2] + dp[i - 1][0];
		dp[i][2] %= mod;
		dp[i][3] += dp[i - 1][3] + dp[i - 1][1];
		dp[i][3] %= mod;
	}

	cout << dp[n][3] << endl;
}

Measured memory_bytes: 34852
#include <stdio.h>
#include <algorithm>

using namespace std;

//long long
long long k , a , b;
long long ans;
void work () {
	scanf ( "%lld%lld%lld" , &k , &a , &b );
	if ( b > a + 2 ) {
		if ( k < a ) {
			ans += k;
			k = 0;
		}
		else {
			ans = a;
			k -= a - 1;
		}
		if ( k % 2 == 1 ) ans++;
		ans += (b-a)*(k/2);
		printf ( "%lld\n" , ans );
	}
	else printf ( "%lld\n" , k + 1 );
}
int main () {
	work ();
	return 0;
}


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


void input(); template<typename First,typename... Rest> void input(First&,Rest&...);
void inputVector(); template<typename First,typename... Rest>  void inputVector(std::vector<First>&,Rest&...);
#define loop(n) for(int i = 0;i < (int)(n);++i)


void calculate(){
    double N,A;
    input(N,A);
    std::cout << ceil((N + A) / 2) << '\n';
}

int main(int,char**){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    calculate();
}



void input(){return;}
template<typename First,typename... Rest>
void input(First &first,Rest&... rest){
    std::cin >> first;
    input(rest...);
}

void inputVector(){return;}
template<typename First,typename... Rest> 
void inputVector(std::vector<First> &first,Rest&... rest){
    int N = first.size();
    for(int i = 0;i < N;i++){
        std::cin >> first[i];
    }
    inputVector(rest...);
}

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

using namespace std;


int main() {
    string s;
    cin >> s;
    int c0 = count(s.begin(), s.end(), '0');
    int c1 = count(s.begin(), s.end(), '1');
    int result = min(c0, c1) * 2;
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 512
package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanLines)

	sc.Scan()
	s := sc.Text()
	s = s + s

	sc.Scan()
	p := sc.Text()

	if strings.Contains(s, p) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}



Measured memory_bytes: 1112
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX_N 10000
#define MAX_V 60000000
#define INF 100000000

int n, A[MAX_N], s, B[MAX_N], T[MAX_V], cur, S, m, x; bool V[MAX_N];

int minimum_cost_sort() {
	int ans = 0;
	for (int i = 0; i < MAX_V; i++) { V[i] = false; }
	for (int i = 0; i < n; i++) { B[i] = A[i]; }
	sort(B, B + n);
	for (int i = 0; i < n; i++) { T[B[i]] = i; }
	for (int i = 0; i < n; i++) {
		if (V[i] == true) { goto owata; }
		cur = i;
		S = 0;
		m = INF;
		x = 0;
		while (1) {
			V[cur] = true;
			x++;
			int v = A[cur];
			m = min(m, v);
			S += v;
			cur = T[v];
			if (V[cur]) { break; }
		}
		ans += min(S + (x - 2)*m, m + S + (x + 1)*s);
	owata:;
	}
	return ans;
}

int main() {
	cin >> n;
	s = INF;
	for (int i = 0; i < n; i++){
		cin >> A[i];
		s = min(s, A[i]);
	}
	cout << minimum_cost_sort() << endl;
	return 0;
}




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

using namespace std;
long long c[500010];
int main(){
	long long i,n,p,q,ans = -10000000000000000,val = 0,val1 = 0;
	cin >> n >> p >> q;
	for(i=1;i<=n;i++){
		long long a; cin >> a;
		c[i - 1] = a + p*i;
		val += a;
	}
	sort(c,c + n);
	ans = max(ans,val);
	for(i=1;i<=n;i++){
		val1 += c[i - 1];
		ans = max(ans,val - val1 + p*i*(q + i));
	}
	cout << ans << endl;
}


Measured memory_bytes: 7072
N = input()
l = len(N)

n = 0
k = l - 1
for i in range(l):
    if N[i] != '9':
        k = i
        break

if k == 0:
    if N[1:] == '9' * (l - 1):
        n = int(N[0]) + 9 * (l - 1)
    elif N[0] == '1':
        n = (l - 1) * 9
    else:
        n = (int(N[0]) - 1) + (l - 1) * 9
else:
    if N == '9' * l:
        n = 9 * l
    else:
        n = (k - 1) * 9 + 8 + 9 + (l - k - 1) * 9

print(n)

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a,b) ((a<b)?a:b)
#define _max(a,b) ((a<b)?b:a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a)?1:-1)
#define SORT(v) sort(v.begin(),v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380


int main() {
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    vector<int> x(n);
    int ma=1, mi=100;
    REP(i, n) {
        cin >> x[i];
        chmax(ma, x[i]);
        chmin(mi,x[i]);
    }
    int ans = INF;
    FOR(p, mi, ma + 1) {
        int tmp = 0;
        REP(i, n) {
            tmp += (x[i] - p) * (x[i] - p);
        }
        chmin(ans,tmp);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue> //std::priority_queue<int> que; // 4, 3, 2, 1 (defualt, less) : 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>  // std::accumulate(m.begin(), m.end(), 0LL);
#include <functional>
#include <cassert>
#include <cctype>  // std::islower(), std::isupper(), std::tolower, std::toupper
#include <iomanip> // std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {
  int A, B, C, X, Y; std::cin >> A >> B >> C >> X >> Y;

  if ( A+B <= C*2 ) {
    std::cout << X*A + Y*B << std::endl;
  }
  else {
    int ans = 0;
    ans += std::min(X,Y) * 2*C;

    int rest = 1e9;

    int restX = X-std::min(X,Y);
    int restY = Y-std::min(X,Y);
    for(int i=0; i<=std::max(X-std::min(X,Y),Y-std::min(X,Y)); i++) {
      rest = std::min(rest, i*2*C + std::max(0,(restX-i))*A + std::max(0,(restY-i))*B);
    }
    std::cout << ans+rest << std::endl;
  }
  return 0;
}


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

int main(){
    int n,q;
    int a,time=0;
    string s;
    queue<int> Q;
    queue<string> name;

    cin >> n >> q;
    for(int i=0;i<n;i++){
	cin >> s >> a;
	Q.push(a);
	name.push(s);

    }

    while(Q.empty()==false){
	a=Q.front();
	s=name.front();
	if(a>q){
	    time+=q;
	    a-=q;
	    Q.pop();
	    name.pop();
	    Q.push(a);
	    name.push(s);
	}else{
	    time+=a;
	    cout << name.front() << " " << time << endl;
	    name.pop();
	    Q.pop();
	}
    }

    return 0;
}

Measured memory_bytes: 5692
#include<bits/stdc++.h>
#define N 100009
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;

int main()
{
    LL m, n;
    cin >> m >> n;
    if(abs(m - n) >= 2) puts("0");
    else
    {
        if(m>n) swap(m,n);
        LL ans = 1ll;
        for(LL i = 1; i <= m; i++) ans = ans * i % mod;
        for(LL i = 1; i < m; i++)
        {
            ans = ans * (n-i+1) % mod;
        }
        n -= m - 1;
        ans = ans * 2 % mod;
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
     
    typedef struct restaurant{
        int number;
        char city[10];
        int point;
    }RESTAURANT;
     
    int compare(const void *a, const void *b){
        RESTAURANT ra = *(RESTAURANT *)a;
        RESTAURANT rb = *(RESTAURANT *)b;
        int cmp = strcmp(ra.city,rb.city);
        if(cmp==0){
            return rb.point - ra.point;
        }else{
            return cmp;
        }
    }
     
    int main(){
     
        int n;
        scanf("%d",&n);
        struct restaurant a[n];
        for(int i=0;i<n;i++){
            a[i].number =i+1;
            scanf("%s %d",a[i].city,&(a[i].point));
        }
     
        qsort(a,n,sizeof(RESTAURANT),compare);
     
        for(int i=0;i<n;i++){
            printf("%d\n",a[i].number);
        }
     
        return 0;
    }

Measured memory_bytes: 128
/*input
1 1
*/
/**
    Author: Kristopher Paul
    Date Created: 24-08-2019
    Contest Name:
                _/    _/   _/_/_/_/   _/   _/_/_/_/
               _/  _/     _/    _/   _/   _/
              _/_/       _/_/_/_/   _/   _/_/_/_/
             _/  _/     _/  _/     _/         _/
            _/    _/   _/    _/   _/   _/_/_/_/
**/
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define INF 1e18
#define MOD 998244353
#define mp make_pair
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define umap unordered_map
#define pii pair<int,int>
#define F first
#define S second
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define itr :: iterator it
#define all(v) v.begin(),v.end()
#define WL(t) while(t--)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define out(x) cout << #x << " is " << x << endl
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

int ModExp(int x,int y,int m){
    int res = 1;
    x = x % m;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % m;

        y = y>>1;
        x = (x*x) % m;
    }
    return res;
}

void solve(){
    int m,d;
    cin >> m >> d;
    int ans = 0;
    FOR(j,1,m+1){
    FOR(i,10,d+1){
        int x = i;
        int a = x % 10;
        x /= 10;
        int b = x % 10;
        if(a >= 2 && b >= 2 && (a*b) == j){
            ans++;
        }
    }
    }
    cout << ans << endl;
}

signed main(){
    FastIO;
    int t = 1;
//    cin >> t;
    WL(t){
        solve();
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int d[100010],a[100010];
int n;
int main()
{
	cin >>n;
	for (int i=0;i<n;i++) cin >>a[i];
	fill(d,d+n,1e9);
	d[0]=0;
	for (int i=0;i<n-1;i++)
	{
		d[i+1]=min(d[i+1],d[i]+abs(a[i]-a[i+1]));
		if (i!=n-2) d[i+2]=min(d[i+2],d[i]+abs(a[i]-a[i+2]));
	}
	cout <<d[n-1];
	return 0;
} 

Measured memory_bytes: 1024
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
char s[400000]={0},a[200001]={0},b[200001]={0},c[200001]={0};
int main()
{
	int n,q,x,y,i=200000;
	scanf("%s",&s[200000]);
	x=200000;
	n=strlen(&s[200000]);
	y=x+n-1;
	scanf("%d",&q);
	for(i=0;i<q;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==1&&a[i-1]==1)
		{
			a[i-1]=0;
			a[i]=0;
		}
		if(a[i]==2)
			scanf("%d %c",&b[i],&c[i]);
	}
	for(i=0;i<q;i++)
	{
		if(a[i]==1)
			reverse(&s[x],&s[y+1]);
		else if(a[i]==2)
		{
			if(b[i]==1)
				s[--x]=c[i];
			else 
				s[++y]=c[i];
		}
	}
//	while(q--)
//	{
//		int a;
//		scanf("%d",&a);
//		if(a==1)
//			reverse(&s[x],&s[y+1]);
//		else if(a==2)
//		{
//			int b;
//			char c;
//			scanf("%d %c",&b,&c);
//			if(b==1)
//				s[--x]=c;
//			else if(b==2)
//				s[++y]=c;
//		}			
//	}
	for(i=x;i<=y;i++)
		printf("%c",s[i]);
}

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

int main(){
    ll n, a, b; cin >> n >> a >> b;

    if((b - a) % 2 == 0){
        cout << (b - a) / 2 << endl;
    }else{
        cout << min((b + a) / 2, (n + n - a + 1 - b + 1) / 2) << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define ALL(a) (a).begin(),(a).end()
 
using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
 
const ll MOD  = 1e9+7;
const ll LINF = 1LL << 60;
const int INF = 1e9 + 7;

int main(){
    ll h, w, k;
    cin >> h >> w >> k;

    vector<string> choco(h);
    rep(i, h)cin >> choco[i];

    //white[i][j] :  座標(i, j)より左上にあるホワイトチョコの数
    ll white[h+1][w+1] = {};

    rep(i, h){
        rep(j, w){
            if(choco[i][j] == '1')white[i+1][j+1]++;
        }
    }

    rep(i, h){
        rep(j, w)white[i+1][j+1] += white[i+1][j];
    }
    
    rep(i, h){
        rep(j, w)white[i+1][j+1] += white[i][j+1];
    }

    ll ans = INF;
    //h方向の直線を全探索
    rep(bit, (1<<h-1)){
        vector<ll> sep_h(1, 0);
        
        rep(i, h-1)if(bit & (1<<i))sep_h.push_back(i+1);
        sep_h.push_back(h);

        //初めから、h方向の0とh, w方向の0番目の直線は引かれている
        ll score = sep_h.size() - 2;

        ll cnt_x = 0;
        ll l_x = 0;

        for(ll x = 1; x <= w; ++x){
            //x列目に直線を引いた場合の最大のチョコの数
            ll c_max = 0;

            ll l_y = 0;
            rep(j, sep_h.size()-1){
                ll y = sep_h[j+1];
                ll num_choco = white[y][x] - white[y][l_x] - white[l_y][x] + white[l_y][l_x];

                l_y = y;

                c_max = max(c_max, num_choco); 
            }

            if(c_max > k){
                //この時点でkより大きいなら、h方向の直線が足りていない。
                if(x == 1){
                    cnt_x = LINF;
                    break;
                }

                cnt_x++;
                l_x = x-1;
            }
        }

        score += cnt_x;

        ans = min(ans, score);
    }

    cout << ans << endl;

}

Measured memory_bytes: 384
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
H, W = map(int, input().split())

I = [list(map(str, input())) for _ in range(H)]

dp = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if i == 0 and j == 0:
			continue
		if i == 0:
			dp[i][j] = dp[i][j-1] if I[i][j] == I[i][j-1] else dp[i][j-1] + 1
			continue
		if j == 0:
			dp[i][j] = dp[i-1][j] if I[i][j] == I[i-1][j] else dp[i-1][j] + 1
			continue

		dp[i][j] = dp[i][j-1] if I[i][j] == I[i][j-1] else dp[i][j-1] + 1
		if I[i][j] == I[i-1][j]:
			dp[i][j] = min(dp[i][j], dp[i-1][j])
		else:
			dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)	

t = dp[-1][-1]
if I[0][0] == "#":
	t += 1
ans = -(-t//2)

print(ans)
		


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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a[3], k;
    cin >> a[0] >> a[1] >> a[2] >> k;
    int ans = 0;
    for (int i = 1, c = 0; i >= -1; i--, c++) {
        if (k <= 0) break;
        int take = min(k, a[c]);
        ans += take * i;
        k -= take;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
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; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};




int main(){
    int n;cin >> n;
    vector<LL> a(n + 1);
    for (int i = 0; i < n + 1; i++) {
        cin >> a[i];
    }
    if(n == 0 && a[0] == 1){
        puts("1");
    }
    else if(a[0]){
        puts("-1");
    }
    else{
        vector<LL> as(n + 2, 0);
        for (int i = n + 1; i >= 1; i--) {
            as[i - 1] = as[i] + a[i - 1];
        }
        LL now = 1;
        LL ans = 1;
        for (int i = 1; i < n + 1; i++) {
            LL nnow = min(2 * now, as[i]);
            ans += nnow;
            nnow -= a[i];
            if(nnow < 0){
                puts("-1");
                return 0;
            }
            now = nnow;
        }
        if(now == 0){
            cout << ans << endl;
        }
        else{
            puts("-1");
        }
    }
    return 0;
}


Measured memory_bytes: 4820
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){

  while(x->left!=NIL){
    x = x->left;
  }
  return x;

}

Node treeSearch(Node x, int k){

  if(x == NIL || k == x->key)
    return x;
  if(k < x->key)
    return treeSearch(x->left, k);
  else
    return treeSearch(x->right, k);

}

Node treeSuccessor(Node x){

  Node y;
  if(x->right != NIL)
    return treeMinimum(x->right);
  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left == NIL || z->right == NIL)
    y=z;
  else 
    y=treeSuccessor(z);
  if(y->left != NIL)
    x=y->left;
  else
    x=y->right;
  if(x != NIL)
    x->parent = y->parent;
  if(y->parent == NIL)
    root=x;
  else if(y ==(y->parent)->left)
    (y->parent)->left=x;
  else
    (y->parent)->right=x;
  if(y != z)
    z->key=z->key;
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key)
      x=x->left;
    else 
      x=x->right;
}

  z->parent=y;
  if(y==NIL)
    root=z;
  else if(z->key < y->key)
    y->left=z;
  else
    y->right=z;

}

void inorder(Node x){

  if(x!=NIL){
    inorder(x->left);
    printf(" %d", x->key);
    inorder(x->right);
  }


}
void preorder(Node x){

  if(x!=NIL){
    printf(" %d", x->key);
    preorder(x->left);
    preorder(x->right);
  }

}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  root=NIL;

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

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

vector< vector<int> > to;
vector<int> ans;

void dfs(int c,int p=-1){
  for(int u:to.at(c)){
    if(u==p){
      continue;
    }
    ans.at(u)+=ans.at(c);
    dfs(u,c);
  }
}
int main(){
  int n,q;
  cin >> n >> q;
  //v.resize(N);
  to.resize(n+5);
  for(int i=0;i<n-1;i++){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    to.at(a).push_back(b);
    to.at(b).push_back(a);
  }
  ans.resize(n);
  for(int i=0;i<q;i++){
    int p,x;
    cin >> p >> x;
    p--;
    ans.at(p)+=x;
  }
  dfs(0);
  for(int i=0;i<n;i++){
    cout << ans.at(i) << endl;
  }
  return 0;
}


Measured memory_bytes: 26624
#![allow(unused)]

//
// Based on EbTech's Scanner https://stackoverflow.com/q/56449027
//
struct Scanner<'a, R: std::io::BufRead> {
    reader: R,
    buf: String,
    iter: std::str::SplitWhitespace<'a>,
}

impl<'a, R: std::io::BufRead> Scanner<'a, R> {
    fn new(reader: R) -> Self {
        Self { reader, buf: String::new(), iter: "".split_whitespace() }
    }

    fn get_str(&mut self) -> &str {
        if let Some(t) = self.iter.next() {
            return t;
        }
        self.buf.clear();
        self.reader.read_line(&mut self.buf).expect("I/O error");
        self.iter = unsafe { std::mem::transmute(self.buf.split_whitespace()) };
        self.get_str()
    }

    fn get<T: std::str::FromStr>(&mut self) -> T {
        self.get_str().parse().ok().expect("Parse error")
    }
}

fn main() {
    let stdin = std::io::stdin();
    solve(Scanner::new(stdin.lock()));
}

fn solve<R: std::io::BufRead>(mut sc: Scanner<R>) {
    let n = sc.get();
    let m = sc.get();
    let hs: Vec<i64> = (0..n).map(|_| sc.get()).collect();
    let roads: Vec<(usize, usize)> =
        (0..m).map(|_| (sc.get(), sc.get())).collect();

    let mut good = vec![true; n];
    for (a, b) in roads {
        let a = a - 1;
        let b = b - 1;
        if hs[a] < hs[b] {
            good[a] = false;
        } else if hs[a] == hs[b] {
            good[a] = false;
            good[b] = false;
        } else {
            good[b] = false;
        }
    }

    println!("{}", good.iter().filter(|&&x| x).count());
}


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

using namespace std;

vector<string> split(const string &str, char delim = ' ') {
  stringstream ss(str);
  vector<string> res;
  for (string tmp; getline(ss, tmp, delim);) res.push_back(tmp);
  return res;
}

template<typename T = long long> inline T toInteger(const string&);

template<> inline int toInteger<int>(const string& s) {
  return stoi(s);
}

template<> inline long toInteger<long>(const string& s) {
  return stol(s);
}

template<> inline long long toInteger<long long>(const string& s) {
  return stoll(s);
}

template<typename T = long long> inline T toInteger(const string& s, int n) {
  T res = 0;
  for (char c : s) {
    if (isdigit(c)) res = res * n + c - '0';
    else if (isalpha(c)) res = res * n + tolower(c) - 'a' + 10;
  }
  return s[0] == '-' ? -res : res;
}

int main() {
  string line;
  int res1 = 0, res2 = 0;
  while (cin >> line) {
    auto v = split(line, ',');
    int a = toInteger<int>(v[0]);
    int b = toInteger<int>(v[1]);
    int c = toInteger<int>(v[2]);
    if (a * a + b * b == c * c) ++res1;
    if (a == b) ++res2;
  }
  cout << res1 << endl << res2 << endl;
}

Measured memory_bytes: 3172
#include <stdio.h>

int hantei(int,int);

int main(void){
    int n;
    scanf("%d",&n);
    if(n==1){printf("%d\n",1);return 0;}
    int i,j;
    for(i=n;i>0;i--){
        for(j=2;j<=i/2;j++){
            if(hantei(i,j)!=1){
                continue;
            }else{
                printf("%d\n",i);
                return 0;
            }
        }
    }
}


int hantei(int a,int b){
    if(a==1){
        return 1;
    }else if(a%b!=0){
        return 0;
    }else{
        a/=b;
        return hantei(a,b);
    }
}

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

typedef long long ll;
typedef pair<ll,ll> P;

const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;

#define rep(i, a, b) for(ll (i) = (a); (i) < (b);++i)

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

int main()
{
  ll N;
  cin >> N;
  ll L[2*N];
  rep(i,0,2*N)cin >> L[i];

  ll ans;
  sort(L, L+2*N);
  rep(i, 0, 2*N){
    if (i % 2 == 0)
    {
      ans += L[i];
    }
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int N, K;
vector<int> adj[2020];
vector<int> v;
int dep[2020];

void dfs(int now, int par) {
	v.push_back(now);
	dep[now] = dep[par] + 1;
	for(int i : adj[now]) {
		if(i == par) continue;
		dfs(i, now);
	}
}

int main() {
	scanf("%d%d", &N, &K);
	for(int i = 1; i < N; i++) {
		int a, b; scanf("%d%d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	int ans = 0;

	for(int i = 1; i <= N; i++) {
		dep[i] = 0;
		int mx = 0, sum = 1;
		for(int j : adj[i]) {
			dfs(j, i);
			int n1 = 0, n2 = 0;
			while(v.size()) {
				if(dep[v.back()] <= K / 2) n1++;
				if((K & 1) && dep[v.back()] == (K + 1) / 2) n2++;
				v.pop_back();
			}
			sum += n1;
			mx = max(mx, n2);
		}
		ans = max(ans, sum + mx);
	}
	printf("%d\n", N - ans);
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define c(P)        cout<<P<<"\n"
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define F           first
#define S           second
#define mem(a,val)  memset(a,val,sizeof(a))
#define fr(i,x,n)   for(ll i=x;i<n;i++)
#define frr(i,x,n)  for(ll i=n-1;i>=x;i--)


const ll N   =  500005;
const ll mod = 1e9 + 7;

using namespace std;


void solve(){

  ll x=0,y=0,c=0,ans=0;
  ll n,m,k;
  string s;
  cin>>n>>s;
  for (int i = 0; i < n-2; ++i)
  {
     if(s[i]=='A' and s[i+1]=='B' and s[i+2]=='C')
        ans++;
  }
  c(ans);

}

signed main(){
     
  ios_base::sync_with_stdio(false);   
  cin.tie(NULL);
  ll T=1;
  //cin>>T;
  while(T--){
  solve();
  }
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x,y,z) max((x),max((y),(z)))
#define tmin(x,y,z) min((x),min((y),(z)))
typedef long long ll; ll MM = 1000000000;ll mod = MM + 7; ll MMM=9223372036854775807;//2^63 -1
ll GCD(ll x, ll y) {if (y == 0) return x;else return GCD(y, x % y);}
ll LCM(ll x, ll y) { return x / GCD(x, y) * y;}
//cout << fixed << setprecision(10);
ll fac(ll x){if(x==0) return 1;  return x*fac(x-1);}

int main(){
    string s; cin>>s;
    rep(i,s.size()) cout<<'x';
}

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

#define M_PI 3.141592653589793

#define MAX_LEN 1000

int array[MAX_LEN];

int main()
{
	while (true)
	{
		int n;
		scanf("%d", &n);
		if (n == 0)break;
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &array[i]);
		}

		double sum = 0;
		for (int i = 0; i < n; i++)
		{
			sum += array[i];
		}
		double ave = sum / n;

		sum = 0;
		for (int i = 0; i < n; i++)
		{
			sum += pow(array[i] - ave, 2);
		}
		double s = sqrt(sum / n);

		printf("%lf\n", s);

	}


}


Measured memory_bytes: 3160
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstddef>
#include<queue>
#include<math.h>
#include<iomanip>
using namespace std;

int main()
{
    long long n, d, x, y, ans = 0;
    cin >> n >> d;
    for(int i = 0; i < n; ++i){
        cin >> x >> y;
        if(x*x + y*y <= d*d) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

#define rep(x,y) for (int (x) = 0;(x) < (y);++(x))
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int max_n = 3000;
ll fact[max_n+1];
ll inv_fact[max_n+1];
ll n, m;
ll dp[max_n+1][max_n+1];

ll extgcd(ll a, ll b, ll& x, ll& y) {
  ll d = a;
  if (b != 0) {
    d = extgcd(b, a%b, y, x);
    y -= (a/b) * x;
  } else {
    x = 1; y = 0;
  }
  return d;
}

ll mod_inverse(ll a, ll m) {
  ll x, y;
  extgcd(a, m, x, y);
  return (m + x%m) % m;
}


void init(ll n, ll mod) {
  fact[0] = 1;
  for (int i = 1; i <= n; ++i) fact[i] = (fact[i-1]*i)%mod;

  for (int i = 0; i <= n; ++i) inv_fact[i] = mod_inverse(fact[i], mod);
}

ll mod_comb(ll n, ll r, ll mod) {
  return fact[n]*inv_fact[r]%mod*inv_fact[n-r]%mod;
}

//x^nをmodのもとで計算する
ll mod_pow(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll res = mod_pow((x*x) % mod, n/2, mod);
  if (n & 1) res = (res*x) % mod;
  return res;
}

ll f[max_n+1];
ll pow_m_1[max_n+1];

int main() {
  cin >> n >> m;
  init(n, m);

  dp[0][0] = 1;
  for (int k = 1; k <= n; ++k) {
    dp[k][0] = 1;
    for (int x = 1; x <= k; ++x) {
      dp[k][x] = (((x+1)*dp[k-1][x]%m) + dp[k-1][x-1])%m;
    }
  }

  for (int i = 0; i <= n; ++i) pow_m_1[i] = mod_pow(2, i, m-1);

  for (int k = 0; k <= n; ++k) {
    ll mp1 = mod_pow(2, pow_m_1[n-k], m), mp2 = mod_pow(2, (n-k), m);
    ll mp0 = 1;
    for (int x = 0; x <= k; ++x) {
      f[k] += dp[k][x] * mp0 % m * mp1 % m;
      f[k] %= m;
      mp0 = mp0 * mp2 % m;
    }
  }

  ll ans = 0;
  for (int k = 0; k <= n; ++k) {
    ans += mod_comb(n, k, m) * f[k] % m * (k & 1 ? -1 : 1) % m;
    ans = (ans+m) % m;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 69120
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define mp make_pair
#define fi first
#define sc second
ll n,a[3000];
ll memo[3000][3000][2];

ll dfs(ll i,ll j,bool t) {//[i,j] t...IOIちゃんのターンか
	if(memo[i][j][t] >= 0) {
		return memo[i][j][t];
	}
	if(t) {
		if(i == j) {
			return memo[i][j][t] = 0;
		}
		if(a[i] > a[j]) {
			return memo[i][j][t] = dfs((i + 1) % n,j,false);
		}
		return memo[i][j][t] = dfs(i,(j - 1 + n) % n,false);
	}

	if(i == j) {
		return memo[i][j][t] = a[i];
	}

	return memo[i][j][t] = max(dfs((i + 1) % n,j,true) + a[i],dfs(i,(j - 1 + n) % n,true) + a[j]);
}

void solve() {
	REP(i,n) {
		REP(j,n) {
			REP(k,2) {
				memo[i][j][k] = -1;
			}
		}
	}

	ll ans = 0;
	REP(i,n) {
		ans = max(ans,dfs((i + 1) % n,(n - 1 + i) % n,true) + a[i]);
	}
	cout << ans << endl;
}
int main(){
	cin >> n;
	REP(i,n) {
		cin >> a[i];
	}
	solve();
	return 0;
}



Measured memory_bytes: 73704
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>

int pop(int n, int i, int a[])
{
    int val;
    int ptr;

    val = a[i];

    for(ptr = i; ptr < n - 1; ptr++) {
        a[ptr] = a[ptr + 1];
    }

    return val;
}

int solve(int n, int a[], int b[])
{
    int i, j;

    for (i = n - 1; i >= 0; i--) {
        a[i] = -1;
        for (j = i; j >= 0; j--) {
            // とりあえず大きい値があったらreject
            if (b[j] > i + 1) {
                return -1;
            }
            // あったら取り除く
            if (b[j] == j + 1) {
                a[i] = j + 1;
                pop(n, j, b);
                break;
            }
        }
        if (a[i] == -1) {
            return -1;
        }
    }

    return 0;
}

int main(int argc, char *argv[])
{
    int n;
    int a[100];
    int b[100];
    int i, j;
    int ret;

    scanf("%d", &n);

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

    ret = solve(n, a, b);

    if (ret != 0) {
        printf("-1\n");
        return 0;
    }

    for (i = 0; i < n; i++) {
        printf("%d\n", a[i]);
    }

    return 0;
}

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

int main() {
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());

    if (s < t) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
random_device rnd;
mt19937 mt(rnd());
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1000000007;

int main()
{
    ll n;
    cin >> n;
    cout << (n - 1) * n / 2 << endl;

    return 0;
}

Measured memory_bytes: 256
O = input()
E = input()
if len(O) == len(E):
    for s in zip(O, E):
        print(s[0] + s[1], end='')
    print()
else:
    print(O[0], end='')
    for s in zip(E, O[1:]):
        print(s[0] + s[1], end='')
    print()


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

using namespace std;
#define ll long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t;

int main()
{
  IOS;
  cin >> t;
  if (t>=30)
    cout << "Yes"<< endl;
  else
    cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF LLONG_MAX/10
#define rep(i,n) for(int i=0;i<n;i++)
#define krep(i,k,n,m) for(int i=k;i<n;i+=m)
#define erep(i,k,n) for(int i=k;i<n;i++)
#define mod 1000000007
//最大公約数
int gcd(int s,int b){
    if(b==0)return s;
    return gcd(b,s%b);
}
signed main(){
    int n;
    cin>>n;
    int a[n];
    int ans=0,con=0;
    rep(i,n){
        cin>>a[i];
        if(a[i]%4==0){
            ans++;
        }
        else if(a[i]%2==0){
            con++;
        }
    }
    if(ans>=n-ans-con){
        cout<<"Yes"<<endl;
    }
    else if(ans==n-ans-con-1){
        if(con>0){
            cout<<"No"<<endl;
        }
        else{
            cout<<"Yes"<<endl;
        }
    }
    else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#include <numeric>
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

int a[100], b[100], c[100], d[100];
int N, M, Q;
int ans = 0;
int st[20];

void dfs(int cur,int sum){
	if (cur == M) {
		st[M] = N - sum;
		vector<int>A;
		for (int i = 1; i <= M; i++) {
			for (int j = 0; j < st[i]; j++)A.pb(i);
		}
		int tmp = 0;
		for (int i = 0; i < Q; i++) {
			if (A[b[i]] - A[a[i]] == c[i])tmp += d[i];
		}
		ans = max(ans,tmp);
	}
	else {
		for (int i = 0; i <= N-sum; i++) {
			st[cur] = i;
			dfs(cur + 1,sum + i);
		}
	}
}

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

	cin >> N >> M >> Q;
	for (int i = 0; i < Q; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		a[i]--, b[i]--;
	}

	dfs(1,0);
	puts(ans);

	return 0;
}

Measured memory_bytes: 3644
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

a, b = ZIP(M)

a_cnt, b_cnt = Counter(a), Counter(b)

for i in range(N):
	if (a_cnt[i]+b_cnt[i])%2 != 0:
		print("NO")
		break
else:
	print("YES") 


Measured memory_bytes: 59608
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

int main(){
  string S;
  string tmp = "keyence";
  cin >> S;
  bool ret = false;
  for(int i=0; i<S.size(); i++) {
    for(int j=i; j<S.size(); j++) {
      string trgt = S.substr(0, i) + S.substr(j, S.size());
      if(trgt == tmp) {
	ret = true;
	break;
      }
    }
  }
  if(ret)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

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

int main(){

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

    int cnt = 0;
    for (i = 0; i < N-2; i++){
        if( ((P[i] < P[i+1]) && (P[i+1] < P[i+2])) || ((P[i] > P[i+1]) && (P[i+1] > P[i+2])) ){
            cnt += 1;
        }
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
n=int(input())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))
c_list = list(map(int,input().split()))
count = 0
for i in range(n):
    index=a_list[i]
    count += b_list[index - 1]
#     print(count)
    if i !=0:
        if a_list[i] == a_list[i-1] + 1:
            count += c_list[a_list[i-1]-1]
print(count)

Measured memory_bytes: 3064
// template
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<long long, long long> LP;
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define REP_AB(i, a, b) for (ll i = ll(a); i <= ll(b); ++i)
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)), v.end());
#define SIZE(x) ((ll)(x).size())
#define REVERSE(v) reverse(ALL(v))
// true / false
#define BIN_SEARCH(v, a) binary_search(ALL(v), a)
// index
#define BIN_LEFT(v, a) (lower_bound(ALL(v), a) - v.begin())
#define BIN_RIGHT(v, a) (upper_bound(ALL(v), a) - v.begin())
#define BIN_INSERT(v, a) (v.insert(v.begin() + BIN_LEFT(v, a), a))
#define DEL(v, i) v.erase(v.begin() + i)
#define INSERT(v, i, a) v.insert(v.begin() + i, a)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a / gcd(a, b)) * b;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
#define out cout
#define in cin
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
// template end

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, m;
    in >> n >> m;
    ll ans = min(n, ll(m / 2));
    ans += ll((m - ans*2) / 4);
    out << ans << endl;
}


Measured memory_bytes: 256
n,x = (int(i) for i in input().split())
a = [int(i) for i in input().split()]

cnt = 0
if a[0] > x:
    cnt += a[0] - x
    a[0] -= cnt

for i in range(1,n):
    c = a[i] + a[i-1] - x
    if c > 0:
        cnt += c
        a[i] -= c


print(cnt)

Measured memory_bytes: 14468
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;
typedef long long ll;

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

	vector<vector<pair<int, int> > > t(n, vector<pair<int, int>>());
	vector<int> c(n-1,0);

	for(int i=0; i<n-1; i++){
		int a, b;
		cin >> a >> b;
		t[a-1].push_back(make_pair(b-1,i));
		t[b-1].push_back(make_pair(a-1,i));
	}

	stack<pair<int, int> > s;
	s.push(make_pair(0,0));
	int r=0;
	while(!s.empty()){
		int cur=s.top().first;
		int l=s.top().second;
		int i=1;
		s.pop();
		for(auto n: t[cur]){
			if(c[n.second]==0){
				if(i==l) i++;
				c[n.second]=i;
				s.push(make_pair(n.first, i));
				i++;
				//cout << i-1 << " " << n.first << " "<< n.second << endl;
			}
		}
		r=max(r,i-1);
	}

	cout << r << endl;
	for(int i=0; i<n-1; i++) cout << c[i] << endl;


	return 0;

}


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

#define PrintLn(X) cout << X << endl
#define Rep(i, n) for(int i = 0; i < (int)(n); ++i)

int main(void)
{
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	if(A * B > C * D){
		PrintLn(A*B);
	}else{
		PrintLn(C*D);
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=1005;
const int mod=1e9+7;
inline int Add(int x,int y){
    return (x+=y)>=mod?x-mod:x;
}
inline int Sub(int x,int y){
    return (x-=y)>=0?x:x+mod;
}
inline int Mul(int x,int y){
    return 1ll*x*y%mod;
}
inline int Pow(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=1ll*res*x%mod;
        y>>=1;
        x=1ll*x*x%mod;
    }
    return res;
}
int n,k,a[max_n];
int f[max_n],inv[max_n];
int C(int n,int m){
    if(n<m||m<0)return 0;
    return 1ll*f[n]*inv[m]%mod*inv[n-m]%mod;
}
int dp[max_n];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)scanf("%d",a+i);
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=Mul(f[i-1],i);
    inv[n]=Pow(f[n],mod-2);
    for(int i=n-1;i>=0;i--)inv[i]=Mul(inv[i+1],i+1);
    dp[0]=1;
    for(int i=1;i<=k;i++){
        for(int j=n;j>=0;j--){
            int res=0;
            for(int l=0;l<=min(j,a[i]);l++){
                int x=dp[j-l];
                x=Mul(x,inv[l]);
                x=Mul(x,C(n-l,a[i]-l));
                res=Add(res,x);
            }
            dp[j]=res;
        }
    }
    printf("%d\n",Mul(f[n],dp[n]));
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int a = 0;
		int b = 0;
		int c = 0;
		int ans = 0;
		for(int i = 0;i < n;i ++) {
			b = in.nextInt();
			if(a == b)c ++;
			else {
				ans += c / 2;
				c = 1;
			}
			a = b;
		}
		ans += c / 2;
		System.out.println(ans);
	}

}


Measured memory_bytes: 21332
#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 <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 2000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define seg_size 524288
int griding[1000000] = {};
int is_sosuu(int now) {
	if (now == 1) return 0;
	for (int i = 2;i <= sqrt(now);++i) {
		if (now % i == 0) return 0;
	}
	return 1;
}
int main() {
	for (int i = 1;i <= 100000;i++) {
		griding[i] = griding[i - 1];
		if (i % 2 == 1) {
			if (is_sosuu(i) && is_sosuu((i + 1) / 2)) {
				griding[i]++;
			}
		}
	}
	int query;
	cin >> query;
	REP(i, query) {
		int a, b;
		cin >> a >> b;
		cout << griding[b] - griding[a - 1] << endl;
	}
	return 0;
}

Measured memory_bytes: 1656
import sys

def isPrime(i):
    if i == 2: return True
    k = 2
    while k ** 2 <= i:
        if i % k == 0: return False
        k += 1
    return True
            
def solve():
    input = sys.stdin.readline
    N = int(input())
    count = 0
    k = 1
    Ans = []
    while count < N:
        if isPrime(5 * k + 1):
            Ans.append(5 * k + 1)
            count += 1
        k += 1
    print(" ".join(map(str, Ans)))
    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int n,ans;
long long m,x[200010],y[200010];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++)
	    if(x[i]*x[i]+y[i]*y[i]<=m*m)
	        ans++;
	cout<<ans;
	return 0;
}

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

#define rep(i, n) for (int i=0; i<(n); ++i)
using ll = long long;
using P = pair<int, int>;

int const MAX = 101;
int const NIL = -1;
struct Node {
  int parent, left, right;
} T[MAX];

int D[MAX], H[MAX];

void setDepth(int u, int p) {
  D[u] = p;
  if (T[u].right != NIL) setDepth(T[u].right, p+1);
  if (T[u].left != NIL) setDepth(T[u].left, p+1);
}

int setHeight(int u) {
  int h1 = 0, h2 = 0;
  if (T[u].left != NIL) {
    h1 = setHeight(T[u].left) + 1;
  }
  if (T[u].right != NIL) {
    h2 = setHeight(T[u].right) + 1;
  }
  return H[u] = max(h1, h2);
}

int getSibling(int u) {
  if (T[u].parent == NIL) return NIL;
  if (T[T[u].parent].right != NIL && T[T[u].parent].right != u) return T[T[u].parent].right;
  if (T[T[u].parent].left != NIL && T[T[u].parent].left != u) return T[T[u].parent].left;
  return NIL;
}

int main() {
  int n;
  cin >> n;
  rep(i,n) T[i].parent = T[i].left = T[i].right = NIL;

  int id, left, right;
  rep(i,n) {
    cin >> id >> left >> right;
    T[id].left = left;
    T[id].right = right;
    if (left != NIL) T[left].parent = id;
    if (right != NIL) T[right].parent = id;
  }
  int r;
  rep(i,n) {
    if (T[i].parent == NIL) r = i;
  }
  
  setDepth(r, 0);
  setHeight(r);

  rep(i,n) {
    int sibling, deg=0;
    sibling = getSibling(i);
    if (T[i].left != NIL) deg++;
    if (T[i].right != NIL) deg++;
    
    string type;
    if (T[i].parent == NIL) type = "root";
    else if (T[i].left == NIL && T[i].right == NIL) type = "leaf";
    else type = "internal node";
    
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n", i, T[i].parent, sibling, deg, D[i], H[i], type.c_str());
  }
  return 0;
}



Measured memory_bytes: 3284
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long X = sc.nextLong();
        long Y= sc.nextLong();
        long a = X;
        int count = 0;
        while(a<=Y){
            count++;
            a = a*2;
        }
        System.out.println(count);


    }


}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

int main(){
    ll A;
    string Bs;
    cin >> A >> Bs;

    int B = (Bs[0] - '0') * 100 + (Bs[2] - '0') * 10 + (Bs[3] - '0');

    ll ans = A * B / 100;

    cout << ans << endl;
}

Measured memory_bytes: 3624
//#include"pch.h"
//#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;

int main() {
	int N, cnt = 0, ans = 0;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			if (i%j == 0)cnt++;
		}
		if (cnt == 8 && i % 2 == 1)ans++;
		cnt = 0;
	}
	cout << ans << endl;

	return(0);
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

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

    ll x,y;cin>>x>>y;
    ll res=1e15,xtmp,ytmp;
    xtmp=x;ytmp=y;
    if(xtmp<=ytmp) res=min(res,ytmp-xtmp);
    xtmp=-x;ytmp=y;
    if(xtmp<=ytmp) res=min(res,ytmp-xtmp+1);
    xtmp=x;ytmp=-y;
    if(xtmp<=ytmp) res=min(res,ytmp-xtmp+1);
    xtmp=-x;ytmp=-y;
    if(xtmp<=ytmp) res=min(res,ytmp-xtmp+2);
    cout<<res<<endl;
}


Measured memory_bytes: 256