akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int gcd(int x, int y) {
    if (x < y) swap(x, y);
    while(y > 0) {
        int tmp = x % y;
        x = y;
        y = tmp;
    }
    return x;
}

int main()
{
    int x, y;
    cin >> x >> y;
    cout << gcd(x, y) << endl;
}



Measured memory_bytes: 3124
MINF = -10 ** 20

n, m = map(int, input().split())
xlst = []
ylst = []
zlst = []
for _ in range(n):
  x, y, z = map(int, input().split())
  xlst.append(x)
  ylst.append(y)
  zlst.append(z)
"""
dp[a] ... 使用数aでの最大スコア
"""

def func(xf, yf, zf):
  dp = [MINF for _ in range(m + 1)]
  dp[0] = 0
  for i in range(n):
    scorei = xlst[i] * xf + ylst[i] * yf + zlst[i] * zf
    for j in range(m, 0, -1):
      dp[j] = max(dp[j], dp[j - 1] + scorei)
  return dp[m]

ans = 0
for xf in (-1, 1):
  for yf in (-1, 1):
    for zf in (-1, 1):
      ans = max(ans, func(xf, yf, zf))
print(ans)

Measured memory_bytes: 52060
W,H,N = map(int,input().split())
XYA = [list(map(int,input().split())) for __ in range(N)]

Xend = W
Yend = H
Xstart = 0
Ystart = 0
for xya in XYA:
    if xya[2] == 1:
        Xstart = max(Xstart,xya[0])
    elif xya[2] == 2:
        Xend = min(Xend,xya[0])
    elif xya[2] == 3:
        Ystart = max(Ystart,xya[1])
    elif xya[2] == 4:
        Yend = min(Yend,xya[1])
if (Xend - Xstart)>0 and (Yend - Ystart)>0:
    print((Xend - Xstart)*(Yend - Ystart))
else:
    print(0)

Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <bitset>

using namespace std;

int mp[550][550];

int main () {
	#ifdef chitongz
//	freopen ("x.in", "r", stdin);
	#endif
	static int n;
	scanf ("%d", &n);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (i == j) continue;
			for (int k = 1; k <= 60; ++k) {
				int x = i >> (k - 1), y = j >> (k - 1);
				if ((x & 1) ^ (y & 1)) {
					mp[i][j] = mp[j][i] = k;
					break;
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			printf ("%d  ", mp[i][j]);
		}
		puts ("");
	}
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#include <cstring>
#include <limits>
using namespace std;
#define ll long long int
#define X first
#define Y second
#define fw(i, start, end) for (ll i = start; i < end; ++i)
#define fe(i, start, end) for (ll i = start; i <= end; ++i)
#define L(T)  \
    ll T;     \
    cin >> T; \
    while (T--)
#define FASTIO                   \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);

vector<ll> v[100004];

ll dp[100005];

ll dfs(ll node)
{
    if (dp[node] != -1)
        return dp[node];
    ll child_len = 0;
    fw(i, 0, v[node].size())
    {
        ll child = v[node][i];
        child_len = fmax(child_len, dfs(child));
    }
    dp[node] = ++child_len;
    return dp[node];
}

int main()
{
    FASTIO
    ll n, m;
    cin >> n >> m;
    fe(i, 1, m)
    {
        ll a, b;
        cin >> a >> b;
        v[a].push_back(b);
    }
    memset(dp, -1, sizeof dp);

    ll pre_ans = 0;
    fw(i, 1, n + 1)
    {
        pre_ans = fmax(pre_ans, dfs(i));
    }
    cout << pre_ans - 1 << "\n";
    return 0;
}

Measured memory_bytes: 8576
def pushing(a,b):
    if a == b:
        return 0
    elif a < b:
        if a * b >= 0:
            return b - a
        else:
            if abs(a) <= b:
                return 1 + b + a
            else:
                return 1 - a - b
    else:
        if a * b > 0:
            return 2 + a - b
        elif a * b == 0:
            return 1 + a - b
        else:
            if a <= abs(b):
                return 1 - b - a
            else:
                return 1 + a + b
x, y = [ int(v) for v in input().split() ]
print(pushing(x,y))
        

Measured memory_bytes: 38256
using System;
using System.Linq;

class SwTN
{
    static void Main()
    {
            string str;
            for (int i=1; ;i++ )
            {
                str = Console.ReadLine();
                int a = int.Parse(str.Split(' ')[0]);
                int b = int.Parse(str.Split(' ')[1]);
                if (a == 0&&b==0)
                {
                    break;
                }
                else if (a > b)
                {
                    int tmp = a; a = b; b = tmp;
                }
                Console.WriteLine( a+" " + b);
            }
    }
}

Measured memory_bytes: 5816
use std::io::Read;
use std::cmp::min;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut a = 0;
    let mut b = 0;
    let mut ba = 0;
    let mut ans = 0;
    for s in s.trim().split_whitespace() {
        let t = s.replace("AB", "");
        ans += (s.len() - t.len()) / 2;
        match (t.starts_with("B"), t.ends_with("A")) {
            (true, true)  => ba += 1,
            (true, false) => b += 1,
            (false, true) => a += 1,
            _ => (),
        }
    }
    if ba > 0 {
        ans += ba - 1;
        if a > 0 {
            ans += 1;
            a -= 1;
        }
        if b > 0 {
            ans += 1;
            b -= 1;
        }
    }
    ans += min(a, b);
    println!("{}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int n,h[100005][3],dp[100005][3],k;
int f(int i,int l)
{
	if(i==(n) )
	return 0;
	if(dp[i][l]!=-1)
	return dp[i][l];
	if(i==0)
	return max(h[i][0]+f(i+1,0),max(h[i][1]+f(i+1,1),h[i][2]+f(i+1,2)));
	
	
	int ans= 0;
	for(int j=0;j<3;j++)
	if(l!=j)
		ans=max(ans,h[i][j]+f(i+1,j));

	return dp[i][l]=ans;
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>h[i][0]>>h[i][1]>>h[i][2];
	memset(dp,-1,sizeof(dp));
	cout<<f(0,0)<<endl;
	return 0;
}

Measured memory_bytes: 10368
K = int(input())

memo = [[None] * (K + 1) for _ in range(K + 1)]

def mygcd(a, b):
    if memo[a][b] != None: return memo[a][b]
    else:
        if a < b:
            ret = mygcd(b, a)
        elif b == 0:
            ret = a
        else:
            ret = mygcd(b, a % b)
        #
        memo[a][b] = ret
        memo[b][a] = ret
        return ret

ans = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        tmp = mygcd(a, b)
        for c in range(1, K + 1):
            ans += mygcd(tmp, c)

print(ans)

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

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef _DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif


signed main() {

    int n,k;
    cin>>n>>k;
    int ans=1;
    rep(i,n){
        if(i>0)
            ans*=k-1;
        else
            ans*=k;
    }
    
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define pri_que priority_queue
#define vint vector<int>
#define vvint vector<vector<int>>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vs vector<string>
#define vvc vector<vector<char>>
#define vc vector<char>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define show(x) cout<<#x<<"="<<x<<endl;
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n,a,b;cin>>n>>a>>b;
    if(a>b){cout<<0<<endl; return 0;}
    if(a==b){cout<<1<<endl; return 0;}
    if(a!=b && n==1){cout<<0<<endl; return 0;}
    int max=a+b*(n-1);
    int min=a*(n-1)+b;
    cout<<max-min+1<<endl;
}

Measured memory_bytes: 3620
def resolve():
    S = input()
    X, Y = list(map(int, input().split()))
    insts = []
    cnt = 1
    series = S[0]

    for i in range(1, len(S)):
        if series == S[i]:
            cnt += 1
        else:
            insts.append((series, cnt))
            cnt = 1
            series = S[i]
    insts.append((series, cnt))
    # print(insts)
    xmoves = []
    ymoves = []
    to_x = True
    for inst in insts:
        if inst[0] == "F":
            if to_x:
                xmoves.append(inst[1])
            else:
                ymoves.append(inst[1])
        else:
            if inst[1]%2 == 1:
                to_x = not to_x
    # print(xmoves)
    # print(ymoves)
    cands = set()
    cands.add(0)
    for i, x in enumerate(xmoves):
        _cands = set()
        while cands:
            xpos = cands.pop()
            _cands.add(xpos+x)
            if not (i == 0 and insts[0][0] == "F"):
                _cands.add(xpos-x)
        cands = _cands
    if X not in cands:
        print("No")
        return

    cands = set()
    cands.add(0)
    for y in ymoves:
        _cands = set()
        while cands:
            ypos = cands.pop()
            _cands.add(ypos+y)
            _cands.add(ypos-y)
        cands = _cands
    if Y not in cands:
        print("No")
        return
    
    print("Yes")

if '__main__' == __name__:
    resolve()

Measured memory_bytes: 9764
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define rep(N) for(int i=0;i<N;i++)
#define repj(N) for(int j=0;j<N;j++)
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define For(I,N) for(int I=0;I<N;I++)
#define cinone(N) int N;cin>>N;
#define scanfone(N) int N;cin>>N;
#define cinng(N,M) int N[M];for(int yiuytvnm=0;yiuytvnm<M;yiuytvnm++) cin>>N[yiuytvnm];
#define scanfng(N,M) int N[M];for(int qrwuoiq=0;qrwuoiq<M;qrwuoiq++) scanf("%d",&N[qrwuoiq]);
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
ll dp[3005][3005];//[)
int n;
int a[3005];

int main()
{
//	freopen("input.txt","r",stdin);
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int i=0;i<=n;i++)
	{
		dp[i][i]=0;
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=0;i<n;i++)
		{
			int j=i+k;
			if(j>n) break;
			if(k&1) dp[i][j]=-1LL*inf*inf;else dp[i][j]=1LL*inf*inf;
		}
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=0;i<n;i++)
		{
			int j=i+k;
			if(j>n) break;
			if(k&1)
			{
				if(i+1<=j) dp[i][j]=max(dp[i][j],dp[i+1][j]+a[i]);
				if(j-1>=i) dp[i][j]=max(dp[i][j],dp[i][j-1]+a[j-1]);
			}
			else
			{
				if(i+1<=j) dp[i][j]=min(dp[i][j],dp[i+1][j]-a[i]);
				if(j-1>=i) dp[i][j]=min(dp[i][j],dp[i][j-1]-a[j-1]);
			}
		}
	}
	if(n&1) cout<<dp[0][n]<<endl;else cout<<-dp[0][n]<<endl;
	return 0;
}

Measured memory_bytes: 70016
#include <iostream>
#include <fstream>
#include <math.h>
#include <string>

using namespace std;

int main(){

  long long n, k, tmp, ans1, ans2;
  cin >> n >> k;

  tmp = n / k;
  ans1 = n - k * tmp;
  ans2 = abs(ans1 - k);

  cout << min(ans1, ans2);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch StringEquivalence | diff StringEquivalence.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address StringEquivalence.cpp && ./a.out

/*
 
 3/15/2020
 
 22:57-23:22 WA
 
 */

int N;

vector<string> res;
void dfs(int maxkind, string &s) {
  int L=SZ(s);
  if(L==N) {
    res.push_back(s);
    return;
  }
  REPE(i,maxkind+1) {
    char c='a'+i;
    s.push_back(c);
    dfs(max(maxkind,i),s);
    s.pop_back();
  }
}
void solve() {
  string s="a";
  dfs(0,s);
  REP(i,SZ(res)) cout<<res[i]<<endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;
  
  cin>>N;
  solve();
  
  return 0;
}


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

int main()
{
  string test;
  getline(cin,test);

  if (test[0] == 'A' && test[1] == 'C')
  {
    cout << "Yes" << endl;
  }
  else if(test[1] == 'A' && test[2] == 'C')
  {
    cout << "Yes" << endl;
  }
  else if(test[2] == 'A' && test[3] == 'C')
  {
    cout << "Yes" << endl;
  }
  else if(test[3] == 'A' && test[4] == 'C')
  {
    cout << "Yes" << endl;
  }
  else
  cout << "No" << endl;
}


Measured memory_bytes: 3608
#include <stdio.h>

int main(void){
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  if(a == b && b == c){
    printf("1\n");
  }else if(a == b || b == c || c == a){
    printf("2\n");
  }else{
    printf("3\n");
  }
}


Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int main() {
	string str;
	char ch;
	int counter[26] = {};
	while (true) {
		cin >> ch;
		if (cin.eof())break;
		
			if (ch >= 'a' && ch <= 'z')counter[ch - 'a']++;
			else if (ch >= 'A' && ch <= 'Z')counter[ch - 'A']++;

		
	}

	for (int i = 0; i <26; i++) {
		cout << (char)('a' + i) <<" : "<< counter[i] << endl;
	}
	return 0;

}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
typedef long long ll;

ll power(ll x, ll y, ll p)
{
    ll res = 1;      // Initialize result

    x = x % p;  // Update x if it is more than or
    // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;

        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}

// Returns n^(-1) mod p
ll modInverse(ll n, ll p)
{
    return power(n, p-2, p);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll x,y;
    cin >> x >> y;
    ll a = (2*x-y)/3;
    ll b = (2*y-x)/3;
    if(a<0 || b<0){
        cout << 0;
        return 0;
    }
    if(2*a+b==x && a+2*b==y){
        ll fac[1000005];
        fac[0] = 1;
        for (ll i=1 ; i<1000005; i++)
            fac[i] = (fac[i-1]*i)%mod;
        cout << ((fac[a+b]* modInverse(fac[a], mod) % mod * modInverse(fac[b], mod) % mod) % mod) % mod;

        return 0;
    }
    cout << 0;
}

Measured memory_bytes: 8064
N = int(input())
H = list(map(int, input().split()))
tmp = 0
ans = 0
for i in range(1, N):
    if H[i-1]>=H[i]:
        tmp +=1
    else:
        ans = max(ans, tmp)
        tmp = 0
ans = max(ans, tmp)
print(ans)

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

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

    int q;
    std::cin >> q;
    std::vector<int> T(q);
    for (int i = 0; i < q; i ++) {
        std::cin >> T[i];
    }

    int C = 0;
    for (int t : T) {
        C += std::binary_search(S.begin(), S.end(), t);
    }
    std::cout << C << std::endl;
}



Measured memory_bytes: 3280
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
typedef int64_t ll;
typedef long double ld;

void solve() {
    ll n;
    cin >> n;
    ll a[n + 1];
    map<ll, ll> m;
    for(ll i = 1; i <= n; i++) {
        cin >> a[i];
        m[i + a[i]]++;
    }
    ll ans = 0;
    for(ll i = 1; i <= n; i++) {
        ans += m[i - a[i]];
    }
    cout << ans;
}    

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

Measured memory_bytes: 27828
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.C_Challenge
{
    class ABC_082
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            int n = ReadInt();
            int[] array = ReadInts();
            long[] cntArray = new long[100000];
            long cnt = 0;
            for (int i = 0; i < n; i++)
            {
                if (array[i] > 100000)
                {
                    cnt++;
                }
                else
                {
                    cntArray[array[i] - 1]++;
                }
            }

            for(int i = 0; i < 100000; i++)
            {
                if (cntArray[i] == 0
                    || cntArray[i] == i + 1) continue;

                if (cntArray[i] > i + 1)
                {
                    cnt += cntArray[i] - (i + 1);
                }
                else if (cntArray[i] < i + 1)
                {
                    cnt += cntArray[i];
                }
            }
            Console.WriteLine(cnt);
        }

        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 29916
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>

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

using namespace std;

int main(){
	int N;
	int work;
	cin >> N;
	work = N / 15;
	cout << (N * 800) - (work * 200) << endl;
	return 0;
}


Measured memory_bytes: 256
use std::env;
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin.bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

fn main() {
    // main の引数
    /*
        引数なしのときargs.len() = 1;
    */
    let args: Vec<String> = env::args().collect();

    let A = read::<i32>();
    let B = read::<i32>();

    if (A+13)%15 > (B+13)%15 {
        println!("Alice");
    } else if (B+13)%15 > (A+13)%15 {
        println!("Bob");
    } else {
        println!("Draw");
    }
}


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


namespace atcorder2
{
    class Program
    {
        public static long Read()
        {

            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {
            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }

       
       
        public static long gcd(long x,long y)
        {
            if (x < y) gcd(y, x);
            
            while (y > 0)
            {
                var z = x % y;
                x = y;
                y = z;
            }
            return x;
        }

        public static long lcm(long x,long y)
        {
            return x * y / gcd(x, y);
        }



        static void Main(string[] args)
        {
            var sw = new StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            SetOut(sw);


            var s = ReadLine();
            long ans = 0;
            long t = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == 'W')
                {
                    ans += (i-t);
                    t++;
                }
            }
            WriteLine(ans);

          
          
            Out.Flush();
        }
    }
}




Measured memory_bytes: 17476
#include<bits/stdc++.h>
using namespace std;
map<int, int> mp;
int main(void) {
    std::ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, x;
    while(cin >> n) {
        mp.clear();
        for(int i = 0; i < n; ++i) {
            cin >> x;
            mp[x]++;
        }
        int cnt = 0;
        for(auto it : mp) {
            if(it.first > it.second) cnt += it.second;
            else cnt += it.second - it.first;
        }
        cout << cnt << endl;
    }
}


Measured memory_bytes: 4736
module.exports=function(r){var e={};function t(n){if(e[n])return e[n].exports;var o=e[n]={i:n,l:!1,exports:{}};return r[n].call(o.exports,o,o.exports,t),o.l=!0,o.exports}return t.m=r,t.c=e,t.d=function(r,e,n){t.o(r,e)||Object.defineProperty(r,e,{enumerable:!0,get:n})},t.r=function(r){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(r,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(r,"__esModule",{value:!0})},t.t=function(r,e){if(1&e&&(r=t(r)),8&e)return r;if(4&e&&"object"==typeof r&&r&&r.__esModule)return r;var n=Object.create(null);if(t.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:r}),2&e&&"string"!=typeof r)for(var o in r)t.d(n,o,function(e){return r[e]}.bind(null,o));return n},t.n=function(r){var e=r&&r.__esModule?function(){return r.default}:function(){return r};return t.d(e,"a",e),e},t.o=function(r,e){return Object.prototype.hasOwnProperty.call(r,e)},t.p="",t(t.s=0)}([function(r,e,t){t(1)(t(2).readFileSync("/dev/stdin","UTF-8").split("\n"))},function(r,e){function t(r,e){return function(r){if(Array.isArray(r))return r}(r)||function(r,e){var t=[],n=!0,o=!1,u=void 0;try{for(var i,l=r[Symbol.iterator]();!(n=(i=l.next()).done)&&(t.push(i.value),!e||t.length!==e);n=!0);}catch(r){o=!0,u=r}finally{try{n||null==l.return||l.return()}finally{if(o)throw u}}return t}(r,e)||function(){throw new TypeError("Invalid attempt to destructure non-iterable instance")}()}r.exports=function(r){var e=t(r[0].split(" ").map(function(r){return Number(r)}),2),n=e[0],o=e[1],u=r[1].split(" ").map(function(r){return Number(r)});u.sort(function(r,e){return r-e});for(var i=!1,l=!1,f=0;f<n;f++)if(0!=f&&u[f]%u[0]==o%u[0]&&(i=!0),u[f]>o&&(l=!0),u[f]==o)return void console.log("POSSIBLE");i&&l?console.log("POSSIBLE"):console.log("IMPOSSIBLE")}},function(r,e){r.exports=require("fs")}]);

Measured memory_bytes: 28752
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int INF=-2000000000;
int main() {
  int h,a;
  cin >> h >> a;
  if(h%a==0) cout << h/a << endl;
  else cout << h/a+1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
 
using namespace std;
 
 
int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, a, k;
    ios::sync_with_stdio(false);
    cin >> n;
    int ans = 0;
    for(i = 1; i <= n; i++) {
        cin >> a >> k;
        while(a % k > 0 && a > k) {
            int d = a / k;
            a -= 1LL * (d + 1) * ((a - 1LL * d * k + d) / (d + 1));
        }
        ans ^= (a / k);
    }
    if(ans == 0)
        cout << "Aoki";
    else
        cout << "Takahashi";
    //cin.close();
    //cout.close();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
using namespace std;
int N,M,D,T;

int main(){
  cin >> N;
  map<int,int> m;
  for(int i=0;i<N;i++){
    cin >> D; m[D]++;
  }
  cin >> M;
  for(int i=0;i<M;i++){
    cin >> T;
    if(m[T]>0) m[T]--;
    else{
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
}

Measured memory_bytes: 9600
#include<stdio.h>
#define mod 1000000007
#define ll long long
ll sp(ll a,ll b)
{
  ll c=1;
  while(a)
  {
    if(a&1){c*=b;c%=mod;}
    b*=b;
    b%=mod;
    a>>=1;
  }
  return c;
}
int main()
{
  ll n,ans;
  scanf("%lld",&n);
  if(n==1)ans=0;
  else if(n==2)ans=2;
  else {
    ans=(sp(n,10)%mod+sp(n,8)%mod-2*sp(n,9)%mod+mod+mod)%mod;
  }
  printf("%lld\n",ans%mod);
}


Measured memory_bytes: 1720
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// FOR FOLDING {
#define debug(var)  do{ std::cout << #var << " : "; view(var); }while(0)
using ll = long long;
using ld = long double;
inline int num (const std::string& S, int idx) noexcept { return S.at(idx) - '0'; }
inline int ctoi(char c) noexcept { return c - '0'; }
inline bool isNumber(char c) noexcept { return ('0'<c && c<'9'? true : false); }
inline int safeCtoi(char c) { if(isNumber(c)) { return ctoi(c); } else { throw 1; } }
inline char itoc(int i) noexcept { return i + '0'; }
inline unsigned int bitMask(int i) noexcept { return (1 << i); }
inline bool isTrue(unsigned int bit, int i) noexcept { return bit & bitMask(i); }
inline bool isEven(int num) noexcept { return !num%2; }
inline bool isOdd(int num) noexcept { return num%2; }
template<typename T> inline short sgn(T num) noexcept { return (num==0? 0 : (num>0? 1 : -1) ); }
template<typename T> inline bool isZero(T num) noexcept { return (num==0? true : false); }
template<typename T> inline bool isPositive(T num) noexcept { return (num>0? true : false); }
template<typename T> inline bool isNegative(T num) noexcept { return (num<0? true : false); }
template<typename T> void view(T e) noexcept { cout << e; }
template<typename T> void view(std::vector<T> v) noexcept { for(const auto& e : v) cout << e << " "; }
template<typename T> void view(std::vector<std::vector<T>> vv) noexcept { for(const auto& v : vv) view(v); }
// }

int sum(vector<int> const& v){
	int res = 0;
	for(const auto& e : v){
		res += e;
	}
	return res;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n-1);
	for(auto& e: a) cin >> e;
	vector<int> subordinates(n);
	for(const auto& e : a){
		subordinates.at(e-1) ++;
	}
	for(const auto& e : subordinates){
		cout << e << endl;
	}
	return 0;
}


Measured memory_bytes: 4752
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
#define go(u) for (int o=ft[u],v;v=E[o].t;o=E[o].n)
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> par;
const int N=100010;
int ft[N],dp[N],n,tot;
struct edge{int t,n;}E[N<<1];
void add(int x,int y){
	E[++tot]=(edge){y,ft[x]},ft[x]=tot;
}
void dfs(int u,int f=0){
	go(u) if (v!=f){
		dfs(v,u);
		dp[u]|=dp[v];
	}
	int bit;
	for (bit=1<<28;bit;bit>>=1){
		int cnt=0;
		go(u) if (v!=f){
			if (dp[v]&bit) ++cnt;
		}
		if (cnt>1) break;
	}
	bit<<=1;
	if (!bit) bit=1;
	for (;;bit<<=1){
		int cnt=0;
		go(u) if (v!=f){
			if (dp[v]&bit) ++cnt;
		}
		if (!cnt) break;
	}
	dp[u]|=bit;
	dp[u]&=~(bit-1);
}
int main(){
	scanf("%d",&n);
	rep(i,2,n){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1);
	per(i,28,0) if (dp[1]&1<<i){
		printf("%d\n",i);
		break;
	}
	return 0;
}


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

int dp[3000][3000];

int main(){
    string s,t;
    cin >> s >> t;
    for(int i = 0; i < s.size();++i){
        dp[0][i] = (s[i] == t[0]);
        if(i > 0) dp[0][i] = max(dp[0][i],dp[0][i-1]);
    }
    for(int i = 0; i < t.size();++i){
        dp[i][0] = (s[0] == t[i]);
        if(i > 0) dp[i][0] = max(dp[i][0],dp[i-1][0]);
    }
    for(int i = 1; i < s.size();++i){
        for(int j = 1; j < t.size();++j){
            if(s[i] == t[j]) dp[j][i] = 1 + dp[j-1][i-1];
            else dp[j][i] = max(dp[j-1][i],dp[j][i-1]);
        }
    }
    string ans = "";
    int i = t.size()-1,j = s.size()-1;
    while(i > -1 && j > -1){
        if(t[i] == s[j]) ans += t[i],--i,--j;
        else{
            if(i > 0 && j > 0){
                if(dp[i-1][j] > dp[i][j-1])
                    --i;
                else
                    --j;
            }
            else if(i > 0) --i;
            else --j;
        }
    }
    reverse(ans.begin(),ans.end());
    cout << ans << "\n";
    return 0;
}


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

int main() {
  
  int A1, A2, A3;
  cin >> A1 >> A2 >> A3;
  
  cout << max(max(A1,A2),A3) - min(min(A1,A2),A3)<< endl;
 
return 0;
}

Measured memory_bytes: 3624
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <unordered_map>

int main () {

	uint64_t n, m;
	scanf("%llu%llu", &n ,&m);

	std::unordered_map<uint64_t, uint64_t> map;
	map[0] = 1;
	map[1] = 1;
	uint64_t currentMaxA = 1;

	const uint64_t c = 1000000007;

	auto fac = [&map, &currentMaxA] (uint64_t a) -> uint64_t {
		if (a > currentMaxA) {
			for (uint64_t i = currentMaxA + 1; i <= a; ++i) {
				map[i] = (map[i - 1] * (i % c)) % c;
			}
			currentMaxA = a;
		}
		return map[a];
	};

	if (n > m) std::swap(n, m);

	if (m - n > 1) {
		printf("0");
	} else {
		uint64_t d = (m == n) ? 2 : 1;
		printf("%llu", (((fac(m) * fac(n)) % c) * d) % c);
	}

	return 0;

}


Measured memory_bytes: 4388
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std; typedef long long ll;
const int MAXN = 10 + 1e5;
const ll oo = 1 + 1e18, mod = 7 + 1e9;

int n, a[MAXN][5], f[MAXN][5];

int main(){
  #define TASK "ABC"
  #ifndef ONLINE_JUDGE
  freopen(TASK".inp","r",stdin),freopen(TASK".out","w",stdout);
  #endif ONLINE_JUDGE
  ios_base::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);

  cin >> n;
  for (int i = 1; i <= n; i++) for (int j = 1; j <= 3; j++) cin >> a[i][j];

  for (int i = 1; i <= n; i++){
    for (int j = 1; j <= 3; j++){
      for (int k = 1; k <= 3; k++){
        if (j != k) f[i][j] = max (f[i][j], f[i - 1][k] + a[i][j]);
      }
    }
  }

  int ans = 0; for (int i = 1; i <= 3; i++) ans = max (ans, f[n][i]);
  cout << ans;

  return 0;
}


Measured memory_bytes: 7452
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
ll MOD = 1000000007;
//ll INF = 21474836470000000;
ll INF = 1000000000000000000;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

ll H,N;
vector<ll> A(1010),B(1010);
ll dp[1010][23000];

int main(){
    cin >> H >> N;
    rep(i,N){
        cin >> A[i] >> B[i];
    }
    rep(i,23000) dp[0][i] = INF;
    dp[0][0] = 0;
    rep(i,N) {
        rep(j,23000){
            if(j >= A[i]){
                dp[i+1][j] = min(dp[i][j],dp[i+1][j-A[i]]+B[i]);
            }else{
                dp[i+1][j] = dp[i][j];
            }
        }
    }
    ll ans = INF;
    rep(i,10100){
        ans = min(dp[N][H+i],ans);
    }
    cout << ans << endl;
}




Measured memory_bytes: 180480
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n = II()
s = SI()

W = [0]
E = [0]
for c in s:
    W.append(W[-1] + (c == 'W'))
    E.append(E[-1] + (c == 'E'))

e_max = E[-1]
ans = INF
for i in range(1, n + 1):
    ans = min(ans, W[i - 1] + e_max - E[i])

print(ans)


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

int main() {
	int N;
	int n=0;
	cin >> N;
	int m=N;
	for(int i=0; i<9; i++){
		n+=N-N/10*10;
		N=N/10;
	}
	if(m%n==0) cout << "Yes" << endl;
	else cout << "No" << endl; 
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>


using namespace std;

int main()
{
	int N,T,A;
	int H[1001];
	double Temp[1001];
	double diff=0;
	double min = 10000;
	int banch;
	cin >> N;
	cin >> T >> A;
	for (int i = 1; i < N+1; ++i) cin >> H[i];

	for (int j = 1; j < N+1; ++j) {
		Temp[j] = T - H[j] * 0.006;
	}

	for (int k = 1; k < N + 1; ++k) {
		diff = abs(A - Temp[k]);
		if (diff < min) {
			min = diff;
			banch = k;
		}

	}


    cout << banch << endl; 
	return 0;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

const T = 10000000

var n int
var A [101][101]int

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}
func Shortestsearch() {
	var Minimum int
	var d, color [100]int
	var u int

	for i := 0; i < n; i++ {
		d[i] = T
		color[i] = 0
	}

	d[0] = 0
	color[0] = 1

	for {
		Minimum = T
		u = -1
		for i := 0; i < n; i++ {
			if Minimum > d[i] && color[i] != 2 {
				u = i
				Minimum = d[i]
			}
		}
		if u == -1 {
			break
		}
		color[u] = 2
		for j := 0; j < n; j++ {
			if color[j] != 2 && A[u][j] != T {
				if d[j] > d[u]+A[u][j] {
					d[j] = d[u] + A[u][j]
					color[j] = 1
				}
			}
		}
	}
	for i := 0; i < n; i++ {
		fmt.Printf("%d %d\n", i, d[i])
	}
}
func main() {
	sc.Split(bufio.ScanWords)
	n = nextInt()

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			A[i][j] = T
		}
	}
	for i := 0; i < n; i++ {
		u := nextInt()
		k := nextInt()
		for j := 0; j < k; j++ {
			v := nextInt()
			c := nextInt()
			A[u][v] = c
		}
	}
	Shortestsearch()
}



Measured memory_bytes: 1188
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include<limits>
#include<iomanip>

using namespace std;

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

const long double pi = 3.141592653589793;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repi(i, j, n) for(int i = j;i < n;i++)
#define pb push_back
#define mp make_pair
#define mod 998244353
#define F first
#define S second

int main() {


 int n,k;
 cin>>n>>k;
 vector<int> A(n);
 rep(i,n) cin>>A[i];
 sort(A.begin(),A.end());
 int sum=0;
 rep(i,k) sum+=A[i];
 cout<<sum;

  return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PP;
//#define MOD 1000000007
#define MOD 998244353
#define INF 2305843009213693951
//#define INF 810114514
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define all1(i) begin(i),end(i)
#define GOODBYE do { cout << "-1" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false
#define debug2 false


int main(void){
    ll K;
    cin >> K;
    REP(i,K){
        cout << "ACL";
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 3596
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int N = scanner.nextInt();
			int okashi = scanner.nextInt();

			List<Integer> integers = new ArrayList<Integer>();
			for (int i = 0; i < N; i++) {
				integers.add(scanner.nextInt());
			}

			Collections.sort(integers);
			int ans = 0;
			for (int i = 0; i < N; i++) {
				okashi -= integers.get(i);
				if (okashi < 0)
					break;
				if (okashi > 0 && i == N - 1)
					break;
				ans++;
			}
			System.out.println(ans);
		}
	}
}

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

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

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


vector<pair<int,int>> g[100010];
int color[100010];
void dfs(int x, int col){
  if( color[x] != -1 ) return;
  color[x] = col;
  for( auto i : g[x]){
    dfs(i.first, col^(i.second));
  }
}
void solve(long long N, std::vector<long long> u, std::vector<long long> v,
           std::vector<long long> w) {
  memset(color, -1, sizeof(color));
  for(int i = 0 ; i < N-1 ; i++){
    v[i]--;
    u[i]--;
    g[u[i]].push_back({v[i], w[i]%2});
    g[v[i]].push_back({u[i], w[i]%2});
  }
  dfs(0, 0);
  for(int i = 0 ; i < N ; i++){
    cout << color[i] << endl;
  }
}

int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> u(N - 1);
  std::vector<long long> v(N - 1);
  std::vector<long long> w(N - 1);
  for (int i = 0; i < N - 1; i++) {
    scanf("%lld", &u[i]);
    scanf("%lld", &v[i]);
    scanf("%lld", &w[i]);
  }
  solve(N, std::move(u), std::move(v), std::move(w));
  return 0;
}


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

int main() {
  int N,K,ans;
  ans = 1;
  cin >> N >> K;
  
  for(int i;i < N;i++){
    if (ans *2 <= ans + K){
      ans *= 2;
    }else{
      ans += K;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define sar(a,n) {cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl;}

using namespace std;

template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";}
template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;}
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;}
template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;}
template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;}
void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);}
template<typename S,typename T,typename U>
struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){}
bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}};
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";}

typedef pair<int, int> P;
typedef pair<ll, ll> pll;
typedef TRI<int, int, int> tri;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef vector<string> vs;

const int MAX_N = 100005;

long long calc(vector<int>& t)
{
    int w = (int)t.size();
    long long ans = 0;
    t.push_back(0);
    stack<pair<int, int> > st;
    for(int j = 0; j <= w; j++){
        int pos = j;
        while(!st.empty()){
            pair<int, int> p = st.top();
            if(p.second < t[j]) break;
            st.pop();
            ans = max(ans, (long long)p.second * (j - (pos = p.first)));
        }
        st.push({pos, t[j]});
    }
	return ans;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vi h(n);
    rep(i,n){
        cin >> h[i];
    }
    cout << calc(h) << "\n";
    return 0;
}


Measured memory_bytes: 3956
//34
#include<iostream>
#include<algorithm>

using namespace std;

#define INF (1<<28)

int main(){
  for(int n,m;cin>>n>>m,n|m;){
    int d[2][201][201];
    fill(d[0][0],d[2][0],INF);
    while(m--){
      int x,y,t;
      char sl;
      cin>>x>>y>>t>>sl;
      int s=sl=='L';
      d[s][x][y]=d[s][y][x]=min(d[s][y][x],t);
    }
    for(int i=0;i<2;i++){
      for(int j=1;j<=n;j++){
	d[i][j][j]=0;
      }
      for(int j=1;j<=n;j++){
	for(int k=1;k<=n;k++){
	  for(int l=1;l<=n;l++){
	    d[i][k][l]=min(d[i][k][l],d[i][k][j]+d[i][j][l]);
	  }
	}
      }
    }
    int r;
    cin>>r;
    int p[2][201];
    fill(p[0],p[2],INF);
    int s;
    cin>>s;
    p[0][s]=0;
    for(int i=0;i<r-1;i++){
      int z;
      cin>>z;
      int b=i&1;
      fill(p[!b],p[!b+1],INF);
      for(int j=1;j<=n;j++){
	p[!b][j]=min(p[!b][j],p[b][j]+d[1][s][z]);
	for(int k=1;k<=n;k++){
	  p[!b][k]=min(p[!b][k],p[b][j]+d[1][s][j]+d[0][j][k]+d[1][k][z]);
	}
      }
      s=z;
    }
    cout<<*min_element(p[~r&1],p[(~r&1)+1])<<endl;
  }
  return 0;
}
	  

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

int prime[78500],size;

int isPrime(int x){
  int i;
  for(i=0;i<size && prime[i]<=sqrt(x);i++){
    if(x % prime[i] == 0) return 0;
  }
  return 1;
}

void mkPrime(void){
  int i;

  size=1;
  prime[0]=2;

  for(i=3;i<=1000003;i++){
    if(isPrime(i)){
      prime[size++] = i;
    }
  }
}

int main(void){
  int i,n;

  mkPrime();
  while(scanf("%d",&n) != EOF){
    for(i=0;prime[i]<=n;i++);
    printf("%d\n",i);
  }

  return 0;
}

Measured memory_bytes: 584
N = int(input())
A = map(int, input().split())
MOD = 10 ** 9 + 7

cnt = [0] * (N + 1)
cnt[0] = 3

ans = 1
for a in A:
    ans = (ans * cnt[a]) % MOD
    cnt[a] -= 1
    cnt[a + 1] += 1

print(ans)


Measured memory_bytes: 11196
#include<iostream>

using namespace std;

int main(){
    long long int n, luca[90];cin >> n;
    luca[0]=2;
    luca[1]=1;
    for(int i=2;i<=n;i++){
        luca[i] = luca[i-1] + luca[i-2];
    }
    cout << luca[n] << endl;
}

Measured memory_bytes: 256
# ABC134D - Preparing Boxes
# Better ver.
def main():
    n = int(input())
    A = [0] + list(map(int, input().rstrip().split()))
    for i in range(n // 2, 0, -1):  # second half: no multiples
        A[i] = sum(A[i::i]) % 2
    ans = [i for i, j in enumerate(A) if j]
    print(len(ans))  # all cells: [1] -> len() (much faster than sum())
    print(*ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 12720
//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define endl '\n'
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
bool sortbysec(const pair<ll,ll>&a,const pair<ll,ll>&b)
{
    return (a.second<b.second);
}
int main()
{
    ios;
    double a,b;
    cin>>a>>b;
    int ans=0,k=1;
    while(k<b)
    {
        --k;
        k+=a;
        ans++;
    }
    cout<<ans<<endl;



}
//Alhamdulillah











Measured memory_bytes: 3680