akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int x,y,z;
struct A{long a,b,c;};
vector<A>a;
vector<long>L,R;
main()
{
	cin>>x>>y>>z;
	for(int i=0;i<x+y+z;i++)
	{
		long s,d,f;
		cin>>s>>d>>f;
		a.push_back({s,d,f});
	}
	sort(a.begin(),a.end(),[](A a,A b){return a.a-a.b<b.a-b.b;});
	priority_queue<long>LL,RR;
	long nL=0,nR=0;
	for(int i=0;i<y;i++)
	{
		LL.push(a[i].c-a[i].b);
		nL+=a[i].b;
	}
	L.push_back(nL);
	for(int i=y;i<y+z;i++)
	{
		LL.push(a[i].c-a[i].b);
		nL+=a[i].b+LL.top();LL.pop();
		L.push_back(nL);
	}
	for(int i=0;i<x;i++)
	{
		RR.push(a[x+y+z-1-i].c-a[x+y+z-1-i].a);
		nR+=a[x+y+z-1-i].a;
	}
	R.push_back(nR);
	for(int i=x;i<x+z;i++)
	{
		RR.push(a[x+y+z-1-i].c-a[x+y+z-1-i].a);
		nR+=a[x+y+z-1-i].a+RR.top();RR.pop();
		R.push_back(nR);
	}
	long ans=0;
	for(int i=0;i<L.size();i++)ans=max(ans,L[i]+R.back()),R.pop_back();
	cout<<ans<<endl;
}

Measured memory_bytes: 4980
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "cmath"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

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

	string s;
	cin >> s;
	int y, x;
	cin >> x >> y;
	int r = 0;
	vector<int>h;
	vector<int>w;
	int box = 0;
	s.push_back('T');
	bool yoko = true;
	bool migi = true;
	for (auto i : s) {
		if (i == 'F') {
			box++;
		}
		else {
			if (migi) {
				migi = false;
				r += box;
			}
			else if (yoko&&box) {
				w.push_back(box);
			}
			else if(!yoko&&box){
				h.push_back(box);
			}
			yoko ^= true;
			box = 0;
		}
	}
	int wsum = 0;
	for (auto i : w) {
		wsum += i;
	}
	vector<bool>wdp(8001);
	wdp[0] = true;
	for (auto i : w) {
		for (int j = 8000; j >= i; j--) {
			wdp[j] = wdp[j] | wdp[j - i];
		}
	}
	int hsum = 0;
	for (auto i : h) {
		hsum += i;
	}
	vector<bool>hdp(8001);
	hdp[0] = true;
	for (auto i : h) {
		for (int j = 8000; j >= i; j--) {
			hdp[j] = hdp[j] | hdp[j - i];
		}
	}
	x -= r;
	//cout << wsum << " " << hsum << endl;
	//cout << x << " " << y << endl;
	if ((wsum - abs(x)) % 2 || (hsum - abs(y)) % 2) {
		cout << "No\n";
		return 0;
	}
	if (wdp[wsum - (wsum - abs(x)) / 2] && hdp[hsum - (hsum - abs(y)) / 2]) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";
	}
	return 0;
}

Measured memory_bytes: 256
const MOD: usize = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let h: usize = sc.read();
    let w: usize = sc.read();
    let a: usize = sc.read();
    let b: usize = sc.read();

    let combination = Combination::new(w + h + 1, MOD);

    let mut ans = 0;
    let mut cur_h = h - a - 1;
    let mut cur_w = b;
    loop {
        let prev = combination.get(cur_h + cur_w, cur_w);
        let next = combination.get(w - 1 - cur_w + h - 1 - cur_h, w - 1 - cur_w);
        ans += (prev * next) % MOD;
        ans %= MOD;
        if cur_w == w - 1 || cur_h == 0 {
            break;
        }
        cur_h -= 1;
        cur_w += 1;
    }

    println!("{}", ans);
}

pub struct Combination {
    fact: Vec<usize>,
    inv_fact: Vec<usize>,
    modulo: usize,
}

impl Combination {
    pub fn new(max: usize, modulo: usize) -> Combination {
        let mut inv = vec![0; max + 1];
        let mut fact = vec![0; max + 1];
        let mut inv_fact = vec![0; max + 1];
        inv[1] = 1;
        for i in 2..(max + 1) {
            inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo;
        }
        fact[0] = 1;
        inv_fact[0] = 1;
        for i in 0..max { fact[i + 1] = fact[i] * (i + 1) % modulo; }
        for i in 0..max {
            inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo;
        }
        Combination { fact: fact, inv_fact: inv_fact, modulo: modulo }
    }

    pub fn get(&self, x: usize, y: usize) -> usize {
        assert!(x >= y);
        self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo
    }
}

struct Scanner {
    ptr: usize,
    length: usize,
    buf: Vec<u8>,
    small_cache: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024] }
    }

    fn load(&mut self) {
        use std::io::Read;
        let mut s = std::io::stdin();
        self.length = s.read(&mut self.buf).unwrap();
    }

    fn byte(&mut self) -> u8 {
        if self.ptr >= self.length {
            self.ptr = 0;
            self.load();
            if self.length == 0 {
                self.buf[0] = b'\n';
                self.length = 1;
            }
        }

        self.ptr += 1;
        return self.buf[self.ptr - 1];
    }

    fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' }

    fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, {
        let mut b = self.byte();
        while Scanner::is_space(b) {
            b = self.byte();
        }

        for pos in 0..self.small_cache.len() {
            self.small_cache[pos] = b;
            b = self.byte();
            if Scanner::is_space(b) {
                return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]).parse().unwrap();
            }
        }

        let mut v = self.small_cache.clone();
        while !Scanner::is_space(b) {
            v.push(b);
            b = self.byte();
        }
        return String::from_utf8_lossy(&v).parse().unwrap();
    }
}



Measured memory_bytes: 10492
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    string s;
    cin >> s;
    ll n = s.size();

    vl dp0(n+1);  // dp0[i+1] : a+bの先頭i文字(iは0-index)がsの先頭i文字と一致しているときの組の数
    vl dp1(n+1);  // dp1[i+1] : a+bの先頭i文字(iは0-index)がsの先頭i文字より辞書順で小さいときの組の数
    dp0[0] = 1;
    rep(i, n) {
        // (a[i], b[i]) = (0, 0) のとき
        if(s[i] == '0') {
            dp0[i+1] += dp0[i];
            dp1[i+1] += dp1[i];
        }
        else if(s[i] == '1') {
            dp1[i+1] += (dp0[i] + dp1[i]);
        }
        // (a[i], b[i]) = (0, 1), (1, 0) のとき
        if(s[i] == '0') {
            dp1[i+1] += 2*dp1[i];
        }
        else if(s[i] == '1') {
            dp0[i+1] += 2*dp0[i];
            dp1[i+1] += 2*dp1[i];
        }
        dp0[i+1] %= mod;
        dp1[i+1] %= mod;
    }

    out((dp0[n] + dp1[n])%mod);
    re0;
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;

ll n;
ll MOD=1e9+7;
vector<pair<ll,ll>> g[303];
ll dp[303][303][303];

ll f(ll x, ll y, ll z){
	ll &r=dp[x][y][z];
	if(r>=0)return r;
	ll m=max({x,y,z});
	if(m==n+1){
		r=333333336; return r;
	}
	for(auto i:g[m]){
		ll tot=(x>=i.fst)+(y>=i.fst)+(z>=i.fst);
		if(tot!=i.snd){
			r=0; return r;
		}
	}
	/*r=(f(m+1,y,z)+f(x,m+1,z));
	if(r>=MOD)r-=MOD;
	r+=+f(x,y,m+1);
	if(r>=MOD)r-=MOD;*/
	r=(f(m+1,y,z)+f(x,m+1,z)+f(x,y,m+1))%MOD;
	return r;
}

int main(){FIN;
	ll m; cin>>n>>m;
	pair<pair<ll,ll>,ll> a[m];
	fore(i,0,m)cin>>a[i].fst.fst>>a[i].fst.snd>>a[i].snd;
	fore(i,0,m){
		g[a[i].fst.snd].pb({a[i].fst.fst,a[i].snd});
	}
	mset(dp,-1);
	cout<<f(0,0,0);
	
	return 0;
}

Measured memory_bytes: 217600
#include <bits/stdc++.h>
using namespace std;
using Int = int_fast64_t;

Int n;
vector<vector<Int>> ans;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	ans.resize(n, vector<Int>(n, -1));
	for(Int i=0; (1ll<<i)<=n; ++i){
		for(Int j=1; j<=n; ++j){
			for(Int k=j+1; k<=n; ++k){
				if((j&((1<<i)-1)) == (k&((1<<i)-1))){
					ans[j-1][k-1] = i+1;
				}
			}
		}
	}
	for(Int i=0; i<ans.size(); ++i)
		for(Int j=i+1; j<ans[i].size(); ++j)
			cout << ans[i][j] << " \n"[j+1==ans[i].size()];
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
const double Pi = acos(-1.0);

int main()
{
    double a, b, x;
    cin >> a >> b >> x;
    if (x > a*a*b/2.0)
    {
        x -= a*a*b/2.0;
        x *= 2.0;
        x /= (a*a);
        double ans = atan(a/(b-x));
        ans *= (180.0/Pi);
        cout << fixed << setprecision(10) << 90.0 - ans << endl;
    }
    else
    {
        x *= 2.0;
        x /= (a*b);
        double ans = atan(x/b);
        ans *= (180.0/Pi);
        cout << fixed << setprecision(10) << 90.0 - ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

//using Graph = vector<vector<edge>>;
using dou =long double;
string yes="yes";
string Yes="Yes";
string YES="YES";
string no="no";
string No="No";
string NO="NO";

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define rep(i, n)         for(ll i = 0; i < (ll)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(ll i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define query int qq;std::cin >> qq;rep(qqq,qq)
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout <<"Case #" <<qqq+1<<": "
#define RES(a,i,j) a.resize(i);rep(ii,i)a[ii].resize(j); 
#define as assign
#define ffor for(;;)
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout<<a<<" "<<b<<" "<<c<<std::endl
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define ssum(a) accumulate(a,0ll) 
#define gre(n) greater<n>()

typedef long long ll;
//
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
//typedef long long T;
const int INF = 1000000000;
const double dINF = 1000000000;
const ll INF64 = 922337203685477580ll;
const ll MOD = 1000000007ll;
//const ll MOD = 998244353ll;
const dou pi=3.141592653589793*2;
ll ggd(ll a, ll b) {//最小公倍数，最大公約数
	if(a<b)swap(a,b);
	if (b == 0) {
		return a;			
	}
	return ggd(b, a % b);
}
ll lcm(ll number1,ll number2){
	return number1/ggd(number1,number2)*number2;	
}
int main(){
    int n,k;
    std::cin >> n>>k;
    VEC(int,a,n);
    sort(all(a));
    int ma=a[n-1];
    int d=ggd(a[0],a[1]);
    rep(i,n){
        d=ggd(d,a[i]);
    }
    if(k<=ma&&k%d==0)std::cout << "POSSIBLE" << std::endl;
    else std::cout << "IMPOSSIBLE" << std::endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  char a,b;
  cin>>a>>b;
  if(a==b) cout<<'H'<<endl;
  else cout<<'D'<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

vector<int> G[MAX_N];

int main() {
    int n, m;
    cin >> n >> m;
    int f[n] = {};
    rep(i,m){
        int a,b; cin >> a >> b;
        a--; b--;
        f[a]++; f[b]++;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int flag = 0;
    rep(i,n){
        if(f[i] % 2 == 1){
            cout << "No" << endl;
            return 0;
        }else{
            flag += f[i]/2 - 1;
        }
    }

    if(flag>=3){
        cout << "Yes" << endl;
    }else if(flag == 2){
        int ma = 0;
        rep(i,n){
            ma = max(ma,f[i]);
        }
        if(ma == 6){
            cout << "Yes" << endl;
            return 0;
        }
        int s = 0; int t = 0;
        rep(i,n){
            if(f[i] == 4){
                t = s; s = i;
            }
        }
        rep(i,4){
            int ff[n] = {};
            ff[s] = 1;
            int x = G[s][i];
            while(true){
                ff[x] = 1;
                rep(j,2){
                    if(ff[G[x][j]] == 0){
                        x = G[x][j];
                        break;
                    }
                }
                if(x == t)break;
                if(G[x][0] == s || G[x][1] == s){
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
        cout << "No" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}
 
 


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

N,M,X,Y = list(map(int, input().rstrip().split()))
x_list = list(map(int, input().rstrip().split())) + [X]
y_list = list(map(int, input().rstrip().split())) + [Y]
#-----

x_list.sort()
y_list.sort()

x_max = x_list[-1]
y_min = y_list[0]

print( "No War" if  (y_min - x_max) > 0 else "War")


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

#define rep(i,n) for(int i=0;i<(n);i++)
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define dbg(x) cout<<#x"="<<x<<endl

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

#define INF 1000000000
#define DAYS 100

int main(){
  int date[DAYS];

  while(true){
    int n,q;
    cin >> n >> q;
    if(n==0 && q==0) break;

    rep(i,DAYS) date[i]=0;

    rep(i,n){
      int m;
      scanf("%d",&m);
      rep(j,m){
	int d;
	scanf("%d", &d);
	date[d-1]++;
      }
    }

    int res=0, resN=q-1;
    rep(i,DAYS){
      if(date[i]>resN){
	res=i+1;
	resN=date[i];
      }
    }

    cout << res << endl;

  }

}

Measured memory_bytes: 1244
var
	N,i,a,j,ni,nj:Longint;
	dp:Array[0..200000,0..3]of int64;
begin
read(N);
for i:=0 to N do for j:=0 to 2 do dp[i,j]:=-1000000000000000000;
dp[0,0]:=0;
for i:=0 to N-1 do begin
read(a);
for j:=0 to 2 do begin
if dp[i+1,j+1]<dp[i,j]then dp[i+1,j+1]:=dp[i,j];
ni:=i+2;if ni>N then ni:=N;
nj:=j;if i+2=N then inc(nj);
if dp[ni,nj]<dp[i,j]+a then dp[ni,nj]:=dp[i,j]+a;
end;
end;
writeln(dp[N,1+N mod 2]);
end.


Measured memory_bytes: 6468
#include <iostream>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (a*a+b*b == c*c || b*b+c*c == a*a || a*a+c*c == b*b) {
            cout << "YES" <<endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1152
def pd(x):
  i = 2
  table = []
  while i * i <= x:
    while x % i == 0:
      x //= i
      table.append(i)
    i += 1
  if x > 1:
    table.append(x)
  return table

n,p=map(int,input().split())
if n==1 or p==1:
    print(p)
    exit()
l=pd(p)
ans=1
r={}
for i in l:
    while p%i==0:
        if i in r: r[i]+=1
        else: r[i]=1
        p//=i
    if i>=p: break
for i in r:
    #if (r[i]//n)>0: ans*=i*(r[i]//n)
    if (r[i]//n)>0: ans*=(i**(r[i]//n))
print(ans)


Measured memory_bytes: 38768
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]

res=0
def func(n):
	x=1
	for i in range(1,n+1):
		x*=i
	return x

for i in range(n-1):
	for j in range(i+1,n):
		res+=((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**0.5*2*func(n-1)
print(res/func(n))


Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;

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

template <typename T>
function<T(T, T)> op_max = [](T a, T b) -> T { return max(a, b); };
template <typename T>
function<T(T, T)> op_min = [](T a, T b) -> T { return min(a, b); };

template <typename T>
function<T(T, T)> op_sum = [](T a, T b) -> T { return a + b; };

namespace detail {
template <typename T, std::size_t NDIMS>
struct vector_builder {
  using type = std::vector<typename vector_builder<T, NDIMS - 1>::type>;

  static type make(std::vector<std::size_t> dims, const T& v = {}) {
    const auto vec = std::vector<T>(dims.empty() ? 0 : dims.back(), v);
    if (!dims.empty()) dims.pop_back();
    return vector_builder<std::vector<T>, NDIMS - 1>::make(dims, vec);
  }
};

template <typename T>
struct vector_builder<T, 1> {
  using type = std::vector<T>;

  static type make(std::vector<std::size_t> dims, const T& v = {}) {
    return type(dims.empty() ? 0 : dims.back(), v);
  }
};
}  // namespace detail

template <typename T, typename... SIZE_T>
auto exvector(const T& v, SIZE_T... dims) {
  static_assert(sizeof...(dims) != 0, "invalid dimension");
  std::vector<std::size_t> vec_dims{dims...};
  return detail::vector_builder<T, sizeof...(dims)>::make(vec_dims, v);
}

using namespace std;
//********************  dumps ************************//

template <typename T>
void dump(const T& data, vector<int>& iter) {
  cout << data << " ";
}
template <typename T>
void dump(const vector<T>& data, vector<int>& iter) {
  for (auto elem : data) dump(elem, iter);
  cout << endl;
}

template <typename T>
void dump(const vector<vector<T>>& data, vector<int>& iter) {
  for (auto elem : iter) {
    cout << "[" << elem << "]";
  }
  cout << endl;
  for (int i = 0; i < data.size(); i++) {
    iter.push_back(i);
    dump(data[i], iter);
    iter.pop_back();
  }
  cout << endl;
}

template <typename T>
void dump(const vector<T>& data, int dummy) {
  for (int i = 0; i < data.size(); i++) {
    cout << "[" << i << "] " << data[i] << endl;
  }
}
template <typename T>
void dump(const T& data) {  // T : data, U = base type val.
  vector<int> iter;
  dump(data, iter);
}
///////////////////////////////////////////////

void solve(long long N, std::vector<long long> A) {
  LL minim = -(1LL << 50);
  vector<LL> dp = {0, minim};
  for (int i = 0; i < N; i++) {
    vector<LL> next = {minim, minim};
    for (int j = 0; j < 2; j++) {
      chmax(next[j], dp[j] + A[i]);
      chmax(next[j], dp[j ^ 1] - A[i]);
    }
    dp = next;
  }
  cout << dp[0] << endl;
}

int main() {
  cout << setprecision(10);
  long long N;
  scanf("%lld", &N);
  std::vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
  }
  solve(N, std::move(A));
  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	if(n==1) printf("1\n");
	if(n>=2 && n<4) printf("2\n");
	if(n<8 && n>=4) printf("4\n");
	if(n<16 && n>=8) printf("8\n");
	if(n<32 && n>=16) printf("16\n");
	if(n<64 && n>=32) printf("32\n");
	if(n<128 && n>=64) printf("64\n");
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};

class MysteriousNumber{

public:
  int num;
  int operator+(const MysteriousNumber& mn){
    return (num - mn.num) * fast_pow(10,compute_digit(num+mn.num))
      + (num+mn.num);
  }
  MysteriousNumber(int _n) : num(_n){}

private:
  int compute_digit(int n){
    int res = 0;
    while(n > 0){
      n/=10;
      res++;
    }
    return res;
  }

  ll fast_pow(ll x, ll n){
    ll res = 1;
    while(n > 0) {
      if (n & 1) res = res * x;
      x = x * x;
      n >>= 1;
    }
    return res;
  }

};
int main(){
  string str;
  while(cin >> str){
    int whole = atoi(str.c_str());
    int res = 0;
    for(int len=0;len<str.size();len++){
      string front_str = str.substr(0,len);
      string rear_str = str.substr(len,str.size()-len);
      int front_num = atoi(front_str.c_str());
      int rear_num = atoi(rear_str.c_str());

      if((rear_num - front_num) < 0) continue;
      if((rear_num - front_num) % 2 != 0) continue;

      MysteriousNumber b((rear_num - front_num) / 2);
      MysteriousNumber a(front_num + b.num);
      if(a + b == whole){
	res++;
      }
    }
    printf("%d\n",res);
  }
}

Measured memory_bytes: 1196
#define _USE_MATH_DEFINES
#include  <iostream>
#include  <algorithm>
#include  <climits>
#include  <vector>
#include  <string>
#include  <cstring>
#include  <stack>
#include  <queue>
#include  <cmath>
#include  <iomanip>
#include  <set>
#include  <map>
#include  <new>
#include <cstdint>
#include <cctype>
#include  <cstdio>
using namespace std;
#define rep(i,n)  for(int i = 0; i < n; i++)
#define lrep(i,n,m)  for(int i = n; i < m; i++)

using ll = long long;
using ld = long double;
using Vii = vector<vector<int> >;
using Gjudge = vector<vector<bool>>;
using Vi = vector<int>;
using Vl = vector<ll>;
using Vd = vector<double>;
using Vld = vector<long double>;
using Vll = vector<vector<ll> >;
using Vldd = vector<vector<ld> >;
using Vs = vector<string>;
using Vb = vector<bool>;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using Pli = pair<ll, int>;
using VPi = vector<Pi>;
using VPl = vector<Pl>;
using VPli = vector<Pli>;
using Ti = tuple<int, int, int>;
using Tl = tuple<ll, ll, ll>;

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

const int Mod = static_cast<int>(1e9 + 7);
const int INF = INT_MAX / 10;
const ll LINF = LLONG_MAX / 10;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };


int gcnt(int h, int w, Vi A, Vs G)
{
	for (int u : A) {
		if (u < h) {
			rep(i, w) G[u][i] = '.';
		}
		else {
			rep(i, h) G[i][u - h] = '.';
		}
	}

	int t = 0;
	rep(i, h) {
		rep(j, w) {
			if (G[i][j] == '#') t++;
		}
	}
	return t;
}


int main()
{
	int h, w, k;

	cin >> h >> w >> k;
	Vs G(h);

	rep(i, h) {
		cin >> G[i];
	}

	int s = h + w;
	//Vi cnt(s, 0);
	//rep(i, h) {
	//	rep(j, w) if (G[i][j] == '#') cnt[i]++;
	//}

	//rep(j, w) {
	//	rep(i, h) if (G[i][j] == '#') cnt[h + j]++;
	//}

	/*for (int u : cnt) cout << u << endl;*/

	int ans = 0;
	for (int bit = 0; bit < (1 << s); ++bit)
	{
		Vi A;
		for (int i = 0; i < s; ++i) {
			if (bit & (1 << i)) { // i が bit に入るかどうか
				A.push_back(i);

			}
		}
		if (gcnt(h, w, A, G) == k) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3620
n=int(input())
a=[int(x) for x in input().split()]
x=1
bb=pow(10,18)
for i in range(n):
    if (a[i]==0):
        print(0)
        exit()
for i in range(n):
    x*=a[i]
    if (x>bb):
        print(-1)
        exit()
print(x)

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

int main() {
	int N, M, K;
	cin >> N >> M >> K;
	for (int i = 0; i <= N; i++) {
		int nowcnt = i*M;
		int zougen = N-i-i;
		for (int j = 0; j <= M; j++) {
			if (nowcnt + (j*zougen) == K) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
s=str(input())
n=len(s)
for i in range((n-1)//2):
    if s[i]!=s[-(i+1)]:
        print("No")
        exit()
if s[:(n-1)//2]!=s[((n-1)//2)+1:]:
    print("No")
    exit()
print("Yes")



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

int main(){
    int W,H,x,y,r;
    cin >> W >> H >> x >> y >> r;
    
    if(x - r >= 0 && x + r <= W && y - r >= 0 && y + r <= H){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3092
def GCD(m, n)
	return 0 if m == 0 || n == 0
	while m != 0 && n != 0
		if m > n then
			m %= n
		else
			n %= m
		end
	end
	return [m, n].max
end

def LCM(m, n)
	return 0 if m == 0 || n == 0
	return m * n / GCD(m, n)
end



n = gets.chomp.to_i
arr = gets.chomp.split.map(&:to_i).sort
ngo = arr[0]
1.upto(n-1) do |i|
	ngo = GCD(ngo, arr[i])
end
puts ngo



Measured memory_bytes: 23248
N,M = map(int,input().split())
mod = 10**9+7
import collections 
# 素因数分解：Counter型で提出
def is_prime(n):
    ans = []
    for i in range(2,int(n**0.5)+1):
        while not n%i:
            n //= i
            ans.append(i)
    if n !=1:
        ans.append(n)
    return collections.Counter(ans)

#重複組み合わせ
def comb(v):
    ans = 1
    for i in range(1,v+1):
        ans *= N+i-1
        ans *= pow(i,mod-2,mod)
        ans %= mod
    return ans

ans = 1
for v in is_prime(M).values():
    ans *= comb(v)
    ans %= mod
print(ans)

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

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

using namespace std;

typedef long long int lli;

int main () {
    int N;
    cin >> N;
    int ans = 0;
    REP (i, 0, N) {
        int l, r;
        cin >> l >> r;
        ans += (r - l + 1);
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

int main() {
  char c;
  cin >> c;
  if( c == 'A' )
    cout << 'T' << endl;
  else if( c == 'T' )
    cout << 'A' << endl;
  else if( c == 'G' )
    cout << 'C' << endl;
  else if( c == 'C' )
    cout << 'G' << endl;
  return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
MOD = 1000000007

if abs(n-m) > 1:
    print(0)
    exit(0)
else:
    n_cnt,m_cnt=1,1
    for i in range(1,n+1):
        n_cnt*=i
        n_cnt%=MOD
    for i in range(1,m+1):
        m_cnt*=i
        m_cnt%=MOD

    if abs(n-m) == 0:
        ans=n_cnt*m_cnt*2
    else:
        ans=n_cnt*m_cnt
print(ans%MOD)

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	vector<int> nums(3);
	for(int& x : nums) cin >> x;
	set<int> check(nums.begin(), nums.end());
	cout << ((int) check.size() == 2 ? "Yes" : "No") << endl;
}


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


using namespace std;

#define debug(x) cout << '>' << #x << ':' << x << endl;
#define loop(i,n) for(int i=0;i<(int)(n);i++)
#define foi(i,k,n) for(int i=(k); i<(int)(n); i+=1)
#define fod(i,n,k) for(int i=k; i>=(int)n; i-=1)
#define fast_io ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define all(x) x.begin(), x.end()
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define endl "\n"

#define int long long
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007

#define fir first
#define sec second
#define pb push_back
#define mp make_pair

typedef long long llint;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<llint> VL;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MII;
typedef set<int> SI;
string tostr(int n) {stringstream rr;rr<<n;return rr.str();}
llint toint(string s) {stringstream ss(s); llint x; ss >> x; return x;}
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//gp_hash_table<string, llint> table;


//int mpow(llint base, llint exp) {
  //base %= MOD;
  //llint result = 1;
  //while (exp > 0) {
    //if (exp & 1) result = ((llint)result * base) % MOD;
    //base = ((llint)base * base) % MOD;
    //exp >>= 1;
  //}
  //return result;
//}


//void makegraph(int n, int m){
	//int i, u, v;
	//while(m--){
		//cin>>u>>v;
		//u--, v--;
		//g[u].pb(v);
		//g[v].pb(u);
	//}
//}

//void dfs(int u, int par){
	//for(int v:g[u]){
		//if (v == par) continue;
		//dfs(v, u);
	//}
//}


// ------------------------------------------------------------------ILB----------------------------------------------------------------  //



void solve(){
	int n;
	cin >> n;
	cout << ((n + 999) / 1000 * 1000) - n;
}




int32_t main() {
	fast_io;
    int t = 1;
    //cin >> t;
    //int xx = 0
    while(t--) {
		//xx++;
		//cout << "Case ";
      solve();
    }
    return 0;
}



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

int n, a[5000], s, r;

int main() {
	while (true) {
		scanf("%d",&n);
		if (n==0) break;
		r = -1001001001;
		rep(i,n) scanf("%d",&a[i]);
		rep(i,n) {
			s = 0;
			for (int j = i; j < n; ++j) {
				s += a[j];
				r = max(r, s);
			}
		}
		printf("%d\n",r);
	}
}


Measured memory_bytes: 3124
#include<iostream>
#include<string>
#include<cmath>
using namespace std;

int n, a[100];

int main(){
	cin >> n;
	int odd = 0, even = 0;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		if (a[i] % 2 == 0) even++;
		else odd++;
	}
	int ans = pow(3, n);
	ans -= pow(2, even);
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

class Main {

	public static void main(String[] args) throws Exception {
		final Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] a = new int[N];
		for (int i = 0; i < N; i++) {
			a[i] = sc.nextInt();
		}
		boolean[] dp = new boolean[K + 1];
		Arrays.fill(dp, true);
		dp[0] = false;

		for (int i = 1; i <= K; i++) {
			for (int j = 0; j < a.length; j++) {
				if (a[j] > i) continue;
				dp[i] &= dp[i - a[j]];
			}
			dp[i] = !dp[i];
		}

		if (dp[K]) {
			System.out.println("First");
		} else {
			System.out.println("Second");
		}
	}
}


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

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


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define pb(x) push_back(x)
#define vi vector<int>
#define vs vector<string>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pcc pair<char, char>
#define pdd pair<double, double>
#define mll map<long long, long long>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define flsh fflush(stdout)
#define gcd __gcd
#define clr(x) memset(x, 0, sizeof(x))
#define mod 1000000007LL
#define mod2 998244353LL
#define INF 1000000000007
 

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> o_tree;

const int N=2e5+5;
vll v[N];
ll vis[N];
ll maxi=0;

void dfs(ll x)
{
    vis[x]=1;
    maxi++;
    for(auto it:v[x])
    {
        if(!vis[it])
        {
            dfs(it);
        }
    }
}

void solve()
{
   ll n,m;
   cin>>n>>m;
   ll i,j;
   
   for(i=0;i<m;i++)
   {
       ll x,y;
       cin>>x>>y;
       x--,y--;
       v[x].emplace_back(y);
       v[y].emplace_back(x);
   }
   ll res=0;
   for(i=0;i<n;i++)
   {
       maxi=0;
       if(!vis[i])
       {
           dfs(i);
       }
       res=max(res,maxi);
   }
   cout<<res<<"\n";

   
}



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


if (fopen("input.txt","r" ))
  {
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
  }
cout<<setprecision(20);


ll t=1;


// cin>>t;


while(t--)
{
solve();
} 


return 0;
}

Measured memory_bytes: 22320
n = int(input()) + 1
a = list(map(int, input().split())) + [0]
money = 1000
stock = 0
greater = [False for i in range(n)]
less = [False for i in range(n)]
buy = [False for i in range(n)]
for i in range(n-1):
    greater[i] = ( a[i] < a[i+1] ) 
    less[i] = a[i] > a[i+1]
    if less[i] and i < n-1:
        buy[i+1] = True
for i in range(n):
    if greater[i]:
        count = money // a[i]
        stock += count
        money -= count * a[i]
    if less[i]:
        count = stock
        stock = 0
        money += count * a[i]
print(money) 


Measured memory_bytes: 62036
s = gets.chomp
t = gets.chomp

arr = s.size.times.map do |n|
  [*0..(s.size - 1)].map do |i|
    x = i + n >= s.size ? i + n - s.size : i + n
    s[x]
  end.join
end

puts arr.include?(t) ? 'Yes' : 'No'

Measured memory_bytes: 1916
n = int(input())
kekka = []
for i in range(1, n+1):
  a = input()
  kekka.append(a)
  
print('AC x ' + str(kekka.count("AC")))
print('WA x ' + str(kekka.count("WA")))
print('TLE x ' + str(kekka.count("TLE")))
print('RE x ' + str(kekka.count("RE")))

Measured memory_bytes: 16040
using System;

    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            var count1 = 0;
            for (var i = 0; i < S.Length; i++)
            {
                if (i % 2 == 0)
                {
                    if (S[i] == '0')
                    {
                        count1++;
                    }
                    continue;
                }
                if (S[i] == '1')
                {
                    count1++;
                }
            }
            var count2 = 0;
            for (var i = 0; i < S.Length; i++)
            {
                if (i % 2 == 0)
                {
                    if (S[i] == '1')
                    {
                        count2++;
                    }
                    continue;
                }
                if (S[i] == '0')
                {
                    count2++;
                }
            }
            Console.WriteLine(Math.Min(count1,count2));
        }
    }

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

#define endl "\n"
#define all(V) V.begin(),V.end()
#define see(x) cerr << #x << " = " << x << "\n";
#define Unique(V) sort(all(V)),V.erase(unique(all(V)),V.end())
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long int LL;
typedef pair <int,int> pii;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const double PI = acos(-1.0);
const long long INF = 1e18;
const int N = 1e5 + 5;

int n;
int a[ N ][ 5 ];
int dp[ N ][ 5 ];

int main( ) {
        IO;
        cin >> n;
        for( int i = 1; i <= n; i++ ) {
                for( int j = 1; j <= 3; j++ ) {
                        cin >> a[i][j];
                }
        }
        dp[n][1] = a[n][1];
        dp[n][2] = a[n][2];
        dp[n][3] = a[n][3];
        for( int i = n - 1; i >= 1; i-- ) {
                dp[i][1] = max( dp[i+1][2] , dp[i+1][3] ) + a[i][1];
                dp[i][2] = max( dp[i+1][1] , dp[i+1][3] ) + a[i][2];
                dp[i][3] = max( dp[i+1][1] , dp[i+1][2] ) + a[i][3];
        }
        cout << max( dp[1][1] ,max( dp[1][2], dp[1][3] ) ) << endl;
        return 0;
}









Measured memory_bytes: 4224
#include <bits/stdc++.h>
//#include <boost/functional/hash.hpp>
//example: unordered_set< pair<int,int>,boost::hash< std::pair<int, int> > > used;
//priority_queue< pair<int,pair<int,int> >, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int> > > > pqueue;    //cost, vertex(行き先)
using namespace std;

#define MODULE 1000000007
#define MP make_pair
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define CONTAINS(x, y) (x.find(y)!=x.end()) //x<T1,T2>, T1 y
#define getPair(x) MP(x->first,x->second)

template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
template<typename A, size_t N, typename T>
inline void Fill(A (&array)[N], const T &val){ //usage: int dp[10][10]; Fill(dp,INF);
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef pair<int, int> P;
typedef long long LL;
const int hogeeeaee  = INT_MAX / 2;
//int_max->2*e+9 LLの時はLLONG_MAX
/*const int MAXN = 100001;

struct edge {
    edge(int to, int cost) : to(to), cost(cost) {}
    int to, cost;
};
vector<edge> graph[MAXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};*/

//-----Template---------
int n;
map<int,int> memo;
map<int,int> over;


int main(){
    ios::sync_with_stdio(false); //cout<< fixed << setprecision(10);
    //cout<<setw(4)<<setfill('0')<<"hoge"<<endl;
    cin>>n;
    for (int i = 0; i < n; ++i) {
        int tmp;
        cin>>tmp;
        memo[tmp]++;
        if(memo[tmp]>1) {
            over[tmp]++;
        }
    }
    int subnum=0;
    for (auto it=memo.begin();it!=memo.end();it++) {
        if(it->second%2==1){
            subnum+=it->second-1;
            it->second=1;
        }else{
            subnum+=it->second-2;
            it->second=2;
        }
    }
    bool rem2=false;
    for(auto it=memo.begin();it!=memo.end();it++){
        if(rem2){
            if(it->second==2){
                rem2=false;
                subnum+=2;
            }
        }else{
            if(it->second==2){
                rem2=true;
            }
        }
    }
    if(rem2)
        subnum+=2;

    cout<<n-subnum<<endl;
 }

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

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

    int A, min_cnt, cnt = 0;
    cin >> A;

    while(A % 2 == 0){
        cnt++;
        A /= 2;
    }

    min_cnt = cnt;
    
    for(int i = 0; i < N-1; i++){
        cnt = 0;
        cin >> A;
        while(A % 2 == 0){
            cnt++;
            A /= 2;
        }
        if(cnt < min_cnt) min_cnt = cnt;
    }

    cout << min_cnt << endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define MOD 1000000007
#define INF 1000000000

void solve_abc_d() {
	ll n;
	ll x;
	ll k;
	ll l_ans = 0;
	cin >> n;

	map<ll, ll> m;
	ll a;
	rep(i, n) {
		cin >> a;
		++m[a];
	}

	ll sum = 0;
	ll num = 0;
	for (auto itr = m.begin(); itr != m.end(); itr++) {
		if (itr->second % 2 == 1) {
			sum += itr->second - 1;
		}
		else {
			sum += itr->second - 2;
			if (num == 0) {
				num++;
			}
			else {
				sum += 2;
				num = 0;
			}
		}
	}

	l_ans = n - sum - num * 2;

	cout << l_ans << "\n";
	return;
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed;
	cout << setprecision(7);

	solve_abc_d();

	return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define rep1(i,n) for(int i=1;i<=n;++i)
#define all(a) a.begin(),a.end()

using P = pair<int,int>;
using Edge = P; // <dist,to>
#define cost first
#define to second
vector<vector<Edge>> g;

// <dist,id>
P farthest(int from, int v, int cost){
    P far = {cost,v};
    for(Edge e : g[v]){
        if(e.to == from) continue;
        if((int)g[e.to].size() == 1) continue;
        P res = farthest(v, e.to, cost+e.cost);
        far = max(far,res);
    }
    return far;
}

int main(void){
    int n;
    while(cin>>n,n){
        vector<int> p(n+1),d(n+1);
        g = vector<vector<Edge>>(n+1);
        for(int i=2;i<=n;i++) cin>>p[i];
        for(int i=2;i<=n;i++) cin>>d[i];
        for(int i=2;i<=n;i++){
            g[i].push_back({d[i],p[i]});
            g[p[i]].push_back({d[i],i});
        }
        int all_size = accumulate(all(d),0);
        int one_way = farthest(-1,farthest(-1,1,0).second,0).first;
        int leaf_cost = 0;
        rep1(i,n){
            if((int)g[i].size() == 1){
                leaf_cost += g[i][0].first;
            }
        }
        if(n<=3){
            cout<<all_size<<endl;
        }else{
            cout<<all_size*3 - one_way - leaf_cost*2<<endl;
        }
    }

    return 0;
}



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

typedef long long ll;
#define PI 3.1415926535897932384626433
#define mod 1000000007

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

int lcm(int a, int b) { return a * b / gcd(a, b); }

int main(){
    string s;
    cin >> s;
    s.erase(s.end() - 8, s.end());
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define llong long long
#define pb(a) push_back(a)
#define INF 9999999

using namespace std;

typedef pair<int,int> P;

int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
string s[100001];
int main(){
	unsigned long long M=0,A=0,R=0,C=0,H=0;
	int N;
	
	cin>>N;
	REP(i,N)cin>>s[i];
	REP(i,N){
		if(s[i][0]=='M')M++;
		if(s[i][0]=='A')A++;
		if(s[i][0]=='R')R++;
		if(s[i][0]=='C')C++;
		if(s[i][0]=='H')H++;
	}
	unsigned long long ans=0;
	ans=M*A*R+M*A*C+M*A*H+M*R*C+M*R*H+M*C*H+A*R*C+A*R*H+A*C*H+R*C*H;
	cout<<ans<<endl;
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
#define in cin >>
#define out cout <<
#define FOR(i,k,l) for(int i(k);i<l ; i++)

int main(void) {
    int a, b;
    in(a); in(b);

    if (a < b) {
        FOR(i, 0, b) out(a);
    } else {
        FOR(i, 0, a) out(b);
    }
    cout << "\n";

}

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

#define endl '\n'
typedef pair<int, int> ii;
typedef long long ll;

#define debug(x) cerr << #x << ": " << x << endl;

#define inf 0x3f3f3f3f;

ii v[3010];

int memo[3010][3010];
int n, t;

int dp(int pos, int t){
  if(pos == n) return 0;
  if(t <= 0) return 0;
  if(memo[pos][t] != -1) return memo[pos][t];

  int ans = max( dp(pos+1, t), v[pos].second + dp(pos+1, t - v[pos].first) );
  return memo[pos][t] = ans;
}

int main(){
  int a, b;
  scanf("%d %d", &n, &t);
  for(int i = 0; i < n; i++){
    scanf("%d %d", &a, &b);
    v[i] = {a,b};
  }

  sort(v, v+n);

  memset(memo, -1, sizeof memo);

  printf("%d\n", dp(0, t));

}


Measured memory_bytes: 35840
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
const long long INF = 1LL << 60;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

vector<char> Alphabet = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char> alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int main()
{
  cout << fixed << setprecision(10);
  char N;
  cin >> N;
  rep(i,26)
  {
    if(N == Alphabet[i])
    {
      cout << "A" << endl;
    }
    else if(N==alphabet[i])
    {
      cout << "a" << endl;
    }
    
  }
  return 0;
}


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

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

Measured memory_bytes: 3632
import sys
from itertools import combinations as combi
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
res = 0
s = S[: N]
t = S[N: ]
a = dd(int)
b = dd(int)
for i in range(N + 1):
  for c in combi([x for x in range(N)], i):
    u = []
    v = []
    for j in range(N):
      if j in c: u.append(s[j])
      else: v.append(s[j])
    a["".join(u) + "?" + "".join(v)] += 1
#print(a)
for i in range(N + 1):
  for c in combi([x for x in range(N)], i):
    u = []
    v = []
    for j in range(N):
      if j in c: u.append(t[j])
      else: v.append(t[j])
    b["".join(u) + "?" + "".join(v)] += 1
for ak in a.keys():
  bk = ak[: : -1]
  res += a[ak] * b[bk]
print(res)

Measured memory_bytes: 166392
c=1
while 1:
    W=int(input())
    if W==0:break
    dp=[0]*(W+1)
    for i in range(int(input())):
        v,w=map(int, input().split(','))
        for j in range(W,w-1,-1):
            if dp[j]<dp[j-w]+v:dp[j]=dp[j-w]+v
    for i in range(W+1):
        if dp[W]==dp[i]:break
    print('Case %d:\n%d\n%d'%(c,dp[W],i))
    c+=1

Measured memory_bytes: 7652
#include <stdio.h>
#include <string.h>
#define maxn 200010
char s[maxn],t[maxn];
int main(){
	int i,n,cnt=0;
	scanf("%s%s",s,t);
	n=strlen(s);
	for(i=0;i<n;i++)
		if(s[i]!=t[i])cnt++;
	printf("%d\n",cnt);
	return 0;
}

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


int main(){
    int n;
    cin >> n;
    bool check = true;
    for (int i=0; i<n; i++){
        int a;
        cin >> a;
        if (a%2 == 0){
            if (a%3==0 || a%5 == 0){
                continue;
            }
            else{
                check = false;
            }
        }
    }
    if (check){
        cout << "APPROVED" << endl;
    }
    else{
        cout << "DENIED" << endl;
    }

    return 0;
}

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

#define INF (INT64_MAX)
#define MAX 100000

priority_queue<long long> kind[MAX];
priority_queue<long long> best;
priority_queue<long long> remain;
vector<long long> bsum;
vector<long long> rsum;

int N, K;

int main() {
	cin >> N >> K;

	for( int i = 0; i < N; i++ ) {
		int t;
		long long d;
		cin >> t >> d;
		kind[t - 1].push( d );
	}

	for( int i = 0; i < N; i++ ) {
		if( !kind[i].empty() ) {
			best.push( kind[i].top() );
			kind[i].pop();
			while( !kind[i].empty() ) {
				remain.push( kind[i].top() );
				kind[i].pop();
			}
		}
	}
	bsum.push_back( 0 );
	while( !best.empty() ) {
		bsum.push_back( bsum.back() + best.top() );
		best.pop();
	}
	rsum.push_back( 0 );
	while( !remain.empty() ) {
		rsum.push_back( rsum.back() + remain.top() );
		remain.pop();
	}
	long long ans = 0;
	for( long long x = 1; x <= K; x++ ) {
		if( x >= bsum.size() ) {
			break;
		}
		if( K - x >= rsum.size() ) {
			continue;
		}
		ans = max( ans, bsum[x] + rsum[K - x] + x * x );
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 8820
#include<iostream>
using namespace std;
int main(){
  int a[5];
  int j;
  int b=9,n=0;
  int time=0;

  cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4];
  for( j=0;j<5;j++){
  	if(a[j]%10!=0 && a[j]%10<b){
    	b=a[j]%10;
      	n=j;
    }
  }
  
  for(int i=0;i<5;i++){
		if(i!=n){
          if(a[i]<=10){
            time+=10;
          }else if(a[i]%10!=0){
  	 	 	time+=(a[i]-(a[i]%10)+10); 
          }else{
          	time+=a[i];
          }
        }
  }
  if(b!=0){
  	time+=a[n];
  }
  cout<<time<<endl;
 return 0; 
}

Measured memory_bytes: 256