akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
//Optimisations
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("O2")
//shortcuts for functions
#define pb push_back
#define mp make_pair
#define ff first 
#define ss second
#define all(v) v.begin(),v.end()
#define prec(n) fixed<<setprecision(n)
#define n_l '\n'
// make it python 
#define gcd __gcd
#define append push_back
#define str to_string
// utility functions shortcuts
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define sswap(a,b) {a=a^b;b=a^b;a=a^b;}
#define swap(a,b) {auto temp=a; a=b; b=temp;}
#define init(dp) memset(dp,-1,sizeof(dp));
#define set0(dp) memset(dp,0,sizeof(dp));
#define bits(x) __builtin_popcount(x)
#define SORT(v) sort(all(v))
#define endl "\n"
#define forr(i,n) for(ll i=0;i<n;i++)
// declaration shortcuts
typedef long long int ll;
#define int ll
// Constants
constexpr int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};
constexpr ll INF = 1999999999999999997; 
constexpr int inf= INT_MAX;
constexpr int MAXSIZE = int(1e6)+5;
constexpr auto PI  = 3.14159265358979323846L;
constexpr auto oo  = numeric_limits<int>::max() / 2 - 2;
constexpr auto eps = 1e-6;
constexpr auto mod = 1000000007;
constexpr auto MOD = 1000000007;
constexpr auto MOD9 = 1000000009;
constexpr auto maxn = 100006;
//void IOfile(){
//freopen(file_name, reade_mode, stdin);
//freopen(file_name, write_mode, stdout);
//}
void fastio(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
int32_t main(){
	fastio();
	int n , m;
	cin >> n >> m;
	int s = 0;
	for(int i = 0; i < m; i++){
		int x;
		cin >> x;
		s += x;
	}
	n-s>=0 ? cout << n-s : cout << -1; 
}

Measured memory_bytes: 3524
#!python3

from itertools import accumulate

def my_bisect(a, x, key, lo=0, hi=None, side="left"):
    if hi is None:
        hi = len(a)

    lov = key(a[lo])
    hiv = key(a[hi])

    if side == "left":
        while lo < hi:
            mid = (lo + hi) // 2
            miv = key(a[mid])

            if miv < val: lo, lov = mid+1, miv
            else: hi, hiv = mid, miv
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            miv = key(a[mid])

            if val < miv: hi, hiv = mid, miv
            else: lo, lov = mid+1, miv

    return lo

from bisect import bisect_right

def resolve():
    N, M = map(int, input().rstrip().split())
    a = list(map(int, input().rstrip().split()))

    a.sort(reverse=True)
    b = list(accumulate(a))
    c = [-i for i in a]

    def count_shake(z):
        n = 0
        for i, x in enumerate(a):
            y = x - z
            #j = my_bisect(a, y, lambda x: -x, lo=i, side="right")
            j = bisect_right(c, y, i)
            if i == j:
                break
            n += 2 * (j - i) - 1
        return n



    lo = a[-1] * 2
    hi = a[0] * 2

    while True:
        mid = (lo + hi) // 2
        x = count_shake(mid)

        if hi - lo <= 1:
            break
        if x < M: hi = mid
        else: lo = mid

    s = 0
    d = [-1] * N
    m = x
    for i, x in enumerate(a):
        y = x - mid
        j = bisect_right(c, x - mid)
        if j == 0: break
        d[i] = j-1
        s += b[j-1] + x * j

    print(s - mid * (m-M))




if __name__ == "__main__":
    resolve()


Measured memory_bytes: 20140
#include <iostream>

int main () {
  char b;
  std::cin >> b;
  switch(b)
  {
    case 'A':
      std::cout << 'T' << std::endl;
      break;
    case 'C' :
      std::cout << 'G' << std::endl;
      break;
    case 'G' :
      std::cout << 'C' << std::endl;
      break;
    case 'T' :
      std::cout << 'A' << std::endl;
      break;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main() {
  ios::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;

  vector<int> cnt(N+1, 0);

  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    cnt[a]++;
    cnt[b]++;
  }

  for(int i = 1; i <= N; i++) {
    cout << cnt[i] << "\n";
  }

  return 0;
}


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

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

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding:utf-8 -*-
w = int(input())
n = int(input())
v_lines = [i for i in range(1,w+1)]
for i in range(n):
    a,b = list(map(int, input().split(',')))
    t = v_lines[a-1]
    v_lines[a-1] = v_lines[b-1]
    v_lines[b-1] = t
for i in range(len(v_lines)):
    print(v_lines[i])

Measured memory_bytes: 7728
import numpy as np
import math
from functools import reduce

# K = int(input())
# N, K = map(int, input().split())
# A = list(map(int, input().split()))

def gcd(a: int, b: int): return gcd(b, a % b) if b else a

N, X = map(int, input().split())
x = list(map(int, input().split()))

d = np.zeros(N, dtype=int)
for n in range(N):
    d[n] = x[n] - X

ret = abs(reduce(gcd, d))

# print(d)
print(ret)


Measured memory_bytes: 23104
#include <bits/stdc++.h>
#include <atcoder/all>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int t;
  cin >> t;
  rep(ti,t) {
    int n,m,a,b;
    cin >> n >> m >> a >> b;
    cout << atcoder::floor_sum(n,m,a,b) << endl;
  }
  return 0;
}

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

int main(){
  
  string a;
  long long int b;
  cin >>a >> b;
  
  
  
 for(int i=0;i<a.size();i++){
   if(i+1 == b &&a[i] == '1'){
     cout << '1' << endl;
     
     return 0;
   }
  else if(a[i] != '1'){   
  
  cout << a[i] << endl;
   
   return 0;
 }
 }
}


Measured memory_bytes: 256
N = int(input())
P = ''.join(input().split())
Q = ''.join(input().split())

candidate = []
candidates = []

for i in range(1, N+1):
    candidate.append(str(i))

import itertools
for p in itertools.permutations(candidate, N):
    candidates.append(''.join(p))

candidates.sort()

a = candidates.index(P)
b = candidates.index(Q)

print(str(abs(a-b)))


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

using namespace std;

string s;
int ans[100010];
int pl[100010];//place of RL 1:R  2:L  0:nothing
int jr[100010];
int jl[100010];
int ne[100010];

int main()
{
	cin>>s;
//	cout<<s[0]<<endl;
	int l=s.length();
	int now=0;
	int cnt=0;
	
	
	for (int i=0;i<l;i++)
	{
		if (s[i+1]=='L' && s[i]=='R') 
		{
			pl[i]=1;
			pl[i+1]=2;
			cnt++;
			jr[cnt]=i;
			jl[cnt]=i+1;
		}
	}
	
	now=1;
	ne[jr[now]]=0;
	ne[jl[now]]=0;
	for (int i=0;i<l;i++)
	{
		if (i==jr[now] || i==jl[now]) continue;
		if (i>jl[now]&&now<=cnt)
		{
			now++; 
			if (now<=cnt)
			{
				ne[jr[now]]=0;
				ne[jl[now]]=0;	
			}
		}
		if (s[i]=='R') ne[i]=jr[now]-i;
		if (s[i]=='L') ne[i]=i-jl[now-1];
//		cout<<i<<' '<<ne[i]<<endl;
	}
	
	
	for (int i=0;i<l;i++)
	{
	//	cout<<s[i]<<' '<<i<<endl;
		if (s[i]=='R')
		{
//			cout<<2<<endl;
			if (pl[i]!=1) ans[i]=0;
			int cha=ne[i];
	//		cout<<cha<<' '<<i<<endl;
			if (cha % 2==0) ans[i+cha]++;
			else ans[i+cha+1]++;
		}
		if (s[i]=='L')
		{
//			cout<<3<<endl;
			if (pl[i]!=2) ans[i]=0;
			int cha=ne[i];
	//		cout<<cha<<endl;
			if (cha % 2==0) ans[i-cha]++;
			else ans[i-cha-1]++;
		}
	}
	for (int i=0;i<l;i++) 
	{
		cout<<ans[i];
		if (i!=l-1) cout<<' '; 
	}
	cout<<endl;
}

Measured memory_bytes: 2176
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
N,K = map(int,input().split())
Z = list(map(int,input().split()))
A = [1 for _ in range(N+1)]
for i in range(2,N+1):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(N+1)]
B[N] = pow(A[N],p-2)
for i in range(N-1,1,-1):
    B[i] = (B[i+1]*(i+1))%p
def f(n,k):
    if k>n:
        return 0
    return (A[n]*B[k]*B[n-k])%p
X = sorted(Z,reverse=True)
X.insert(0,0)
ans = 0
for i in range(1,N-K+2):
    ans = (ans+X[i]*f(N-i,K-1))%p
Y = sorted(Z)
Y.insert(0,0)
for i in range(1,N-K+2):
    ans = (ans-Y[i]*f(N-i,K-1))%p
print(ans)

Measured memory_bytes: 100980
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <math.h>
using namespace std;
 
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define EPS 1e-9
#define PI acos(-1)
 
using ll = unsigned long long;
using pll = pair<ll,ll>;
using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;
using vll = vector<ll>;
using ui = unsigned int;


int main() {
    ofstream out("output.txt");
    ios_base::sync_with_stdio(false);
    

    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    for(int i =0;i<n;i++){
        cout<<s[i]<<""<<t[i];
    }

    return 0;
}   


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main() {
	ios::sync_with_stdio(false);
	cin >> a >> b;
	if(!(a % 3) || !(b % 3) || !((a + b) % 3))
		cout << "Possible\n";
	else
		cout << "Impossible\n";
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ std::cin >> head; _cin(std::forward<Tail>(tail)...); }
void _cout(){ std::cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ std::cout << head; _cout(std::forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Vec2(T, n, m, xs) vector<vector<T>> xs(n, vector<T>(m))
#define Sum(a) accumulate(Range(a), 0)
#define Cusum(T, n, xs, sxs) vector<T> sxs(n+1); For(i, n) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) for(const auto &e : xs) cout << e << " "; cout << "\n"
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")

using namespace std;
using ll = long long;

int main(void){
    Cin(string, s);
    Cout(s.size() - Search(s.rbegin(), s.rend(), 'Z') - Search(s.begin(), s.end(), 'A'));
}


Measured memory_bytes: 640
//#include<bits/stdc++.h>	// 全てのヘッダーファイルをinclude
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#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++)
const int MOD{ int(1e9 + 7) };	// int 1000000007
const int inf{ int(1e9) };	// inf = 1000000000 // 1e9 はdouble型
using namespace std;
typedef long long ll;

int main(void) {

	string w;
	cin >> w;

	map <char, int> a = {};
	REP(i, w.size()) {
		a[w[i]]++;
	}
	REP(i, 25) {
		if (a[w[i]] % 2 == 1) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

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

namespace ABC110 {
	class ABC110_A {
		static void Main(string[] args) {
			var input = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
			var MAX = input.Max();
			input.Remove(MAX);
			Console.WriteLine(input.Sum() + MAX * 10);
		}
	}
}


Measured memory_bytes: 13280
#include <stdio.h>

#define M 25

struct A{
  int parent;
  int left;
  int right;
};

struct A B[M];
int C[M], D[M];

void Depth(int i, int d);
int Height(int i); 
int pick(int i);
void pr(int i);

int main(void) {
  int n,i,d,le,ri;
  scanf("%d", &n);
  
  for (i = 0; i < M; i++) {
    
    B[i].parent = -1;
    B[i].left = -1;
    B[i].right = -1;
  }

  for (i = 0; i < n; i++) {

    scanf("%d %d %d", &d, &le, &ri);
    B[d].left = le;
    B[d].right = ri;
    if (le != -1) B[le].parent = d;
    if (ri != -1) B[ri].parent = d;
  }

  for (i = 0; i < n; i++) {
    if (B[i].parent == -1) ri = i;
  }

  Depth(ri, 0);
  Height(ri);

  for (i = 0; i < n; i++) {
    pr(i);
  }

  return 0;
}
void Depth(int a, int b) {
  if (a == -1) return;
  D[a] = b;
  Depth(B[a].left, b+1);
  Depth(B[a].right, b+1);
}
int Height(int a) {
  int b1 = 0, b2 = 0;
  if (B[a].left != -1) {
    b1 = Height(B[a].left) + 1;
  }
  if (B[a].right != -1) {
    b2 = Height(B[a].right) + 1;
  }

  if (b1 >= b2) {
    return C[a] = b1;
  } else {
    return C[a] = b2;
  }
}
int pick(int a) {
  if (B[a].parent == -1) return -1;
  if (B[B[a].parent].left != a && B[B[a].parent].left != -1) {
    return B[B[a].parent].left;
  }
  if (B[B[a].parent].right != a && B[B[a].parent].right != -1) {
    return B[B[a].parent].right;
  }
  return -1;
}
void pr(int a) {
  printf("node %d: ", a);
  printf("parent = %d, ", B[a].parent);
  printf("sibling = %d, ", pick(a));

  int c;
  c = 0;
  if (B[a].left != -1) c++;
  if (B[a].right != -1) c++;
  printf("degree = %d, ", c);

  printf("depth = %d, ", D[a]);
  printf("height = %d, ", C[a]);

  if (B[a].parent == -1) {
    printf("root");
    printf("\n");
  } else if (B[a].left == -1 && B[a].right == -1) {
    printf("leaf");
    printf("\n");
  } else {
    printf("internal node");
    printf("\n");
  }
}



Measured memory_bytes: 2144
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#include<iomanip>
#define int long 
using namespace std;

signed main() {
	int N;
	cin >> N;
	vector<int> vec(N);
	for(int i = 0;i < N;i++) {
		vec.at(i) = i + 1;
	}
	vector<int> A(1001);
	for(int i = 0;i < N;i++) {
		for(int j = 2;j < 1001;j++) {
			while(vec.at(i) % j == 0) {
              	vec.at(i) = vec.at(i) / j;
              	A.at(j - 2)++;
            }
		}
	}
	int answer = 1;
	for(int i = 0;i < 1001;i++) {
		answer = answer * (A.at(i) + 1) % 1000000007;
	}
	cout << answer << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	
	long long  n,i,sum;
	cin>>n;
	sum=0;
	for(i=1;i<=n;i++)
	{
		if(i%5!=0 && i%3!=0)
		{
			sum=sum+i;
		}
	}
	cout<<sum<<endl;
return 0;
}

Measured memory_bytes: 3192
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <bitset>
#include <iomanip>
#include <deque>
#include <tuple>
#include <algorithm>

using namespace std;

int main()
{
    int num[3];

    cin >> num[0] >> num[1] >> num[2];

    sort(num, num+3);

    if (num[2] == num[0]+num[1]) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

int main() {
string s, vs;
vs = "CODEFESTIVAL2016";
cin >> s;
int ans = 0;
for ( int i = 0 ; i < s.length() ; i ++ )
    if (s[i] != vs[i]) ans ++;
cout << ans << endl;
}

Measured memory_bytes: 256
//
//AtCoder Beginner Contest 136
//C - Build Stairs
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;

const double PI = 3.14159265358979323846;

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

int main()
{
    string s;
    cin >> s;

    int len = s.size();
    vector<int> ans(len, 0);

    char flag = 'R';
    int rCnt = 0;
    int lCnt = 0;
    int idx = -1;
    s+="R";
    REP(i, len){
        if (s[i]=='R') {rCnt++;lCnt=0;}
        if (s[i]=='L') {rCnt=0;lCnt++;}
        if (s[i]=='R' && s[i+1]=='L'){
            ans[i] += (rCnt/2 + rCnt%2);
            ans[i+1] += rCnt/2;
            idx = i;
        }
        if (s[i]=='L' && s[i+1]=='R'){
            ans[idx] += lCnt/2;
            ans[idx+1] += (lCnt/2+lCnt%2);
        }
    }
    for(int v: ans) cout << v << " ";
    cout << endl;
    return 0;
}


Measured memory_bytes: 1024
/*input
5
2 1 5 4 3
*/

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

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

    ll ans = 0;
    int ma = 0;
    rep(i, n) {
        int a;
        cin >> a;
        if (a < ma) ans += ma-a;
        else ma = a;
    }
    cout << ans << endl;
}

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

using namespace std;

typedef long long llint;

const int MAXN = 200005;
const int OFS = 2002;
const int LIM = 4010;
const int MOD = 1000000007;

llint n, sol;
int a[MAXN], b[MAXN];
llint dp[LIM][LIM];
int nck[LIM*2][LIM];

void precompute () {
    for (int i=0; i<LIM*2; i++) {
        nck[i][0] = nck[i][i] = 1;
        for (int j = 1; j < min(i, LIM-1); j++) {
            nck[i][j] = (nck[i-1][j] + nck[i-1][j-1]) % MOD;
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> a[i] >> b[i];
        dp[OFS - a[i]][OFS - b[i]]++;
    }
    for (int i=1; i<LIM; i++) {
        for (int j=1; j<LIM; j++) {
            dp[i][j] = (dp[i][j] + dp[i][j-1] + dp[i-1][j]) % MOD;
        }
    }
    precompute();
    for (int i=0; i<n; i++) {
        sol += dp[OFS + a[i]][OFS + b[i]];
        sol -= nck[a[i]*2 + b[i]*2][a[i]*2];
        sol = (sol % MOD + MOD) % MOD;
    }
    cout << sol * (MOD + 1)/2 % MOD;
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    int a,b;
    int flag = 0;
    string ans = "No";
    for (int i = 0; i < n; i++){
        cin >> a >> b;
        if (a==b){
            flag++;
        }else{
            flag = 0;
        }

        if (flag == 3){
            ans = "Yes";
        }

    }
    cout << ans << endl;
}

Measured memory_bytes: 3600
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author zyc
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int h = in.nextInt(), w = in.nextInt();

            if (h % 3 == 0 || w % 3 == 0) {
                out.println(0);
            } else {
                int res = Integer.MAX_VALUE;

                if (h > 2) res = Math.min(res, w);
                if (w > 2) res = Math.min(res, h);
                int tmp = Math.min(gao(h, w), gao(w, h));
                out.println(Math.min(res, tmp));
            }
        }

        private int gao(int h, int w) {
            int base = h / 3, remain = h % 3;
            int res = Integer.MAX_VALUE;
            for (int i = 0; i <= remain; ++i) {
                int first = w * (base + i), second, third;
                if (w % 2 == 0) {
                    second = third = (h - base - i) * (w / 2);
                    res = Math.min(res, Math.abs(first - second));
                } else {
                    second = (h - base - i) * (w / 2);
                    third = (h - base - i) * w - second;
                    int lower = Math.min(first, second), upper = Math.max(first, third);
                    res = Math.min(res, upper - lower);
                }
            }
            return res;
        }

    }
}



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

typedef long long ll;


int main() {
  string n;
  cin >> n;
  for(int i=0; i<n.length(); i++){
    if(n[i]=='1') n[i]='9';
    else if(n[i]=='9') n[i]='1';
  }

  cout << n << endl;
}

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

#define int long long
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define fs first
#define sc second
#define mpr make_pair
#define iter iterator
#define all(X) X.begin(),X.end()
#define sau(X) sort(all(X)),X.resize(unique(all(X))-X.begin())
#define exist(X,ele) binary_search(all(X),ele)

main()
{
	ios::sync_with_stdio(false);
	
	int H,W,N; cin>>H>>W>>N;
	if(!(N%(max(H,W)))) cout<<N/max(H,W);
	else cout<<N/max(H,W)+1;
	
	return 0;
}






















Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    ll N;
    cin >> N;
    vector<ll> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    ll s = 0;
    for (ll i = 0; i < N; i++) {
        s  = (s + a[i]) % MOD;
    }

    ll ans = 0;
    ll tmp;
    for (ll i = 0; i < N; i++) {
        tmp = (MOD + s - a[i]) % MOD;
        ans = ans + tmp * a[i];
        ans = ans % MOD;
    }

    vector<ll> inv(3); inv[1] = 1;
    for (int i = 2; i < 3; i++) {
        inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
    }   
    ans = ans * inv[2] % MOD;

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

}

Measured memory_bytes: 4836
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>
#include <set>

struct Book {
	int read, write;
};
int main() {
	while (true) {
		int n; std::cin >> n; if (n == 0) break;
		std::vector<Book> books(n);
		for (auto& book : books) std::cin >> book.read >> book.write;
		if (n == 1) {
			std::cout << books.front().read * 2 + books.front().write << '\n';
			continue;
		}
		const auto sum_length = std::accumulate(books.begin(), books.end(), 0, [](int acc, const Book& b) {return acc + b.read; });
		std::sort(books.begin(), books.end(), [](const Book& a, const Book& b) {return a.read > b.read; });
		const auto longest = books.front().read;
		if (sum_length >= longest * 2) {
			std::cout << sum_length + std::accumulate(books.begin(), books.end(), 0, [](int acc, const Book& b) {return acc + b.write; }) << '\n';
		}
		else {
			std::sort(std::next(books.begin()), books.end(), [](const Book& a, const Book& b) {return a.write < b.write; });
			const auto rest_time = longest * 2 - sum_length;
			auto write_time = std::accumulate(books.begin(), books.end(), 0, [](int acc, const Book& b) {return acc + b.write; });
			std::vector<bool> can_make(rest_time + 1, false); can_make[0] = true;
			for (auto i = 1; i < n; ++i) {
				for (int j = rest_time; j >= books[i].write; --j) {
					can_make[j] = can_make[j] || can_make[j - books[i].write];
				}
			}
			for (auto i = rest_time; i > 0; --i) {
				if (can_make[i]) {
					write_time -= i;
					break;
				}
			}
			std::cout << longest * 2 + write_time << '\n';
		}
	}
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d,a[220001],b[220001];
main()
{
	cin>>n>>d;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	for(int i=2;i<=n;i++)b[i]=min(b[i],b[i-1]+d);
	for(int i=n-1;i;i--)b[i]=min(b[i],b[i+1]+d);
	int pos=min_element(a+1,a+1+n)-a,ans=0;
	for(int i=pos-1;i;i--)ans+=a[i]+b[i+1]+d;
	for(int i=pos+1;i<=n;i++)ans+=a[i]+b[i-1]+d;
	cout<<ans<<'\n';
} 


Measured memory_bytes: 3328
#include<stdio.h>
int main(void){
  int a[4][13]={};
  int i,j;
  int n,p;
  char q;
  
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf(" %c %d",&q,&p);
    if(q=='S'){
      a[0][p-1] = 1;
    }
    else if(q=='H'){
      a[1][p-1] = 1;
    }
    else if(q=='C'){
      a[2][p-1] = 1;
    }
    else if(q=='D'){
      a[3][p-1] = 1;
    }
  }
  
  for(i=0;i<4;i++){
    for(j=0;j<13;j++){
      if(!a[i][j]){
	if(i==0){
	  printf("%c %d\n",'S',j+1);
	}
	else if(i==1){
	  printf("%c %d\n",'H',j+1);
	}
	else if(i==2){
	  printf("%c %d\n",'C',j+1);
	}
	else if(i==3){
	  printf("%c %d\n",'D',j+1);
	}
      }
    }
  }
  return(0);
}

Measured memory_bytes: 1788
#include <iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#include<set>
#include<deque>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;

const ll MOD_CONST = 1000000007;


const int BIG_INT = 1000000000;

const int MAX_N = 1005;
const int MAX_V = MAX_N * (MAX_N - 1) / 2;

vector<int> to[MAX_V];
int id[MAX_N][MAX_N];

int toId(int i,int j) {
	if (i > j) {
		swap(i, j);
	}
	return id[i][j];
}
int dp[MAX_V];
bool visited[MAX_V];
bool calculated[MAX_V];

int dfs(int v) {
	
	if (visited[v]) {
		
		if (!calculated[v]) {
			
			return -1;
		}

		return dp[v];
	}

	visited[v] = true;
	dp[v] = 1;
	for (int u: to[v]) {
		int res = dfs(u);
		if (res == -1) {
			return -1;
		}
		dp[v] = max(dp[v], res + 1);
	}

	calculated[v] = true;
	
	return dp[v]; 
}

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

	vector<vector<int>> a(n,vector<int>(n-1));
	for (int i = 0; i < n; i++) {
		
		for (int j = 0; j < n - 1; j++) {
			cin >> a[i][j];
			a[i][j]--;

		}
	}
	int v = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i < j) {
				id[i][j] = v;
				v++;
			}
		}
	}


	for (int i = 0; i < n; i++) {

		for (int j = 0; j < n-1; j++) {
			a[i][j] = toId(i, a[i][j]);
		}

		for (int j = 0; j < n - 2; j++) {
			to[a[i][j+1]].emplace_back(a[i][j]);
		}
	}
	int ans = 0;
	for (int i = 0; i < v; i++) {
		int res = dfs(i);
		if (res == -1) {
			cout << -1 << endl;
			return 0;
		}
		ans = max(ans, res);
	}

	cout << ans << endl;

	return 0;
}  



Measured memory_bytes: 38528
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ull unsigned long long
#define F first
#define S second
#define eps 1e-6
#define mp make_pair
const long long INF=2*1e9+2;
const int MX=200003;
int N, M, k;
int arr[MX];
int main()
{
    int X;
    cin>>N>>X;
    for(int i=1;i<=N;i++)
    {
        scanf("%d", &arr[i]);
    }
    sort(arr+1, arr+N+1);
    int g=0;
    ll D=0, id=1;
    D=abs(arr[1]-X);
    for(int i=2;i<=N;i++)
    {
        g=__gcd(g, arr[i]-arr[i-1]);
        if(abs(arr[i]-X) > D)
        {
            D=abs(arr[i]-X);
            id=i;
        }
    }
    g=__gcd(g, abs(arr[id]-X));
    cout<<g;
    return 0;
}


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

public class Main {

    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main (String[] args) {
        FastReader sc = new FastReader();
        int n = sc.nextInt();
        int c, ss = 0, se = n - 1;
        System.out.println(ss);
        System.out.flush();
        String l, ls = sc.nextLine();
        if(ls.equals("Vacant"))
            return;
        System.out.println(se);
        System.out.flush();
        String le = sc.nextLine();
        if(le.equals("Vacant"))
            return;
        do{
            c = (ss + se) / 2;
            System.out.println(c);
            System.out.flush();
            l = sc.nextLine();
            if(((c - ss) % 2 == 0 && ls.equals(l)) || ((c - ss) % 2 == 1 && !ls.equals(l))){
                ss = c;
                ls = l;
            }
            else{
                se = c;
                le = l;
            }
        }
        while(!l.equals("Vacant"));
    }
}


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


class Program
{
    static void Main(string[] args)
    {
        // 入力
        //var s = Console.ReadLine();
        long n = long.Parse(Console.ReadLine());
        long ans = 0;
        if (n % 2 == 0)
        {
            long f = 5;
            for (int i = 1; f <= n; i++)
            {
                ans += (long)Math.Floor(((decimal)n / (decimal)f)/2);
                f *= 5;
            }
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 27512
#include<bits/stdc++.h>
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
const int INF = 0x3f3f3f3f, nINF = 0xcfcfcfcf, INFMEM = 0x3f, nINFMEM = 0xcf;
const int PR1 = 1e6 + 3, PR2 = 1e9 + 7;
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 103;
ll k,ans1,ans2,n;
char s[N];

int main(){
    scanf("%s",s);
    scanf("%lld",&k);
    n=strlen(s);
    for(int i = 0; i<n; i++) {
        if(s[i]!=s[0]) break;
        if(i==n-1){
            printf("%lld\n",1ll*k*n/2);
            return 0;
        }
    }
    for(int i = 0; i+1<n; i++){
        if(s[i]==s[i+1]) ans1++,i++;
    }
    for(int i = 0; i+1<2*n; i++){
        if(s[i%n]==s[(i+1)%n]) ans2++,i++;
    }
    printf("%lld\n",ans1+(ans2-ans1)*(k-1));
    return 0;
}

Measured memory_bytes: 256
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import bisect
n = int(input())
#n, k = map(int, sys.stdin.readline().split())
#s = input()
a = list(map(int, sys.stdin.readline().split()))

b = list(map(int, sys.stdin.readline().split()))
c = list(map(int, sys.stdin.readline().split()))

a.sort()
c.sort()
ans = 0
for i in range(n):
    x = bisect.bisect_left(a,b[i])
    y = n - bisect.bisect_right(c,b[i])
    ans += (x*y)

print(ans)



















Measured memory_bytes: 24600
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;

int main(){
	long long int N,K,Q;
	cin >> N >> K >> Q;
	long long int ca[N];
	for(int i=0;i<N;i++){
		ca[i]=0;
	}

	for(int i=0;i<Q;i++){
		int A;
		cin >> A;
		ca[A-1]++;
	}

	for(const auto& p : ca){
		long long int point = K-(Q-p);
		if(point<=0){
			cout << "No" << endl;
		}else{
			cout << "Yes" << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 1408
#pragma once

#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;

#define rep(a,n) for(int a = 0;a < n;a++)
#define repi(a,b,n) for(int a = b;a < n;a++)

int main(void)
{
	ll n;
	cin >> n;
	vector<P> vs(n);
	rep(i, n) {
		int a;
		cin >> a;
		vs[i] = { a, i };
	}
	sort(vs.begin(), vs.end(), std::greater<P>());
	set<ll> upper;
	upper.insert(-1);
	upper.insert(n);
	upper.insert(vs[0].second);
	ll sum = 0;
	for (int i = 1; i < n; i++) {
		auto f = vs[i];
		auto u = upper.upper_bound(f.second);
		if (*u != n) {
			auto w1 = *u;
			u++;
			auto w2 = *u;
			u--;
			u--;
			auto w3 = *u;
			sum += f.first * (w2 - w1) * (f.second - w3);
			if (w3 != -1) {
				u--;
				auto w4 = *u;
				sum += f.first * (w3 - w4) * (w1 - f.second);
			}
		}
		else {
			auto w1 = *u;
			u--;
			auto w3 = *u;
			u--;
			auto w4 = *u;
			sum += f.first * (w3 - w4) * (w1 - f.second);
		}
		upper.insert(f.second);
	}
	cout << sum << endl;
	return 0;
}


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

using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;
using vld = vector<ld>;
using vvld = vector<vld>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T& a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T& a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
const long long INF = 1LL << 60;

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

  ld a, b;
  cin >> a >> b;
  ld ans = a * b;
  cout << (ll)floor(ans) << endl;

  return 0;
}


Measured memory_bytes: 3764
#include "bits/stdc++.h"
using namespace std;
int main() {
    long long N;
    cin >> N;
    vector<long long>A(N);
    long long sum = 0;
    bool check = true;
    for (long long i = 0; i < N; i++) {
        cin >> A.at(i);
        if (A.at(i) % 2 != 0) check = false;
    }
    if (!check) cout << "first" << endl;
    else cout << "second" << endl;
}

Measured memory_bytes: 1024
/******************************************
* AUTHOR : RAJAGOPALAN *
* NICK : ARNO *
* INSTITUTION : VIT *
******************************************/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define FP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define FS(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define IT(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

template<class T> inline T gcd(T x, T y) { if (!y) return x; return gcd(y, x%y);}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector< pair<int, int> > VPII;
typedef vector< pair<int, PII > > VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;

inline ll modulo(ll a, ll m)
{
	return (a % m + m) % m;
}

inline ll modInverse(ll a, ll m)
{
	assert(__gcd(a, m) == 1);
	ll m0 = m;
	ll y = 0, x = 1;

	if (m == 1)
		return 0;

	while (a > 1)
	{
		ll q = a / m;
		ll t = m;

		m = a % m, a = t;
		t = y;

		y = x - q * y;
		x = t;
	}

	if (x < 0)
		x += m0;

	return x;
}

inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
	if (y == 0)
		return 1LL;
	else if (y == 1)
		return x;
	else
	{
		ll ans = modPow(x, y / 2, m) % m;
		if (y & 1)
		{
			return (((ans * ans) % m) * x) % m;
		}
		else
		{
			return (ans * ans) % m;
		}
	}
}

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin>>s;
	for(int i=0;i<s.size();++i)
	cout<<"x";
	return 0;
}

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

typedef long long ll;

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

#define FOR(i, start, end) for(ll i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)

int main(void) {
    int N;
    cin >> N;
    int ans = 0;
    for(int i = 1; i <= N; i += 2) {
        int count = 0;
        FOR(j, 1, i+1) {
            if ((i % j) == 0) {
                count++;
            }
        }
        if (count == 8) {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <functional>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mk make_pair

template <class key, class cmp = std::less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

void solve()
{
    ll n, k;
    unordered_map<ll,ll>h;
    cin>>n>>k;
    ll st = n/k;
    n-=(k*st);
    ll ans = n;
    for(int i=0;i<10;i++)
    {
        n = abs(n-k);
        ans = min(ans, n);
    }
    cout<<ans<<endl;
}

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

    // ll t;
    // cin >> t;

    // while (t--)
    // {
    //     solve();
    // }
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define all(v) v.begin(),v.end()
template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
const ll INFL = 1LL << 60;

struct Edge { int to; ll len; };

class Solver {
  public:
    vector<vector<Edge>> E;

    tuple<ll, ll> solve2(int root, int prev) {
        ll sum = 0, maxi = 0;
        bool branch = true;
        for(Edge e : E[root]) {
            if(e.to == prev) continue;
            branch = false;
            auto ret = solve2(e.to, root);
            if(get<0>(ret) < 0) continue;
            set_max(maxi, get<1>(ret) + e.len);
            sum += get<0>(ret) + e.len;
        }
        return make_tuple(branch ? -INFL : sum, maxi);
    }
    
    bool solve() {
        int N; cin >> N;
        if(N == 0) return 0;
        vector<int> P(N - 1), D(N - 1); cin >> P >> D;
        E.resize(N);
        rep(i, N - 1) {
            E[i + 1].push_back(Edge{P[i] - 1, D[i]});
            E[P[i] - 1].push_back(Edge{i + 1, D[i]});
        }

        ll ans = INFL;
        rep(i, N) {
            auto ret = solve2(i, -1);
            set_min(ans, get<0>(ret) * 2 - get<1>(ret));
        }
        
        cout << ans + accumulate(all(D), 0LL) << endl;
        
        return 1;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(true) {
        Solver s;
        if(!s.solve()) break;
    }
    return 0;
}

Measured memory_bytes: 3324
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
using namespace std;
int n,k;
const int mod = 1e9+7,N=1e5+5;
int dp[N][2];
vi adj[N];
void dfs(int v,int p) {
    dp[v][0] = dp[v][1] = 1;
    for (int i : adj[v])
    if (i != p) {
        dfs(i,v);
        dp[v][0] = (ll)dp[v][0]*(dp[i][1] + dp[i][0])%mod;
        dp[v][1] = (ll)dp[v][1]*dp[i][0]%mod;
    }

}
main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a,b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(1,0);
    cout << (dp[1][0] + dp[1][1])%mod;
}


Measured memory_bytes: 16740
#![allow(unused)]
use std::io::{self, Read};

fn get_stdin() -> String {
    let mut buf = String::new();
    let mut stdin = io::stdin();
    stdin.read_to_string(&mut buf);
    return buf
}

fn to_nums(ss: &str) -> Vec<usize> {
    ss.split_whitespace()
        .map(|x| x.parse::<usize>().unwrap())
        .collect()
}

fn main() {
    let input = get_stdin();
    let lines = input.split('\n');
    for line in lines {
        let v = to_nums(line);
        let rect = Rectangle {
            height: v[0],
            width: v[1],
        };
        if rect.is_valid() {
            println!("{}", rect.draw_frame());
        } else {
            break;
        }
    }
}

struct Rectangle {
    height: usize,
    width: usize,
}

impl Rectangle {
    fn draw_frame(&self) -> String {
        let mut buf = String::new();
        self._draw_edge(&mut buf);
        match self.height {
            1 => buf,
            2 => {
                self._draw_edge(&mut buf);
                return buf
            },
            _ => {
                for _ in 2..self.height {
                    self._draw_inner(&mut buf);
                }
                self._draw_edge(&mut buf);
                return buf
            },
        }
    }

    fn is_valid(&self) -> bool {
        self.height > 0 && self.width > 0
    }

    fn _draw_edge(&self, buf: &mut String) {
        let mut pic = "#".repeat(self.width);
        pic.push('\n');
        buf.push_str(&pic);
    }

    fn _draw_inner(&self, buf: &mut String) {
        match self.width {
            1 => { buf.push_str("#\n"); },
            2 => { buf.push_str("##\n"); },
            _ => {
                let mut edge = String::new();
                edge.push('#');
                let dots = ".".repeat(self.width - 2);
                edge.push_str(&dots);
                edge.push_str("#\n");
                buf.push_str(&edge);
            }
        }
    }
}



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

using namespace std;
typedef long long ll;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll x,res=0;cin>>x;
  res = (x/11)*2;
  if(x%11>6) res+=2;
  else if(x%11>0) res+=1;
  cout<<res<<endl;
}


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

const int XD = 1e5 + 1;
vector <int> v;
bool dp[ XD ];

int main()
{
    ios_base::sync_with_stdio( false );
    int n, k; cin >> n >> k;
    while( n-- )
    {
        int a; cin >> a; v.push_back( a );
    }
    for( int i = 1; i <= k; i++ )
    {
        for( auto j : v )
        {
            if( j > i ) continue;
            if( !dp[ i - j ] ) { dp[ i ] = true; break; }
        }
    }
    dp[ k ]? cout << "First":cout << "Second";
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#define MAX 100000

int parent(int i ) {return i /2;}
int left(int i) {return 2*i;}
int right(int i){return 2*i+1;}

int main(void)
{
	int H , i , A[MAX+1];
	
	scanf("%d",&H);
	
	for( i = 1; i <= H; i++)
	{
		scanf("%d",&A[i]);
	}
	for( i = 1; i <= H; i++)
	{
		printf("node %d: key = %d, ",i,A[i]);
		if(parent(i) >= 1) printf("parent key = %d, ",A[parent(i)]);
		if(left(i) <= H) printf("left key = %d, ",A[left(i)]);
		if(right(i) <= H) printf("right key = %d, ",A[right(i)]);
		printf("\n");
	}
	return 0;
}


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

int main(){
  string s = "YES";
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0; i<n; i++){
  	cin >> a.at(i);
  }
  sort(a.begin(),a.end());
  for(int i=0; i<n-1; i++){
  	if(a.at(i) == a.at(i+1)){
    	s = "NO";
    }
  }
  cout << s << endl;
}


Measured memory_bytes: 4044
#include<bits/stdc++.h>
using namespace std;
main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long i,j,k,l,m,n,o,p,q;
    while(cin>>m)
    {
        cout<<m/3<<endl;
    }
    return 0;
}


Measured memory_bytes: 3508
#include <stdio.h>

// 線形探索
int search(int A[], int n, int key) {
	int i = 0;
	A[n] = key;
	while(A[i] != key) i++;
	return i != n;
}

int main(void) {
	int i, n, A[10000+1], q, key, sum = 0;
	
	scanf("%d",&n);
	for(i=0; i<n; i++) scanf("%d", &A[i]);
	scanf("%d",&q);
	for(i=0; i<q; i++) {
		scanf("%d", &key);
		if(search(A, n, key))sum++;
	}
	printf("%d\n", sum);
	
	return 0;
}

Measured memory_bytes: 636
N,M = list(map(int, input().split()))

ans = ["-1"] * N
for _ in range(M):
    s,c = list(map(int, input().split()))

    if ans[s-1] != "-1" and str(c) != ans[s-1]:
        print(-1)
        exit()
    else:
        ans[s-1] = str(c)

if N>=2 and ans[0] == "-1":
    ans[0] = "1"

for i in range(N):
    if ans[i] == "-1":
        ans[i] = "0"

if ans[0] == "0" and N>=2:
    print(-1)
else:
    print("".join(ans))


Measured memory_bytes: 3064
package main

import (
	"fmt"
)

func abs(a int)int {
	if a<0{
		return -a
	}
	return a
}


func main() {
	var L,R int
	fmt.Scan(&L,&R)
	
	ans := 2020
	for i:= 0; i<2019;i++ {
		l:=L+i
		if l>=R || l <0{
			break
		}
		for j:=0;j<2019;j++{	
			r := R - j
			if r<=L ||r<0{
				break
			}
			mod := abs((2019-l)*(2019-r)%2019)
			if ans > mod {
				ans = mod
			}
			if mod==0{
				break
			}
		}	
	}
	fmt.Println(ans)
}

Measured memory_bytes: 512