akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i < (int)(n); i++) 
#define dunk(n) cout << n << endl
#define all(a) (a).begin(),(a).end()
typedef pair<int,int> P;
typedef long long ll;

int main() {
    int n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    vector<ll> c;
    rep(i,n-1){
        if(a[i] < a[i+1]) c.push_back(0);
        else if(a[i] > a[i+1]) c.push_back(1);
        else c.push_back(2);
    }
    ll m = 1000,s = 0;
    rep(i,c.size()){
        if(c[i] == 0){
            s += m/a[i]; //buy
            m = m%a[i];
        }
        if(c[i] == 1){
            m += s*a[i]; //sell
            s = 0;
        }
        if(c[i] == 2){
            continue;
        }
    }
    m += s*a[n-1];
    dunk(m);
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const ll INF=1e18;


int main() {
	ll n,ans = 0;
	cin >> n;
	vector<int> a(n);
	rep(i,n){
		cin >> a[i];
	}
	for(int i = 1;i<n;i++){
		if (a[i] < a[i - 1]){
			ans+=a[i - 1] - a[i];
			a[i] = a[i - 1];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 4064
x, y, A, B, C = map(int, input().split())
r  = list(map(int, input().split()))
b  = list(map(int, input().split()))
mu = list(map(int, input().split()))

mu += sorted(r)[-x:]
mu += sorted(b)[-y:]
print(sum(sorted(mu)[-(x+y):]))


Measured memory_bytes: 23328
while True:
    N, M, P, A, B = map(int, input().split())
    if not (N | M | P | A | B):
        break
    A, B = A - 1, B - 1
    T = [int(x) for x in input().split()]
    dp = [[float("inf")] * M for _ in range(1 << N)]
    dp[0][A] = 0
    edges = []
    for _ in range(P):
        s, t, c = map(int, input().split())
        s, t = s - 1, t - 1
        edges.append((s, t, c))
        edges.append((t, s, c))
    ans = float('inf')
    for state in range(1 << N):
        for s, t, c in edges:
            for k in range(N):
                if not (state >> k & 1):
                    next_s = state | (1 << k)
                    dp[next_s][t] = min(dp[next_s][t], dp[state][s] + c / T[k])
    ans = min(dp[state][B] for state in range(1 << N))
    print("Impossible" if ans == float("inf") else "{:.010f}".format(ans))

Measured memory_bytes: 7888
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


def solve():
  N, A, B, C, D = map(int, input().split())
  seen_values = set()
  queue = []
  heapq.heappush(queue, (0, N))

  while True:
    cost, value = heapq.heappop(queue)

    if value in seen_values:
      continue

    seen_values.add(value)

    if value == 1:
      print(cost + D)
      return

    for k, c in ((2, A), (3, B), (5, C)):
      v, m = divmod(value, k)

      if v == 0:
        continue
      elif m == 0:
        heapq.heappush(queue, (cost + c, v))
      else:
        heapq.heappush(queue, (cost + c + D * m, v))
        heapq.heappush(queue, (cost + c + D * (k - m), v + 1))

      heapq.heappush(queue, (cost + D * (value - v), v))


def main():
  for _ in range(int(input())):
    solve()


if __name__ == '__main__':
  main()


Measured memory_bytes: 87232
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 10010
using namespace std;
int n,k,a[N],f[N],ok=1,s;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=min(a[i],k),s+=a[i];
	sort(a+1,a+n+1);
	f[0]=1;
	for(int i=n;i>=0;i--){
		ok=1;
		for(int j=max(k-s,0);j<=k-1;j++) 
	        if(f[j]==1) {ok=0;break;}
	    if(ok){
	    	printf("%d",i);
	    	break;
	    }
	    for(int j=k;j>=a[i];j--) f[j]=f[j-a[i]]|f[j];
	    s-=a[i];
	} 
}/*
6 3
10 4 3 10 25 2
*/

Measured memory_bytes: 256
function main()
  
  (N, M) = map(x -> parse(Int, x), split(readline()))
  
  ans = 0
  
  if M >= 2N
    ans += N
    M -= 2N
  else
    ans += div(M,2)
    M = 0
  end

  ans += div(M,4)
  
  println(ans)
  
end

main()

Measured memory_bytes: 110220
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

vector<int> ps() {
  vector<bool> isP(55556);
  for (int i = 0; i < 55556; i++)
    isP[i] = true;
  isP[0] = isP[1] = false;
  isP[2] = true;
  for (int i = 3; i < 55556; i++) {
    if (i % 2 == 0) {
      isP[i] = false;
      continue;
    }
    for (int j = 3; j * j <= i; j++) {
      if (i % j == 0)
        isP[i] = false;
    }
  }
  vector<int> ret;
  for (int i = 0; i < 55556; i++) {
    if (isP[i] && i % 10 == 1)
      ret.push_back(i);
  }
  return ret;
}

int main() {
  int n;
  cin >> n;
  vector<int> p = ps();
  cout << p[0];
  for (int i = 1; i < n; i++)
    cout << " " << p[i];
  cout << endl;
  return 0;
}


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

struct Point { double x, y; };
void koch( int n, Point a, Point b ){
	if( n == 0 ){ return; }
	Point s, t, u;
	double th = M_PI * 60.0 / 180.0;//?????????????????¢?????????????????????

	s.x = ( 2.0 * a.x + 1.0 * b.x ) / 3.0;
	s.y = ( 2.0 * a.y + 1.0 * b.y ) / 3.0;
	t.x = ( 1.0 * a.x + 2.0 * b.x ) / 3.0;
	t.y = ( 1.0 * a.y + 2.0 * b.y ) / 3.0;
	u.x = ( t.x - s.x ) * cos( th ) - ( t.y - s.y ) * sin( th ) + s.x;
	u.y = ( t.x - s.x ) * sin( th ) + ( t.y - s.y ) * cos( th ) + s.y;

	koch( n - 1, a, s );
	cout << fixed << setprecision( 8 ) << s.x << " " << s.y << endl;
	koch( n - 1, s, u );
	cout << fixed << setprecision( 8 ) << u.x << " " << u.y << endl;
	koch( n - 1, u, t );
	cout << fixed << setprecision( 8 ) << t.x << " " << t.y << endl;
	koch( n - 1, t, b );
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	Point a, b;
	int n;
	cin >> n;

	a.x = 0;
	a.y = 0;
	b.x = 100;
	b.y = 0;

	cout << fixed << setprecision( 8 ) << a.x << " " << a.y << endl;
	koch( n, a, b );
	cout << fixed << setprecision( 8 ) << b.x << " " << b.y << endl;

	return 0;
}

Measured memory_bytes: 3248
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long ll;

int main(){
    int N; cin >> N;
    int h[100001];
    rep(i, N) cin >> h[i];

    int max = 0;
    int tmp = 0;
    rep(i, N-1){
        if(h[i] >= h[i+1] ){
            tmp++;
            if(tmp > max) max = tmp;
        }
        else{
            tmp = 0;
        }
    }
    cout << max << endl;

    return 0;
}

Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n;
    cin >> n;
    long long int a[n];
    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
    }
    sort(a,a + n);
    int ans = 0;
    long long int sum = 0;
    int i = 0;
    for(int i = 0;i < n;i++)
    {
        if(a[i] > sum * 2)
        {
            ans = 0;
        }
        sum += a[i];
        ans++;
    }
    cout << ans << "\n";

    return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll count_a(int N, int K, int B) {
  ll res = 0;
  res += (N / B) * (B - K);
  res += max(0, (N % B) - (K-1));
  return res;
}

int main2() {
  int N, K; cin >> N >> K;
  if (K == 0) {
    cout << (ll)N*N << endl;
  } else {
    ll ans = 0;
    for (int b = K+1; b <= N; b++) {
      ans += count_a(N, K, b);
    }
    cout << ans << endl;
  }
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
const int MOD = 1e9+7;
const ll LINF = 1e18;
const int INF = 1e9;
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;

int main()
{
    cin >> S;
    smatch ssmm;
    if(regex_search(S,ssmm,regex("^A[a-z]+C[a-z]+$")))
    {
        cout << "AC";
        return 0;
    }
    cout << "WA";

    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int cnt[26] = {0, };
    string s; cin >> s;
    for (auto c : s) {
        if (cnt[c - 97]++ == 1) {
            cout << "no\n";
            return 0;
        }
    }
    cout << "yes\n";
    return 0;
}


Measured memory_bytes: 256
//besmellah
    #include <bits/stdc++.h>
    using namespace std;
     
    int main() {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	int n;
    	cin >> n;
    	vector <int> A;
    	bool f = 0;
    	for (int i = 0; i < n; i++) {
    		int r;
    		cin >> r;
    		if (r == 1)
    			f = 1;
    		if (f)
    			A.push_back(r);
    	}
    	vector <int> vec;
    	vec.push_back(0);
    	int k = 0;
    	for (int i = 0; i < A.size(); i++) {
    		if (A[i] == k + 1)
    			k++;
    	}
    	if (k)
    	cout << n - k;
    	else
    		cout << -1;
    }

Measured memory_bytes: 1400
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    money = 1000
    stock = 0
    for i in range(N-1):
        if A[i+1]>A[i]:
            if money//A[i]>0:
                stock += money//A[i]
                money -= stock * A[i]
        elif A[i+1] < A[i]:
            money += stock * A[i]
            stock = 0
    if stock>0:
        money += A[-1] * stock
    print(money)


if __name__ == '__main__':
    main()



Measured memory_bytes: 8976
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class A
{
	public static void Main()
	{
		int N = GetInt();
		int A = GetInt() - 1;
		int B = GetInt() - 1;
		int C = GetInt() - 1;
		int D = GetInt() - 1;
		string S = GetString();

		bool isPrevStone = false;
		for(int i = A; i <= D; i++)
		{
			if(S[i] != '#')
			{
				isPrevStone = false;
				continue;
			}

			if(isPrevStone)
			{
				Console.WriteLine("No");
				return;
			}
			isPrevStone = true;
		}

		if(C < D)
		{
			Console.WriteLine("Yes");
			return;
		}

		int numConnectedFree = 0;
		for(int i = B-1; i <= D+1; i++)
		{
			if(S[i] == '.')
			{
				numConnectedFree++;
				if(numConnectedFree == 3)
				{
					Console.WriteLine("Yes");
					return;
				}
			}
			else
				numConnectedFree = 0;
		}

		Console.WriteLine("No");
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}

Measured memory_bytes: 12384
var K,N,i,t,v:Longint;
A:Array[1..200000]of Longint;
begin
read(K,N);
for i:=1 to N do read(A[i]);
for i:=2 to N do begin
v:=A[i]-A[i-1];
if t<v then t:=v;
end;
v:=K+A[1]-A[N];
if t<v then t:=v;
writeln(K-t);
end.

Measured memory_bytes: 896
#include<iostream>
using namespace std;
int main()
{
    int n,l,r,i,c=0;
    cin>>l>>r>>n;
    if(l>r)
        swap(l,r);
    for(i=l;i<=r;i++)
    {
        if(i%n==0)
            c++;
    }
    cout<<c<<endl;
}


Measured memory_bytes: 3616
public class Main {
	public static void main(String[] args) {
		java.util.Scanner sc = new java.util.Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int a;// = sc.nextInt();
		String op;// = sc.next();
		int b;// = sc.nextInt();

		do {
			a = sc.nextInt();
			op = sc.next();
			b = sc.nextInt();
			if (op.equals("?")) {break;}
			if (op.equals("+")) {sb.append(a+b).append("\n");}
			if (op.equals("-")) {sb.append(a-b).append("\n");}
			if (op.equals("*")) {sb.append(a*b).append("\n");}
			if (op.equals("/")) {sb.append(a/b).append("\n");}
		} while(true);
		System.out.print(sb);
	}
}

Measured memory_bytes: 26148
#include <iostream>
#include <cstring>
#include<vector>
#include <algorithm>
#include<cstdlib>
#include<set>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(n,x) for(ll i=0;i<n;i++) cin>>x[i];
#define forr(a,b) for(ll i=a;i<b;i++);
ll gcd(ll x, ll y)
{
	if (x % y == 0) return y;
	else return gcd(y, x % y);
}
// 1or素数だと１を返す
ll prime(ll x)
{
	for (ll i = 2; i * i <= x; i++)
	{
		if (x % i == 0) return 0;
	}
	return 1;
}



int main()
{
	ll n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	ll y = 0;
	ll no = 0;
	for (ll i = 0; i < n - 1; i++)
	{
		if (s[i] == s[i + 1])
		{
			y++;
		}
		else no++;
	}
	ll ans = y + min(2 * k, no);
	cout << ans << "\n";
}

Measured memory_bytes: 3764
#include<stdio.h>
#include<string.h>
 
int main(){
    int ans = 0, l = 0, i;
    char s[101], k[] = "keyence";
    char *ret;
    scanf("%s", s);
    l = strlen(s);
    if(l < 7){
        puts("NO");
        return 0;
    }

    for(i = 0; i < 7; ++i){
        if(s[i] != k[i]) break;
        if(i == 6) ans = 1;
    }

    for(i = l - 7; i < l; ++i){
        if(s[i] != k[i - l + 7]) break;
        if(i == l - 1) ans = 1;
    }

    for(i = 0; i < strlen(s); ++i){
        if(s[i] == k[i]) {
            l = i;
        }else break;
    }
    if((ret = strstr(&s[strlen(s) - l - 2], &k[i])) != NULL) ans = 1;
    if(ans) puts("YES");
    else puts("NO");
    return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main {
	static int a, b, c, d, e, k;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
        b = sc.nextInt();
        c = sc.nextInt();
        d = sc.nextInt();
        e = sc.nextInt();
        k = sc.nextInt();
        
        if(hoge()) {
        	System.out.println("Yay!");
        }else {
        	System.out.println(":(");
        }
	}
	
	static boolean hoge() {
		if(b - a > k) return false;
		else if(c - a > k) return false;
		else if(d - a > k) return false;
		else if(e - a > k) return false;
		else if(c - b > k) return false;
		else if(d - b > k) return false;
		else if(e - b > k) return false;
		else if(d - c > k) return false;
		else if(e - c > k) return false;
		else if(e - d > k) return false;
		return true;
	}
}


Measured memory_bytes: 21716
N, M = map(int, input().split())
lis_Number = [[] for i in range(N)]
for m in range(M):
    s, c = map(int, input().split())
    lis_Number[s-1].append(c)

lis_ans = [[] for i in range(N)]
condition_ok = True
for i in range(N):
    if len(list(set(lis_Number[i]))) == 0:
        if i == 0:
            lis_ans[i] = 1
        else :    
            lis_ans[i] = 0
    elif len(list(set(lis_Number[i]))) == 1:
        if (N != 1)&(i == 0) &(lis_Number[i][0]==0):
            condition_ok = False
        else :
            lis_ans[i] = lis_Number[i][0]
    else :
        condition_ok = False

if M == 0:
    if N == 3:
        ans = 100
    elif N == 2:
        ans = 10
    elif N == 1:
        ans = 0
else :
    if condition_ok:
        haha = ''
        for i in range(N):
            haha += str(lis_ans[i])
        ans = int(haha)
    else :
        ans = -1

print(ans)

Measured memory_bytes: 3064
n, m = map(int, input().split())
l_ = list(map(int, input().split()))
l = [(-1)*l_[i] for i in range(n)]

import heapq
heapq.heapify(l)

for i in range(m):
  x = (-1)*heapq.heappop(l)
  heapq.heappush(l, (x//2)*(-1))

print(sum(l)*(-1))

Measured memory_bytes: 14252
// VU TRUONG AN
#include <bits/stdc++.h>
#define FORX(i,x,y) for(int i = x; i <= y ; ++i)
#define FORN(i,x,y) for(int i = x; i >= y ; --i)
#define reset(x,y) memset(x,y,sizeof(x))
#define bp(i) (1 << i)
#define F first
#define S second
#define maxn 100001
#define MOD 1000000007
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define bit(p,x) ((x>>p) & 1)
#define Task "ATC"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<db> vdb;
typedef vector<str> vstr;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdb;

const int base = 100003;
const long long MM = 1ll*MOD*MOD;
const int maxc = 2e9;



void Solve(){
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    if(a >= k){
        cout << k;
    } else {
        k -= a;
        if(b >= k){
            cout << a;
        } else {
            k -= b;
            cout << a - min(k,c);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Solve();
}


Measured memory_bytes: 3544
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;

class Program {
    static void Main(string[] args) {
        var s = ReadLine();
        string res = "";

        for (int i = 0; i < s.Length; i++) {
            if (i % 2 == 0) {
                res += s[i];
            }
        }

        WriteLine(res);
    }
}



Measured memory_bytes: 34772
#include <iostream>
#include <deque>

using namespace std;

int n;
deque<int> q;

int main() {
    cin >> n;
    bool flag = false;

    for(int i = 0; i < n; i++) {
        int v;
        cin >> v;
        if(flag) {
            q.push_front(v);
        } else {
            q.push_back(v);
        }
        flag ^= 1;
    }

    if(n % 2 == 0) {
        for(int i = 0; i < n; i++) cout << q[i] << ' ';
    } else {
        for(int i = n - 1; i >= 0; i--) cout << q[i] << ' ';
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 2944
#include <iostream>
#include <cstdio>
#include <vector>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;

int N;
int A[100003];
int bck[100003];
int main() {
	fastio();
	cin >> N;
	for(int i = 0 ; i < N; i++) {
		cin >> A[i];
		A[i]--;
		bck[i] = A[i];
	}
	int ans = 0;
	for(int i = 0 ; i < N - 1; i++){
		if(A[i] == i) swap(A[i], A[i + 1]), ans++;
	}
	if(A[N - 1] == N - 1) ans++;
	
	cout << ans;
	return 0;
}

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

int main() {
    long long r, d, x[11];
    cin >> r >> d >> x[0];
    for(int i = 0; i < 10; i++) {
        x[i + 1] = r * x[i] - d;
        cout << setprecision(15) << x[i + 1] << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int dy[4]={ 1, 0,-1, 0};
int dx[4]={ 0, 1, 0,-1};

int main() {
  int H,W,Ch,Cw,Dh,Dw; cin>>H>>W>>Ch>>Cw>>Dh>>Dw; Ch--,Cw--,Dh--,Dw--;
  char S[H][W];
  int dist[H][W];
  for(int y=0;y<H;y++) for(int x=0;x<W;x++) cin>>S[y][x],dist[y][x]=0;
  
  queue<P> que,warpFrom;
  que.emplace(P(Ch,Cw));
  warpFrom.emplace(P(Ch,Cw));
  S[Ch][Cw]='x';
  
  while(!que.empty()){
    P p=que.front(); que.pop();
    int y=p.first,x=p.second;
    if(y==Dh&&x==Dw){cout<<dist[y][x]; return 0;}
    warpFrom.push(P(y,x));
    for(int i=0;i<4;i++){
      int ny=y+dy[i],nx=x+dx[i];
      if(ny<0||H<=ny||nx<0||W<=nx||S[ny][nx]!='.') continue;
      que.push(P(ny,nx));
      S[ny][nx]='x';
      dist[ny][nx]=dist[y][x];
    }

    if(que.empty()){
      while(!warpFrom.empty()){
        P p=warpFrom.front(); warpFrom.pop();
        int y=p.first,x=p.second;
        if(y==Dh&&x==Dw){cout<<dist[y][x]; return 0;}
        for(int wy=-2;wy<=2;wy++){
          for(int wx=-2;wx<=2;wx++){
            int ny=y+wy,nx=x+wx;
            if(ny<0||H<=ny||nx<0||W<=nx||S[ny][nx]!='.') continue;
            que.push(P(ny,nx));
            S[ny][nx]='x';
            dist[ny][nx]=dist[y][x]+1;
          }
        }
      }
    }
  }
  cout<<-1;
}

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

int main(){
  string s;
  cin >> s;
  int cnt1=0, cnt2=0, now=0;
  for(int i=0; i<s.length(); i++){
    if(s[i]!=now+'0')cnt1++;
    if(s[i]==now+'0')cnt2++;
    now=(now+1)%2;
  }
  cout << min(cnt1, cnt2);
  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>

using namespace std;

int main() {
	int st[3], ed[3], t[3];
	for (int i = 0; i < 3; ++i) {
		int h, m, s;
		cin >> h >> m >> s;
		st[i] = 60*60*h + 60*m + s;
		
		cin >> h >> m >> s;
		ed[i] = 60*60*h + 60*m + s;
	}

	for (int i = 0; i < 3; ++i) {
		t[i] = ed[i]-st[i];
		int h = t[i] /60 /60;
		int m = t[i] /60 %60;
		int s = t[i] %60;
		printf("%d %d %d\n", h, m, s);
	}

	return 0;
}

Measured memory_bytes: 1144
#include<bits/stdc++.h>
using namespace std;
int gcd1(int m,int n){
	if(m%n==0) return n;
	return gcd1(n,m%n);
}
int gcd(int a,int b,int c){
	return gcd1(gcd1(a,b),c);
}
int main(){
	int k,sum=0;
	scanf("%d",&k);
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			for(int x=1;x<=k;x++){
				sum+=gcd(i,j,x);
			}
		}
	}
	printf("%d",sum);
	return 0;
}

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

int main() {
	// your code goes here
	string a,b,c;
	int d,e;
	cin>>a>>b>>d>>e>>c;
	if(a==c) cout<<d-1<<" "<<e<<endl;
	else cout<<d<<" "<<e-1<<endl;
	return 0;
}


Measured memory_bytes: 256
function Main(input) {
  let s = input;
  let ans = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "1") {
      ans++;
    }
  }
  console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <functional>
#include <queue>

using namespace std;

#define int long long
#define rep(i,n) for(int i=0;i<(int)n;++i)

int X,Y,Z,K;

struct Data {
	int v, a, b, c;
	Data(int v, int a, int b, int c) : v(v), a(a), b(b), c(c) {}
	bool operator<(const Data &data) const {
		return v < data.v;
	}
	bool operator>(const Data &data) const {
		return v > data.v;
	}
};

map<int, bool> used;

int encode(int a, int b, int c)
{
	return a + b*1000ll + c*1000ll*1000ll;
}

signed main()
{
	cin >> X >> Y >> Z >> K;

	vector<int> A(X), B(Y), C(Z);
	rep(i, X) cin >> A[i];
	rep(i, Y) cin >> B[i];
	rep(i, Z) cin >> C[i];

	sort(begin(A), end(A), greater<int>());
	sort(begin(B), end(B), greater<int>());
	sort(begin(C), end(C), greater<int>());

	priority_queue<Data> pq;
	pq.push(Data(A[0]+B[0]+C[0],0,0,0));

	rep(_, K) {
		Data d(0,0,0,0);
		int v,a,b,c;

		do {
			d = pq.top();
			v = d.v, a = d.a, b = d.b, c = d.c;
			pq.pop();
		} while (used[encode(a,b,c)]);

		used[encode(a,b,c)] = true;

		cout << v << endl;

		if (a + 1 < X) pq.push(Data(A[a+1]+B[b]+C[c], a+1,b,c));
		if (b + 1 < Y) pq.push(Data(A[a]+B[b+1]+C[c], a,b+1,c));
		if (c + 1 < Z) pq.push(Data(A[a]+B[b]+C[c+1], a,b,c+1));
	}
}


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

int main(){
  string S;
  cin >> S;
  ll K;
  cin >> K;
  for(int i=0; i<S.size(); ++i){
    if(i==K){
      printf("1\n");
      return 0;
    }
    if(S[i]=='1') continue;
    printf("%c\n", S[i]);
    return 0;
  }
  printf("1\n");
  return 0;
}

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

using namespace std;
const int mod = 1e9+7;
int add(int a, int b) {
	return a + b < mod ? a + b : a + b - mod;
}
int mul(int a, int b) {
	return int(1LL * a * b % mod);
}
int fexp(int b, int e = mod - 2) {
	int ans = 1;
	while(e) {
		if(e & 1) ans = mul(ans, b);
		b = mul(b, b);
		e /= 2;
	}
	return ans;
}

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

	int ans = fexp(10, n);
	ans = add(ans, mod - fexp(9, n));
	ans = add(ans, mod - fexp(9, n));
	ans = add(ans, fexp(8, n));

	printf("%d\n", ans);
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int mod = 1e9 + 7;
map<ll, ll> mp;

ll work(ll x) {
	if(mp.count(x)) return mp[x];
	return mp[x] = ((work(x / 2) + work((x - 1) / 2)) % mod + work((x - 2) / 2)) % mod;
}

int main() {
	ll n;
	mp[0] = 1, mp[1] = 2;
	scanf("%lld", &n);
	printf("%lld\n", work(n));
	return 0;
}

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

int main() {
    int n, m;
    while (cin >> n >> m) {
        map<int,int> a;
        for (int i = 0; i < n; ++i) {
            int c; cin >> c;
            a[c]++;
        }
        for (int i = 0; i < m; ++i) {
            int c; cin >> c;
            a[c]++;
        }
        vector<int> And, Or;
        for (auto it : a) {
            if (it.second == 2) And.push_back(it.first);
            Or.push_back(it.first);
        }
        cout << And.size() << " " << Or.size() << endl;
        for (auto v : And) cout << v << endl;
        for (auto v : Or) cout << v << endl;
    }
}



Measured memory_bytes: 14072
import java.util.*;
 
public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		
        int N = sc.nextInt();
        String s = sc.next();
        char[] c = s.toCharArray();
        int blue = 0; int red = 0;

        for(int i = 0;i<N;i++){
      if(c[i] == 'R'){red++;}
      if(c[i] == 'B'){blue++;}
}
 if(red>blue){System.out.print("Yes");}
else{System.out.print("No");}
 

	}
}

Measured memory_bytes: 21844
import collections
n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]
S = collections.Counter(s)
T = collections.Counter(t)
c = 0
for i, j in S.items():
    c = max(j-T[i], c)
print(c)

Measured memory_bytes: 9404
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;
using i64 = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
const int INF = (1 << 30);
const i64 INFL = (1LL << 62);
const i64 MOD = 1000000007;
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;
}
template <class T>
i64 mod_pow(i64 a, i64 n, T mod) {
  mod = (i64)mod;
  i64 res = 1, p = a % mod;
  while (n) {
    if (n & 1) res = res * p % mod;
    p = p * p % mod;
    n >>= 1;
  }
  return res;
}
void print() { std::cout << std::endl; }
template <typename T, typename... A>
void print(const T& first, const A&... rest) {
  cout << sizeof...(rest) << endl;
  std::cout << first;
  if (sizeof...(rest)) std::cout << " ";
  print(rest...);
}
template <typename... A>
void print(const A&... rest) {
  print(rest...);
}
template <typename A>
void print(const std::vector<A>& v) {
  std::for_each(v.begin(), v.end(), [](A x) { std::cout << x << " "; });
  std::cout << std::endl;
}
int n, q;
string s;
char t[200200];
char d[200200];
int check_drop(int k) {
  rep(i, q) {
    if (t[i] != s[k]) continue;
    k += (d[i] == 'L' ? -1 : 1);
    if (k < 0) return -1;
    if (k >= n) return 1;
  }
  return 0;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> q;
  cin >> s;
  rep(i, q) { cin >> t[i] >> d[i]; }

  int h = n;
  int l = -1;
  while (abs(h - l) > 1) {
    int mid = (h + l) / 2;
    if (check_drop(mid) == -1) {
      l = mid;
    } else {
      h = mid;
    }
  }
  int left = h;
  h = n;
  l = -1;
  while (abs(h - l) > 1) {
    int mid = (h + l) / 2;
    if (check_drop(mid) == 1) {
      h = mid;
    } else {
      l = mid;
    }
  }
  int right = n - 1 - l;
  cout << n - (left + right) << endl;
  return 0;
}

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

int main() {
  int N;
  cin>>N; 
 vector<int> v(N);
  for(int i=0;i<N;++i){
    cin>>v[i];
  }
  sort(v.begin(),v.end());
  int answer=v[v.size()/2]-v[v.size()/2-1];
  cout<<answer<<endl;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        var LR = ReadLine().Split().Select(long.Parse).ToArray();
        var L = LR[0];
        var R = LR[1];
        var ans = 2019L;
        for (var i = L; i < L + 2019; i++)
        {
            for (var j = i+1; j < L + 2019; j++)
            {
                if (i <= R && j <= R) ans = Min(ans, i * j % 2019);
            }
        }
        WriteLine(ans);
    }
}


Measured memory_bytes: 13396
def inpl(): return list(map(int, input().split()))
n,m,x,y = inpl()
xs = inpl()
ys = inpl()

for z in range(-100,101):
    if max(xs)<z and z<=min(ys) and x<z and z<=y:
        print('No War')
        break
else:
    print('War')

Measured memory_bytes: 3064
#include<iostream>

int main(){
    int N;
    std::cin >> N;
    int ans = 0, max = 0;
    for(int i=0; i<N; ++i){
        int p;
        std::cin >> p;
        if(p > max) max = p;
        ans += p;
    }
    ans -= max / 2;
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>
#include <cstring>
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>

using namespace std;

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

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

    // sort
    sort(a.begin(), a.end());
    int thres_point_1 = a[ n / 2  -1];
    int thres_point_2 = a[ n / 2];
    
    cout << thres_point_2 - thres_point_1 << endl;

    return 0;
}

Measured memory_bytes: 640
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
## libs ##
from itertools import accumulate as acc
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#

def main():
    a,b,c = MII()
    if a+b>=c: print('Yes')
    else: print('No')


if __name__ == '__main__':
    main()

Measured memory_bytes: 3444
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 先頭から連続n枚 合計 と 残りカード合計 での比較 !!
int main(int argc , char **argv)
{
	(void)argc;
	(void)argv;

	vector<int64_t> v;
	int N;
	cin >> N;
	for(int i=0;i<N;i++){
		int64_t a;
		cin >> a;
		v.push_back(a);
	}

	int64_t Sum = 0;
	for(int i=0,iMax=v.size();i<iMax;i++){ Sum += v[i]; }

	int64_t min_Ans = LLONG_MAX;
	int64_t A_sum = 0;
	for(int i=0,iMax=v.size()-1;i<iMax;i++){
		A_sum += v[i];
		int64_t b = Sum-A_sum;
		int64_t ans = abs(A_sum - b);
//		printf("A:%ld , B:%ld , ans:%ld\n",A_sum,b,ans);
		if ( ans < min_Ans ) { min_Ans = ans;}
	}
	printf("%ld\n",min_Ans);

	return 0;
}

Measured memory_bytes: 2420
#include<stdio.h>
int main(void)
{
	int L,a,b,c,d,i;
	scanf("%d%d%d%d%d",&L,&a,&b,&c,&d);
	for(i=1;;i++){
	    a=a-c;
	    b=b-d;
	    if(a<c && b<d){
	        break;
	    }
	}
	L=L-i;
	if(a!=0 && b!=0){
	    L=L-1;
	}
	printf("%d\n",L);
	return 0;
}


Measured memory_bytes: 2140
import sys

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))

A.sort()

acum = 0
ans = 0
for i in range(N-1):
    acum += A[i]
    if acum * 2 >= A[i+1]:
        ans += 1
    else:
        ans = 0

print(ans+1)

Measured memory_bytes: 63856
#include <stdio.h>
#include <math.h>

typedef struct{
  double x;
  double y;
}Point;

void koch(int, Point, Point);
int main(){
  int n;
  Point p1,p2;
  scanf("%d",&n);

  p1.x = 0.0;
  p1.y = 0.0;
  p2.x = 100.0;
  p2.y = 0.0;
  
  printf("%f %f\n",p1.x ,p1.y);
  koch(n,p1,p2);
  printf("%f %f\n",p2.x ,p2.y);
  
  return 0;
}

void koch(int n, Point p1, Point p2){
  Point s,u,t;
  double deg = 60;
  double rad = deg * M_PI / 180.0;
  if(n == 0) return;
  
  s.x = (2*p1.x+1*p2.x)/3.0;
  s.y = (2*p1.y+1*p2.y)/3.0;
  t.x = (1*p1.x+2*p2.x)/3.0;
  t.y = (1*p1.y+2*p2.y)/3.0;
  u.x = (t.x-s.x) * cos(rad) - (t.y-s.y) * sin(rad) + s.x;
  u.y = (t.x-s.x) * sin(rad) + (t.y-s.y) * cos(rad) + s.y;

  koch(n-1, p1, s);
  printf("%f %f\n",s.x ,s.y);
  koch(n-1, s, u);
  printf("%f %f\n",u.x, u.y);
  koch(n-1, u, t);
  printf("%f %f\n",t.x, t.y);
  koch(n-1, t, p2);
}

Measured memory_bytes: 636
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func solve() {
	n := getInt()
	numOdd := 0
	for i := 0; i < n; i++ {
		a := getInt()
		if a%2 == 1 {
			numOdd++
		}
	}

	ans := "YES"
	if numOdd%2 == 1 {
		ans = "NO"
	}
	fmt.Fprintln(wr, ans)
}

// -----------------------------------------

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


Measured memory_bytes: 2176
/******************************************
*    AUTHOR:         julianferres         *
******************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
#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 esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl
const int INF = 2000000000;
#define MOD 1000000007
const int N = 305;

double dp[N][N][N];
int n;

double fill(int a,int b, int c){
	// DBG(a);
	// DBG(b);
	// DBG(c);
	if (dp[a][b][c] > -0.5)
		return dp[a][b][c];
	// DBG(a);
	// DBG(b);
	// DBG(c);

	int z = n-(a+b+c);
	int nz = (a+b+c);
	double aux1=0,aux2=0,aux3=0;

	if(a)
		aux1 = (double) a/(a+b+c)*fill(a-1, b, c);
	if(b)
		aux2 = (double) b/(a+b+c)*fill(a+1, b-1, c);
	if(c)
		aux3 = (double) c/(a+b+c)*fill(a, b+1, c-1);

	double ans = (double) nz/n*(aux1+aux2+aux3+1) + (double)z/n;
	ans *= (double)n/nz;
	return dp[a][b][c] = ans;
}


int main(){
    FIN;
    cin >> n;
    vi a(n);
    int c[4] = {0,0,0,0};
    forn(i,n){
    	int x; cin >> x;
    	++c[x];
    }
	forn(i, N) forn(j, N) forn(k, N) dp[i][j][k] = -1;
	dp[0][0][0] = 0;

	fill(c[1],c[2],c[3]);
	// DBG(dp[0][0][0]);
	// DBG(dp[1][0][0]);
	// DBG(dp[2][0][0]);
	// DBG(dp[3][0][0]);
	cout << fixed << setprecision(15) << dp[c[1]][c[2]][c[3]] << endl;

	return 0;
}



Measured memory_bytes: 221952
import java.util.*;
import java.util.Map.Entry;
 
class Main {
	 static int mod =  (int) (Math.pow(10,9)+7);
   	 static List<ArrayList<Integer>> list= new ArrayList<ArrayList<Integer>>();
//	 static int mod = 998244353;
	 public static void main(String[] args) {
	        Scanner sc = new Scanner(System.in);
	        int K = sc.nextInt();
	        int i=0;
			LinkedList<Long> queue = new LinkedList<Long>();
			queue.add(1l);
			queue.add(2l);
			queue.add(3l);
			queue.add(4l);
			queue.add(5l);
			queue.add(6l);
			queue.add(7l);
			queue.add(8l);
			queue.add(9l);
	        while(i<K-1) {
	        	long node = queue.poll();
	        	i++;
	        	if(node%10==0) {
	        		queue.add(node*10);
	        		queue.add(node*10+1);
	        	} else if(node%10==9) {
	        		queue.add(node*10+8);
	        		queue.add(node*10+9);	        		
	        	} else {
	        		queue.add(node*10+(node%10)-1);
	        		queue.add(node*10+(node%10));
	        		queue.add(node*10+(node%10)+1);
	        	}
	        }
        	long ans = queue.poll();
	        		
	        System.out.println(ans);
	        	        	        
	 }
}

Measured memory_bytes: 36308
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
#define int long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dup(x,y) (((x)+(y)-1)/(y))
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const long double PI = (acos(-1));

struct edge { int to, cost; };

vector<vector<edge>>tree;
vector<int>ans;
void dfs(int v, int clr, int p = -1) {
	rep(i, tree[v].size()) {
		int u = tree[v][i].to;
		if (u == p)continue;
		int nclr;
		if (tree[v][i].cost == 0)nclr = clr;
		else nclr = 1 - clr;
		ans[u] = nclr;
		dfs(u, ans[u], v);
	}
}

signed main() {
	int N;
	cin >> N;
	tree.resize(N);
	ans.resize(N);
	ans[0] = 0;
	rep(i, N - 1) {
		int u, v, w;
		cin >> u >> v >> w;
		u--; v--;
		w %= 2;
		tree[u].push_back({ v,w });
		tree[v].push_back({ u,w });
	}
	dfs(0, 0);
	rep(i, N)cout << ans[i] << endl;
}

Measured memory_bytes: 14196
import java.util.*;

public class Main {
	static final long MOD = 1000000007;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int X = sc.nextInt();
		
		Integer[] S = new Integer[N];
		for(int i=0; i<N; i++)
			S[i] = sc.nextInt();
		Arrays.sort(S, Comparator.reverseOrder());
		
		long[] rev = new long[N+1];
		for(int i=1; i<=N; i++)
			rev[i] = rev(i);
		
		int MAX=Math.max(X, S[0]);
		long[][] dp = new long[N+1][MAX+1];
		dp[0][X]=1;
		for(int i=0; i<N; i++) {
			for(int j=0; j<=MAX; j++) {
				if(dp[i][j]>0) {
					dp[i+1][j%S[i]] += dp[i][j]*rev[N-i];
					dp[i+1][j%S[i]] %= MOD;
					
					dp[i+1][j] += ((dp[i][j]*(N-i-1))%MOD)*rev[N-i];
					dp[i+1][j] %= MOD;
				}
			}
		}
		
		long sum = 0;
		for(int i=0; i<=MAX; i++) {
			sum = (sum + dp[N][i]*i)%MOD;
		}
		for(int i=1; i<=N; i++) {
			sum = (sum*i)%MOD;
		}
		System.out.println(sum);
		sc.close();
	}
	
	static long rev(long a) {
		return pow(a, MOD-2);
	}
	
	static long pow(long a, long b) {
		long ans = 1;
		while(b>0) {
			if((b&1)!=0)
				ans = (ans * a)%MOD;
			b>>=1;
			a = (a*a)%MOD;
		}
		return ans;
	}

}


Measured memory_bytes: 240976
#include<iostream>
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define niv vector<int>
#define LL long long
#define IT iterator
#define PB(a) push_back(a)
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
int  n;
int res[505][505];
void dfs(int start,int to,int index){
	if(to-start+1<=1) return;
	for(int i=start;i<to;i++)
		for(int j=i+1;j<=to;j++) {res[i][j]=index;
		}
	int mid=(start+to)>>1;
	dfs(start,mid,index+1),dfs(mid+1,to,index+1);
}
int main(){
	cin>>n;
	dfs(1,n,1);
 
	for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
	cout<<res[i][j]<<" "<<endl;
}

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

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

using namespace std;

int n;
int x[100000];
int l, q;
int a[100000];
int b[100000];
int dbl[100000][18];
int rdbl[100000][18];

int main(){
	cin >> n;
	rep(i, n){
		cin >> x[i];
	}
	cin >> l >> q;
	rep(i, q){
		cin >> a[i] >> b[i];
		--a[i];
		--b[i];
	}

	rep(i, n){
		dbl[i][0] = upper_bound(x, x + n, x[i] + l) - x - 1;
		rdbl[i][0] = lower_bound(x, x + n, x[i] - l) - x;
	}
	rep(j, 17){
		rep(i, n){
			dbl[i][j + 1] = dbl[dbl[i][j]][j];
			rdbl[i][j + 1] = rdbl[rdbl[i][j]][j];
		}
	}

	rep(i, q){
		if(a[i] < b[i]){
			int s = 0;
			for(int j = 17; j >= 0; --j){
				if(dbl[a[i]][j] < b[i]){
					a[i] = dbl[a[i]][j];
					s += 1 << j;
				}
			}
			cout << s + 1 << endl;
		}
		else{
			int s = 0;
			for(int j = 17; j >= 0; --j){
				if(rdbl[a[i]][j] > b[i]){
					a[i] = rdbl[a[i]][j];
					s += 1 << j;
				}
			}
			cout << s + 1 << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 16000
#define errOut(s) \
  { std::cerr << __LINE__ << ":" << #s << ":" << (s) << std::endl; }

#include <bits/stdc++.h>
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Weverything"
//#include <boost/multi_array.hpp>
//#include <boost/optional.hpp>
//#include <boost/range/adaptors.hpp>
//#include <boost/range/algorithm.hpp>
//#include <boost/range/irange.hpp>
#pragma clang diagnostic pop

using namespace std;

int64_t solve(std::string s, std::string t) {
  int64_t  ret = 0;
  int const n = s.length();
  for (int i = 0; i < n; ++i) {
    if (s[i] != t[i]) {
      ret ++;
    }
  }
  return ret;
}

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  std::string s;
  std::cin >> s;
  std::string t;
  std::cin >> t;
  auto const res = solve(s, t);
  std::cout << res << std::endl;
  return 0;
}


Measured memory_bytes: 4076
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

const int mod = 998244353;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if(!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }
mint fact(int n) {
  if(n == 1 || n == 0) return 1;
  mint res = n;
  return res * fact(n - 1);
}

struct UnionFind {
  vector<int> d;
  UnionFind(int n) : d(n, -1) {}
  int root(int x) {
    if(d[x] < 0) return x;
    return d[x] = root(d[x]);
  }
  bool unite(int x, int y) {
    x = root(x);
    y = root(y);
    if(x == y) return false;
    if(d[x] > d[y]) swap(x, y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return root(x) == root(y); }
  int size(int x) { return -d[root(x)]; }
};

int main() {
  ll n;
  cin >> n;
  vector<P> p(n);
  rep(i, n) cin >> p[i].first >> p[i].second;
  sort(all(p));
  UnionFind uf(n);
  vl num(n, 0);
  for(int i = n - 1; i >= 0; i--) {
    ll x = p[i].first, d = p[i].second;
    ll l = -1, r = n;
    while(l + 1 < r) {
      ll now = (l + r) / 2;
      if(p[now].first < x + d)
        l = now;
      else
        r = now;
    }
    rep2(j, i + 1, l + 1) {
      int nj = j + uf.size(j) - 1;
      uf.unite(i, j);
      j = nj;
    }
    num[n - i - 1] = uf.size(i) - 1;
  }
  vector<mint> dp(n + 1, 0);
  dp[0] = 1;
  rep(i, n) dp[i + 1] = dp[i] + dp[i - num[i]];
  cout << dp[n] << endl;
}

Measured memory_bytes: 7296
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,b,c,sum=0,total=0;
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j>0;)
        {
            c=j%10;
            sum=sum+c;
            j=j/10;

        }
        if(sum>=a&& sum<=b) total=total+i;
        sum=0;
   }
   cout<<total<<endl;
    return 0;
}


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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int N;
  cin >> N;
  string s;
  cin >> s;
  set<int> sR, sG, sB;

  rep(i, s.length()){
    if(s[i]=='R'){
      sR.insert(i);
    }else if(s[i] == 'G'){
      sG.insert(i);
    }else{
      sB.insert(i);
    }
  }


  ll ans = 0;
  for(auto i : sR){

    for(auto j : sG){

      int a, b;
      a = i;
      b = j;
      if(a > b){
        swap(a, b);
      }

      int dec = 0;
      if(2*a-b>=0){
        if(sB.find(2*a-b) != sB.end()){
          dec++;
        }
      }

      if(2*b-a<N){
        if(sB.find(2*b-a) != sB.end()){
          dec++;
        }
      }

      if((b-a)%2==0){
        if(sB.find(a+(b-a)/2) != sB.end()){
          dec++;
        }
      }
       
      ans += sB.size() - dec;

    }
  }

  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 3744