akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod=1000000007;
int main() {
	ll i,j,k,l,m,n,t,w;
	ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> w;
 
  vector<pair<ll, ll> > weights(n);
  for (i = 0; i < n; i++){
    cin >> j >> k;
    weights[i] = make_pair(j, k);
  }
 
  vector<vector<ll> > dp(n+1, vector<ll>(w+1,0)), exists(n+1, vector<ll>(w+1,0));
 
 
  ll ans = 0;
  for (i = 0; i < n; i++)
  {
    exists[i][0] = 1;
    for (j = 0; j < w; j++){
      exists[i + 1][j] = 1;
      dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
      ll weight = weights[i].first, value = weights[i].second;
      if (!exists[i][j] || j > w - weight)
      {
        continue;
      }
      dp[i + 1][j + weight] = max(dp[i + 1][j + weight], dp[i][j] + value);
      ans = max(ans, dp[i + 1][j + weight]);
      exists[i + 1][j + weight] = 1;
      // cout << i << ' ' << j << ' ' << exists[i + 1][j + weight] << endl;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 159088
import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int H = scan.nextInt();
		int W = scan.nextInt();
		char[][] s = new char[H][W];
		String inputStr;
		for(int i = 0; i < H; i++) {
			inputStr = scan.next();
			s[i] = inputStr.toCharArray();
		}
		int[][] dist = new int[H][W];
		int firstBlackNum = 0;	// マスの色を変える前の時点での黒いマスの数
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				if(s[i][j] == '#') {
					firstBlackNum++;
				}
				dist[i][j] = -1;
			}
		}
		scan.close();
		ArrayDeque<Point_088_C> que = new ArrayDeque<Point_088_C>();
		// スタート地点の登録
		que.add(new Point_088_C(0,0));
		dist[0][0] = 0;
		Point_088_C v;
		int[] dx = {1, -1, 0, 0};
		int[] dy = {0, 0, 1, -1};
		int nextX, nextY;
		int result;
		while(!que.isEmpty() && dist[H - 1][W - 1] == -1) {
			v = que.poll();
			for(int i  =0; i < 4; i++) {
				nextX = v.x + dx[i];
				nextY = v.y + dy[i];
				// 領域外であればスルー
				if(nextX < 0 || nextY < 0 || nextX >= W || nextY >= H) {
					continue;
				}
				// 黒である場合スルー
				if(s[nextY][nextX] == '#') {
					continue;
				}
				// 探索済みである場合スルー
				if(dist[nextY][nextX] != -1) {
					continue;
				}
				dist[nextY][nextX] = dist[v.y][v.x] + 1;
				que.add(new Point_088_C(nextX, nextY));
			}
		}
		if(dist[H - 1][W - 1] == -1) {
			result = -1;
		}else {
			result = H * W - firstBlackNum - (dist[H - 1][W - 1] + 1);
		}
		System.out.println(result);
	}
}

class Point_088_C{
	int x;
	int y;
	Point_088_C(int x, int y){
		this.x = x;
		this.y = y;
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i= (a); i < (b); ++i)
typedef long long ll;
typedef pair<int,int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int main() { char c;
  cin >> c;
  if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o'){
    puts("vowel");
  }else{
    puts("consonant");
  }
}

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

const int N = 1e3 + 5, mod = 1e9 + 7;

int dp[8192][N], n, m;
pair<int, int> a[N];

int solve(int mask, int i)
{
    if (i == m)
        return mask == ((1 << n) - 1)? 0: 1e9;
    if (dp[mask][i] != -1)
        return dp[mask][i];
    int ans = solve(mask, i + 1);
    if (mask != ((1 << n) - 1))
        ans = min(ans, solve((mask | a[i].second), i + 1) + a[i].first);
    return dp[mask][i] = ans;
}

int main()
{
    //ios::sync_with_stdio(false);cin.tie(nullptr);ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a[i].first;
        int y;
        cin >> y;
        a[i].second = 0;
        while (y--)
        {
            int x;
            cin >> x;
            a[i].second |= (1 << (x - 1));
        }
    }
    memset(dp, -1, sizeof dp);
    int ans = solve(0, 0);
    if (ans > 1e8)
        cout << -1;
    else
        cout << ans;
    return 0;
}

Measured memory_bytes: 35808
#include <stdio.h>
#include <string.h>

const int N = 1300;

int main()
{
    char str[N];

    while (fgets(str, N, stdin))
    {
        int sum = 0;

        if (str[0] == '0')
            break;
        for (int i = 0; i < strlen(str) - 1; i++)
        {
            sum += str[i] - 48;
        }
        printf("%d\n", sum);
    }
}


Measured memory_bytes: 2712
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n;i>=0;i--)
#define For(i,m,n) for(int i=m;i<n;i++)
#define Forr(i,m,n) for(int i=m;i>n;i--)
#define Sort(a) sort(a.begin(),a.end())
#define pb push_back
#define vl vector<ll>
#define vll vector<vector<ll>>
#define INF 999999999999

int main(){
  string S,T,U;
  int A,B;
  cin>>S>>T>>A>>B>>U;
  if(S==U) cout<<A-1<<" "<<B<<endl;
  else cout<<A<<" "<<B-1<<endl;
return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
X, Y, A, B, C = map(int, input().split())
p_list = list(map(int, input().split()))
p_list.sort(reverse=True)

q_list = list(map(int, input().split()))
q_list.sort(reverse=True)

r_list = list(map(int, input().split()))

red_list = p_list[:X]
green_list = q_list[:Y]
min_num = min(red_list[-1], green_list[-1])
white_list = [i for i in r_list if i > min_num]

ans_list = red_list + green_list + white_list
ans_list.sort(reverse=True)
ans_list = ans_list[:X + Y]
print(sum(ans_list))

Measured memory_bytes: 23328
#!/usr/local/bin/ruby
while (n=gets.to_i)!=0
  rec=Array.new
  for i in 1..n
    rec << gets.to_i
  end
  ans = -1000000
    for x in 1..n
    sum = 0
    for y in (x-1)..n
      sum = sum + rec[y].to_i
      if sum > ans
        ans = sum
      end
    end
  end
  puts "#{ans}"
end

Measured memory_bytes: 6120
using System;
//using System.Collections;
//using System.Collections.Generic;
//using System.Linq;

namespace problem
{
  class Test
  {
    static void Main()
    {
      while (true)
      {
        var s = Console.ReadLine().Split();
        if (s[0] == "0" && s[1] == "0") break;
        int H = int.Parse(s[0]);
        int W = int.Parse(s[1]);
        for (int i = 0; i < H; i++)
        {
          for (int j = 0; j < W; j++)
          {
            if ((i + j) % 2 == 1) Console.Write(".");
            else Console.Write("#");
          }
          Console.WriteLine();
        }
        Console.WriteLine();
      }
    }
  }
}


Measured memory_bytes: 8896
#include<iostream>
#include <algorithm>
#include <string>
#include<math.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
int main() {
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a,a+3);
    int ans = 0;
    ans += abs(a[0] - a[1]);
    ans += abs(a[1] - a[2]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <utility>
#include <algorithm>
 
using namespace std;
int main(void){
    // Your code here!
    int N;
    cin >> N;
    vector<int> d;
    
    for(int i =0; i < N; i++){
        int tmp;
        cin >> tmp;
        d.push_back(tmp);
    }
    
    int sum = 0;
    for(int i =0; i < N; i++){
        for(int j =0; j < i; j++){
            sum += d[i] * d[j];
           // cout << d[i] * d[j] << "\t";
        }
        //cout << endl;
    }
    cout << sum << endl;

}


Measured memory_bytes: 256
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
MOD = 10**9 + 7
if k == 1:
    print(0)
    exit()

mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(10 ** 5):
    new_fact = fact[-1] * (i + 1) % mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, mod - 2, mod))


def cmb(n, k, mod=MOD):
    return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod


for max_index in range(k-1, n):
    ans += a[max_index] * cmb(max_index, k-1)
    ans %= MOD

for min_index in range(0, n-k+1):
    ans -= a[min_index] * cmb(n-(min_index+1), k-1)
    ans %= MOD

print(ans)




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

int main(void){
    int s,num[1000001] = {},memo,i = 1;
    cin >> s;
    num[s]++;
    memo = s;
    while( 1 ){
        i++;
        //cout << memo << endl;
        if((memo)%2 == 0){
            memo /= 2;
        } else memo = 3*memo+1;
        if(num[memo] == 1)break;
        num[memo]++;
    }
    cout << i << endl;
}

Measured memory_bytes: 4096
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        String N;
        int firstDigit, ans;
        boolean allNine = true;

        void solve(InputReader in, PrintWriter out) {
            N = in.next();
            firstDigit = Character.getNumericValue(N.toCharArray()[0]);
            for (int i = 1; i < N.length(); ++i) {
                allNine &= N.toCharArray()[i] == '9';
            }

            ans = firstDigit + 9*(N.length() - 1);
            if (!allNine) ans--;

            out.println(ans);
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        int[] nextIntArray(int n) {
        	int[] arr = new int[n];
        	for (int i = 0; i < n; ++i) {
        		arr[i] = nextInt();
        	}
        	return arr;
        }

        long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = nextLong();
            }
            return arr;
        }
    }
}


Measured memory_bytes: 21460
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;

int dp[110][100][310]; //i,j,k i番目まででj個使って，重さの差の和がkの時の最大価値

int main(){
    int N,W,st; cin>>N>>W;
    vector<int> w(N);
    vector<int> v(N);
    cin>>st>>v[0]; w[0]=0;
    for (int i = 1; i <N ; ++i) {
        cin>>w[i]>>v[i];
        w[i]-=st;
    }

    memset(dp,0, sizeof(dp));
    //配るDP
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <=i; ++j) {
            for (int k = 0; k < 310; ++k) {
                dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
                if((ll)st*(j+1)+k+w[i]<=W)dp[i+1][j+1][k+w[i]]=max(dp[i+1][j+1][k+w[i]],dp[i][j][k]+v[i]);
            }
        }
    }

    int ans=-1;
    for (int i = 0; i <=N; ++i) {
        for (int j = 0; j < 310; ++j) {
            ans=max(ans,dp[N][i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 13568
//inlclude前用define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
//#include<deque>
#include<iomanip>
#include<set>
#include<tuple>
#include<map>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef long long int ll;

//define
#define INF 1e9 
#define NUM 1000000007
#define all(x) begin(x), end(x)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
int dp[110][10010]={}; //[v][w]

int main() {
    int N,W;
    cin>>N>>W;
    VI v(N),w(N);
    for(int i=0;i<N;i++){
        cin>>v[i]>>w[i];
    }

    for(int i=0;i<N+1;i++){
        for(int j=0;j<W+1;j++){
            if(j<w[i]){
                //取れないときは前と同じ状態
                dp[i+1][j]=dp[i][j];
            }else{
                //取れるときは取った時と比較してvalueが大きい方
                dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
            }
        }
    }
    cout<<dp[N][W]<<endl;
}




Measured memory_bytes: 7076
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;

int main(void) {
    ll n,x;
    cin>>n>>x;
    ll res = 0;
    res += n;
    ll height = x,width = n-x;
    DEBUG{printf("height : %lld, width : %lld\n", height, width);}
    while(width % height!=0){
        res += height * (width / height) * 2;
        ll tmp = width % height;
        width = height;
        height = tmp;
        DEBUG{printf("height : %lld, width : %lld\n", height, width);}
    }
    res += width * 2 - height;
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int main(){
    int x[5];
    rep(i, 5) cin >> x[i];
    rep(j, 5){
        if(x[j] == 0) cout << j+1 << endl;
    }
}

Measured memory_bytes: 3620
def main():
    import sys

    input = sys.stdin.readline

    inf = (10 ** 5) * (10 ** 3)

    n, m = map(int, input().split())

    dp = [inf] * (1 << n)
    dp[0] = 0

    for _ in range(m):
        cost, _ = map(int, input().split())
        c = (int(x) - 1 for x in input().split())

        mask = 0
        for k in c:
            mask |= 1 << k

        for b in range((1 << n) - 1):
            if dp[b] == inf:
                continue
            nb = b | mask
            dp[nb] = min(dp[nb], dp[b] + cost)

    res = dp[(1 << n) - 1]
    print(-1 if res == inf else res)


if __name__ == '__main__':
    main()


Measured memory_bytes: 41840
#include <stdio.h>
#include <string.h>

typedef long long ll;

char A[200005];

int alphabet[26];
ll sequence[200005];

int main() {

	scanf("%s",A);

	int len = strlen(A);

	int i;

	for (i = 0; i < len; i++) {
		alphabet[A[i]-'a']++;
	}
	sequence[1] = 0ll;
	for (i = 2; i < 200005; i++) {
		sequence[i] = sequence[i - 1] + (ll)(i-1);
	}

	ll len2 = (ll)len;

	ll ans = (len2*(len2 - 1ll) / 2ll) + 1ll;

	for (i = 0; i < 26; i++) {
		if (alphabet[i] >= 2) {
			ans -= sequence[alphabet[i]];
		}
	}

	printf("%lld\n",ans);

	return 0;
}

Measured memory_bytes: 1920
#ABC087C
N=int(input())
A1=list(map(int,input().split()))
A2=list(map(int,input().split()))
ans_tmp=0
ans=0

for i in range(N):
    ans_tmp=0
    for j in range(i+1):
        ans_tmp+=A1[j]
    for k in range(N-i):
        ans_tmp+=A2[N-1-k]
    if ans<ans_tmp:
        ans=ans_tmp
print(ans)

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

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

  int count = 0;
  int dup = 0;
  
  for(int a = 1; a * a < n; ++a)
  {
    for(int b = a; b < n; ++b)
    {
      if(a * b < n)
      {
        if(a == b) dup++;
        else count++;
      }
    }
  }
  
  cout << count * 2 + dup << endl;
}

Measured memory_bytes: 3652
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const ll INF=2e18;
const ll MOD=1e9+7;

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

Measured memory_bytes: 3776
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int K,N,mx=0;
  cin>>K>>N;
  vector<int> A(N);
  for(int &i:A)cin>>i;
  for(int i=0;i<N;i++)mx=max(mx,(A[(i+1)%N]-A[i]+K)%K);
  cout<<K-mx<<endl;
}

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

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


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n,a,b;
    cin >> n >> a >> b;
    if((b - a) % 2 == 0)
    {
        cout << "Alice\n";
    }
    else
    {
        cout << "Borys\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <complex>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
int main() {
	string s;
	cin >> s;
	bool f = 1;
	if (s[0] != 'A')f = 0;
	int cnt = 0, num = 0;
	for (int i = 2; i < s.size() - 1; i++) {
		if (s[i] == 'C') {
			cnt++;
			num = i;
		}
	}
	if (cnt != 1)f = 0;
	for (int i = 0; i < s.size(); i++) {
		if ((s[i] - 'A') >= 0 && (s[i] - 'A') <= 26 && (i != 0 && i != num))f = 0;
	}
	cout << (f ? "AC" : "WA") << endl;
	return 0;
}


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

int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 long long a,b,c;
 cin>>a>>b>>c;
 if(c-a-b<0){
	 cout<<"No";
 }
 else if((c-a-b)*(c-a-b)>4*a*b){
	 cout<<"Yes";
 }
 else{
	 cout<<"No";
 }
}   

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;

int n;

vi seps(string &s){
	vi ans;
	rep(i,1,n) if(s[i] != s[i-1]) ans.push_back(i);
	return ans;
}

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	string s, t;
	cin >> s >> t;

	vi ss = seps(s), tt = seps(t);

	int ans = 1e9;

	rep(dif, -sz(ss)-1, sz(tt)+2) if((dif + (s[0]==t[0]))%2){
		int cur = 0;
		rep(i, min(-dif,0), max(sz(ss), sz(tt)-dif)){
			int j = i + dif;
			int sx = i<0 ? 0 : i<sz(ss) ? ss[i] : n;
			int tx = j<0 ? 0 : j<sz(tt) ? tt[j] : n;
			cur += abs(sx - tx);
		}
		ans = min(ans, cur);
	}
	cout << ans << endl;
}


Measured memory_bytes: 512
#include <cstdio>
#include <cassert>
#include <vector>
using namespace std;

const int N = 100500;

int to[N];
vector<int> E[N];

int ans = 0;
int k;

int DFS(int x, int p = -1) {
    int d = 0;
    for (int y : E[x]) {
        d = max(d, DFS(y, x) + 1);
    }
    assert(d <= k - 1);
    if (x == 0)
        return -42;
    if (p == 0)
        return -42;
    if (d + 1 == k) {
        ans++;
        return -1;
    }
    return d;
}

int main() {
    int n;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &to[i]);
        --to[i];
    }
    int add = 0;
    if (to[0] != 0)
        add = 1, to[0] = 0;
    for (int i = 1; i < n; i++) {
        E[to[i]].push_back(i);
    }
    DFS(0);
    printf("%d\n", add + ans);
}


Measured memory_bytes: 10752
# -*- coding: utf-8 -*-

def main():
    a, b, c, k = map(int, input().split())

    ans = 0

    k1 = k - a
    k1 = max(0, k1)
    ans += k - k1
    k = k1

    if k > 0:
        k1 = k - b
        k1 = max(0, k1)
        k = k1

        if k > 0:
            k1 = k - c
            k1 = max(0, k1)
            ans -= k - k1
            k = k1

    print(f'{ans}\n')

if __name__ == '__main__':
    main()


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

int a[510][510];
int main(){
    int n, m, q; cin >> n >> m>> q;    
    for(int i = 0; i < m; i++){
        int l, r; cin >> l >> r;
        a[l][r]++;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] += a[i][j-1];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] += a[i-1][j];
        }
    }
    for(int i = 0; i < q; i++){
        int l, r; cin >> l >> r;
        cout << a[l-1][l-1] +a[r][r] - a[r][l-1]- a[l-1][r]<< endl;
    }
}

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

int main(){
    int N,M,sum;
     cin >> N >> M;
    sum = N;
    vector<int> homework(M);


    for(int i = 0;i < M; i++){
        cin >> homework.at(i);
    }

    for(int i = 0;i < M;i++){
        if(sum >= homework.at(i))
            sum -= homework.at(i);
        else{
            sum = -1;
            break;
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define p 1000000007
char c[100010];
int sum[1010],n;
int main(){
	
	std::cin>>n;scanf("%s",c+1);
	for(int i=1;i<=n;i++)sum[c[i]-'a']++;
	int ans=1;
	for(int i=0;i<26;i++)ans=1ll*ans*(sum[i]+1)%1000000007;
	std::cout<<(ans+1000000006)%1000000007;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <iomanip>

#define fori(x) for(int i=0;i<x;++i)

// cout << fixed << setprecision(10) << num << endl;

using namespace std;

int main(){
  int h,n;
  cin>>h>>n;
  int a[110000];
  fori(n)cin>>a[i];
  
  int s=0;
  fori(n)s+=a[i];
  cout<<((s>=h)?"Yes":"No");
  return 0;
}

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

int a[10005];

bool hasnum(int k,int n){
    int i=0;
    for(i=0;i<n&&a[i]!=k;i++){

    }
    if (i<n) return true;
    return false;
}

int main(){
    int sum=0;
    int n,q,k;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>k;
        sum+=hasnum(k,n);
    }
    cout<<sum<<endl;
}



Measured memory_bytes: 3120
#include<iostream>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

int main(){
  string s; cin >>s;
  int n=s.size();
  rep(i,n){
    if(s[i]=='?') s[i]='D';
  }
  print(s);
}


Measured memory_bytes: 3720
from itertools import permutations

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

a = 0
b = 0
for i, iter in enumerate(permutations(range(1, N+1))):
    if iter == P:
        a = i
    if iter == Q:
        b = i

print(abs(a-b))


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

string str;
string ans;
int N;

int cal(string s) {
    if (s == "") return 1;
    stringstream ss;
    ss << s;
    int ret;
    ss >> ret;
    return ret;
}

string make_str(string s, int left) {
    if (s.size() == 1) return s;

    string ret;
    string ch;
    string num;
    for (int i = 0, len = s.size(), count = 0; i < len; i++) {
        if (!count && '0' <= s[i] && s[i] <= '9') num += s[i];
        else {
            ch += s[i];
            if (s[i] == '(') count++;
            if (s[i] == ')') count--;
            if (count == 0) {
                if(ch.size() > 0 && ch[0] == '(') {
                    ch.erase(ch.begin());
                    ch.erase(ch.end()-1);
                }

                string tmp = make_str(ch, left + ret.size());
                for (int j = 0, len = cal(num); j < len; j++) {
                    if (ret.size() + left > N + 1) break;
                    ret += tmp;
                }
                ch = "";
                num = "";
            }
        }
    }

    return ret;
}

void calc_char(int c, string s, int sum) {
    string ans_str = make_str(s, N - sum);
    string ans_;
    for (int i = 0; i < c; i++) {
        ans_ += ans_str;
        if (ans_.size() > sum + 1) break;
    }
    ans = ans_[sum];
}

int dfs(string s, int left) {
    if (s.size() == 1) return 1;
    int sum = 0;

    string num;
    string ch;
    for (int i = 0, len = s.size(), count = 0; i < len; i++) {
        if (!count && '0' <= s[i] && s[i] <= '9') num += s[i];
        else {
            ch += s[i];
            if (s[i] == '(') count++;
            if (s[i] == ')') count--;
            if (count == 0) {
                int c = cal(num);
                if(ch.size() > 0 && ch[0] == '(') {
                    ch.erase(ch.begin());
                    ch.erase(ch.end()-1);
                }

                int tmp = dfs(ch, sum + left);
                if (tmp < 0) return -1;
                sum += c * tmp;
                if (sum + left > N) {
                    calc_char(c, ch, N - (sum - c * tmp) - left);
                    return -1;
                }
                ch = "";
                num = "";
            }
        }
    }

    return sum;
}

void solve() {
    ans = "0";

    if (str.size() > 1)
        dfs(str, 0);
    else if (N == 0)
        ans = str;

    cout << ans << endl;
}

int main() {
    while (cin >> str >> N, str != "0" || N) solve();

    return 0;
}

Measured memory_bytes: 7220
#include <iostream>
#include <vector>
using namespace std;
int main(){
    long long N;
    cin >> N;
    for(long long i = 1; i <= 3500; i++){
        for(long long j = 1; j <= 3500; j++){
            long long t = i * j * N;
            long long s = 4 * i * j - N * (i + j);
            if(s != 0 && t % s == 0 && t / s > 0){
                long long w = t / s;
                cout << i << ' ' << j << ' ' << w << endl;
                return 0;
            }
        }
    }
}

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

using ll = int64_t;

#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 ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << std::setprecision(10);

  int n, k; std::cin >> n >> k;
  int ans = 0;
  while (n > 0)
    ans++, n /= k;
  std::cout << ans << "\n";
}


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

const static ll MOD = (1e+9)+7;

int main(){
    ll n;string s;cin>>n>>s;
    vector<ll> s_;
    for(char x:s)s_.push_back(x-'0');
    vector<ll> dim_2(n,0);
    //まず、2桁のパスワードを用意.
    //↓TLE.逆から数えることにする.
    // rep(i,n){
    //     //iより右にいる数字で作れるパスワードをdim_2[i]にいれる。
    //     //まずはmapを作る.
    //     map<ll,ll> cnt;
    //     set<ll> used;
    //     for(int j=i;j<n;j++){
    //         cnt[(ll)s[j]]++;
    //     }
    //     //iから右へ見ていく.
    //     for(int j = i;j<n;j++){
    //         if(used.count((ll)s[j])){
    //             cnt[(ll)s[j]]--;
    //             if(cnt[(ll)s[j]]==0)cnt.erase((ll)s[j]);
    //             continue;
    //         }
    //         used.insert((ll)s[j]);
    //         cnt[(ll)s[j]]--;
    //         if(cnt[(ll)s[j]]==0)cnt.erase((ll)s[j]);
    //         dim_2[i]+=cnt.size();
    //     }
    // }
    //↓後ろから見ていくアルゴリズムに改良する.
    vector<ll> lst(10,0);
    set<ll> used;
    used.insert(s_[n-1]);
    for(int i = n-2;i>=0;i--){
        if(!used.count(s_[i])){
            //今までに登場していない.
            lst[s_[i]] += used.size();
            used.insert(s_[i]);
            dim_2[i] = lst[s_[i]] + dim_2[i+1];
        }else{
            //今までにs_[i]が登場していた場合.
            ll tmp = 0;
            //自分を含めてとりあえずあり得る個数を足す.
            tmp += used.size();
            //そこからいままで作っていた分を引く.
            //2回数えることになるので.
            tmp-=lst[s_[i]];
            //このtmpが2から始まる新しく作られる列の数を表している.
            lst[s_[i]] += tmp;
            dim_2[i] = tmp+dim_2[i+1];
        }
    }

    used.clear();
    ll ans = 0;
    rep(i,n-1){
        if(used.count((ll)s[i]))continue;
        used.insert((ll)s[i]);
        ans += dim_2[i+1];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 912
#include<bits/stdc++.h>
using namespace std;
int n,a[200004],b[200004],i;
int main(){
	cin>>n;
	for(i=0;i<n;i++)cin>>a[i]>>b[i];
	sort(a,a+n);sort(b,b+n);
	if(n%2)cout<<b[n/2]-a[n/2]+1;
	else cout<<(b[n/2-1]+b[n/2])-(a[n/2-1]+a[n/2])+1;
}


Measured memory_bytes: 5192
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main(void)
{
	int a,b,c,d,i,j,k,n,x[5][4][11];
	cin>>n;
	for(i=1;i<=4;i++){
		for(j=1;j<=3;j++){
			for(k=1;k<=10;k++) x[i][j][k]=0;
		}
	}
	for(i=1;i<=n;i++){
		cin>>a>>b>>c>>d;
		x[a][b][c]=x[a][b][c]+d;
	}
	for(i=1;i<=4;i++){
		for(j=1;j<=3;j++){
			for(k=1;k<=10;k++) cout<<" "<<x[i][j][k];
			cout<<endl;
		}
		if(i==4) break;
		cout<<"####################"<<endl;
	}
	
	
	return 0;
}



Measured memory_bytes: 3100
while True:
  n = int(input())
  if n == 0:
    break
  c = 0
  l = []
  d = {}
  for i in range(n):
    num,x,y = map(int,input().split())
    if num in d:
      d[num] = d[num] + x*y
    else:
      d[num] = x*y
      l.append(num)
  for i in l:
    if d[i] >= 1000000:
      print(i)
      c += 1
  if c == 0:
    print('NA')

Measured memory_bytes: 7872
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

string s, S, t;
int res;
bool c[1000000];
ll a, b[2000000], d[1000000], p;

int main() {
	cin >> S >> t;
	while (s.size() < t.size()) {
		s += S;
	}
	s += s;
	p = 1;
	for (char c : t) {
		a = (a * 30 + c - 'a') % mod;
		p = p * 30 % mod;
	}
	for (int i = 0; i < s.size(); ++i) {
		b[i + 1] = (b[i] * 30 + s[i] - 'a') % mod;
	}
	for (int i = 0; i < s.size() / 2; ++i) {
		if ((b[i + t.size()] + mod - b[i] * p%mod) % mod == a) {
			c[i] = true;
		}
	}
	for (int i = 0; i < s.size() / 2; ++i) {
		if (c[i] && !c[(i + t.size()) % (s.size() / 2)]) {
			int cnt = 0;
			int q = i;
			while (c[q]) {
				++cnt;
				c[q] = false;
				q = (q - t.size() + s.size()) % (s.size() / 2);
			}
			res = max(cnt, res);
		}
	}
	for (int i = 0; i < s.size() / 2; ++i) {
		if (c[i]) {
			cout << -1 << endl;
			return 0;
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 21576
func backtrack(_ price: Int, _ points: [Int], _ remained: Int, 
               _ bookIndex: Int, _ prices: [Int], _ bookPoints: [[Int]]) -> Int {
	if remained == 0 {
      return price
    }
  	if bookIndex == prices.count {
    	return Int.max
    }
	
 	let notPick = backtrack(price, points, remained, bookIndex + 1, prices, bookPoints)
  	let nextPrice = price + prices[bookIndex]
  	var remained = remained
  	var points = points
  	for i in 0..<bookPoints[bookIndex].count {
      	let prev = points[i]
  		points[i] -= bookPoints[bookIndex][i]
      	if prev > 0 && points[i] <= 0 {
          remained -= 1
        }
    }
  	let pick = backtrack(nextPrice, points, remained, bookIndex + 1, prices, bookPoints)
  	return min(pick, notPick)
}


let first = readLine()!.split(separator: " ")
let N = Int(first[0])!
let M = Int(first[1])!
let X = Int(first[2])!
var prices: [Int] = .init(repeating: -1, count: N)
var points: [Int] = .init(repeating: X, count: M)
var bookPoints: [[Int]] = .init(repeating: .init(repeating: 0, count: M), count: N)
for i in 0..<N {
  let line = readLine()!.split(separator: " ")
  prices[i] = Int(line[0])!
  for j in 0..<M {
    bookPoints[i][j] = Int(line[j + 1])!
  }
}
let res = backtrack(0, points, M, 0, prices, bookPoints)
print(res == .max ? -1 : res)


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

#define   ll     long long int

const int N = 100005;
ll ara[N], ara2[N], ara3[N];
ll n;

int sign(int x)
{
    if (x == 0) return -2;
    return (x / abs(x));
}

ll func(ll s, ll ara[])
{
    ll i, j, k, sum = 0;
    ll ss;
    ll fl = -sign(s);
    for (i = 2; i <= n; i++) {
        ss = s + ara[i];
        if (ss == 0 || sign(ss) != fl) {
            j = fl - s;
            sum += abs(j - ara[i]);
            ara[i] = j;
        }
        s = s + ara[i];
        fl = -fl;
    }
    return sum;
}

int main( )
{
    ll i, j;
    ll s = 0;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> ara[i];
        ara2[i] = ara[i];
        ara3[i] = ara[i];
    }
    if (ara[1] == 0) {
        cout << (1 + min(func(-1, ara), func(1, ara2))) << '\n';
    }
    else {
//        cout << abs(-1 - ara[1]) + func(-1, ara) << '\n';
//        cout << abs(+1 - ara2[1]) + func(+1, ara2) << '\n';
//        cout << func(ara3[1], ara3) << '\n';
        cout << min( abs(-1 - ara[1]) + func(-1, ara), min( abs(+1 - ara2[1]) + func(+1, ara2), func(ara3[1], ara3) ) ) << '\n';
    }
    return 0;
}


/**

        cout << abs(-1 - ara[1]) + func(-1) << '\n';
        cout << abs(+1 - ara[1]) + func(+1) << '\n';
        cout << func(ara[1]) << '\n';
        cout << min(abs(-1 - ara[1]) + func(-1), min( abs(1 - ara[1]) + func(1),    func(ara[1]))) << '\n';


**/

Measured memory_bytes: 2560
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const double PI = acos(-1);

ll dp[110][510] = {};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/

	ll N, W;
	cin >> N >> W;

	vector<ll> w(N), v(N);
	rep(i, N) cin >> w[i] >> v[i];

	ll sum = 0;
	rep(i, N) {
		ll ww = w[i] - w[0];
		//同じ荷物を複数回使わないように
		for (int j = i; j >= 0; j--) {
			for (int k = sum; k >= 0; k--) {
				chmax(dp[j + 1][k + ww], dp[j][k] + v[i]);
			}
		}
		sum += ww;
	}

	ll ans = 0;
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= sum; j++) {
			if (w[0] * i + j > W) continue;
			chmax(ans, dp[i][j]);
		}
	}

	out(ans);

	return 0;
}

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

int main () {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int N, x; cin >> N >> x;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i];
    long long ans = 0;
    for (int i = 0; i < N-1; ++i) {
        if (a[i] + a[i+1] > x) {
            ans += min(a[i+1], a[i+1] + a[i] - x);
            a[i+1] -= min(a[i+1], a[i+1] + a[i] - x);
            if (a[i] + a[i+1] > x) 
                ans += a[i+1] + a[i] - x;
            
        }
    }

    cout << ans << '\n';

    return 0;
}



Measured memory_bytes: 3920
#include <stdio.h>

int main(void)
{
	int l, m, n;
	int i, ct;
	
	while (scanf("%d", &l), l){
		ct = 0;
		for (i = 0; i < 12; i++){
			scanf("%d %d", &m, &n);
			if (l > 0){
				l -= (m - n);
				ct++;
			}
		}
		if (l > 0){
			printf("NA");
		}
		else {
			printf("%d", ct);
		}
		printf("\n");
	}
	return (0);
}

Measured memory_bytes: 604
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc_168b
{
    class Program
    {
        static void Main(string[] args)
        {
            int kazu = int.Parse(Console.ReadLine());
            string moji = Console.ReadLine();

            if(moji.Length <= kazu)
            {
                Console.WriteLine(moji);
            }
            else
            {
                string res = moji.Substring(0, kazu);

                Console.WriteLine(res + "...");
            }
            
            Console.Read();
        }
    }
}


Measured memory_bytes: 27500
/*
  Author - KISHAN TIWARI
  Dream bigger. Do bigger.
  Wake up with determination. Go to bed with satisfaction.
*/
//Sometimes later becomes never. Do it now.
#include<bits/stdc++.h>
using namespace std;
#define ll           long long
#define f(i,a,b)     for(ll i=a;i<b;i++)
#define mod          1000000007
#define fi           first
#define se           second
#define pa           pair <ll,ll>
#define mp           make_pair
#define pb           push_back
#define ve           vector<ll>
#define vep          vector< pa >
#define all(a)       a.begin(), a.end()
#define sz(x)        (ll)x.size()
#define c(t)         cout<<t<<"\n"
using namespace std;
void solve()
{  ll n;
cin>>n;
ll a[n+1],b[n+1],c[n];
f(i,1,n+1)
cin>>a[i];
f(i,1,n+1)
cin>>b[i];
f(i,1,n)
cin>>c[i];
ll su=0;
f(i,1,n)
{
    su+=b[a[i]];
    if(a[i]+1==a[i+1])
     su+=c[a[i]];
}
su+=b[a[n]];
c(su);
}
int main()
{
    ios::sync_with_stdio(true);
   //freopen ("input.txt","r",stdin);
   //freopen ("output.txt","w",stdout);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    //cin>>t;
    while(t--)
    {

        solve();
    }
return 0;
}


Measured memory_bytes: 256
N, M, Q = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
for a in range(1, M+1):
    for b in range(a, M+1):
        for c in range(b, M+1):
            for d in range(c, M+1):
                for e in range(d, M+1):
                    for f in range(e, M+1):
                        for g in range(f, M+1):
                            for h in range(g, M+1):
                                for i in range(h, M+1):
                                    for j in range(i, M+1):
                                        tmp = 0
                                        MM = [a, b, c, d, e, f, g, h, i, j][:N]
                                        for ai, bi, ci, di in A:
                                            if MM[bi-1]-MM[ai-1] == ci:
                                                tmp += di
                                        ans = max(ans, tmp)
print(ans)



Measured memory_bytes: 9192
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		int a,b,c;
		int t=0;
	    try (Scanner sc = new Scanner(System.in)) {
	    	a = sc.nextInt();
	    	b = sc.nextInt();
	    	c = sc.nextInt();
	    }

	    for(int i=a; i<=b; i++) {
	    	if(c%i == 0) {
	    		t++;
	    	}
	    }

	    System.out.println(t);
	}

}



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

#define M 1000000007

int64_t mpow(int64_t x, int64_t n) {
    x=x%M;
    if(n==0) return 1;
    else if(n%2==1) {
        return (x*mpow(x,n-1))%M;
    } 
    else return mpow((x*x)%M, n/2)%M;
}

int64_t con(int m, int n) {
    int64_t ans = 1;
    int64_t a = 1;
    int64_t b = 1;
    int64_t c = 1;

    for(int i=1; i<=m; i++) {
        a *= i;
        a = a%M;
    }

    for(int i=1; i<=n; i++) {
        b *= i;
        b = b%M;
    }
    b = mpow(b, M-2);

    for(int i=1; i<=m-n; i++) {
        c *= i;
        c = c%M;
    }
    c = mpow(c, M-2);

    ans = a;
    ans *= b;
    ans = ans%M;
    ans *= c;
    ans = ans%M;

    return ans;
}


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

    if((x+y)%3!=0) {
        cout<<0<<endl;
    }
    else if(fabs(x-y) > (x+y)/3) {
        cout<<0<<endl;
    }
    else {
        int m = (x+y)/3;
        int n = (m-fabs(x-y))/2;

        int64_t ans = con(m,n);

        ans = ans%M;

        cout<<ans<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
n = ARGF.gets.strip.to_i
travel_plan = ARGF.readlines.collect{|i| i.split(/\s+/).collect{|j| j.strip.to_i}}
travel_plan.unshift([0, 0, 0])

travel_plan.each_cons(2) do |previous, following|
  t1, x1, y1 = *previous
  t2, x2, y2 = *following

  time = t2 - t1
  distance = (x2 - x1).abs + (y2 - y1).abs

  next if distance - time == 0

  if distance > time or (time - distance).odd?
    puts 'No'
    exit
  end
end

puts 'Yes'


Measured memory_bytes: 27980
#include<bits/stdc++.h>
using namespace std;
#define MAXN	1000005
#define P	1000000007
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
long long f[MAXN], s[MAXN], n;
int main() {
	read(n);
	f[0] = 1; f[1] = n;
	s[0] = 1; s[1] = n + 1;
	for (int i = 2; i <= n; i++) {
		f[i] = (s[i - 1] + (n + 1 - i) + (n - 1) * (n - 1) - f[i - 2] + P) % P;
		s[i] = (s[i - 1] + f[i]) % P;
	}
	cout << f[n] << endl;
	return 0;
}

Measured memory_bytes: 15872
#include <stdio.h>
int main(void)
{
   int i,j,h,w;
    
   while(1){
      scanf("%d %d",&h,&w);
      if(h == 0 && w == 0) break;
    
      for(i = 0; i < h; i++) {
        for(j = 0; j < w; j++){
           if(i == 0 || i == h-1 || j == 0 || j == w-1){
              printf("#");
           }
           else printf(".");
        }
        printf("\n");
      }
      printf("\n");
   }
        return 0;
}           

Measured memory_bytes: 572
#include <vector>
#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <cmath>
#include <utility>
#include <bitset>
#include <complex>
#include <stack>
#include <tuple>
 
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll INF = 1e7;
const ll MOD = (1e9)+7;
const ll MAX_N = 1 << 17;

int main(){
	ll A,B;
	cin >> A >> B;
	cout << (A+B)%24 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <fstream>

using namespace std;

#define ll long long
#define INF 2000000000
#define LINF 2000000000000000000
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define dum(x) cout<<#x<<'='<<x<<endl
#define dum2(x,y) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<'\n'<<endl
#define dum3(x,y,z) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<'\n'<<endl
#define darr(arr,n) rep(i,(n-arr)){cout<<*(arr+i)<<' ';}cout<<endl

//ifstream in("Text.txt");cin.rdbuf(in.rdbuf());

ll t[200020];

int main() {
    int N, T;
    cin >> N >> T;
    rep(i, N)cin >> t[i];

    ll sum = 0;
    for (int i = 0; i < N-1; i++) {
        if (t[i] + T > t[i + 1])sum += t[i + 1] - t[i];
        else sum += T;
    }
    cout << sum+T << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

ll MOD = 998244353;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    vector<vector<ll>> dp(c, vector<ll>(d, 0));
    dp[a-1][b-1] = 1;
    for(int i = b; i < d; i++)dp[a-1][i] = dp[a-1][i-1] * a % MOD;
    for(int i = a; i < c; i++)dp[i][b-1] = dp[i-1][b-1] * b % MOD;
    for(int i = a; i < c; i++){
        for(int j = b; j < d; j++){
            dp[i][j] = (dp[i][j] + dp[i-1][j] * (j+1) % MOD) % MOD;
            dp[i][j] = (dp[i][j] + dp[i][j-1] * (i+1) % MOD);
            dp[i][j] = (dp[i][j] - dp[i-1][j-1] * (i * j % MOD) % MOD + MOD) % MOD;
        }
    }
    cout << dp[c-1][d-1] << endl;
}

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

int main()
{
    ll s, size, j, K, k;
    cin >> s >> K;

    int i = 0;
    while (s >= K)
    {
        s /= K;
        i++;
    }
    i++;

    cout << i << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
  
using namespace std;
  
typedef pair<int,int> P;
vector<P> vec;
  
void change(int p, int S, int l){
    vector<P> tmp;
    int Next = vec[p].second - S;
  
    for(int i = 0 ; i < p ; i++){
	tmp.push_back(vec[i]);
    }
  
    tmp.push_back(P(l, S));
    tmp.push_back(P(-1,Next));
  
    for(int i = p+1 ; i < vec.size() ; i++){
	tmp.push_back(vec[i]);
    }
    vec = tmp;
}
  
void Wri(){
    int len = vec.size(), l, S;
  
    cin >> l >> S;
  
    if(len == 0){
	vec.push_back(P(l,S));
	return;
    }
  
    for(int i = 0 ; i < len ; i++){
	if(vec[i].first == -1){
	    if(S - vec[i].second >= 0){
		vec[i].first = l;
		S -= vec[i].second;
	    }else{
		change(i, S, l);
		return;
	    }
	}
    }
  
    if(S > 0){
	vec.push_back(P(l,S));
    }
}
  
void Del(){
    int len = vec.size(), l;
  
    cin >> l;
    if(len == 0){
	return;
    }
  
    for(int i = 0 ; i < len ; i++){
	if(vec[i].first == l){
	    vec[i].first = -1;
	}
    }
}
  
int Ref(){
    long long cnt = 0;
    int len = vec.size(), l, num = vec[0].first;
  
    cin >> l;
    if(len == 0){
	return -1;
    }
  
    for(int i = 0 ; i < len ; i++){
	cnt += vec[i].second;
	num = vec[i].first;
      
	if(cnt > l){
	    return num;
	}
    }
  
    if(cnt <= l){
	return -1;
    }else{
	return vec[len-1].first;
    }
}
  
int main(){
    int N;
    char ch;
  
    while(cin >> N, N){
	vec.clear();
	for(int i = 0 ; i < N ; i++){
	    cin >> ch;
  
	    switch(ch){
	    case 'W':
		Wri();
		break;
	    case 'D':
		Del();
		break;
	    default:
		cout << Ref() << endl;
		break;
	    }
	}
	cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3104