akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cmath>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;

int n,m,k;

int main()
{
    int i,j;
    int xx;
    cin>>n>>m>>k;
    
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++)
        {
            xx=i*(m-j)+(n-i)*j;
            
            if(xx==k)
            {
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream> //入出力
#include <stdio.h>
#include <map>
#include <set>
#include <string>
#include <math.h> //算術演算子
#include <vector>
#include <cstdlib>
#include <queue>
#include <stack>
#include <list>
#include <iomanip> //小数点以下を表示させる(setprecision())
// #include <bits/stdc++.h>
using namespace std;
typedef long long ll; //64bit型

#define INF 1050000000
#define N_MAX 110
#define M_MAX 100010

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << x << " " \
                      << "(L:" << __LINE__ << ")" << '\n'
#define PRINT(V)                                   \
        {                                          \
                for (int i = 0; i < V.size(); i++) \
                {                                  \
                        cout << V[i] << " ";       \
                }                                  \
                cout << endl;                      \
        }

int gcd(int a, int b)
{
        return b ? gcd(b, a % b) : a;
}

ll dp[N_MAX][M_MAX];

int main() //input->compute->output
{
        int N, W;
        cin >> N >> W;
        vector<int> we(N);
        vector<int> va(N);
        rep(i, N) { cin >> we[i] >> va[i]; }

        rep(i, N)
        {
                for (int s_we = 0; s_we < W + 1; s_we++)
                {
                        if (s_we - we[i] >= 0)
                        {
                                dp[i + 1][s_we] = max(dp[i][s_we], dp[i][s_we - we[i]] + va[i]);
                        }
                        else
                        {
                                dp[i + 1][s_we] = dp[i][s_we];
                        }
                }
        }
        cout << dp[N][W] << endl;

        return 0;
}

Measured memory_bytes: 79360
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[2000010];
struct edge{int to,cost;};
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
void init_fact(){
    kaijo[0]=1;
    for(int i=1;i<=2000000;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=MOD;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%MOD;
    int memo=modpow(a,b/2);
    return memo*memo%MOD;
}
int comb(int a,int b){
    if(!kaijo[0])init_fact();
    return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int inv(int x){
    x=modpow(x,MOD-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}
double dist(double ax,double ay,double bx,double by){
    return sqrt((bx-ax)*(bx-ax)+(ay-by)*(ay-by));
}
int n,k;
double p[200010];
signed main(){
    cin>>n>>k;
    rep(i,n){
        cin>>p[i];
        p[i]=(p[i]+1)/2;
    }
    double ans=0.0;
    //[0,k-1]
    double now=0.0;
    rep(i,k)now+=p[i];
    ans=max(ans,now);
    for(int i=k;i<n;i++){
        now+=p[i];
        now-=p[i-k];
        ans=max(ans,now);
    }
    printf("%.12lf\n",ans);
    return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <string.h>
#define lop(i, n) for(i=0; i<n; i++)

int main(void)
{
	int n, m,i,j,tmp, sum=0;
	scanf("%d %d", &n, &m);
	
	int A[10000];
	lop(i, m){
		scanf("%d", &A[i]);
	}
	
	for (i=0; i<m; ++i) {
    for (j=i+1; j<m; ++j) {
      if (A[i] <A[j]) {
        tmp =  A[i];
        A[i] = A[j];
        A[j] = tmp;
      }
    }
  }
 
	lop(i, m){
		sum+=A[i];
	}
	
	if(sum>n)printf("-1");
	else if(sum==n){ printf("0"); }
	else{ printf("%d", n-sum); }
	
	return 0;
}

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

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

  vector<bool> row(n,false);
  vector<bool> col(m,false);
  for(int i = 0;i < n;i++){
    for(int j = 0;j < m;j++){
      if(a[i][j] == '#'){
        row[i] = true;
        col[j] = true;
      }
    }
  }
  for(int i = 0;i < n;i++){
    if(row[i]){
      for(int j = 0;j < m;j++){
        if(col[j]){
          cout << a[i][j];
        }
      }
      cout << endl;
    }
  }

}


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

int main() {
  long long n, a, b;
  cin >> n >> a >> b;
  if (a > b){
    cout << 0 << endl;
  }
  else if (n == 1){
    if(a != b){
      cout << 0 << endl;
    }
    else{
      cout << 1 << endl;
    }
  }
  else{
    cout << (b - a) * (n - 2) + 1 << endl;
  }
}

Measured memory_bytes: 256
#include <cstdio>
int Q; double ax, ay, bx, by, cx, cy;
int main() {
	scanf("%lf%lf%lf%lf%d", &ax, &ay, &bx, &by, &Q); bx -= ax, by -= ay;
	while (Q--) {
		scanf("%lf%lf", &cx, &cy); cx -= ax, cy -= ay;
		double t = (bx * cx + by * cy) / (bx * bx + by * by);
		printf("%.9lf %.9lf\n", ax + bx * t, ay + by * t);
	}
	return 0;
}

Measured memory_bytes: 2760
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(); 
		int min = get2times(sc.nextInt());
		
		for(int i=1; i<n; i++) {
			int k = sc.nextInt();
			if(get2times(k)<min) {
				min = get2times(k);
			}
		}
		
		System.out.println(min);
	}
	
	public static int get2times(int n) {
		int count = 0;
		while(n%2 == 0) {
			n = n/2;
			count ++;
		}
		
		return count;
	}
}


Measured memory_bytes: 21588
n, k = map(int, input().split())
h = list(map(int, input().split()))

INF = 10 ** 10

dp = [INF for _ in range(n)]
dp[0] = 0

for i in range(1, n):
    for j in range(max(i-k, 0), i):
        #print(i, j, dp[j] + abs(h[j] - h[i]))
        dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]))

print(dp[n-1])


Measured memory_bytes: 56544
#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>

using namespace std;
int q;
string text;
int ans[160];
int dp[1100][1100];

int main(){
    cin >> q;
    vector<string> texts;

    for(int i=0;i<q*2;i++){
         cin >> text;
         texts.push_back(text);
    }
    for(int k=0;k<q;k++){
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<texts[2*k].size();i++){
            for(int j=0;j<texts[2*k+1].size();j++){
                if(texts[2*k][i]==texts[2*k+1][j]) dp[i+1][j+1] = max(dp[i][j]+1, max(dp[i+1][j], dp[i][j+1]));
                else dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
            }
        }
        ans[k]=dp[texts[2*k].size()][texts[2*k+1].size()];
    } 
    for(int i=0;i<q;i++)cout << ans[i] << endl;
}


Measured memory_bytes: 7960
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define vv(T) vector<vector<T>>
#define coa cout << ans << endl; return 0;
using namespace std;
using ll = long long;
template<typename T>
using vec = vector<T>;
template<typename T>
using vvec = vector<vector<T>>;
using qint = queue<int>;
using sint = stack<int>;
using pii = pair<int, int>;

class UnionFind{
    vector<int> parent;
    // UnionFind木の実装
public:
    UnionFind(int N) : parent(N, -1) {} // コンストラクタ
    int root(int x){
        // 根を求める。
        if(parent[x] < 0) return x;
        return parent[x] = root(parent[x]);
    }
    void unite(int x, int y){
        // xとyの木を結合する。
        int rx = root(x);
        int ry = root(y);
        if(rx == ry) return;
        if(-parent[rx] > -parent[ry]){
            // 小さい方の木を大きい方につなげる。
            parent[rx] += parent[ry];
            parent[ry] = rx;
        }
        else{
            parent[ry] += parent[rx];
            parent[rx] = ry;
        }
        return;
    }
    bool isSame(int x, int y){
        // 同じ木にあるか?
        return root(x) == root(y);
    }
    int size(int x){
        // xの木に属する要素はいくつか?
        return -parent[root(x)];
    }
};

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

    UnionFind uf(n);

    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        uf.unite(a, b);
    }

    int ans = -1;
    rep(i, n){
        int ri = uf.root(i);
        if(ri == i) ans++;
    }

    coa;
}


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

int main(){

int h1,h2,k1,k2,a,b,c,d;

cin >> h1 >> h2 >> k1 >> k2 >> a >> b >> c >> d;

if(h1*a + h2*b + h1/10*c + h2/20*d > k1*a + k2*b + k1/10*c + k2/20*d){
    cout << "hiroshi" << endl;
}else if(h1*a + h2*b + h1/10*c + h2/20*d < k1*a + k2*b + k1/10*c + k2/20*d){
    cout << "kenjiro" << endl;
}else{
    cout << "even" << endl;
}

return 0;

}


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

using namespace std;

#define inf (ll)1e15
#define ll long long
#define all(x) x.begin(), x.end()
#define x first
#define y second

typedef pair<int, int> Point;

const int mod = (int) 1e9 + 7;
const int mod2 = 998244353;
const int MAX_NODES = 1000;

struct Trie{

	int sz;
	int t[MAX_NODES][26], cnt[MAX_NODES][26];

	Trie(){
		memset(t, 0xff, sizeof t);
		memset(cnt, 0, sizeof cnt);
		sz = 0;
	}

	void insert(string s){
		int node = 0;
		for(int i = 0; i < s.size(); ++i){
			if(t[node][s[i] - 'a'] == -1)
				t[node][s[i] - 'a'] = ++sz;
			++cnt[node][s[i] - 'a'];
			node = t[node][s[i] - 'a'];
		}
	}

	int find(string s){
		int node = 0;
		int res = 0;
		for(int i = 0; i < s.size(); ++i){
			res = cnt[node][s[i] - 'a'];
			node = t[node][s[i] - 'a'];
		}
		return res;	
	}

}trie;

int main(){

    cin.tie(0);
    cin.sync_with_stdio(0);

    #ifdef Cyborg101
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

 	string s;
 	cin >> s;

 	int n = s.size();

 	// auto chk = [](string x){
 			
 	// 	int sz = x.size();
 	// 	for(int i = 0; i < sz / 2; ++i){
 	// 		if(x[i] != x[sz - i - 1])
 	// 			return false;
 	// 	}
 	// 	return true;
 	// };
 	

 	// if(chk(s)){
 	// 	cout << 0 << endl;
 	// 	return 0;
 	// }

 	// string pure;

 	int res = 0;

 	int l = 0, r = n - 1;

 	while(l < r){

 		if(s[l] == s[r]) l++, r--;
 		else if(s[l] == 'x') l++, res++;
 		else if(s[r] == 'x') r--, res++;
 		else
 			break;
 		
 	}

 	if(l >= r){
 		cout << res << endl;
 	}
 	else{
 		cout << -1 << endl;
 	}
 	
    return 0;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  string s;
  cin >> s;
  int max_count = 0, count = 0;
  for(int i = 0; i < 3; i++){
    if(s.at(i) == 'R') count++;
    if(s.at(i) == 'S') count = 0;
    max_count = max(max_count, count);
  }
  cout << max_count << endl;
}

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

typedef long long int ll;
#define INF 1999999999
#define MODA 1000000007
#define PI 3.1415926535897932384626433

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int len = s.length();
    int countA;
    for(int i = 0; i < len; i++){
        if(s[i] == 'A'){
            countA = i;
            break;
        }
    }

    int countZ;
    for(int ii = len-1; ii >= 0; ii--){
        if(s[ii] == 'Z'){
            countZ = ii;
            break;
        }
    }
    cout << countZ - countA + 1 << endl;
    //cout << countA << endl;
    //cout << countZ << endl;

    return 0;
}


Measured memory_bytes: 720
N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = 1001001001;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const int max_v = 100100;
const int max_n = 110;
 
// dp[i][sum_v] = i-1番目までの品物から価値がsum_vになるように選んだ時の重さの総和の最小値
ll dp[max_n][max_v];

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

  rep(i,max_n) rep(j,max_v) dp[i][j] = infll;

  int n, max_w;
  cin >> n >> max_w;
  vi w(n), v(n);
  rep(i,n) cin >> w[i] >> v[i];
  dp[0][0] = 0;
  REP(i,n+1) {
    rep(j,max_v) {
      if(j >= v[i-1]) chmin(dp[i][j], dp[i-1][j-v[i-1]]+w[i-1]);
      chmin(dp[i][j], dp[i-1][j]);
    }
  }
  int ans = 0;
  rep(j,max_v) {
    if(dp[n][j] <= max_w) chmax(ans, j);
  }
  cout << ans << endl;
}

Measured memory_bytes: 86272
"
3. ABC104C - All Green
リンク：　https://atcoder.jp/contests/abc104/tasks/abc104_c
"

# 入力
D, G = gets.split.map(&:to_i)
p = []
c = []
D.times do |i|
  p[i], c[i] = gets.split.map(&:to_i)
end

# Dでbit全探索
# i桁目をp[i]進報で表せば、得点の計算できそう
ans = 1000
(1 << D).times do |i|
  point = 0
  ma = -1
  gap = 0
  num = 0
  tmp = 0
  D.times do |j|
    # i[j]==1なら配点100(j+1)の問題を完全に解く
    if i[j] == 1
      point = point + 100*(j+1) * p[j] + c[j]
      num = num + p[j]
      if point >= G
        ans = [ans, num].min
      end
    else
      ma = [ma, j].max
    end
  end
  # ここまでで全問解く配点の問題は決まった
  # 目標までの差を出す
  gap = G - point
  if  gap > 0
  # 完全に解かない(i[j]==0なるjの最大値)もののうち、
  # 最も高い配点はmaに入ってる配点100(ma+1)点 
    tmp = (gap.to_f / (100*(ma+1)).to_f).ceil #その配点を何問解けば目標達成できるか
    if tmp <= p[ma]-1 # これを満たさない場合は、完全に解く選択がミスってる
      # ここに入ったってことは、maの問題をnumだけ中途半端に解けば目標達成できる
      num = num + tmp
      ans = [ans, num].min
    end
  end
end
puts ans

Measured memory_bytes: 1788
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    C = [int(input()) for _ in range(N)] + [-1]
    C = [C[i] for i in range(N) if C[i] != C[i + 1]]

    N = len(C)
    # dp[i] := i個までの色の塗り方の総和
    dp = [0] * N
    dp[0] = 1
    used = [-1] * (max(C) + 1)
    used[C[0]] = 0

    for i in range(1, N):
        if used[C[i]] == -1:
            dp[i] = dp[i - 1]
        else:
            dp[i] = dp[i - 1] + dp[used[C[i]]]

        dp[i] %= MOD
        used[C[i]] = i

    print(dp[-1])


if __name__ == "__main__":
    main()


Measured memory_bytes: 20412
S = input()

ans = 0
for i in range(2 ** (len(S) - 1)):
    formula = ''
    flag = bin(i)[2:].zfill(len(S) - 1)
    for j, x in enumerate(flag):
        formula += S[j]
        if x == '1':
            formula += '+'
    if len(S) > 1:
        formula += S[-1]
    ans += eval(formula)

print(ans)


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

int main() {
  ll A, B, N;
  cin >> A >> B >> N;
  ll x = min(B - 1, N);
  ll ans = (A * x) / B;
  // ll n = min(B, N);
  // ll ans = 0;
  // for (ll x = n - 2; x <= n; x++) {
  //   ll y = (A * x) / B - A * (x / B);
  //   ans = max(ans, y);
  // }
  cout << ans << endl;
}


Measured memory_bytes: 3492
#include <bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int n;
int a[100];
int main() {  
  cin >> n;
  rep(i,n) cin >> a[i];
  int sum_x = 0, sum_y = 0;
  rep(i, n) {
    int max_v = 0, k = 0;
    REP(j, i, n) {
      if ( max_v < a[j] ){
        k = j;
        max_v = a[j];
      }
    }
    int tmp = a[i];
    a[i] = a[k];
    a[k] = tmp;
    if ( i % 2 == 0) {
      sum_x += max_v; 
    }else {
      sum_y += max_v;
    }
  }
  cout << sum_x - sum_y << endl;
  return 0;
}

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


int main(){
    int n;
    cin >>n;
    vector<string> S(n);
    rep(i,n) cin >> S[i];
    int C[4] = {};
    rep(i,n){
        if(S[i]=="AC"){
           C[0]+=1; 
        }else if(S[i]=="WA"){
           C[1]+=1; 
        }else if(S[i]=="TLE"){
           C[2]+=1; 
        }else if(S[i]=="RE"){
           C[3]+=1; 
        }
    }

    cout<<"AC x "<<C[0]<<'\n'<<"WA x "<<C[1]<<'\n'<<"TLE x "<<C[2]<<'\n'<<"RE x "<<C[3]<<endl;

}

Measured memory_bytes: 6424
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
int main()
{
	/*#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif*/
ios_base::sync_with_stdio(0);
cin.tie(0);


int n,dig;
cin>>n;
dig=n%10;
if(dig==2 || dig==4 ||dig==5||dig==7||dig==9){
	cout<<"hon"<<endl;
}
else if(dig==3){
	cout<<"bon"<<endl;
}
else{
	cout<<"pon"<<endl;
}



return 0;
}


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

using namespace std;
using ll = long long;

int main() {
  vector<int> xs(3);
  rep(i, 3) cin >> xs[i];
  cout << xs[2] << " " << xs[0] << " " << xs[1] << endl;
  return 0;
}

Measured memory_bytes: 3604
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, ll> P;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

struct edge{
	int v;
	ll c;
};

vector<edge> g[828];
int p[828],deg[828];
ll dist[828];
queue<int> q;

int main(void){
	int n,i,j,v;
	ll d,ans,tmp;
	edge e;
	while(true){
		fill(deg,deg+828,-1);
		ans = 0ll,tmp=-INFLL;
		cin >> n;
		if(!n){
			break;
		}
		for(i=1; i<n; ++i){
			cin >> p[i]; --p[i];
			++deg[p[i]]; ++deg[i];
		}
		for(i=1; i<n; ++i){
			cin >> d;
			ans += d;
			e.v = i; e.c = d;
			g[p[i]].push_back(e);
			e.v = p[i];
			g[i].push_back(e);
		}
		for(i=0; i<n; ++i){
			if(!deg[i]){
				continue;
			}
			for(j=(g[i].l_ength()-1); j>=0; --j){
				e = g[i][j];
				if(deg[e.v]){
					ans += e.c;
				}
			}
		}
		for(i=0; i<n; ++i){
			if(!deg[i]){
				continue;
			}
			fill(dist,dist+828,INFLL);
			dist[i] = 0ll;
			q.push(i);
			while(!q.empty()){
				v = q.front();
				q.pop();
				for(j=(g[v].l_ength()-1); j>=0; --j){
					e = g[v][j];
					if(!deg[e.v]){
						continue;
					}
					if(dist[e.v] > dist[v]+e.c){
						dist[e.v] = dist[v]+e.c;
						q.push(e.v);
					}
				}
			}
			for(j=0; j<n; ++j){
				if(!deg[j]){
					continue;
				}
				tmp = max(tmp,dist[j]);
			}
		}
		ans -= tmp;
		cout << ans << endl;
		for(i=0; i<n; ++i){
			g[i].clear();
		}
	}
	return 0;
}



Measured memory_bytes: 3220
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**3
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    while True:
        n = I()
        if n == 0:
            break
        r = 0
        for i in range(1,n):
            t = i
            while t < n:
                i += 1
                t += i
            if t == n:
                r += 1
        rr.append(r)

    return '\n'.join(map(str, rr))


print(main())




Measured memory_bytes: 9024
#include<bits/stdc++.h>
#define N 105
using namespace std;
#define X(x,u,v) (b[x][v]-b[x][(u)-1])
#define Y(x,u,v) (a[v][x]-a[(u)-1][x])
int n,m,u,v;short dp[N][N][N][N],a[N][N],b[N][N],Ans;
char s[N];
void upd(short &x,short y)
{
	x=max(x,y);
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		for (int j=1;j<=m;j++)
		{
			if (s[j]=='E') u=i,v=j;
			if (s[j]=='o') a[i][j]=b[i][j]=1;
			a[i][j]+=a[i-1][j];
			b[i][j]+=b[i][j-1];
		}
	}
	/*
	dp[x1][x2][y1][y2] ->
	*/
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)
	{
		for (int x1=1;x1+i<=n;x1++)
		for (int y1=1;y1+j<=m;y1++)
		{
			int x2=x1+i,y2=y1+j;
			short tmp=dp[x1][x2][y1][y2];
			/*if (x1+(n-u)<x2||x2-(u-1)>x1||y1+(m-v)<y2||y2-(v-1)>y1)continue;
			cout<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<endl;*/
			upd(Ans,dp[x1][x2][y1][y2]);
			int _x1=max(1,x2-(u-1)),_x2=min(n,x1+(n-u)),_y1=max(1,y2-(v-1)),_y2=min(m,y1+(m-v));
			//_x1=min()
			if (_x1>_x2||_y1>_y2)continue;
			
			if (x1>1&&_x1<x1) upd(dp[x1-1][x2][y1][y2],tmp+X(x1-1,max(y1,_y1),min(y2,_y2)));
			if (x2<n&&_x2>x2) upd(dp[x1][x2+1][y1][y2],tmp+X(x2+1,max(y1,_y1),min(y2,_y2)));
			if (y1>1&&_y1<y1) upd(dp[x1][x2][y1-1][y2],tmp+Y(y1-1,max(x1,_x1),min(x2,_x2)));
			if (y2<m&&_y2>y2) upd(dp[x1][x2][y1][y2+1],tmp+Y(y2+1,max(x1,_x1),min(x2,_x2)));
		}
	}
	printf("%d\n",(int)Ans);
}

Measured memory_bytes: 225664
#include<bits/stdc++.h>
#define for0(i,n) for(int i=0;i<n;i++)
#define rep(i,s,n) for(int i=s;i<n;i++)
#define sp <<" "<<					// giving space
#define MOD 1000000007				// for mod
#define ll_max 1000000000000000000
#define ll long long
#define ld long double
#define BOOST ios_base::sync_with_stdio ( false ); cin.tie ( nullptr ); cout.tie ( nullptr );
using namespace std;
// Vector
#define vi vector<int>					//integer vector
#define vll vector<ll>
#define pb push_back				//vector element insertion
#define pf push_front
#define er(v,i) v.erase(v.begin()+i)			// erase ith element in a vector
#define erng(v,x) v.erase(v.begin(),v.begin()+x)       	// delete a range in array

//Stack
/*  stack<int> s;						//declaring stack
s.push(1)						// enter  element in stack
s.top()							//returns top element in stack
s.pop()							//removes top element in  stack
*/
// pair
#define pii pair<int,int>					//pair integers
#define ff first
#define ss second
#define mp(a,b) make_pair(a,b)			// entering pair element in vector(size not defined)

//Hashmap
/* map<string,string> a;				//declaration
a[“abc”]=”xyz”;					// element entry in map;
gquiz1.insert(pair<int, int>(1, 40));
map<string,string>::iterator itr;			//iterating map
for (itr = a.begin(); itr!=a.end(); itr++){
    cout <<(*itr).first  << itr->second <<endl;
  }
  itr = companies.find("abc");		//finding element in map
  cout << itz->second;

//*/
vi g[100005];

int vis[100005];
int dp[100005];
int dfs(int i,int d)
{
    vis[i]=d+1;
    int mx=1,x;
    for(auto j:g[i])
    {
        if(!vis[j])x=dfs(j,vis[i]);
        else x=dp[j];
        mx=max(mx,x+1);
    }
    dp[i]=mx;
    return mx;
}
int main()
{
    int n,m,u,v;
    cin>>n>>m;
    for0(i,m)
    {
        cin>>u>>v;
        g[u].pb(v);
    }
    int mx=0,x;
    rep(i,1,n+1)
    {
        if(!vis[i])
        {x=dfs(i,0);
        mx=max(mx,x);}
    }
    cout<<mx-1;
}


Measured memory_bytes: 8576
//shara's here
//SPEEEEEEEEEED IS KEEEEEEEEEEY
//REEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEAD
#include <bits/stdc++.h>
using namespace std;
typedef string s;
typedef long long ll;
typedef long double ld;
#if !defined(ONLINE_JUDGE)
#include "C:\debug.hpp"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define pb push_back
#define ins insert
#define vl vector<ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
int main(){
    speed;
    ll k;
    cin >> k;
    s ss;
    cin >> ss;
    ll n = (ll) ss.size();
    if( n <= k )cout<<ss<<endl;
    else {
        for( ll i = 0; i < k; i++)cout<<ss[i];
        cout<<"..."<<endl;
    }









return 0;}
/*
███████████████████████████████████████████████████
███████████████████████████████████████████████████
██████████████████████████████████▀████████████████
██████████████████████████████████░▀███████████████
██████████████████████████████▌███░░░▀▀████████████
██▀████████████████████▐██████░▐██░░░░░░▀▀█████████
██░████████████████████▐█████▌░██▌▄░░░░▄▄░▄████▀███
█▌░███████████████████▀░█████░░░█░░░▄████░░███▀▐███
█▌░▐██████████████████░░████▌░░░▀░░▀███▀▀░▐███▄████
██░▀██████████████▌▐█▐▄▄████▌░░░░░░░░░░░░░▌████████
███░███████████████▀░▄▄██▀█▐░░░░░░░░░░░░░░▐████████
███▄░██████████████▄░░░░░░▀▀▀░░░░░░░░░░░░░█▐███████
████▄░██████████████████▄▄▄▄▄▄▐▄░░░░░░░░░░░████████
█████▄█████████████████▀▀▀▀▀▀░░░░░░░░░░░░░░████████
████████████████████████▄░░░░░░░░░░░░░░░▄░░████████
██████████████████████████▄▄▄░░░░░░░░░▄█░▄█████████
████████████████████████████████▄░░░░██▄███▀░░▀████
█████████████████████████████▀█████▄███▀▀▀░░▄▄░████
████████████████████████████▀░░▀░░▀▀░░░░▄▄▄██▀░░▀▀█
███████████████████████████▌░░░░░░░░░░░███████░░░▄█
███████████████▄░▀████████▀░░░░░░▀░░░░███████▌░░░██
███▄▄████████████▄░▀██████▄░░░░░█░░░░████████░░░▀▀
░▀█████████████████▄░▀█████░░░░██░░░░▀██████░░░░░▄█
▐█▄▀█████████████████▄░▀████░░░██▌░░░▐████▀░░░░▄███
▐███▄▀▀█████████████████▄░▀▀░░░░▀██▌▄█▀▀░░░▄▄██████
▀▀▀▀▀░░░▀▀▀▀▀░░░▀▀▀▀▀▀▀▀▀▀▀░░░░░░░▀▀░░░░░░▀▀▀▀▀▀▀▀▀
*/


Measured memory_bytes: 3612
#include <stdio.h>

#define N 100

int main(){

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

  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(A[j]<A[j-1]){
	tmp = A[j-1];
	A[j-1] = A[j];
	A[j] = tmp;
	count++;
      }
    }
  }

  for(i=0;i<n;i++){
    if(i==n-1) printf("%d\n",A[i]);
    else printf("%d ",A[i]);
  }

  printf("%d\n",count);

  return 0;
}

Measured memory_bytes: 600
s = input()

b = 0
w = 0
for i in range(len(s)):
  if i % 2 == 0:
    if s[i] == '0':
      b += 1
    else:
      w += 1
  else:
    if s[i] == '0':
      w += 1
    else:
      b += 1

print(min(b,w))


Measured memory_bytes: 3188
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input! {
        s: chars
    }
    let init_len = s.len();
    let mut s = s;
    let mut i = 0;
    let mut prev = s[0];
    i += 1;
    while i < s.len() {
        let curr = s[i];
        if prev != curr {
            s.remove(i - 1);
            s.remove(i - 1);
            if s.len() < 2 {
                break;
            }
            if i == 1 {
                prev = s[0];
                i = 1;
            } else {
                prev = s[i - 2];
                i = i - 1;
            }
        } else {
            prev = curr;
            i += 1;
        }
    }
    println!("{}", init_len - s.len());
}


Measured memory_bytes: 4352
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

using I = pair<ll, ll>;

ll solveUnion(const vector<I>& is) {
  ll p = numeric_limits<ll>::min();
  ll res = 0;
  for (auto i : is) {
    p = max(p, i.fst);
    res += max(0ll, i.snd - p);
    p = max(p, i.snd);
  }
  return res;
}

ll solve(ll N, ll X, ll D) {
  if (D == 0 && X == 0) return 1;
  if (D < 0) X = -X, D = -D;
  if (D == 0) return N + 1;
  map<ll, vector<I>> mods;
  ll lo = 0, hi = 0;
  for (ll k = 0; k <= N; k++) {
    ll s = k * X + D * lo;
    ll t = k * X + D * hi;
    ll m = (s % D + D) % D;
    mods[m].push_back({(s - m) / D, (t - m) / D + 1});
    lo += k;
    hi += N - k - 1;
  }
  ll res = 0;
  for (auto& e : mods) {
    auto is = e.snd;
    sort(is.begin(), is.end());
    res += solveUnion(is);
  }
  return res;
}

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  ll N, X, D;
  while (cin >> N >> X >> D) {
    cout << solve(N, X, D) << endl;
  }
  return 0;
}


Measured memory_bytes: 22144
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int par[100002];
int rk[100002];
 
void init(int n){
	for(int i=0; i<n; i++){
		par[i]=i;
	}
}
 
int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}
 
void unite(int x, int y){
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(rk[x]<rk[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(rk[x]==rk[y]) rk[x]++;
	}
}
 
bool same(int x, int y){
	return find(x)==find(y);
}
int main()
{
	int n, m; cin>>n>>m;
  vector<int> v[100000];
  for(int i=0; i<n; i++){
    int k; cin>>k;
    for(int j=0; j<k; j++){
      int l; cin>>l; l--;
      v[l].push_back(i);
    }
  }
  init(n);
  for(int i=0; i<m; i++){
    for(int j=1; j<v[i].size(); j++){
      unite(v[i][j], v[i][j-1]);
    }
  }
  int p=find(0);
  for(int i=1; i<n; i++){
    if(p!=find(i)){
      cout<<"NO"<<endl;
      return 0;
    }
  }
  cout<<"YES"<<endl;
	return 0;
}

Measured memory_bytes: 4608
#include <iostream>
#include <string>

using namespace std;

int calc(int a, int b)
{
    if (0 == a)
    {
        return b;
    }else
    {
        return -1 * b;
    }
    
}

char op(int a)
{
    if (0 == a)
    {
        return '+';
    }else
    {
        return '-';
    }
    
}

int main(int argc, char const *argv[])
{
    string S;
    int A, B, C, D;
    cin >> S;
    A = (int)(S[0] - '0');
    B = (int)(S[1] - '0');
    C = (int)(S[2] - '0');
    D = (int)(S[3] - '0');

    int sum;
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                sum = A + calc(i, B) + calc(j, C) + calc(k, D);
                if (7 == sum)
                {
                    cout << A << op(i) << B << op(j) << C << op(k) << D << "=7" << endl;
                    return 0;
                }
                
            }
            
        }
        
    }

    return 0;
}

Measured memory_bytes: 256
def cross_section_diagram():
	down = []
	edge = []
	pool = []

	for i, c in enumerate(input()):
		if c == '\\':
			down.append(i)
		elif c == '/' and down:
			left = down.pop()
			area = i - left

			while edge:
				if edge[-1] > left:
					edge.pop()
					area += pool.pop()
				else:
					break

			edge.append(left)
			pool.append(area)

	print(sum(pool))
	print(len(pool), *pool)

if __name__ == '__main__':
	cross_section_diagram()

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

int main(){

    std::vector<int> numbers;

    for(int num; std::cin >> num;){
        numbers.push_back(num);
    }

    int place_num;
    for(int i = 0; i < 5; ++i){

            if (numbers.at(i) == 0){
                    place_num = i + 1;
            }
    }
    std::cout << place_num << std::endl;

}

Measured memory_bytes: 3600
#include <stdio.h>

int main(void)
{
	int m, d, w;
	char week[20][20] = 
			{
				"Wednesday",
				"Thursday",
				"Friday",
				"Saturday",
				"Sunday",
				"Monday",
				"Tuesday"
			};

	while (1) {
		scanf("%d %d", &m, &d);
		if (m == 0) break;

		w = d % 7;

		switch (m) {
		  case 2:
		  	w = (w + 3) % 7;
		  	break;
		  case 3:
		  	w = (w + 4) % 7;
		  	break;
		  case 5:
		  	w = (w + 2) % 7;
		  	break;
		  case 6:
		  	w = (w + 5) % 7;
		  	break;
		  case 8:
		  	w = (w + 3) % 7;
		  	break;
		  case 9:
		  	w = (w + 6) % 7;
		  	break;
		  case 10:
		  	w = (w + 1) % 7;
		  	break;
		  case 11:
		  	w = (w + 4) % 7;
		  	break;
		  case 12:
		  	w = (w + 6) % 7;
		  	break;
		  default:
		  	break;
		}
		printf("%s\n", week[w]);
	}

	return (0);
}

Measured memory_bytes: 584
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	int x;
	cin>>x;
	for (int i = 1; i*i <= x; ++i)
	{
		if(!(x%i)){
			int d=i;
			for (int A = -300; A <= 300; ++A)
			{
				int B=A-d;
				if((A*A*A*A*A-B*B*B*B*B)==x){
					cout<<A<<" "<<B<<"\n";
					return 0;
				}
			}
			d=x/i;
			for (int A = -300; A <= 300; ++A)
			{
				int B=A-d;
				if((A*A*A*A*A-B*B*B*B*B)==x){
					cout<<A<<" "<<B<<"\n";
					return 0;
				}
			}
		}
	}
	return 0;
}
//long long
//array bounds
//special cases
//binary search

Measured memory_bytes: 3648
def gcd(a,b):
  while b:a,b=b,a%b
  return a
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for k in range(1,k+1):
      ans+=gcd(i,gcd(j,k))
print(ans)

Measured memory_bytes: 68708
a=[]
for _ in range(3):
  b=list(map(int,input().split()))
  a.append(b)
  
n=int(input())
for _ in range(n):
  x=int(input())
  for i in range(3):
    for j in range(3):
      if a[i][j]==x:
        a[i][j]=-1
        
if a[0][0]==a[0][1]==a[0][2] or a[1][0]==a[1][1]==a[1][2] or a[2][0]==a[2][1]==a[2][2] or a[0][0]==a[1][0]==a[2][0]  or a[0][1]==a[1][1]==a[2][1] or a[0][2]==a[1][2]==a[2][2] or a[0][0]==a[1][1]==a[2][2] or a[0][2]==a[1][1]==a[2][0]:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 9260
#include <iostream>
#include <assert.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <queue>

// 40 min left...

int main(){
    int32_t N, M;
    std::cin >> N >> M;

    std::vector<std::vector<int32_t>> rewards(M, std::vector<int32_t>(0));
    int32_t A,B;
    for(int32_t i = 0; i < N; i++){
        std::cin >> A >> B;
        if(A <= M){
            rewards[A-1].push_back(B);
        }
    }

    std::priority_queue<int32_t> pque;
    int64_t res = 0;
    for(int32_t i = 0; i < M; i++){
        if(!rewards[i].empty()){
            for(auto& j : rewards[i]){
                pque.push(j);
                //std::cout << "push(i,j): " << i << "," << j << std::endl;
            }
        }
        if(!pque.empty()){
            res += pque.top();
            pque.pop();
        }
    }
    std::cout << res;

    //std::vector< std::pair<int32_t, int32_t>> pairs(N);
    //for(auto &i : pairs){
    //    std::cin >> i.first >> i.second;
    //}

    // the cost for all job is 1.
    // constraints: Ai job must be done before M - Ai
    // max reward until D with I input dp[I][D]
    // reordering with A is needed?
    // NlogN
    // std::sort(pairs.begin(), pairs.end(), std::greater<>());
    // dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + B[i]) @ A[i]+j <= M;
    // dp[i][j] = dp[i-1][j-1] @ A[i]+j > M;
    // This is n^2 approach and had RE.
    // int32_t dp[N+1][M+1] = {};
    //for(int32_t i = 1; i <= N; i++){
    //    for(int32_t j = 1; j <=  M; j++ ){
    //        if(j + pairs[i-1].first > M + 1){
    //            dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
    //        }
    //        else{
    //            dp[i][j] = std::max(dp[i-1][j-1] + pairs[i-1].second, dp[i-1][j]);
    //        }
    //        //std::cout << i <<"," << j << ":"  << dp[i][j] << std::endl;
    //    }
    //}
    //std::cout << dp[N][M];

    return 0;
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A,B,M; cin>>A>>B>>M;
    vi a(A),b(B);
    int ma=101010,mb=101010;
    rep(i,A){
        cin>>a[i];
        chmin(ma,a[i]);
    }
    rep(i,B){
        cin>>b[i];
        chmin(mb,b[i]);
    }
    int ans=ma+mb;
    rep(i,M){
        int x,y,c; cin>>x>>y>>c; x--; y--;
        chmin(ans,a[x]+b[y]-c);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
A = int(input())
B = int(input())
C = int(input())
X = int(input())
k = 0
for p in range(A+1):
  for q in range(B+1):
    for r in range(C+1):
      if (10*p+2*q+r == X//50):
        k += 1
print(k)

Measured memory_bytes: 3060
#include <cstdio>
long long a [100010];
int main (){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
int zero =0;
for(int i=0;i<n;i++)if(a[i]==0) zero ++;
if(zero >0){
printf("0\n");
return 0;
}
long long prod =1;
for(int i=0;i<n;i++){
if(a[i ] <=1000000000000000000/ prod ){
prod *=a[i];
}else{
printf("-1\n");
return 0;
}
}
printf("%lld\n",prod );
}


Measured memory_bytes: 2460
from collections import deque

N,Q=map(int,input().split())
G=[[] for i in range(N+1)]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a].append(b)
  G[b].append(a)

P=[0 for i in range(N+1)]
for i in range(Q):
  p,x=map(int,input().split())
  P[p] += x

def bfs(s):
    seen = [0 for i in range(N+1)]
    prev = [0 for i in range(N+1)]
    todo = deque([])
    now = s
    seen[now]=1
    todo.append(now)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          P[b] += P[a]

bfs(1)
print(*P[1:])

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

int main(){
	long long A = 1;
	int N;
	cin >> N;
	for(int i=0;i<N;i++){
		long long S;
		cin >> S;
		if(S == 0){
			A = 0;
			break;
		}
		if(A == -1) continue;
		long long B = A;
		A *= S;
		if(A > 1000000000000000000 || B > LLONG_MAX / S){
			A = -1;
		}
	}
	cout << A << endl;
}


Measured memory_bytes: 3640
using System;

class Program
{
    static void Main(string[] args) {
        String ret;
        ret = process(new System.IO.StreamReader(Console.OpenStandardInput()));
        //ret = process("20 4");

        Console.WriteLine(ret);
        //Console.ReadLine();
    }

    static string process(string input) {
        return process(new System.IO.StringReader(input));
    }

    static string process(System.IO.TextReader input) {
        var s     = input.ReadLine();
        var spl   = s.Split(' ');
        int n     = int.Parse(spl[0]);
        int d     = int.Parse(spl[1]);

        int capa = (2 * d) + 1;

        var ret = n / capa;
        if (n % capa != 0) ret++;
        return ret.ToString();
    }
}

Measured memory_bytes: 13140
# -*- coding: utf-8 -*-
# abc142/abc142_a
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    print(1-N//2/N)
    return

main()


Measured memory_bytes: 3064
num,taste = gets.split.map(&:to_i)

tastes = []
num_a = (1..num).to_a

num_a.each do |n|
  tastes << taste + n - 1
end

if tastes.include?(0)
  puts tastes.sum
elsif 1 <= tastes.min
  puts tastes.sum - tastes.first
else tastes.max <= -1
  puts tastes.sum - tastes.last
end


Measured memory_bytes: 14320
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> a;
int main(){
    
    int n;
    
    scanf("%d",&n);
    
    for(int i=0,tmp;i<n;i++) {
        
    scanf("%d",&tmp);
        a.push_back(tmp);
}
    
    sort(a.begin(),a.end());
    
    int al = 0;
    int sl = 0;
    
    for(int i=0;i<n;i++){
        if(i&1) sl+=a[i];
        else al +=a[i];
    }
    
    printf("%d\n",(sl-al > 0) ? sl-al : -(sl-al));
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
const int MOD=(int)1e9+7;
using namespace std;
int dsum(int x){
    int ans=0;
    while (x>0){
        ans += x%10;
        x/=10;
    }
    return ans;
}
int main(){
    int n,a,b,ans=0;
    cin>>n>>a>>b;
    REP(i,n+1) if(dsum(i)<=b and a<=dsum(i))ans+=i;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  char s[500010],c[500010];
  int i,r=0,d[500010]={};
  scanf("%s %s",s,c);
  for(i=0;s[i];i++){
    if(s[i]==c[r]){
      d[i]=1;
      r++;
    }
  }
  if(c[r])goto END;
  while(i--){
    if(s[i]==c[r-1]){
      if(d[i]==0)goto END;
      r--;
    }
  }
  printf("yes\n");
  return 0;
 END:;
  printf("no\n");
  return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define endl '\n';
#define FASTER ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll POSITIVE_INFINITY = 9223372036854775807;
const ll NEGATIVE_INFINITY = -9223372036854775807;
const ll MOD = 1000000007;
const ld PI = acos(-1.0);

template <typename T> inline T bigMod(T A,T B,T M = MOD){A %= M;T ret = 1;while(B){if(B & 1) ret = (ret * A) % M;A = (A * A) % M;B = B >> 1;}return ret;}
template <typename T> inline T invMod (T A,T M = MOD){return bigMod(A,M-2,M);}

const int N = 200005;

int main(){
  FASTER;
  string ar;
  cin >> ar;
  int n = 0;
  n += (ar[0] - '0');
  n *= 10;
  n += (ar[1] - '0');
  int m = 0;
  m += (ar[2] - '0');
  m *= 10;
  m += (ar[3] - '0');

  if (m > 0 && m <= 12 && (n == 0 || n > 12)){
    cout << "YYMM\n";
  }
  else if (n > 0 && n <= 12 && (m == 0 || m > 12)){
    cout << "MMYY\n";
  }
  else if (n > 0 && n <= 12 && m > 0 && m <= 12){
    cout << "AMBIGUOUS\n";
  }
  else {
    cout << "NA\n";
  }

  return 0;
}


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

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


typedef pair<int, int> P;

int h, w;
vector<vector<char>> v;

const P NOT_FOUND = make_pair(-1,-1);

int main() {
    
    cin >> h >> w;
    v = vector<vector<char>>(h, vector<char>(w));
    
    REP(i,h) {
        REP(j,w) {
            char c;
            cin >> c;
            v[i][j] = c;
        }
    }
    
    int x = 0;
    int y = 0;
    
    bool poss = false;
    int cnt = 1;
    while (true) {
        if (x+1 < h && v[x+1][y] == '#') {
            x++;
        }else if (y+1 < w && v[x][y+1] == '#') {
            y++;
        }else {
            break;
        }
        cnt++;
        
        if (x == h-1 && y == w-1) {
            poss = true;
            break;
        }
    }
    
    int cntall = 0;
    REP(i,h) {
        REP(j,w) {
            if (v[i][j] == '#') {
                cntall++;
            }
        }
    }
    
    if (poss && cnt == cntall) {
        cout << "Possible" << endl;
        return 0;
    }
    cout << "Impossible" << endl;
    return 0;
}

Measured memory_bytes: 256
while 1:
    n,x=map(int, input().split())
    sum=0
    if n+x==0:
        break
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            for k in range(j+1,n+1):
                if i+j+k==x:
                    sum=sum+1
     
    print(sum)        


Measured memory_bytes: 5592