akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

ll dp[110][100100];

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

    vector<ll> w(N);
    vector<int> v(N);
    
    rep(i,N) cin >> w[i] >> v[i];
    int V = 0;
    rep(i,N) V += v[i];
    rep(i,N+1)rep(j,V+1) dp[i][j] = LINF;

    dp[0][0] = 0;
    rep(i,N) {
        for (int j = 0; j<=V; ++j) {
            dp[i+1][j] = dp[i][j];
            if (j-v[i]>=0) dp[i+1][j] = min(dp[i+1][j],dp[i][j-v[i]]+w[i]);
        }
    }
    int ans = 0;
    for (int j = 0; j<=V; ++j) {
        if (dp[N][j]<=W) ans = max(ans,j);
    }
    cout << ans << endl;
    return 0;
}


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

vector<vector<int>> G(1e5+1, vector<int>(0));
vector<int> path (1e5+1, -1);

int dfs(int v){
    if (path[v]!=-1) return path[v];
    else{
       path[v] = 0;
       for (auto i:G[v]){
          path[v] = max(path[v], dfs(i)+1); 
       }
    } 
    return path[v];
}

int main(){
    int n, m; cin >> n >> m;
    for (int i=1; i<=m; i++){
        int a, b; cin >> a >> b;
        G[a].push_back(b);
    }    

    int max_path = 0;
    for (int i=1; i<=n; i++){
        if (path[i]==-1){
            max_path = max(max_path, dfs(i));
        }
    }
    cout << max_path << endl;
    
    return 0;
}

Measured memory_bytes: 11108
#include <stdio.h>
#include <map>
#include <math.h>
#include <vector>

#define INF 100000000

using namespace std;
char tmp[10000], res[3];
int main(){
  for(int i=0; i< 3; i++){
    scanf("%s", tmp);
    res[i] = toupper(tmp[0]);
  }
  printf("%s\n", res);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, z, n) for(int i = z; i < n; i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
//const int INF = 1<<29;
//const int MODINF = 1000000007;
using namespace std;

int main(){
    
    string S;
    cin >> S;
    int64_t L = S.size();
    int64_t ans = 0;
    for (int64_t tmp = 0; tmp < (1 << L - 1); tmp++){
        bitset<9> s(tmp);
        int64_t start = 0;
        rep(i, 0, L - 1){
            if(s.test(i)){
                ans += stoll(S.substr(start, i - start + 1));
                start = i + 1;
            }
        }
        ans += stoll(S.substr(start, L - start));
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <queue>
using std::queue;

const int N = 500 + 10;

int n;
char s[N][20];
int g[255][255];
int deg[255];
queue<int> Q;

bool topsort()
{
	while(!Q.empty()) Q.pop();
	for(int i = 0; i < 255; i++) if(deg[i] == 0) Q.push(i);
	int cnt = 0;
	while(!Q.empty())
	{
		int x = Q.front(); Q.pop(); cnt++;
		for(int i = 0; i < 255; i++)
			if(g[x][i] == 1)
			{
				deg[i]--;
				if(deg[i] == 0) Q.push(i);
			}
	}
	//printf("cnt = %d\n", cnt);
	return cnt == 255;
}

bool solve()
{
	memset(g, 0, sizeof(g));
	memset(deg, 0, sizeof(deg));
	for(int i = 2; i <= n; i++)
	{
		for(int j = 0; s[i][j] || s[i-1][j]; j++)
		{
			if(s[i][j] == s[i-1][j]) continue;
			if(!s[i][j]) return 0;
			char lesser = s[i-1][j], larger = s[i][j];
			if(g[larger][lesser] == 1) return 0;
			if(g[lesser][larger] == 0)
			{
				g[lesser][larger] = 1;
				deg[larger]++;
			}
			break;
		}
	}
	return topsort();
}

int main()
{
	while(scanf("%d", &n) == 1 && n)
	{
		memset(s, 0, sizeof(s));
		for(int i = 1; i <= n; i++) scanf("%s", s[i]);
		if(solve()) puts("yes"); else puts("no");
	}
	return 0;
}

Measured memory_bytes: 1308
using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            String x = Console.ReadLine();
            //???????????????????????£??\
            String[] array = x.Split(' ');

            //??°???????????´????????£??\
            int a = int.Parse(array[0]);
            int b = int.Parse(array[1]);
            int c = int.Parse(array[2]);

            //??????????????¨???
            if (a < b && b < c)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }

        }
    }
}

Measured memory_bytes: 8836
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

struct edge{
    ll u,v,w;
    edge(){};
    edge(ll u,ll v ,ll w):u(u),v(v),w(w){}
};

vector<vector<edge>> G;
vector<int> color;

void rec(ll n,ll len,ll pre){
    if(len%2 == 0) color[n] = 0;
    for(auto e:G[n]){
        if(e.v == pre) continue;
        rec(e.v,len+e.w,n);
    }
}
template<class Type>
Type solve(Type res = Type()){
    ll N; cin >> N;
    G.resize(N);
    color.resize(N);
    fill(color.begin(),color.end(),1);
    
    for(int i = 0; i < N-1;i++){
        ll u,v,w; cin >> u >> v >> w;
        u--; v--;
        G[u].emplace_back(u,v,w);
        G[v].emplace_back(v,u,w);
    }
    rec(0,0,-1);
    
    for(int i = 0; i < N;i++){
        cout << color[i] << endl;
    }
    
    
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    solve(0);
    //cout << fixed << setprecision(15) << solve<ll>() << endl;
    return 0;
}


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

int main() {
  string s, t;
  cin >> s;
  int n = s.size();
  // s.push_back('-');
  for (int i = 0; i < n; i++)
    if (s[i] == 'B' && s[i + 1] == 'C')
      t.push_back('D'), i++;
    else
      t.push_back(s[i]);

  ll ans = 0, add = 0;
  for (int i = 0; i < t.size(); i++) {
    if (t[i] == 'A')
      add++;
    else if (t[i] == 'D')
      ans += add;
    else
      add = 0;
  }
  cout << ans << endl;
}


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

int main() {
  int N, M;
  cin >> N >> M;
  vector<ll> X(M);
  rep(i, 0, M) cin >> X[i];
  sort(X.begin(), X.end());
  vector<ll> D(M-1);
  rep(i, 0, M-1) D[i] = X[i+1] - X[i];
  sort(D.begin(), D.end());
  ll ans = 0;
  rep(i, 0, M - N) {
    ans += D[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll int arr[100] , h;
int main()
{
    int i = 0;
    cin >> h;

    while(h > 1)
    {
        arr[i++] = h / 2;
        h /= 2;
    }
    arr[i++] = 1;
    ll k = pow(2 , i) - 1;
    cout << k << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int e = 1e5+ 69;
const int mod = 1e9 + 7;

ll a[e], b[e], tt[e];
ll dp[e][15];

int main()
{
    string s;
    cin >> s;
    ll n = s.size();
    dp[0][0] = 1;
    for(int i=0; i<n; i++)
    {
        ll cur;
        if(s[i] == '?') cur = -1;
        else cur = s[i] - '0';
        for(int j=0; j<10; j++)
        {
            if(cur != -1 && cur != j) continue;
            for(ll md=0; md<=12; md++)
            {
                dp[i+1][(md*10 + j)%13] += dp[i][md];
            }
        }
        for(int md=0; md<=12; md++)
        {
            dp[i+1][md] %= mod;
        }
    }
    cout << dp[n][5];
}


Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}
template<typename T>vector<T> & cset(vector<T> &A,T e=T()){for(auto &I:A){I=e;} return A;}

namespace str{
    vector<ll> Manacher(const string &s){
        vector<ll> ret(s.size(),0);
        int j=0;
        for(int i=0;i<s.size();){
            while(i>=j && i+j<s.size() && s[i-j]==s[i+j]){j++;}
            ret[i]=j;
            int k=1;
            while(k<j && ret[i-k]+k<j){ret[i+k]=ret[i-k]; k++;}
            i+=k; j-=k;
        }
        return ret;
    }
    
    vector<ll> Z_Algorithm(const string &s){
        vector<ll> ret(s.size(),0);
        ret[0]=s.size();
        int j=0;
        for(int i=1;i<s.size();){
            while(i+j<s.size() && s[j]==s[i+j]){j++;}
            ret[i]=j;
            if(j==0){i++; continue;}
            int k=1;
            while(k+ret[k]<j){ret[i+k]=ret[k]; k++;}
            i+=k; j-=k;
        }
        return ret;
    }
    
    //1-indexed
    vector<ll> MP(const string &s){
        vector<ll> ret(s.size()+1,-1);
        ll j=-1;
        for(int i=0;i<s.size();i++){
            while(j>=0 && s[i]!=s[j]){j=ret[j];}
            j++;
            ret[i+1]=j;
        }
        return ret;
    }
};

using namespace str;


int main(){
  string s,t;
  cin>>s>>t;
  while(s.size()<t.size()){string bk=s;  s+=bk;}
  ll n=s.size();
  string r=t+s+s;
  auto A=Z_Algorithm(r);
  ll st=t.size();
  vector<int> used(r.size(),0);
  vector<int> vis(r.size(),-1);
  ll w;
  for(int i=st;i<st+n;i++){
    if(used[i]){continue;}
    w=i;
    ll cnt=1;
    vector<ll> P;
    while(!used[w]){
      if(A[w]<(ll)t.size()){break;}
      P.push_back(w);
      w=w%n+t.size();
      if(vis[w]==i){cout<<-1<<endl; return 0;}
      vis[w]=i;
    }
    cnt=used[w];
    while(!P.empty()){
      cnt++;
      used[P.back()]=cnt;
      P.pop_back();
    }
  }
  ll mx=0;
  for(auto &I:used){mx=max<ll>(mx,I);}
  cout<<mx<<endl;
  

  return 0;
}


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

int main() {

  int A,B;
  cin >> A >> B;
  if (A == B){
  cout << 2*A << endl;
  }
  else if (A<B){
  cout << 2*B-1 << endl;
  }
  else{
  cout << 2*A-1 << endl;
  }
}


Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve():
    A, B = input().split()

    A = int(A)
    B = B.replace(".", "")
    B = int(B)
    print((A * B) // 100)


def main():
    solve()


if __name__ == '__main__':
    main()


Measured memory_bytes: 9940
# coding: utf-8
# Your code here!


n, m = map(int, input().split())
A = [[0 for j in range(m)] for i in range(n)]

for i in range(n):
   A[i] = list(map(int, input().split()))

S = [0 for j in range(m)]
c = 0
for i in range(n):
   for j in range(m):
      print(A[i][j], end = "")
      print(" ", end = "")
   print(sum(A[i]))
   c += sum(A[i])

for j in range(m):
   sum = 0
   for i in range(n):
      sum += A[i][j]
   print(sum, end = "")
   print(" ", end = "")
print(c)
   
   
      


Measured memory_bytes: 6748
#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

short checkTable[1001][1001];

int tmp_max=0;


void calc(int index,char pattern[],char to_search[],int to_search_length){

	for(int i=to_search_length-1;i>=0;i--){
		if(to_search[i]==pattern[index]){
			checkTable[index][i]=1;
			if(pattern[index+1]!='\0' && i < to_search_length-1){
				checkTable[index][i] = checkTable[index+1][i+1] + checkTable[index][i];
			}
		}else{
			if(i != to_search_length-1){
				if(pattern[index+1] != '\0'){
					checkTable[index][i]=(checkTable[index+1][i]>checkTable[index][i+1])
							?checkTable[index+1][i]:checkTable[index][i+1];

				}else{
					checkTable[index][i]=(checkTable[index][i+1]>0)?checkTable[index][i+1]:0;
				}
			}else{
				if(pattern[index+1] != '\0'){
					checkTable[index][i]=(checkTable[index+1][i]>0)?checkTable[index+1][i]:0;
				}else{
					checkTable[index][i] = 0;
				}
			}
		}
		tmp_max = (tmp_max >= checkTable[index][i])?tmp_max:checkTable[index][i];
	}
}

int main(){

	int q,left_length,right_length;
	char left[1001],right[1001];

	scanf("%d",&q);

	for(int i=0;i<q;i++){
		left_length=0;
		right_length=0;
		scanf("%s %s",left,right);
		for(int k=0;left[k]!='\0';k++)left_length++;
		for(int k=0;right[k]!='\0';k++)right_length++;

		if(right_length>=left_length){

			for(int k=left_length-1;k>=0;k--)calc(k,left,right,right_length);
		}else{

			for(int k=right_length-1;k>=0;k--)calc(k,right,left,left_length);
		}
		printf("%d\n",tmp_max);
		tmp_max=0;
	}

    return 0;
}



Measured memory_bytes: 5172
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = []
    l = [0]*(n + 1)
    now = 0

    for i in range(n):
        a.append(int(input()) - 1)

    for i in range(n):
        now = a[now]
        if now == 1:
            print(i + 1)
            exit()
    print(-1)

main()

Measured memory_bytes: 7852
using System.IO;
using System.Linq;
using System.Collections.Generic;
using static System.Math;
using static System.Console;
class Z { static void Main() => new K(); }
class K
{
	int[] G => Strs.Select(int.Parse).ToArray();
	string[] Strs => ReadLine().Split();
	long MaxSum(List<long> a) => a.Where(i => i >= 0).Sum();
	bool Good(List<long> a) => a.Any(i => i >= 0);
	readonly List<int> del = new List<int>();
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		WriteLine(Solve());
		WriteLine(del.Count);
		foreach (var x in del) WriteLine(x + 1);
		Out.Flush();
	}
	long Solve()
	{
		var N = G[0];
		var a = G;
		var ev = new List<long>(N / 2);
		var od = new List<long>(N / 2);
		for (var i = 0; i < N; i++) if (i % 2 == 0) ev.Add(a[i]); else od.Add(a[i]);
		bool gev = Good(ev), god = Good(od);
		if (!gev && !god)
		{
			var m = a.Max(); int i = 0, j = N;
			while (a[i] != m) { i++; j--; }
			for (var k = 0; k < i; k++) del.Add(0);
			while (j > 1) del.Add(--j);
			return m;
		}
		long mev = MaxSum(ev), mod = MaxSum(od);
		var l = new LinkedList<bool>();
		if (mev >= mod && gev) for (var i = 0; i < N; i++) l.AddLast(i % 2 == 0 && ev[i / 2] >= 0);
		else for (var i = 0; i < N; i++) l.AddLast(i % 2 == 1 && od[i / 2] >= 0);
		while (l.Count > 2)
		{
			var n = l.First;
			if (!n.Value) { del.Add(0); l.RemoveFirst(); }
			else if (!l.Last.Value) { del.Add(l.Count - 1); l.RemoveLast(); }
			else if (n.Next.Next.Value) { del.Add(1); l.RemoveFirst(); l.RemoveFirst(); }
			else { del.Add(2); l.Remove(n.Next); l.Remove(n.Next); }
		}
		if (l.Count > 1) del.Add(l.First.Value ? 1 : 0);
		return Max(mev, mod);
	}
}


Measured memory_bytes: 13684
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<deque>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define ll __int64
//#define __int64 long long
#define P pair<ll,ll>
string s;
 

 
int main(){
	cin>>s;
	int mo=s.size()%2;
	bool f;
	if(s[0]==s[s.size()-1]){//奇数長
		if(mo)f=1;
		else f=0;
	}
	else{
		if(mo)f=0;
		else f=1;
	}
	if(f)cout<<"Second"<<endl;
	else cout<<"First"<<endl;
return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;

int main(){
    int a,b,c;
    while(scanf("%d%d%d",&a,&b,&c)!=EOF){
        int k=a-b;
        printf("%d\n",k%c);
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int n = sc.nextInt();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }
        int max = h[0];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (max <= h[i]) {
                cnt++;
            }
            max = Math.max(max, h[i]);
        }
        System.out.println(cnt);
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }
    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }
    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
        return hasNextByte();
    }
    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 21204
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    color = [-1] * N
    color[0] = 0
    uvw = []
    edge = [[]for _ in range(N)]
    # append=uvw.append
    for i in range(N-1):
        ui, vi, wi = map(int, input().split())
        ui -= 1
        vi -= 1
        edge[ui].append((vi, wi))
        edge[vi].append((ui, wi))
    stack = [0]
    for i in range(N):
        tmp = deque()
        while stack:
            i = stack.pop()
            for e, w in edge[i]:
                if color[e] == -1:
                    stack.append(e)
                    if color[i] == 0:
                        if w % 2 == 0:
                            color[e] = 0
                        else:
                            color[e] = 1
                    else:
                        if w % 2 == 0:
                            color[e] = 1
                        else:
                            color[e] = 0
                # ここを追加--------------------------------------
                # 矛盾判定
                else:
                    if (color[i] == color[e]) != (w % 2 == 0):
                        print(-1)
                        exit()
                # ^^^^^^^^--------------------------------------
        # print(color)
        stack = tmp
    print(*color, sep="\n")


if __name__ == '__main__':
    main()


Measured memory_bytes: 67600
import java.util.Scanner;

public class Main{
	static int ans = 0;
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		//int n=sc.nextInt();
		String s=sc.next();
		String put="";
		if(s.equals("A"))put="T";
		if(s.equals("C"))put="G";
			if(s.equals("G"))put="C";
			if(s.equals("T"))put="A";
		//for(int i=0;i<n;i++)

		System.out.println(put);
	}
}


Measured memory_bytes: 23124
import java.util.*;

class Main {
    public static void main(String[] args) {
        new Solver().run();
    }
}

class Solver {

    public void run() {
        Scanner sc = new Scanner(System.in);
        char[] S = sc.next().toCharArray();
        char[] T = sc.next().toCharArray();

        int cnt = 0;
        for (int i = 0; i < 3; i++) {
            char ch = S[i];
            if (ch == T[i]) {
                cnt++;
            }
        }

        System.out.println(cnt);
        return;
    }

}

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

int main() {
  string S;
  cin >> S;
  int n = S.size();
  int ans = 0;
  for (int i = 1; i < n; i++) {
    if (S[i] == '1' && S[i-1] == '1') {
      S[i] = '0';
      ans++;
    }
    if (S[i] == '0' && S[i-1] == '0') {
      S[i] = '1';
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3768
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <vector>
#define ALL(a) (a).begin(), (a).end()
using namespace  std;
using ll = long long;
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
struct sushi{
    ll val;
    ll kind;
    sushi(ll v, ll k): val(v), kind(k){}
};
bool operator< (const sushi &x, const sushi &y){
    if(x.kind != y.kind) return x.kind < y.kind;
    else return x.val < y.val;
}
bool operator> (const sushi &x, const sushi &y){
    if(x.kind != y.kind) return x.kind > y.kind;
    else return x.val > y.val;
}
ostream& operator<< (ostream& s, sushi x){
    s<<"<" << x.val << ", " << x.kind << ">";
    return s;
}
signed main(){
    ll N, K;
    cin>>N>>K;
    vector<vector<sushi>> A(N+1, vector<sushi>());
    vector<sushi> B;
    for(int i=0; i<N; i++){
        ll t, d; cin>>t>>d;
        A[t].emplace_back(sushi(d, 0));
    }
    for(int i=0; i<=N; i++){
        if(A[i].empty()) continue;
        sort(ALL(A[i]), [&](sushi x, sushi y){return x.val>y.val;});
        A[i][0].kind= 1;
        for(auto &s: A[i]) B.emplace_back(s);
    }
    sort(ALL(B), [&](sushi x, sushi y)->bool{return x.val>y.val;});
    priority_queue<sushi, vector<sushi>, greater<sushi>> pq;
    priority_queue<sushi, vector<sushi>, less<sushi>> sl;
    ll scr = 0;
    ll cnt = 0;
    for(int i=0; i<K; i++) {
        pq.push(B[i]);
        scr+=B[i].val;
        if(B[i].kind) cnt++;
    }
    ll res = scr + cnt*cnt;
    for(int i=K; i<N; i++) if(B[i].kind) sl.push(B[i]);
    while(sl.size()){
        sushi s = pq.top(); pq.pop();
        if(s.kind==1) break;
        sushi ns = sl.top(); sl.pop();
        scr = scr - s.val + ns.val;
        cnt = cnt - s.kind + ns.kind;
        res = max(res, scr+cnt*cnt);
        pq.push(ns);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 9844
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
const long long INF = 1ll << 60;


int main() {
  int N; cin >> N;
  string S; cin >> S;
  int x = 0;
  int ans = 0;
  rep(i,N){
    if(S[i] == 'I') x++;
    else x--;
    ans = max(ans,x);
  }
  cout << ans << endl;
	return 0;
}



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

int main() {
    int N,K;
    cin >> N >> K;
    cout << (N-1+K-2)/(K-1) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i , n) for (int i = 0; i < (int)(n); i++)
const int INF = 1<<29;
using namespace std;
using ll = long long;
int main(){
    int N;
    cin >> N;
    vector <string> S(N);
    vector <int> A(N , 0);
    for(int i = 0; i < N; i++){
        string s;
        cin >> s;
        sort(s.begin() , s.end());
        S[i] = s;
    }
    sort(S.begin() , S.end());
    map <string , int> t;
    ll m = 0;
    for(int i = 0; i < N; i++){
        m += t[S[i]];
        t[S[i]]++;
    }
    cout << m << endl;
}


Measured memory_bytes: 14548
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.insert(0, None)

history = [None] * (N+1)

next_town = 1
i = 0
skip_flg = False
while i < K:
  if history[next_town] == None:
    history[next_town] = i
  elif skip_flg == False:
    skip_flg = True
    
    i = i + ((K - i)//(i - history[next_town])) * (i - history[next_town])
  if i < K:
    i += 1
    next_town = A[next_town]
print(next_town)

Measured memory_bytes: 93472
#include <cstdio>

// ???????????¢??¢?´¢
int search(int A[], int n, int key)
{
	int i = 0;
	A[n] = key;
	while (A[i] != key)
	{
		i++;
	}
	return i != n;
}

int main()
{
	int n, A[10000 + 1], q, key, sum = 0;

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

	scanf("%d", &q);
	for (int i = 0; i < q; i++)
	{
		scanf("%d", &key);
		if (search(A, n, key))
		{
			sum++;
		}
	}
	printf("%d\n", sum);
}

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

int main() {
  int n, k; cin >> n >> k;
  int cnt = 0;
  while (n) {
    n /= k;
    cnt++;
  }
  cout << cnt;
  return 0;
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

// Problem Specific Parameter:

int main(void){
	int w,h,n;
	cin >> w >> h >> n;

	int l=0,r=w,t=0,b=h;
	rep(i,n){
		int x,y,a;
		cin >> x >> y >> a;
		switch(a){
			case 1:
				chmax(l,x);
				break;
			case 2:
				chmin(r,x);
				break;
			case 3:
				chmax(t,y);
				break;
			case 4:
				chmin(b,y);
				break;
		}
	}

	cout << max(r-l,0)*max(b-t,0) << endl;
	return 0;
}

Measured memory_bytes: 384
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1e9+7;
const int maxn = 200005;
int T,n,m;
ll a[maxn];
vector< pair<ll,ll> >num;
int gcd(int a,int b)
{
    return b>0?gcd(b,a%b):a;
}
int main() {
	cin>>n;
	for(int i=0;i<n;i++){
		ll x,y;
		cin>>x>>y;
		num.push_back({y,x});
	}
	//num.push_back({y,x});
		sort(num.begin(),num.end());
		ll cnt = 0;
		for(int i=0;i<n;i++){
			cnt+=num[i].second;
			if(cnt>num[i].first){
				cout<<"No\n";
				return 0;
			} 
		}
	cout<<"Yes\n";
	return 0;
}



Measured memory_bytes: 6512
#include <iostream>
using namespace std;
int main(void) {
  string a, b;
  cin >> a >> b;
  string ans = "EQUAL";
  if (a.size() > b.size()) {
    ans = "GREATER";
  } else if (a.size() < b.size()) {
    ans = "LESS";
  } else {
    for (int i = 0; i < a.size(); i++) {
      if (a[i] < b[i]) {
        ans = "LESS";
        break;
      } else if (a[i] > b[i]) {
        ans = "GREATER";
        break;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define rng(a) a.begin(), a.end()
#define ina(n,a) cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]
#define sz(x) (int)(x).size()
#define se second
#define fi first
#define prev            coyhhhhhhyoc    
#define next          sdNNNmNNNNNNNmds  
#define y0           hNNNNy_yNNNNNN_sNh
#define y1          mNNNNNdtdNNNNNNtsNNm
#define yn          mNNNNNNNNy___smNNNms
#define tm            oooooosyysooooot 
#define read               tyhyt        
#define rank              ytmNmo         
#define index              yyy
#define pb push_back
#define pcnt __builtin_popcountll
#define rrep(i,a,b) for(int i = (b); i >= (a); i--)
#define rall(x,a) for(auto x : a)
#define MOD 1000000007
#define endl "\n"
typedef long long ll;
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int x;
    cin >> x;
    rep(i, 1, 9) {
        rep(j, 1, 9) {
            if(i * j == x) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
//#include <boost/foreach.hpp>
//#include <boost/range/algorithm.hpp>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
#define INF 1000000000
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define MOD 1000000007LL
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};

int main (){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<min(a,min(b,c))<<" ";
    cout<<max(a,max(b,c))<<endl;

    

}



/*
1 2 3 4 5

6
*/



Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a, b;
ll gcd(ll x, ll y) {
	if(y==0) return x;
	return gcd(y,x%y);
}
int main() {
	scanf("%lld%lld",&a,&b);
	ll c = gcd(a,b);
	if(c==b) printf("-1");
	else {
		for(ll i=2;i<=200;i++) {
			if(gcd(i,b/c)==1LL) {
                return !printf("%lld",i*a);
			}
		}
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <set>
#define llint long long
#define mod 998244353

using namespace std;
typedef pair<pair<llint, llint>, llint> T;

llint n, k;
vector<T> ans;
bool used[300005];
set<llint> S;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	for(int i = 0; i < 2*n; i++) S.insert(i);
	
	llint lim = 3*n-1 - k, r = 2*n-1, l = lim - r;
	if(l < 0){
		cout << -1 << endl;
		return 0;
	}
	used[l] = used[r] = true;
	ans.push_back(make_pair(make_pair(l+k, r+k), 3*n-1+k));
	
	for(int i = 3*n-2; i >= 2*n; i--){
		l++, r-=2;
		if(l >= r || used[l] || used[r]){
			lim = i;
			break;
		}
		used[l] = used[r] = true;
		ans.push_back(make_pair(make_pair(l+k, r+k), i+k));
	}
	
	l = 0, r = 2*n-1;
	while(1){
		while(r > 0 && used[r]) r--;
		while(l < 2*n-1 && used[l]) l++;
		if(l >= r) break;
		used[l] = used[r] = true;
		ans.push_back(make_pair(make_pair(l+k, r+k), lim+k));
		lim--;
	}
	
	for(int i = 0; i < ans.size(); i++){
		if(ans[i].first.first + ans[i].first.second > ans[i].second){
			cout << -1 << endl;
			return 0;
		}
	}
	
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i].first.first << " " << ans[i].first.second << " " << ans[i].second << endl;
	}
	
	return 0;
}

Measured memory_bytes: 14832
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _0057
{
    public class Program

    {
        public static void Main(string[] args)
        {
            while (true)
            {
                string line = Console.ReadLine();
                if (string.IsNullOrEmpty(line)) return;

                int n = int.Parse(line);
                Console.WriteLine(n * (n + 1) / 2 + 1);
            }
        }
    }

}



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

int main()
{
    int h, w;
    cin >> h >> w;
    string ss[h];
    for (int i = 0; i < h; i++)
    {
        string s;
        cin >> s;
        ss[i] = s;
    }

    int x[8] = {1, 1, 1, 0, 0, -1, -1, -1};
    int y[8] = {1, 0, -1, 1, -1, 1, 0, -1};

    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            if (ss[i][j] == '#')
                continue;

            int n = 0;
            for (int k = 0; k < 8; k++)
            {
                int ai = i + y[k];
                int aj = j + x[k];
                if (ai < 0 || ai >= h)
                    continue;
                if (aj < 0 || aj >= w)
                    continue;
                if (ss[ai][aj] == '#')
                {
                    n++;
                }
            }
            ss[i][j] = char(n + '0');
        }
    }
    for (int i = 0; i < h; i++)
    {
        cout << ss[i] << endl;
    }
}


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

#define ll long long
#define ld long double
#define COIN const int
#define ite iterator
#define PII pair<int,int>
#define PSI pair<string,int>
#define PIS pair<int,string>

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

#define ALL(c) (c).begin(), (c).end()
#define sz(s) (s).size()
#define CLEAR(x) memset(x,0,sizeof x);

#define MP make_pair
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define X first
#define Y second

#define VI vector<int>
#define VS vector<string>
#define VII vector<PII>
#define VVI vector<VI>

#define PIII 3.1415926
#define PI 3.14
/*****************************************************************************/
const ll mod=1e9+7;
const ll INF=1e18;
/*****************************************************************************/

using namespace std;

vector <int> ans;

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ll n; cin >>n;
	while (1) {
		n--;
		ans.pb(n%26);
		n/=26;
		if (n==0) break;
	}
	for (int i=sz(ans)-1;i>=0;i--) {
		cout <<(char)(ans[i]+'a');
	}
	return 0;
}
/******************************************************************************
******************************************************************************/


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

int main(){
	int a,b,c;
	int ans;
	bool flg;
	int cnt=-1;
	
	while(cin>>a>>b){
		cnt++;flg=false;
		//-----test-----
		switch(cnt){
		case 0:
			if(a<500000) flg=true; 
			break;
		}
		
		if(flg) break;
		
		//--------------
		c=a+b;
		ans=1;
		while(10<=c){
			c/=10;
			ans++;
		}
		cout<<ans<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
int main(void){
    
    int a,b,ans;
    char op;
    
    while(op != '?'){
    scanf("%d %c %d",&a,&op,&b);

    if(op != '?'){
    
    switch (op){
        case '+': ans = a+b;    break;
        case '-': ans = a-b;    break;
        case '*': ans = a*b;    break;
        case '/': ans = a/b;    break;
    }
    printf("%d\n",ans);
    }
    }
    
        
        return 0;
    
    
}


Measured memory_bytes: 2104
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define at(x,i) get<i>(x);
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
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;
}
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;
}
int main(){
    vl v,w;
    rep(i,200){
        ll x=(i+1)*(i+2)*(i+3)/6;
        if(x>1000000)break;
        v.pb(x);
        if(x%2==1)w.pb(x);
    }
    ll sz=v.size();
    vl dp(1000001,inf);
    dp[0]=0;
    rep(i,sz){
        rep(j,1000001){
            if(j<v[i])continue;
            chmin(dp[j],dp[j-v[i]]+1);
        }
    }
    ll ssz=w.size();
    vl ddp(1000001,inf);
    ddp[0]=0;
    rep(i,ssz){
        rep(j,1000001){
            if(j<w[i])continue;
            chmin(ddp[j],ddp[j-w[i]]+1);
        }
    }
    while(true){
        ll a;cin >> a;
        if(a==0)break;
        cout << dp[a] << " " <<ddp[a] << endl;
    }
}


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

int h, W;

int w[50], b[50], r[50];

int main() {
	std::cin >> h >> W;
	char ch;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < W; ++j) {
			std::cin >> ch;
			if (ch == 'W') {
				++w[i];
			}
			else if (ch == 'B') {
				++b[i];
			}
			else {
				++r[i];
			}
		}
	}
	for (int i = 1; i < h; ++i) {
		w[i] += w[i - 1];
		b[i] += b[i - 1];
		r[i] += r[i - 1];
	}

	int min = 2600;

	for (int i = 0; i < h - 2; ++i) {
		for (int j = i + 1; j < h - 1; ++j) {
			int sum = 0;
			sum += W*(i + 1) - w[i];//2
			sum += W*(j - i) - (b[j] - b[i]);//3
			sum += W*(h - j - 1) - (r[h-1] - r[j]);//
			min = std::min(min, sum);
		}
	}
	std::cout << min << std::endl;
	return 0;
}

Measured memory_bytes: 3080
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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; }
typedef pair<int, int>P;
const int INF = 1e8;

signed main() {
	int A, B, K;
	cin >> A >> B >> K;
	if (B - K + 1 <= A + K - 1) {
		rep(i, B - A + 1)cout << A + i << endl;
	}
	else {
		rep(i, K)cout << A + i << endl;
		rep(i, K)cout << B - K + i + 1 << endl;
	}
}

Measured memory_bytes: 256
void main() {
	auto D = ri;
	switch(D) {
		case 25: writeln("Christmas"); break;
		case 24: writeln("Christmas Eve"); break;
		case 23: writeln("Christmas Eve Eve"); break;
		case 22: writeln("Christmas Eve Eve Eve"); break;
		default: break;
	}
}

// ===================================

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

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 256
n = int(input())
list_words = []
for q in range(n):
    list_words.append(input())


def check(l):
    for i in range(len(l)-1):
        if l[i][-1] != l[i+1][0]:
            return "No"
    for o in range(len(l)):
        if l[o] in l[:o] or o in l[o+1:]:
            return "No"
    return "Yes"


print(check(list_words))


Measured memory_bytes: 3060
a,b,c = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

if (c - a - b)<=0:
	print("No")
	exit(0)

if (4 * a * b) < (c - a - b)**2:
	print("Yes")
else:
	print("No")




Measured memory_bytes: 2940
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int bk[17][100001];

int main() {
    int n, l, q;
    cin >> n;
    VI x(n);
    REP(i,n) scanf("%d", &x[i]);
    cin >> l >> q;

    int r = 0;
    REP(i,n){
        while (r < n-1 && x[r+1]-x[i] <= l) r++;
        bk[0][i] = r;
    }

    FOR(i,1,16){
        REP(j,n){
            bk[i][j] = bk[i-1][bk[i-1][j]];
        }
    }

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

        int ans = 0;
        FORR(i,16,0){
            if (bk[i][a] < b){
                ans += 1<<i;
                a = bk[i][a];
            }
        }
        printf("%d\n", ans+1);
    }


    return 0;
}


Measured memory_bytes: 7808