akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int cnt[110];

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    REP(i, 2, N) cnt[i]++;
    REP(i, 2, N) {
        int n = i;
        int j = 2;  
        while(n > 1) {
            while (n % j == 0) {
                cnt[j]++;
                n /= j;
            }
            j++;
        }
    }
    //REP(i, 2, N) cout << i << " " << cnt[i] << endl;
    int ans = 0;
    REP(i, 2, N) {
        if (cnt[i] >= 75) ans++; 
    }
    REP(i, 2, N) {
        REP(j, i + 1, N) {
            if (cnt[i] >= 3 && cnt[j] >= 25) ans++;
            if (cnt[i] >= 25 && cnt[j] >= 3) ans++;
        }
    }
    REP(i, 2, N) {
        REP(j, i + 1, N) {
            if (cnt[i] >= 15 && cnt[j] >= 5) ans++;
            if (cnt[i] >= 5 && cnt[j] >= 15) ans++;
        }
    }
    REP(i, 2, N) {
        REP(j, i + 1, N) {
            REP(k, j + 1, N) {
                if (cnt[i] >= 3 && cnt[j] >= 5 && cnt[k] >= 5) ans++;
                if (cnt[i] >= 5 && cnt[j] >= 3 && cnt[k] >= 5) ans++;
                if (cnt[i] >= 5 && cnt[j] >= 5 && cnt[k] >= 3) ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
s = list(input())
t = list(input())

s = s + s
for i in range(len(t)):
    for j in range(len(t)):
        if s[i+j] == t[j]:
            if j == len(t)-1:
                print('Yes')
                exit(0)
            continue
        else:
            break
print('No')

Measured memory_bytes: 3060
N,K,Q = map(int,input().split())
A = []
for i in range(Q):
  A.append(int(input()))
point = [0]*N
for i in range(Q):
  point[A[i]-1] += 1

for i in range(N):
  if Q - point[i] < K:
    point[i] = 'Yes'
  else:
    point[i] = 'No' 

for i in range(N):
  print(point[i])

Measured memory_bytes: 8600
#include <iostream>

using namespace std;

int main()
{
    int x, y;
    cin >>x>> y ;

    if (x<=12)
    {
        if (x<=5)
        {
            cout<<0;
        }
        else
            cout<<y/2 ;
    }
    else
        cout<<y;
    return 0;
}


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

int n, m, h, w, a[510][510];

int main() {
    scanf("%d %d %d %d", &n, &m, &h, &w);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = 1000;
        }
    }
    for (int i = h; i <= n; i += h) {
        for (int j = w; j <= m; j += w) {
            a[i][j] = -(h * w - 1) * 1000 - 1;
        }
    }
    long long s = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s += a[i][j];
        }
    }
    printf("%s\n", s > 0 ? "Yes" : "No");
    if (s <= 0) exit(0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 2560
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String args[]) throws Exception {

        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.nextLine());
        int A[] = new int[N];
        for (int a = 0; a < N; ++a) {
            A[a] = sc.nextInt();
        }

        Arrays.sort(A);

        int alice = 0;
        int bob=0;
        for (int i=0; i < N; i++) {
            if (i%2 == 0) {
                alice += A[N-1-i];
            } else {
                bob += A[N-1-i];
            }
        }
        System.out.println(alice - bob);
    }
}


Measured memory_bytes: 21972
import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

S, T = map(int, input().split())

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = deque([S])
ans[S][0] = 0
while q:
    now = q.popleft()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

if ans[T][0] == inf:
    print(-1)
else:
    print(ans[T][0]//3)


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

typedef long long ll;

using namespace std;

#define rep(i, n) for(ll i=0; i<n; i++)
#define repr(i, n) for(ll i=n; i>=0; i--)
#define reps(i, s, e) for(ll i=s; i<e; i++)
#define all(x) x.begin(),x.end()

int main(){
	int N;

	cin >> N;

	vector<int> v(N);
	vector<int> w(N);


	int l, i = 0;
	while (cin >> l) {
        v[i] = l;
        w[i] = l;

        i++;
        if (i >= N) {
            break;
        }
    }

    

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

    size_t v_len = v.size();

    // cout << "v_len : "  << v_len << endl; 


    vector<ll> x(v_len);

    rep(i,v_len){
    	size_t n_count = count(w.begin(), w.end(), v[i]);
    	x[i] = n_count;
    }

    // cout << "x_len : "  << x.size() << endl;

    // rep(i,v_len) cout << v[i] << x[i] << endl;



    ll count = 0;
 
    rep(i,v_len){
    	// 正三角形
    	if(x[i] >= 3) count += ((ll)(x[i]*(x[i] - 1))*(x[i] -2))/6;

    	reps(j,i+1,v_len){
    		// 二等辺三角形			
    		if(x[i] >= 2 && v[j] < 2*v[i]) count += (x[i]*(x[i]-1))/2 * x[j];
    		if(x[j] >= 2 && v[i] < 2*v[j]) count += (x[j]*(x[j]-1))/2 * x[i];

    		reps(k,j+1,v_len){
    			if(abs(v[i] - v[j]) < v[k] && v[k] < v[i] + v[j] ){
    				count += x[i] * x[j] * x[k];
    			}
    			else if(v[k] >= v[i] + v[j]) break;
    		}
    	}
    }

    cout << count << endl;

    return 0;
}	

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e18;
int n;
ll cst[26], sat[366][26], last[26], tmp[26];
int main(){
	scanf("%d", &n);
	memset(last, 0ll, sizeof(last));
	for(int i=0; i<26; i++) scanf("%lld", &cst[i]);
	for(int i=0; i<n; i++) for(int j=0; j<26; j++)
		scanf("%lld", &sat[i][j]);
	ll res = 0ll;
	for(int nw, i=0; i<n; i++){
		memset(tmp, 0ll, sizeof(tmp));
		for(nw=0; nw<26; nw++){
			tmp[nw] += sat[i][nw];
			for(int j=0; j<26; j++) if(j != nw)
				res -= cst[j] * (i+1-last[j]);
		}
		ll get = -inf; int id = -1;
		for(nw=0; nw<26; nw++) 
			if(get < tmp[nw]){
				get = tmp[nw]; id = nw;
			}else if(get == tmp[nw] && cst[nw] > cst[id]){
				get = tmp[nw]; id = nw;
			}
		printf("%d\n", id+1);
		last[id] = i+1;
	}
	return 0;
}

Measured memory_bytes: 3932
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main() {
	long long a, b, v, w, t;
	scanf("%lld%lld\n", &a, &v);
	scanf("%lld%lld\n", &b, &w);
	scanf("%lld", &t);
	if (w >= v) {
		printf("NO");
		return 0;
	}
	if (abs(b - a) / (double)(v - w) <= t) printf("YES");
	else printf("NO");

	return 0;
}

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

using namespace std;

const int N = 20;

vector<int> a[N];
int p[N];

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int k;
    scanf("%d", &k);
    for (int j = 0; j < k; j++) {
      int x;
      scanf("%d", &x);
      a[i].push_back(x - 1);
    }
  }
  for (int i = 0; i < m; i++) {
    scanf("%d", p + i);
  }
  long long ans = 0;
  for (int mask = 0; mask < (1 << n); mask++) {
    int on = 0;
    for (int i = 0; i < m; i++) {
      int cnt = 0;
      for (int j : a[i]) {
        if (mask & (1 << j)) cnt++;
      }
      cnt %=2;
      if (cnt == p[i]) on++;
    }
    if (on == m) ans++;
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 256
#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 h;
    cin>>h;
    ll cnt=0;
    ll ans=1;
    while(h!=1){
        h/=2;
        cnt++;
        ans+=pow(2,cnt);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 4080
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>

using namespace std;

typedef unsigned uint;
// typedef long long Int;

const int INF = 1001001001;
// const Int INFLL = 1001001001001001001LL;

struct Info {
	int to, cost, time, com;
	Info(int to, int cost, int time, int com) : to(to), cost(cost), time(time), com(com){}
	Info(){}
};

bool operator < (const Info &a, const Info &b)
{
	return (a.cost > b.cost);
}

int main()
{
	int n, m, h, k;
	
	while (scanf("%d %d %d %d", &n, &m, &h, &k) && n){
		vector<Info> G[128];
		
		for (int i = 1; i <= m; i++){
			int a, b, c, th, r;
			scanf("%d %d %d %d %d", &a, &b, &c, &th, &r);
			--r;
			G[a].push_back(Info(b, c, th, r));
			G[b].push_back(Info(a, c, th, r));
		}
		
		int s, t;
		
		scanf("%d %d", &s, &t);
		
		int p;
		scanf("%d", &p);
		
		int dp[256];
		
		fill(dp, dp + 256, INF);
		
		dp[0] = 0;
		for (int i = 0; i < p; i++){
			int l, d;
			int mask = 0;
			scanf("%d %d", &l, &d);
			for (int j = 0; j < l; j++){
				int x;
				scanf("%d", &x);
				--x;
				
				mask |= (1 << x);
			}
			
			for (int j = 0; j < 256; j++){
				dp[j | mask] = min(dp[j | mask], dp[j] + d);
			}
		}
		
		int ret = INF;
		
		for (int i = 0; i < (1 << k); i++){
			vector<Info> tmp[128];
			
			for (int j = 1; j <= n; j++){
				tmp[j] = G[j];
			}
			
			for (int j = 1; j <= n; j++){
				for (int k = 0; k < tmp[j].size(); k++){
					if ((i >> G[j][k].com) & 1) tmp[j][k].cost = 0;
				}
			}
			
			priority_queue<Info> pq;
			bool done[128][25] = {0};
			
			for (pq.push(Info(s, 0, 0, -1)); !pq.empty(); pq.pop()){
				Info x = pq.top();
				
				if (done[x.to][x.time]) continue;
				done[x.to][x.time] = true;
				
				if (x.to == t){
					ret = min(ret, x.cost + dp[i]);
				}
				
				for (int j = 0; j < tmp[x.to].size(); j++){
					Info e = tmp[x.to][j];
					if (x.time + e.time > h) continue;
					pq.push(Info(e.to, x.cost + e.cost, x.time + e.time, -1));
				}
			}
		}
		
		printf("%d\n", ret != INF ? ret : -1);
	}
}

Measured memory_bytes: 1860
#include <bits/stdc++.h>
typedef long long ll;
#define INF 1000000000
#define MOD 1000000007
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
using namespace std;
int main(void){
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    int len=s.size();
    int num[len]={0};
    for(int i=1;i<len;i++){
        if(s[i]=='C' and s[i-1]=='A')num[i]=1;
    }
    for(int i=0;i<len-1;i++){
        num[i+1]+=num[i];
    }
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        cout<<num[r-1]-num[l-1]<<endl;
    }
 return 0;   
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define LL long long
#define N 100005

using namespace std;

int x[N];

int main() {
	int n,k,i;
	LL ans=(LL)1e11;
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;++i) {
		scanf("%d",&x[i]);
	}
	for(i=1;i<=n-k+1;++i) {
		LL tot=0;
		if(x[i]<0) {
			tot-=1LL*x[i];
			if(x[k+i-1]>=0) {
				tot-=1LL*x[i];
				tot+=1LL*x[k+i-1];
				ans=min(ans,tot);
				tot=0;
				tot+=1LL*2*x[k+i-1];
				tot-=1LL*x[i];	
				ans=min(ans,tot);			
			}
		}
		else tot+=1LL*x[k+i-1];
		ans=min(ans,tot);
	}
	cout<<ans;
}
 

Measured memory_bytes: 640
N,M = [int(x) for x in input().split()]
count = [0]*N
ac = 0
wa = 0
ireta = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    if b == "AC" and count[a-1] == 0:
        count[a-1] = 1
        ac += 1
    elif count[a-1] == 0:
        ireta.append(a)
        wa += 1
for i in range(len(ireta)):
    if count[ireta[i]-1] == 0:
        wa -= 1
print(ac,wa)

Measured memory_bytes: 7784
#include <bits/stdc++.h>
using namespace std;
long long s, sm;
long long dp[2001][2001];	
int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> s;
	for (int i = 3; i <= s; i++) dp[1][i]=1;
	for (int i = 2; i <= s/3; i++) {
		for (int j = 3 * i; j <= s; j++) {
			for (int i1= 3; i1 <= j; i1++) {
				dp[i][j] = dp[i][j] + dp[i-1][j-i1];
				if (dp[i][j] >= (long long)(1e9+7)) {
					dp[i][j] -= (long long)(1e9+7);
				}
			}
		}
	}
	for (int i = 1; i <= s/3; i++) {
		sm += dp[i][s];
		if (sm >= (long long)(1e9+7)) {
			sm -= (long long)(1e9+7);
		}
	}
	cout << sm;
}

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

int main()
{
    int n;
    cin >> n;
    int a[n + 1], c[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    c[1] = 0;
    // c[2] = abs(a[2] - a[1]);
    for (int i = 2; i <= n; i++)
    {
        c[i] = c[i - 1] + abs(a[i] - a[i - 1]);
        if (i > 2)
            c[i] = min(c[i], c[i - 2] + abs(a[i] - a[i - 2]));
    }
    cout << c[n] << endl;
    return 0;
}

Measured memory_bytes: 1024
from itertools import zip_longest
import sys
input = sys.stdin.readline


def main():
    ABCD = list(input().rstrip())
    n = len(ABCD) - 1

    for i in range(2**n):
        op = ['+' if ((i >> j) & 1) else '-' for j in range(n)]
        cal = ''.join([i + j for i, j in zip_longest(ABCD, op, fillvalue='')])
        if eval(cal) == 7:
            print(cal + '=7')
            break


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define INF 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n,m,R;
ll dp[201][201];
ll dp2[1<<9][10];
int r[9];

int main(void){
	scanf("%d%d%d",&n,&m,&R);
	for(int i=0;i<R;i++){
		scanf("%d",&r[i]);
		r[i]--;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			dp[i][j]=INF;
		}
		dp[i][i]=0;
	}
	for(int i=0;i<m;i++){
		int l,r,c;
		scanf("%d%d%d",&l,&r,&c);
		l--;
		r--;
		dp[l][r]=min(dp[l][r],(ll)c);
		dp[r][l]=min(dp[r][l],(ll)c);
	}
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	for(int i=0;i<(1<<R);i++){
		for(int j=0;j<R;j++){
			dp2[i][j]=INF*100LL;
		}
	}
	for(int i=0;i<R;i++){
		dp2[1<<i][i]=0;
	}
	for(int i=0;i<(1<<R);i++){
		for(int j=0;j<R;j++){
			for(int k=0;k<R;k++){
				dp2[i|(1<<k)][k]=min(dp2[i|(1<<k)][k],dp2[i][j]+dp[r[j]][r[k]]);
			}
		}
	}
	ll res=INF*100LL;
	for(int i=0;i<R;i++){
		res=min(res,dp2[(1<<R)-1][i]);
	}
	printf("%lld\n",res);
	return 0;
}

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

using namespace std;

int main(){
	int a[3];
	int f=0,s=0;
	cin>>a[0]>>a[1]>>a[2];
	for(int i=0;i<3;i++){
		if(a[i]==5){
			f++;
		}
		if(a[i]==7){
			s++;
		}
	}
	if(f==2&&s==1){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	}
}



Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
const int p=1e9+7;
int n;
long long f[110][4][4][4],ans;
int main(){
	scanf("%d",&n);
	fo(a,0,3)
		fo(b,0,3)
			fo(c,0,3){
				if (a==0&&b==1&&c==2) continue;
				if (a==1&&b==0&&c==2) continue;
				if (a==0&&b==2&&c==1) continue;
				f[3][a][b][c]++;
			}
	fo(i,3,n-1)
		fo(a,0,3)
			fo(b,0,3)
				fo(c,0,3)
					fo(d,0,3){
						if (b==0&&c==1&&d==2) continue;
						if (b==1&&c==0&&d==2) continue;
						if (b==0&&c==2&&d==1) continue;
						if (a==0&&c==1&&d==2) continue;
						if (a==0&&b==1&&d==2) continue;
						f[i+1][b][c][d]+=f[i][a][b][c];
						if (f[i+1][b][c][d]>=p) f[i+1][b][c][d]-=p;						
					}
	fo(a,0,3)
		fo(b,0,3)
			fo(c,0,3)
				ans+=f[n][a][b][c];
	ans%=p;
	printf("%lld\n",ans);
	return 0;
}

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

int main(){
    int n, m, q;cin >> n >> m >> q;
    int A[10];
    int atai[q][4];
    long long ans =0;
    long long max = 0;
    for (int i = 0; i < q; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            cin >> atai[i][j];
        }
        
    }

   
    for (A[0] = 1; A[0] <= m; A[0]++)
    {
        for (A[1] = A[0]; A[1] <= m; A[1]++)
        {
            for (A[2] = A[1]; A[2] <= m; A[2]++)
            {
                for (A[3] = A[2]; A[3] <= m; A[3]++)
                {
                    for (A[4] = A[3]; A[4] <= m; A[4]++)
                    {
                        for (A[5] = A[4]; A[5] <= m; A[5]++)
                        {
                            for (A[6] = A[5]; A[6] <= m; A[6]++)
                            {
                                for (A[7] = A[6]; A[7] <= m; A[7]++)
                                {
                                    for (A[8] = A[7]; A[8] <= m;A[8]++)
                                    {
                                        for (A[9] = A[8]; A[9] <= m; A[9]++)
                                        {
                                            ans = 0;
                                            for(int i = 0; i < q; i++)
                                            {
                                                if(A[atai[i][1]-1] - A[atai[i][0]-1] == atai[i][2])
                                                {
                                                    ans += atai[i][3];
                                                }
                                            }
                                            if (ans >= max) max = ans;

                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << max << endl;

    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    string S;
    cin >> S;
    int ans = 700;
    for(auto e:S) if(e == 'o') ans+=100;
    cout << ans << endl;
}


Measured memory_bytes: 256
import sys
import os
import math

def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.readline().rstrip())

    max = int(math.sqrt(N) + 1)
    ret = float('inf')
    for i in range(1, max):
        q, mod = divmod(N, i)
        if mod == 0:
            j = N // i
            ret = min(ret, ((j-1)+(i-1)))

    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

const int LG = 30;
int dp[LG][100001];

int main(){
    int N, L, Q;
    cin >> N;
    vi x(N);
    rep(i, N)scanf("%d", &x[i]);
    cin >> L >> Q;
    
    rep(i, N){
        int lo = i, hi = N;
        while(hi - lo>1){
            int mid = (hi + lo) / 2;
            if(x[mid] - x[i] <= L)lo = mid;
            else hi = mid;
        }
        dp[0][i] = lo;
    }

    rep(i, LG - 1){
        rep(j, N){
            dp[i + 1][j] = dp[i][dp[i][j]];
        }
    }

    while(Q--){
        int a, b;
        scanf("%d%d", &a, &b);
        if(a > b)swap(a, b);
        --a; --b;

        int lo = 0, hi = N;
        while(hi - lo > 1){
            int mid, cur = a;
            mid = (hi + lo) / 2;
            rep(i, LG)if(mid >> i & 1){
                cur = dp[i][cur];
            }
            if(cur >= b)hi = mid;
            else lo = mid;
        }
        printf("%d\n", hi);
    }
}

Measured memory_bytes: 12928
# ALDS_11_B - 深さ優先探索
import sys

n = int(input())
e = [None] * n
for _ in range(n):
    u, k, *v = map(int, sys.stdin.readline().strip().split())
    e[u - 1] = [i - 1 for i in v]


S = []  # stack
time = 0
t_in = [0] * n
t_out = [0] * n
fp = [False] * n  # foot print  訪問の記録


def dfs(u):
    global time

    S.append(u)
    time += 1
    t_in[u] = time
    fp[u] = True

    while S:
        u = S[-1]

        v = None
        for i in e[u]:
            if fp[i] is False:
                v = i
                break

        time += 1
        if v is not None:
            S.append(v)
            t_in[v] = time
            fp[v] = True

        else:
            v = S.pop()
            t_out[v] = time


while False in fp:
    dfs(fp.index(False))

for i in range(n):
    print(f'{i + 1} {t_in[i]} {t_out[i]}')



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

int main() {
	int N, K, l[50];
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> l[i];
	}
	sort(l, l + N, greater<int>());
	int count = 0;
	for (int i = 0; i < K; i++) {
		count += l[i];
	}
	cout << count << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#define maxn 200100
#define INF 100000000
using namespace std;
int main()
{
	long long  n;
	scanf("%lld",&n);
	long long ans;
	ans=n*(n-1)/2;
	printf("%lld\n",ans);
}

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

typedef struct pp{
  char name[100];
  int t;
}P;
int head=0, tail, n;
void enqueue(P x);

P Q[LEN+1];
int main(){
  int elaps = 0, c=0;
  int i, q;
  
  scanf("%d %d", &n, &q);
  tail=n;
  for ( i = 0; i < n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
    c+=Q[i].t;
  }
  while(elaps - c !=0){
      if(   Q[head].t>q   ){
	Q[head].t-=q;
	elaps+=q;
	enqueue(Q[head]);
      }
      else {
	elaps+=Q[head].t;
	printf("%s %d\n",Q[head].name,elaps);
      }
      head++;
      if(tail==LEN+1)tail=0;
if(head==LEN+1)head=0;
  }
  return 0;
}
void enqueue(P x){
  strcpy(Q[tail].name,x.name);
  Q[tail].t=x.t;
  tail++;
  if(tail==LEN+1)tail=0;
}

Measured memory_bytes: 10768
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
	double md=-1.0,den;
	int s,sw,ms=1,msw=-1;
	int a,b,c,d,e,f;
	cin>>a>>b>>c>>d>>e>>f;
	FOR(ia,0,31){
		FOR(ib,0,16){
			if(!ia&&!ib)continue;
			FOR(ic,0,51){
				FOR(id,0,26){
					sw=a*100*ia+b*100*ib+c*ic+d*id;
					s=c*ic+d*id;
					if(100*s>e*(sw-s)||sw>f)break;
					if(msw==-1){
						msw=sw;
						ms=s;
					}else{
						if(msw==0||ms==0||ms*sw<s*msw){
							msw=sw;
							ms=s;
						}
					}
				}
			}
		}
	}
	cout<<msw<<" "<<ms<<endl;

    return 0;
}


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

int main(void) {
	int r, D, x;
	cin >> r >> D >> x;
	int sum = x;
	for (int i = 0; i < 10; i++) {
		sum = sum * r - D;
		cout << sum << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define U [1<<17]={}
typedef long long L;using namespace std;map<L,L> path U;L P U,E U,Z U,H U,C U,A U,O U,X U,B U,k,n,a,b,c,p,r;char s U;
L D(L a){Z[a]=1;for(map<L,L>::iterator I=path[a].begin();I!=path[a].end();I++){L d=I->first;if(d-P[a]){P[d]=a;E[d]=E[a]+1;C[d]=I->second;D(d);Z[a]+=Z[d];!H[a]|Z[H[a]]<Z[d]?H[a]=d:0;}}}
L G(L a){r=A[a]+A[P[a]]+C[a];return r%k?r:0;}
L M(L i){return i?B[i]+M(i-(i&-i)):0;}
L S(L x,L i){for(x=G(x)-M(i+1)+M(i++);i<1<<17;B[i]+=x,i+=i&-i);}
main(){for(cin>>n>>k;p<n-1;p++)cin>>a>>b>>c,path[a][b]=path[b][a]=c;
       for(D(c=p=0);p<n;p++)if(!p|H[P[p]]-p)for(a=p;!c|a;)X[a]=p,S(a=H[a],O[a]=c++);
       for(cin>>a;cin>>s>>a>>b;)if(*s&2){
           for(c=0;p=X[a],n=X[b],p-n;a=P[p])E[p]<E[n]?swap(p,n),swap(a,b),0:0,c+=M(O[a])-M(O[p])+G(p);cout<<c+abs(M(O[a])-M(O[b]))<<endl;}
       else A[a]+=b,S(H[a],O[a]),a?S(a,O[a]-1):0;}

Measured memory_bytes: 33464
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
			Reader.init(System.in);

			int n=Reader.nextInt();
			int[] a= new int[n];
			int[] b= new int[n];
			int[] c= new int[n];

			for(int i=0; i<n; i++) {
				a[i]=Reader.nextInt();
				b[i]=Reader.nextInt();
				c[i]=Reader.nextInt();
			}
			
			int[][]dp= new int[n][3];
			
				dp[0][0]=a[0];
				dp[0][1]=b[0];
				dp[0][2]=c[0];
			
			
			for(int i=1; i<n; i++) {
				dp[i][0]=a[i]+Math.max(dp[i-1][1], dp[i-1][2]);
				dp[i][1]=b[i]+Math.max(dp[i-1][0], dp[i-1][2]);
				dp[i][2]=c[i]+Math.max(dp[i-1][0], dp[i-1][1]);
			}
			
			int ans= Math.max(Math.max(dp[n-1][0], dp[n-1][1]),dp[n-1][2]);
			System.out.println(ans);
	}
	}

	class Reader {
	    static BufferedReader reader;
	    static StringTokenizer tokenizer;
	    static void init(InputStream input) {
	        reader = new BufferedReader(
	                     new InputStreamReader(input) );
	        tokenizer = new StringTokenizer("");
	    }

	    static String next() throws IOException {
	        while ( ! tokenizer.hasMoreTokens() ) {

	        	tokenizer = new StringTokenizer(
	                   reader.readLine() );
	        }
	        return tokenizer.nextToken();
	    }

	    static int nextInt() throws IOException {
	        return Integer.parseInt( next() );
	    }
		
	    static double nextDouble() throws IOException {
	        return Double.parseDouble( next() );
	    }
	    static long nextLong() throws IOException {
	        return Long.parseLong( next() );
	    }
	    

	}

Measured memory_bytes: 55800
N, M = map(int, input().split())
A = []
for i in range(M):
    a = int(input())
    A.append(a)
def step(n):
    steps = [0 for i in range(n + 1)]
    ind = 0
    steps[0] = 1
    steps[1] = 1
    if M != 0:
        if 1 == A[ind]:
            steps[1] = 0
            if ind < M-1:
                ind += 1
    for i in range(2, n + 1):
        steps[i] = steps[i - 1] + steps[i - 2]
        if M != 0:
            if i == A[ind]:
                steps[i] = 0
                if ind < M-1:
                    ind += 1
    return steps[n] % 1000000007
print(step(N))

Measured memory_bytes: 460056
//============================================================================
// Name        : JOI.cpp
// Author      : 
// Version     : 20min
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

	string str;
	cin>>str;
	int flg=0;
	for(int i=0;i<str.size()-1;++i){
		if(str[i]=='A'&&str[i+1]=='C')flg=1;
	}

	if(flg==0){
		cout<<"No"<<endl;
	}else{
		cout<<"Yes"<<endl;

	}
	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
 
typedef long long ll;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define DBGV(v,n) forn(i,n) cout << v[i] << " "; cout << endl
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl
#define MAXN 2005


int main()
{ 
	FIN;
	
	#ifdef input
		//freopen("test1.txt", "r", stdin);
	#endif
	
	int n;
	cin >> n;
	vector <int> v(n);
	forn(i,n) cin >> v[i];
	int ans = 0 ;
	forn(i,n) ans=(ans^v[i]);
	forn(i,n) cout << (ans^v[i]) << " ";
		
		
	
	return 0;
}


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

namespace test
{
    class MainClass
    {
        public static void Main(string[] args)
        {

            //問題161

            string[] line = Console.ReadLine().Split(' ');

            long n = long.Parse(line[0]);
            long k = long.Parse(line[1]);

            n %= k;

            long ans = Math.Min(n, Math.Abs(n - k));

            Console.WriteLine(ans);
        }

    }





    
}


Measured memory_bytes: 26884
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define bg begin()
#define en end()

using namespace std;

typedef long long ll;

int N, L, R;
char S[105];
bool used[105];

int main() {
  scanf("%d", &N);
  scanf("%s", S);
  
  rep(i, 0, N) {
    if (S[i] == '(') {
      rep(j, i+1, N) {
        if (S[j] == ')' && !used[j]) {
          used[i] = used[j] = true;
          break;
        }
      }
    }
  }
  rep(i, 0, N) {
    if (!used[i]) {
      if (S[i] == '(' ) R++;
      else L++;
    }
  }
  
  rep(i, 0, L) printf("(");
  printf("%s", S);
  rep(i, 0, R) printf(")");
  
  return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
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 <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <class T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;

int main() {
	ll n, a, b;
	cin >> n >> a >> b;
    ll ans;
    if ((b-a)%2) {
        ans = min((b-a+1)/2+(a-1), ((b-a+1)/2+(n-b)));
    } else {
        ans = (b-a)/2;
    }
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>

int main() {
  size_t A, B, Q;
  scanf("%zu %zu %zu", &A, &B, &Q);

  std::vector<intmax_t> s(A), t(B);
  for (auto& si: s) scanf("%jd", &si);
  for (auto& ti: t) scanf("%jd", &ti);

  s.push_back(1e17);
  t.push_back(1e17);

  for (size_t i = 0; i < Q; ++i) {
    intmax_t x;
    scanf("%jd", &x);

    auto ss = std::lower_bound(s.begin(), s.end(), x);
    auto tt = std::lower_bound(t.begin(), t.end(), x);

    intmax_t s1 = *ss;
    intmax_t t1 = *tt;

    intmax_t s0 = -1e17;
    intmax_t t0 = -1e17;
    if (ss > s.begin()) s0 = *--ss;
    if (tt > t.begin()) t0 = *--tt;

    intmax_t res = std::min({std::max(s1, t1)-x, x-std::min(s0, t0),
                             (s1-x)+(s1-t0), (x-t0)+(s1-t0),
                             (t1-x)+(t1-s0), (x-s0)+(t1-s0)});
    printf("%jd\n", res);
  }
}


Measured memory_bytes: 2912
{
  const main = (
    input: string
  ): void | string | number | string[] | number[] => {
    const r = _reader(input)
    const [N] = r.nn()
    const P = r.nn()

    let min = P[0]
    let sum = 1

    for (let i = 1; i < N; i++) {
      if (min > P[i]) {
        sum += 1
        min = P[i]
      }
    }

    return sum
  }

  const _reader = (str: string, i = 0) => {
    const lines = str.trim().split('\n')
    const s = () => lines[i++] || ''
    const n = () => Number(s())

    const mn = (v: string[]) => v.map(Number)
    const sp = (v: string) => v.split(' ')
    const ss = () => sp(s())
    const nn = () => mn(ss())
    const nls = () => mn(lines.slice(i))
    const nnls = () => lines.slice(i).map(v => mn(sp(v)))

    return { lines, s, n, ss, nn, nls, nnls }
  }

  const _getInput = () => require('fs').readFileSync('/dev/stdin', 'utf8')
  const _res = main(_getInput())

  if (typeof _res === 'number' || typeof _res === 'string') console.log(_res)
  if (typeof _res === 'object') console.log(_res.join(' '))
}


Measured memory_bytes: 22224
n, k = [int(x) for x in input().split()]
r, s, p = [int(x) for x in input().split()]
t = input()
z = {'r': 'p', 's': 'r', 'p': 's'}
v = {'r': r, 's': s, 'p': p, 'z': 0}
x = []
for a in t:
    x.append(z[a])
for i in range(k):
    for j in range(k + i, n, k):
        if x[j] == x[j - k]:
            x[j] = 'z'
ans = 0
for i in range(n):
    ans += v[x[i]]
print(ans)

Measured memory_bytes: 45680
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

int main(){
  int D, G; cin >> D >> G;
  
  int P[D], C[D], ans = 0;
  for (int i = 0; i < D; i++){
    cin >> P[i] >> C[i];
    ans += P[i];
  }

  int all = pow(3, D);
  for (int i = 0; i < all; i++){
    int Now_Num = i;
    vector <int> now(D);
    int cnt2 = 0;
    for (int j = 0; j < D; j++){
      now[j] = Now_Num % 3;
      Now_Num /= 3;
      if (now[j] == 2) cnt2++;
    }

    if (cnt2 >= 2) continue;

    int Now_Point = 0, Now_Count = 0;
    for (int j = 0; j < D; j++){
      if (now[j] == 1) {
        Now_Point += P[j] * (j + 1) * 100 + C[j];
        Now_Count += P[j];
      }
    }

    for (int j = 0; j < D; j++){
      if (now[j] == 2 && Now_Point < G){
        int Rest = (G - Now_Point) / ((j + 1) * 100);
        if ((G - Now_Point) % ((j + 1) * 100) != 0) Rest++;

        if (Rest <= P[j]){
          Now_Point += Rest * (j + 1) * 100;
          Now_Count += Rest;
        }
      }
    }
    
    if (Now_Point >= G){
      ans = min(ans, Now_Count);
    }
  }
  cout << ans << endl;

  return 0;
}


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

int main(){
	int n,q,c,t,x;
	vector<int> V[1005];
	cin>>n>>q;
	for(int i=0;i<q;i++){
		cin>>c>>t;
		switch(c){
			case 0:
				cin>>x;
				V[t].push_back(x);
				break;
			case 1:
				for(int j=0;j<V[t].size();j++){
					if(j==V[t].size()-1) cout<<V[t][j];
					else cout<<V[t][j]<<" ";
				}
				cout<<endl;
				break;
			case 2:
				if(!V[t].empty()) V[t].clear();
		}
	}
	return 0;
}


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

long long A, B, l;

int main(void) {
  scanf("%lld%lld", &A, &B);
  if(A == B) return puts("1"), 0;
  for(l = 60; ~l; l--)
    if((A >> l & 1) != (B >> l & 1))
      break;
  
  long long T = 1LL << l;
  A %= T; B %= T;
  for(l--; ~l; l--)
    if(B >> l & 1)
      break;
  long long L = T + (1LL << l + 1);
  cout << L - A + 2 * T - max(L, T + A) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#include <functional>
#include <cassert>
using namespace std;
#define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#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 MOD (long long int)(1e9+7)
#define INF (int)(1e9)
#define LINF (long long int)(1e18)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}
ll lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size() > n) return kaijo_memo[n];
  if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
  while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
  if(n < r || r < 0) return 0;
  ll ret = 1;
  if(n <= 1e7){
    ret *= kaijo(n); ret %= MOD;
    ret *= gyaku_kaijo(r); ret %= MOD;
    ret *= gyaku_kaijo(n-r); ret %= MOD;
  }else{
    rep(i,r){
      ret *= n-i; ret %= MOD;
      ret *= mpow(r-i, MOD-2); ret %= MOD;
    }
  }
  return ret;
}



int main(void){
  fast_io
  cout<<fixed<<setprecision(15);
  int n;
  cin >> n;
  vector<ll> ls(n);
  rep(i,n){
	  cin >> ls[i];
  }
  ll ans = 0;
  rep(i,n-2){
	  for(int j=i+1;j<n-1;j++){
		  if(ls[i] != ls[j]){
			  for(int k=j+1;k<n;k++){
				  if(ls[i] != ls[k] && ls[k] != ls[j]){
					  if(ls[i]+ls[j]>ls[k]&&ls[j]+ls[k]>ls[i]&&ls[k]+ls[i]>ls[j]){
						  ans++;
					  }
				  }
			  }
		  }
	  }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int a[10010],tp,ans;
int main(){
	cin>>n;
	while(n)a[++tp]=n%10,n/=10;
	for(int i=tp,sum=0;i>=1;--i)if(a[i]){
		ans=max(ans,(i-1)*9+sum+a[i]-(i==1?0:1));
		sum+=a[i];
	}
	printf("%d",ans);
}


Measured memory_bytes: 256
# ref https://qiita.com/ZhangChaoran/items/71fab0e4b8647a93d3a0
from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
g = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

mod = 10**9 + 7
par = [0] * (n + 1)
order = []
stk = deque()
stk.append(1)

while stk:
    v = stk.pop()
    order.append(v)
    for x in g[v]:
        if x == par[v]:
            continue
        par[x] = v
        stk.append(x)

rev = pow(2, mod - 2, mod)
po2_inv = [1] * (n + 1)
size = [1] * (n + 1)
for i, y in enumerate(order[::-1], 1):
    p = par[y]
    size[p] += size[y]
    po2_inv[i] = po2_inv[i - 1] * rev % mod

ans = 1
for i in size[2:]:
    ans += (1 - po2_inv[i] - po2_inv[n - i] + po2_inv[n]) % mod
ans -= po2_inv[n] + n * po2_inv[1]
ans %= mod
print(ans)


Measured memory_bytes: 59600
A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())
X=[A%10,B%10,C%10,D%10,E%10]
minimum=100
for i in range(5):
  if X[i]!=0:
    minimum=min(minimum,X[i])
Y=[A,B,C,D,E]
if minimum==100:
  minimum=0
last=X.index(minimum)
time=0
import math
for i in range(5):
  if i!=last:
    time =time+10*math.ceil(Y[i]/10)
if X==[0,0,0,0,0]:
  print(sum(Y))
else:
  print(time+Y[last])

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

int main() {
  double a;
  cout.precision(10);
  while(cin>>a) {
    double sum = a;
    for(int i=2; i<=10; ++i) {
      if(i%2==0) {
        a *= 2;
        sum += a;
      }else{
        a /= 3;
        sum += a;
      }
    }
    cout<<sum<<endl;
  }
}

Measured memory_bytes: 0
hash = {"a" => gets.chomp,"b" => gets.chomp,"c" => gets.chomp}
trashCard = hash["a"][0]
hash["a"].slice!(0)
loop do
  break if hash[trashCard].length == 0
  tempTrashCard = hash[trashCard][0]
  hash[trashCard].slice!(0)
  trashCard = tempTrashCard
end
puts trashCard.upcase

Measured memory_bytes: 1788
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
    	
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int N = 3;

		// Mapの宣言
        Map<Integer, Integer> mMap = new HashMap<Integer, Integer>();
        
		for (int i = 0; i < N;i ++ ){
			// 年、点数の入力
			mMap.put( sc.nextInt(),i+1);
		}

		// キーでソートする
        Object[] mapkey = mMap.keySet().toArray();
        Arrays.sort(mapkey);
        
        int cnt = 0;
        int ans = 0;
        for (Object nKey : mapkey)
        {
//            System.out.println(nKey);
//            System.out.println(mMap.get(nKey));
            cnt ++;
//            System.out.println(mMap.get(nKey));
//            System.out.println(nKey);
            ans = ans + Integer.parseInt(nKey.toString());
            if (cnt == 2){
            	break;
            }
        }
        if(cnt == 1){
        	ans = ans * 2;
        }
		
		
		System.out.println(ans);

   		sc.close();
        return ;

    }
    
}



Measured memory_bytes: 22996
#include <string>
#include <vector>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <map>
using namespace std;


#define prec(i) cout << fixed << setprecision(i)

void outPut_YN(bool isYes) {
	if(isYes)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

const long long MOD = 1000000007;

long long fact(long long k) {
	long long sum = 1;
	for (long long i = 2; i <= k; i++)
		sum *= i;

	return sum;
}

long long fact_mod(long long k) {
	long long sum = 1;
	for (long long i = 2; i <= k; i++)
		sum = (sum * i) % MOD;

	return sum;
}

int ctoi(char c) {
	if (c >= '0' && c <= '9')
		return c - '0';
	else
		return -1;
}

long long pow_mod(int a, int b) {
	long long ans = 1;
	for (int i = 0; i < b; i++)
		ans = (ans * a) % MOD;

	return ans;
}

long long powll(long long a, long long  b) {
	long long ans = 1;
	for (long long i = 0; i < b; i++)
		ans = ans * a;

	return ans;
}

long long modinv(long long a) {
	long long b = MOD, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= MOD;
	if (u < 0) u += MOD;
	return u;
}

vector<vector<int>> checkTree;
vector<int> turnTree;
vector<bool> isPassed;
int maxTurn;

int func(int pos, int turn) {
	cout << pos << endl;
	if (turn > maxTurn)
		return 0;

	if (checkTree[pos].size() > 0) {
		int max = 0;
		for (int i = 0; i < checkTree[pos].size(); i++) {
			if (!isPassed[checkTree[pos][i]]) {
				int t;
				if((t = func(checkTree[pos][i], turn + 1)) > max)
					max = t;
			}
		}
		isPassed[pos] = true;
		return max;
	}
	else {
		return turn;
	}
		
}


int main()
{
	long long n, cnt = 0;

	cin >> n;

	vector<long long> p(n);

	for (int i = 0; i < n; i++)
		cin >> p[i];

	long long min = p[0];
	for (int i = 0; i < n; i++) {
		if (p[i] <= min) {
			min = p[i];
			cnt++;
		}
	}
		

	cout << cnt << endl;


	return 0;
}

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

using namespace std;

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

    bool ans=false;
    for(int i=1; i<=9; ++i)
    {
        int q=n/i;
        if(n%i == 0 && q>=1 && q<=9)    ans = true;
    }

    if(ans) cout<<"Yes";
    else cout<<"No";

    return 0;
}

Measured memory_bytes: 256
def s(d, k, i, c):
	if i == len(d): return c + int(k)
	return s(d, d[i], i + 1, int(k) + c) + s(d, k + d[i], i + 1, c)

d = [x for x in input()]
print(s(d, d[0], 1, 0))


Measured memory_bytes: 2940
n, k = map(int, input().split())
*V, = map(int, input().split())
M = [v if v < 0 else 0 for v in V]
S = [0]
for i in range(1, min(k+1, n+1)):
    for j in range(i+1):
        s = sum(V[:i-j])+sum(V[n-j:])
        M_sub = sorted(M[:i-j]+M[n-j:])
        s -= sum(M_sub[:k-i])
        S += [s]
print(max(S))

Measured memory_bytes: 40688
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007ll)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}
template<class T> void chmax(T &a, const T &b){if(a<b)a=b;}
template<class T> void chmin(T &a, const T &b){if(a>b)a=b;}
void YN(bool b){cout<<(b?"YES":"NO")<<endl;}
void Yn(bool b){cout<<(b?"Yes":"No")<<endl;}
void yn(bool b){cout<<(b?"yes":"no")<<endl;}

ll dp[394];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m,w;
	cin>>n;
	memset(dp,-1,sizeof(dp));
	vl s(n),l(n),p(n);
	rep(i,n)cin>>s[i]>>l[i]>>p[i];
	dp[0]=0;
	rep(i,n){
		rep(j,394){
			for(int k=s[i];k<=l[i];k++){
				if(j-k>=0&&dp[j-k]!=-1)chmax(dp[j],dp[j-k]+p[i]);
			}
		}
	}
	cin>>m;
	vi ans;
	rep(i,m){
		cin>>w;
		if(dp[w]==-1){cout<<"-1"<<endl;return 0;}
		ans.push_back(dp[w]);
	}
	rep(i,ans.size()){
		cout<<ans[i]<<"\n";
	}
}


Measured memory_bytes: 3220
using System;
 
public class Test
{
	static long n, a, b;
	static long[] monster;
	 
    static bool enough(long t) {
			long attack = b * t;
			long diff = a - b;
			long count = 0;
			
			foreach (long i in monster) {
				long tmp = i - attack;
				if (tmp > 0) {
					count += tmp / diff;
					if (tmp % diff != 0) {
						count++;
					}
				}
			}
			
			if (count <= t) {
				return true;
			} else {
				return false;
			}
		}
		
	static long bs() {
		long left = 0;
		long right = 1000000000;
		long mid;
		while (left < right) {
			mid = (left + right) / 2;
			if (enough(mid)) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return right;
	}
		
	
	public static void Main()
	{	
		string[] str = Console.ReadLine().Split(' ');
        n = long.Parse(str[0]);  
        a = long.Parse(str[1]);
        b = long.Parse(str[2]);
        monster = new long[n];
        for (int i = 0; i < n; i++) {
        	monster[i] = long.Parse(Console.ReadLine());
        }
      
		Console.Write(bs());
		
	}
}

Measured memory_bytes: 16080
import java.io.*;
import java.util.*;
class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        while(true){
            try{
                int n=Integer.parseInt(br.readLine());
                int count=0;
                for(int i=0;i<10;i++){
                    for(int j=0;j<10;j++){
                        for(int k=0;k<10;k++){
                            for(int l=0;l<10;l++){
                                if(i+j+k+l==n){
                                    count++;
                                }
                            }
                        }
                    }
                }System.out.println(count);
            }catch(Exception e){System.exit(0);}
        }
    }
    
}

Measured memory_bytes: 25068
#include <vector>
#include <cmath>
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <set>

using namespace std;

#define S 1000

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

    string s;
    unordered_map<string,int> m;
    for(int i = 0; i < N; i++) {
        cin >> s;
        m[s]++;
    }

    cout << "AC x " << m["AC"] << '\n';
    cout << "WA x " << m["WA"] << '\n';
    cout << "TLE x " << m["TLE"] << '\n';
    cout << "RE x " << m["RE"] << '\n';
    return 0;
}

Measured memory_bytes: 3624