akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Text;
using System.Linq;
using System.Collections.Generic;


class Program {

	const long mod = 1000000007;
	//public static int[] max;

	static void Main(string[] args) {

		char[] cs = new char[] { ' ', ',' };
		//int val = int.Parse(Console.ReadLine());
		//int[] vals = parseAry(Console.ReadLine().Split(cs));
		//string str = Console.ReadLine();
		//string[] strs = Console.ReadLine().Split(cs);

		//int[] vals = parseAry(Console.ReadLine().Split(cs));
		//int n = vals[0];
		//string res="";

		//int y = vals[0];
		//int x = vals[1];
		char a = 'a';
		string str = Console.ReadLine();
		Dictionary<char, int> dic = new Dictionary<char, int>();

		if (str == "zyxwvutsrqponmlkjihgfedcba") {

			Console.WriteLine("-1");
			return;
		}


		for (int i = 0; i < str.Length; i++) {
			dic.Add(str[i], 1);
		}
		if (dic.Count == 26) { //all 
			for (int k = 25; k >= 0; k--) {
				for (int i = str[k]+1; i <= 'z'; i++) {
					if (!dic.ContainsKey((char)i)) {
						str = str.Remove(k);
						str += ( (char)i ).ToString();
						Console.WriteLine(str);
						return;
					}				
				}
				dic.Remove((char)str[k]);
				str=str.Remove(k);
			}
		} else {
			for (int i = 'a'; i <= 'z'; i++) {
				if (!dic.ContainsKey((char)i)) {
					str += ( (char)i ).ToString();
					Console.WriteLine(str);
					return;
				}				
			}		
		}


		//deug
		Console.WriteLine("");


		return;
	}



	//　String[]  ----->  int[]
	static int[] parseAry(string[] str) {
		int[] nums = new int[str.Length];
		for (int i = 0; i < str.Length; i++) { nums[i] = int.Parse(str[i]); }
		return nums;
	}
	//　String[]  ----->  long[]
	static long[] parseAryl(string[] str) {
		long[] nums = new long[str.Length];
		for (int i = 0; i < str.Length; i++) { nums[i] = int.Parse(str[i]); }
		return nums;
	}



	//文字列を1文字ずつString[]に入れる
	static string[] strAry(String str) {
		string[] re = new string[str.Length];
		for (int i = 0; i < str.Length; i++) { re[i] = str[i].ToString(); }
		return re;
	}

}

Measured memory_bytes: 13268
def max2(x,y):
    return x if x > y else y
def min2(x,y):
    return x if x < y else y

N, K = map(int, input().split())
V = list(map(int, input().split()))
res = 0
for l in range(K+1):
    for r in range(K+1-l):
        if l+r>N:
            continue
        temp=V[:l]+V[N-r:]
        temp.sort()
        S = sum(temp)
        for cnt in range(min2(K-l-r,l+r)):
            if temp[cnt]<0:
                S -= temp[cnt]
            else:
                break
        res = max2(res, S)
print(res)

Measured memory_bytes: 73344
a,sums= list(map(int,input().split()))
yuki = sums//10000
taishi = (sums%10000) //5000
noguchi = (sums%5000) //1000
while a>yuki+taishi+noguchi:
  if ((a-(yuki+taishi+noguchi))%4==0)&(taishi>0):
    taishi-=1
    noguchi+=5
  elif yuki>0:
    yuki-=1
    taishi+=2
  else:
    break
if a==yuki+taishi+noguchi:
  print(yuki,taishi,noguchi)
else:
  print("-1 -1 -1")

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int top,s[1000];
int pop(){
	top--;
	return s[top+1];
}
int push(int a){
	s[++top]=a;
}
int main(){
	int b,a;
	top=0;
	char c[3];
	while(cin>>c){
		if(c[0]=='+'){
			a=pop();
			b=pop();
			push(a+b);
		}
		else if(c[0]=='-'){
			a=pop();
			b=pop();
			push(b-a);
		}
		else if(c[0]=='*'){
			a=pop();
			b=pop();
			push(a*b);
		}
		else{
			push(atoi(c));
		}
	}
	cout<<pop()<<endl;
	return 0;
}



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

int main(void) {
  int N;
  cin >> N;
  int A[N+1];
  int B[N+1];
  A[0] = -1;
  B[0] = -1;
  for(int i=1; i<=N; i++) cin >> A[i];

  int numB = 0;
  int lnum;
  for(int i=N; N/i != 2; i--){
    lnum = i;
    if(i == 1) break;
    if(A[i] == 1) {
      B[i] = 1; numB++;
    }else B[i] = 0;
  }
  if(lnum != 1) lnum--;
  
  for(int i=lnum; i>=1; i--){
//    int divN = N/i;
    int tmpSum = 0;
    for(int j=2*i; j<=N; j=j+i){
      tmpSum += B[j];
    }
    tmpSum = tmpSum%2;
    if(tmpSum != A[i]) {
      B[i] = 1; numB++;
    }
    else B[i] = 0;
  }
  cout << numB << endl;
  for(int i=1; i<=N; i++){
    if(B[i] == 1){
      cout << i << " ";
    }
  }
  cout << endl;

  return 0; 
}

Measured memory_bytes: 2432
// clang-format off
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
// clang-format on

const int N = 55;

int n, m, q;
int a[N], b[N], c[N], d[N];

int ans = 0;
int x[N];

void dfs(int k, int p) {
    if (k == n) {
        int t = 0;
        rep(i, q) {
            if (x[b[i]] - x[a[i]] == c[i]) t += d[i];
        }
        ans = max(ans, t);
        return;
    }

    for (int i = p; i <= m; ++i) {
        x[k] = i;
        dfs(k + 1, i);
    }
}

int main() {
    cin >> n >> m >> q;
    rep(i, q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i];
        --b[i];
    }

    dfs(0, 1);
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3596
// B.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int main(int argc, char *argv[]) {
	int n;
	cin >> n;
	map<string, int> m;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		m[s] += 1;
	}
	for (string s : {"AC", "WA", "TLE", "RE"}) {
		cout << s << " x " << m[s] << endl;
	}
	return 0;
}


Measured memory_bytes: 3640
#!/usr/bin/env python3



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())

    if N == 1:
        print("Hello World")
    else:
        A = int(input())
        B = int(input())
        print(A+B)



if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define setbits(x)  __builtin_popcount(x)
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;

//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
/*int find(int a){
     if(a==par[a])return a;
     return par[a]=find(par[a]);
}
void unite(int a,int b){
     a=find(a),b=find(b);
     if(a==b)return ;
     par[b]=a;
}
ll modexpo(ll a,ll b)
{
     ll ans=1LL;
     while(b>0)
     {
          if(b&1)ans=(ans*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return ans;
}
*/
vector<int> adj[100005];
int indeg[100005];
int par[100005];
int main(){
     int n;
     cin>>n;
     ll cost=0LL;
     ll dp[n][n];
     for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){cin>>dp[i][j];
          cost+=1LL*dp[i][j];}
     }
     cost/=2LL;
     for(int i=0;i<n;i++){
          for(int j=i+1;j<n;j++){
               bool is=false;
               for(int k=0;k<n;k++){
                    if(dp[i][k]+dp[k][j]<dp[i][j]){cout<<-1;return 0;}
                    if(i!=k&&j!=k&&(dp[i][k]+dp[k][j]==dp[i][j])){
                         is=true;
                    }
               }
               if(is){
                    cost-=dp[i][j];
               }
          }
     }
     cout<<cost;
     



}
 
 
 
 

























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

// consider the complement of the original graph
// every connected components must be bipartites
// easy dp

const int MAXN = 710;
int N;
int M;
bool G[MAXN][MAXN];
vector<int> adj[MAXN];

int color[MAXN];

bool dp[2][MAXN];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for (int a = 1; a <= N; a++) {
		for (int b = a+1; b <= N; b++) {
			G[a][b] = true;
		}
	}
	for (int e = 0; e < M; e++) {
		int a, b; cin >> a >> b;
		if (a > b) swap(a, b);
		G[a][b] = false;
	}
	for (int a = 1; a <= N; a++) {
		for (int b = a+1; b <= N; b++) {
			if (G[a][b]) {
				adj[a].push_back(b);
				adj[b].push_back(a);
			}
		}
	}

	dp[0][0] = true;
	for (int st = 1; st <= N; st++) {
		if (color[st]) continue;
		int cnt[2] = {};
		{
			function<void(int, int)> dfs = [&](int cur, int curCol) -> void {
				assert(!color[cur]);
				color[cur] = curCol;
				cnt[curCol-1]++;
				for (int nxt : adj[cur]) {
					if (!color[nxt]) {
						dfs(nxt, 3-curCol);
					} else if (color[nxt] == curCol) {
						cout << -1 << '\n';
						exit(0);
					}
				}
			};
			dfs(st, 1);
		}
		{
			for (int i = 0; i <= N; i++) {
				dp[1][i] = false;
			}
			for (int i = 0; i <= N; i++) {
				if (dp[0][i]) {
					for (int j = 0; j < 2; j++) {
						dp[1][i + cnt[j]] = true;
					}
				}
			}
			for (int i = 0; i <= N; i++) {
				dp[0][i] = dp[1][i];
			}
		}
	}

	auto c2 = [&](int n) -> int {
		return n * (n-1) / 2;
	};
	int ans = N * N;
	for (int i = 0; i <= N; i++) {
		if (dp[0][i]) {
			ans = min(ans, c2(i) + c2(N-i));
		}
	}
	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 3584
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;

int main() {
int n;
cin>>n;
vector<ll> v;

rep(i,n){
    int a;cin>>a;
    v.push_back(a);
}

ll ansum=MOD;

for(int long long i=-100;i<=100;i++){
    ll sum=0;
    rep(j,n){
        ll u=abs(v[j]-i);
        sum+=u*u;
    }
    ansum=min(ansum,sum);
}
cout<<ansum<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int lld;
typedef pair<lld,lld> katana;

const lld mod = 1e9+7;
const lld INF = 1e9;
//const lld MAXN = 1e9;

int main()
{
    vector<katana> k;
    lld n,h;

    cin >> n >> h;

    for(int i = 0; i < n; i++)
    {
        lld a = 0,b = 0;
        cin >> a >> b;
        katana x;
        x.first = b, x.second = a;
        k.push_back(x);
    }

    lld max_a = 0;

    for(int i = 0; i < n; i++)
    {
        if (max_a < k[i].second)
        {
            max_a = k[i].second;
        }
    }

    sort(k.begin(),k.end());
    lld sol = 0;

    for(int i = n-1; i >= 0; i--)
    {
        if (max_a <= k[i].first)
        {
            sol++;
            h -= k[i].first;

            //cout << "h = " << h << endl;
            if (h <= 0)
            {
                break;
            }
        }
    }

    if (h > 0)
    {
        sol += ceil((double)h / max_a);
    }

    cout << sol << endl;


    return 0;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
#define ff        first
#define ss        second
#define ll        long long
#define int       long long
#define inf       ((ll)1e18)
#define mod       1000000007
#define double    long double
#define ull       unsigned long long
#define vi        vector<ll>
#define ppi       pair<int,int>
#define pii       pair<pair<int,int>,int>
#define pb        push_back
#define pi        2*acos(0.0)
#define rev       greater<int>()
#define pr(a,x,y) for(int i=x;i<y;i++){cout<<a[i]<<" ";}
#define ps(s)     for(auto i:s){cout<<i<<" ";}
#define sp(x,y)   fixed<<setprecision(y)<<x
#define w(x)      ll x; cin>>x; while(x--)
#define all(v)    v.begin(), v.end()
#define rall(v)   v.rbegin(), v.rend()
#define test      cout<<"This is test"<<endl;
#define str       string
#define endl      '\n'
#define e         cout<<'\n';
void kehsihba(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif*/
}
double get(pair<int,int>a,pair<int,int>b){
	int x=a.ff-b.ff;
	int y=a.ss-b.ss;
	x=x*x;y=y*y;
	return (double)sqrt(x+y);
}
void solve(){
	ll n;cin>>n;
	ll arr[n+1]={0};
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	ll a[n+1]={0};
	for(int i=1;i<=n;i++){
		a[arr[i]]=i;
	}
	pr(a,1,n+1);
}
int32_t main(){
	kehsihba();
	//init();
	ll t=1;
	//cin>>t;
	for(int k=1;k<=t;k++){
		//cout<<"Case "<<k<<": ";
		solve();
		//e;
	}
}

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

int main(){
  long long A,B,ans;
  char o;
  cin>>A>>o>>B;
  if(o=='+'){
    ans=A+B;
    cout<<ans<<endl;
  }
  else if(o=='-'){
    ans=A-B;
    cout<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 256
n,m = map(int,input().split())
info_list=[]
for i in range(m):
    info_list.append(list(map(int,input().split())))
p_list = list(map(int,input().split()))

count= 0

for i in range(2**n):
    swith = str(bin(i))[2:]
    swith_num = swith.zfill(n) 
    for j in info_list:
        flag = 0
        swith_sum = 0
        for k in j[1:]:
            swith_sum += int(swith_num[int(k)-1])
        if swith_sum%2 == p_list[info_list.index(j)]:
            pass
        else:
            flag = 1
            break
    if flag == 0:        
        count += 1

print(count)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                                     \
  ifstream in("atcoder-problems/agc015_a.txt"); \
  cin.rdbuf(in.rdbuf());
#else
#define INPUT_FILE
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
const int INF = 100100100;
const ll LINF = 1e18 + 100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  ll N, A, B;
  cin >> N >> A >> B;

  ll max = A + B * (N - 1);
  ll min = A * (N - 1) + B;

  ll ans = max - min + 1;
  cout << (ans > 0 ? ans : 0) << endl;
}

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

constexpr int inf = 2147483647;

int main() {
  int n, m, x;
  cin >> n >> m >> x;
  vector<int> c(n);
  vector<vector<int>> a(n, vector<int> (m));
  rep(i,n) {
    cin >> c[i];
    rep(j,m) cin >> a[i][j];
  }

  int res = inf;
  rep(bit,(1 << n)) {
    int cnt = 0;
    vector<int> understand(m, 0);
    rep(i,n) {
      if (bit & (1 << i)) {
        rep(j,m) understand[j] += a[i][j];
        cnt += c[i];
      }
    }
    bool flag = true;
    rep(i,m) if (understand[i] < x) flag = false;
    if (flag) res = min(res, cnt);
  }

  cout << (res == inf ? -1 : res) << endl;
  return 0;
}

Measured memory_bytes: 3648
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
//cout<<setprecision(20)
const llint mod=1000000007;
const llint big=1e18+10;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-9;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int LBI(vector<int>&ar,int in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
int UBI(vector<int>&ar,int in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	//弱い方から考える
	//2^n
	int n,m,i,j,k;cin>>n>>m;
	vector<int>toku(m);
	for(i=0;i<m;i++){cin>>toku[i];}
	SO(toku);REV(toku);
	static llint ki[1<<16]={0};
	static llint gu[1<<16]={0};
	static llint nki[1<<16];
	static llint ngu[1<<16];
	gu[0]=1;
	static llint kai[(1<<16)+1];kai[0]=1;
	for(i=1;i<=(1<<n);i++){kai[i]=(kai[i-1]*i)%mod;}
	static llint gya[(1<<16)+1];
	
	gya[(1<<n)]=1;llint bgen=kai[(1<<n)];
	
	for(int h=0;h<30;h++){
		if((mod-2)&(1<<h)){gya[1<<n]*=bgen;gya[1<<n]%=mod;}
		bgen*=bgen;bgen%=mod;
	}
	
	for(i=(1<<n);i>0;i--){gya[i-1]=(gya[i]*i)%mod;}
	//cerr<<"de"<<(gya[4]*kai[4])%mod<<endl;
	for(i=0;i<m;i++){
		for(j=0;j<(1<<n);j++){nki[j]=ki[j];ngu[j]=gu[j];}
		for(j=0;j<(1<<n);j++){
			//ここから遷移
			for(k=0;k<n;k++){
				if(j&(1<<k)){continue;}
				int mto=1+(1<<n)-toku[i]-j;//自分を含めた総人数
				if(mto-(1<<k)<0){continue;}
				llint ka=kai[mto-1]*gya[mto-(1<<k)];ka%=mod;
				ka*=(1<<k);ka%=mod;
				ngu[j+(1<<k)]+=ki[j]*ka;ngu[j+(1<<k)]%=mod;
				nki[j+(1<<k)]+=gu[j]*ka;nki[j+(1<<k)]%=mod;
			}
		}
		for(j=0;j<(1<<n);j++){ki[j]=nki[j];gu[j]=ngu[j];}
	}
	llint ans=0;
	for(j=0;j<(1<<n);j++){
		//cerr<<"ki["<<j<<"]="<<ki[j]<<endl;
		ans+=gu[j]*kai[(1<<n)-j-1];ans%=mod;
		ans-=ki[j]*kai[(1<<n)-j-1];ans%=mod;
	}
	ans+=mod;ans*=(1<<n);
	ans%=mod;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (V)) cout <<x <<" " <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


int N;
vector<ll> C, S, F;

void input() {
  cin >>N;
  C.assign(N-1, 0); S.assign(N-1, 0); F.assign(N-1, 0);
  rep(i, N-1) cin >>C[i] >>S[i] >>F[i];
}

int main() {
  input();
  for (int start=0; start<N; start++){
    ll res = 0;
    for (int i=start; i<N-1; i++){
      // 今は駅iにいます。次の駅i+1に進みたいです
      if (res <= S[i]){
        // 最初の列車がまだなら最初の列車に乗ります
        res = S[i] + C[i];
      }else{
        // 最初の列車が既に発射しているなら次のF[i]で割り切れる時間に列車に乗ります
        if (res % F[i] == 0) res = res + C[i];
        else res = ( (res / F[i]) + 1 ) * F[i] + C[i];
      }
    }
    cout <<res <<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) ((y)<0||(x)<0||(y)>=(h)||(x)>=(w))
#define dump(...)
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
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;}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct{template<class T> operator T(){T x;cin>>x;return x;}} IN;
struct before_main_function {
    before_main_function() {
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

bool solve() {
    int n;
    cin>>n;
    vector<int> a(n);
    cin>>a;
    set<int> s(ALL(a));
    if(SZ(s)>=3) return false;

    int X=*begin(s);
    if(SZ(s)==1 && (X==n-1 || X<=n/2)) {
        return true;
    } else if(*begin(s)+1==*rbegin(s)) {
        int cu=0,cuu=0;
        REP(i,n) {
            if(a[i]==X) cu++;
            else cuu++;
        }
        if(X+1-cu>0 && X+1-cu<=cuu/2) {
            return true;
        }
    }
    return false;
}
signed main() {
    cout<<(solve()?"Yes":"No")<<endl;
    return 0;
}



Measured memory_bytes: 5760
#!/usr/bin/env python3
import sys
from functools import reduce

def gcd(n, m):
    if n > m: # require n <= m
        n, m = m, n
    o = m % n
    if o == 0:
        return n
    else:
        m = n
        n = o
        return gcd(n, m)

def gcds(ns):
    return reduce(gcd, ns)

def solve(N: int, A: "List[int]"):
    print(gcds(A))
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 15880
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[] { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] { 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
	return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
	return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifdef EZZAT
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#else
#endif
}
const int N = 1e5 + 9, MOD = 1e9 + 7;
vector<int> adj[N];
ll mem[N][2];
void add(int &a, int b) {
	if ((a += b) >= MOD)
		a -= MOD;
}

//color = current color of node
ll solve(int node, int par, bool color) {
	ll &rt = mem[node][color];
	if (~rt)
		return rt;
	rt = 1;
	for (int ch : adj[node])
		if (ch != par)
			rt = (rt * (solve(ch, node, 0) + (color == 0) * solve(ch, node, 1)))
					% MOD;
	return rt;
}

int main() {
	run();
	memset(mem, -1, sizeof(mem));
	int n;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cout << (solve(1, -1, 0) + solve(1, -1, 1)) % MOD << endl;
}

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

int main(){
    int N,M;    cin>>N>>M;
    int result[M+1];
    
    for(int i=0;i<M+1;i++)    result[i]=0;
    
    for(int j=0;j<N;j++){
        int k;  cin>>k;
        for(int i=0;i<k;i++){
            int a;  cin>>a;
            result[a]++;
        }
    }
    int count=0;
    for(int i=0;i<M+1;i++){
        if(result[i]==N)    count++;
    }
    cout<<count<<endl;
        
}

Measured memory_bytes: 256
import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto n = readln.chomp.to!int;

  foreach (i; 1..n+1)
    if (i % 3 == 0 || include3(i))
      writef(" %d", i);
  writeln;
}

bool include3(int x)
{
  for (; x > 0; x /= 10)
    if (x % 10 == 3) return true;
  return false;
}

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

int main(){
    ll q, c, x, y;
    set<ll> s;
    cin >> q;
    for(ll i = 0; i < q; i++){
        cin >> c >> x;
        if (c == 0){
            s.insert(x);
            cout << s.size() << endl;
        }else if(c == 1){
            if (s.find(x) != s.end()){
                cout << "1" << endl;
            }else{
                cout << "0" << endl;
            }
        }else if(c == 2){
            auto j = s.find(x);
            if(j != s.end()){
                s.erase(j);
            }
        }else{
            cin >> y;
            auto b = s.lower_bound(x);
            auto e = s.upper_bound(y);
            if(b != e){
                for(auto j = b; j != e; j++){
                    cout << *j << endl;
                }
            }
        }
    }
    return 0;
}



Measured memory_bytes: 12428
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
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; }
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
// ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(void){
  int n; cin >> n;
  string s; cin >> s;
  FOR(i,0,1){
    FOR(j,0,1){
      int sw[n];
      sw[0] = i; sw[1] = j;
      FOR(k,1,n-2){
        int tf;
        if(s[k]=='o') tf = 0;
        else tf = 1;

        if(sw[k]==0){
          sw[k+1] = (sw[k-1] + 1 + tf) % 2;
        } else {
          sw[k+1] = (sw[k-1] + tf) % 2;
        }
      }
      bool flag = true;
      bool tf;
      if(s[n-1]=='o') tf = true;
      else tf = false;

      if((sw[n-2]==sw[0]) == tf && sw[n-1]==1){

      } else if((sw[n-2]==sw[0]) != tf && sw[n-1]==0){

      } else {
        flag = false;
      }

      if(s[0]=='o') tf = true;
      else tf = false;

      if((sw[n-1]==sw[1]) == tf && i==1){

      } else if((sw[n-1]==sw[1]) != tf && i==0){

      } else {
        flag = false;
      }
      if(flag){
        FOR(k,0,n-1){
          if(sw[k]==1) cout << "S";
          else cout << "W";
        }
        cout << endl;
        return 0;
      }
    }
  }
  cout << -1 << endl;

}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
const int N=5050;
int n,m;
int ans;
int main(){
	while(scanf("%d",&n)!=EOF){
		if(n<1200)
		    printf("ABC\n");
		else if(n<2800)
		    printf("ARC\n");
		else
		    printf("AGC\n");
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>

using namespace std;

void solve2() {
	int N;
	cin >> N;
	long long A[100009] = { 0 };
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	long long ans = 0;
	for (int i = 0; i < N; i++)
	{
		ans = ans + A[i] / 2;
		
		if (A[i] % 2 == 1 && A[i + 1] > 0) {
			A[i + 1]--;
			ans++;
		}
	}
	cout << ans << endl;
}

void solve1() {
	string s;
	cin >> s;
	map<char, int> p;
	bool flag = false;
	for (int i = 0; i < s.size(); i++)
	{
		p[s[i]]++;
	}
	
	if (((p['W'] != 0 && p['E'] != 0) || (p['W'] == 0 && p['E'] == 0))&&
		((p['N'] != 0 && p['S'] != 0) || (p['N'] == 0 && p['S'] == 0)))flag = true;
	if (flag) {
		cout << "Yes" << endl;
	}
	else
		cout << "No" << endl;
}

int main() {
	solve2();
	return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

const long long INF = 1e18;
//const ll mod = 1000000007;
ll N;
ll num[10010000];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for(ll i = 1; i <= N; i++) {
        for(ll j = i; j <= N; j += i) {
            num[j]++;
        }
    }
    ll ans = 0;
    for(ll i = 1; i <= N; i++) {
        ans += i * num[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 81748
A, B = map(int, input().split())

Bit = [0] * 40
ai, aj, bi, bj = A//2, A%2, B//2, B%2
one = (bi - ai) + bj
Bit[0] = one % 2

for i in range(1, 40):
    two = 2 ** i
    ai, aj = A // two, A % two
    bi, bj = B // two, B % two
    if ai == bi and ai % 2 == 1: Total = bj - aj + 1
    else:
        Total = 0
        if ai % 2 == 1:
            Total +=  two - aj
        if bi % 2 == 1:
            Total +=  bj + 1
    if Total % 2 == 1: Bit[i] = 1
Ans = 0
for i in range(40):
    if Bit[i] == 1: Ans += 2 ** i
print(Ans)


Measured memory_bytes: 3064
fn read1<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn main() {
    let s = read1::<String>().chars().collect::<Vec<char>>();
    let n = s.len();
    let m = n / 2;
    let l = s.iter().map(|&c| {
        if c == 'g' { 0 }
        else { 1 }
    }).sum::<usize>();
    println!("{}", m - l);
}

Measured memory_bytes: 4352
n = int(input())
l = [int(x) for x in input().split()]
s = [0, 0, 0]
count=0

l.sort()

for i in range(len(l)):
    for j in range(len(l)):
        for k in range(len(l)):
            if i == j or j == k or k==i:
                pass
            else:
                if l[i] >= l[j] or l[j] >= l[k] or l[k] <= l[i]:
                    pass
                else:
                    s[0] = l[i]
                    s[1] = l[j]
                    s[2] = l[k]
                  
                    if s[2] < s[1] + s[0]:
                        count += 1
                    else:
                        pass

print(count)

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

const int mod = 1e9+7;
long long h, w;
char grid[1010][1010];


long long mem[1010][1010] = {};

int main(){
    scanf(" %lld %lld ", &h, &w);
    mem[h - 1][w - 1] = 1;
    for(int i = 0 ; i < h ; ++i){ scanf("%s", grid + i); };

    for(int i = h-1 ; i >= 0 ; --i){
        for(int j = w-1 ; j >= 0 ; --j){
            if((i == h-1 && j == w-1) || grid[i][j] == '#')  continue;
            //long long bottom = mem[i+1][j];
            //long long right = mem[i][j+1];
            mem[i][j] = (mem[i+1][j]%mod + mem[i][j+1]%mod)%mod;
        }
    }
    cout << mem[0][0] << endl;
return 0;
}


Measured memory_bytes: 9216
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
    int n;
    cin>>n;
    vector<int>v(n,0);
    map<pair<int,int>,int>ans;
    vector<pair<int,int>>r(n-1);
    vector<vector<int>>g(n);
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        a--,b--;
        g[a].push_back(b);
        g[b].push_back(a);
        r[i]={a,b};
    }
    int ans1=-1;
    queue<pair<int,int>>q;
    q.push({0,0});
    while(!q.empty()){
        auto now=q.front();
        q.pop();
        v[now.first]=1;
        int c=1;
        for(auto x:g[now.first]){
            if(!v[x]){
                if(now.second==c)c++;
                q.push({x,c});
                ans[{now.first,x}]=c;
                ans[{x,now.first}]=c;
                v[x]=1;
                ans1=max(ans1,c);
                c++;
            }
        }
    }
    cout<<ans1<<endl;
    for(auto x:r){
        cout<<ans[{x.first,x.second}]<<endl;
    }
}

Measured memory_bytes: 19712
#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)
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");}

int main() {
    int n;
    cin >> n;
    int a[n+1];
    srep(i,1,n+1)cin >> a[i];
    
    int l = 1;
    int r = n+1;
    vp v;

    while(l<r){
        int ma = -1;
        int argma = l;
        srep(i,l,r){
            if(ma < abs(a[i])){
                ma = abs(a[i]);
                argma = i;
            }
        }
        if(ma==0){
            l = argma;
            r = argma;
            break;
        }
        if(0<a[argma]){
            r = argma;
        }else{
            
            l = argma + 1;
        }
    }

    srep(i,l,n){
        v.push_back(P(i,i+1));
        v.push_back(P(i,i+1));
    }

    for(int i=l-1;i>1;i--){
        v.push_back(P(i,i-1));
        v.push_back(P(i,i-1));
    }

    cout << v.size() << endl;
    rep(i,v.size()){
        cout << v[i].first << ' ' << v[i].second << endl;
    }

    return 0;
}
 
 


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <numeric>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define pb push_back
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};

int A, B, C, X, Y;
 
signed main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> A >> B >> C >> X >> Y;

  int ans = INF;
  for (int i=0; i<202020; i++) {
    if (i % 2 == 1) continue;
    int aa = max(0LL, X - i / 2);
    int bb = max(0LL, Y - i / 2);
    ans = min(ans, A * aa + B * bb + C * i);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
a=int(input())
b=list(map(int,input().split()))
c=[0]*a
"""
for i in range(a):
    c.append(b.index(i+1)+1) #おそらく計算量O(N^2)
"""
for i in range(a):
    c[b[i]-1]=i+1
result = ' '.join(map(str,c))
print(result)

Measured memory_bytes: 24324
import sys

def warshall(n, matrix):
  for i in xrange(n):
    matrix[i][i] = 0
  for i in xrange(n):
    for j in xrange(n):
      for k in xrange(n):
        matrix[j][k] = min(matrix[j][k], matrix[j][i]+matrix[i][k])
  return matrix

V,E = map(int, raw_input().split())
path = [[sys.maxint] * V for _ in xrange(V)]
for _ in xrange(E):
  s,t,d = map(int, raw_input().split())
  path[s][t] = d
cost = warshall(V, path)
isNegative = False
for i in xrange(V):
  if cost[i][i] < 0:
    isNegative = True
    break

if isNegative:
  print "NEGATIVE CYCLE"
else:
  for i in xrange(V):
    printlist = []
    for j in xrange(V):
      if cost[i][j] > 10 ** 12:
        printlist.append("INF")
      else:
        printlist.append(str(cost[i][j]))
    print " ".join(printlist)

Measured memory_bytes: 7048
/* -*- coding:utf-8 -*- */

#include <iostream>
#include <string>
using namespace std;

int main()
{
  string s;
  cin >> s;
  string::reverse_iterator it = s.rbegin();

  while(it != s.rend()) {
    cout << *it;
    it++;
  }
  cout << endl;

  return 0;
}

Measured memory_bytes: 1172
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(void){
	int N;
	string A, B, tmp;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> A;
		cin	>> B;
		if(A.size()>80 || B.size()>80){
			cout << "overflow" << endl;
			continue;
		}
		if(A.size() < B.size()) tmp = B, B = A, A = tmp;
		int dif = A.size() - B.size();
		int carry = 0;
		for(int i=A.size(); i>=0; i--){
			if(i-dif>=0) A[i] = A[i]+B[i-dif]-'0'+carry;
			else A[i] += carry;
			if(A[i] >= '0'+10) carry = 1, A[i] -= 10;
			else carry = 0;
		}
		if(carry==1){
			if(A.size()==80){
				cout << "overflow" << endl;
				continue;
			}else cout << '1';
		}
		for(int i=0; i<A.size(); i++) cout << A[i];
		cout << endl;
	}
}

Measured memory_bytes: 1204
#pragma GCC optimize("O3")
 #pragma GCC optimize("unroll-loops")
 #pragma GCC optimize("fast-math")
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define int long long
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

void accell() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
}
const int N = 2000;

signed main() {
    accell();
    int n;
    cin >> n;
    vector<int>p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        --p[i];
    }
    int cur = 1e9;
    int d = 1;
    vector<int>s(n);
    for (int i = 0; i < n; ++i) {
        s[p[i]] = cur;
        cur += d;
    }
    cur = 3e4;
    d = 3e4;
    vector<int>a(n), b(n);
    for (int i = 0; i < n; ++i) {
        a[i] = cur;
        b[i] = s[i] - cur;
        cur += d;
    }
    for (int i = 0; i < n; ++i) {
        cout << a[i] << ' ';
    }
    cout << '\n';
    for (int i = 0; i < n; ++i) {
        cout << b[i] << ' ';
    }
    return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
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;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s; cin >> s;
  ll cnt=0, tmp=0;
  for(auto c:s) {
    if(c == 'S') ++tmp;
    if(c == 'T' && tmp !=0) {
      --tmp;
      ++cnt;
    }
  }
  cout << s.size()-(cnt*2) << endl;
}

Measured memory_bytes: 720
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"---------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
						For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> vi;
typedef long double LD;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f|=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int N=200005;
int n;
int c0[N],c1[N];
LL ans=0;
int p[N];
int fa[N];
int getf(int x){
	return fa[x]==x?x:fa[x]=getf(fa[x]);
}
struct Node{
	int v;
	Node(){}
	Node(int _v){
		v=_v;
	}
	friend bool operator < (Node a,Node b){
		// c0[a]/c1[a] > c0[b]/c1[b]
		if ((LL)c0[a.v]*c1[b.v]!=(LL)c1[a.v]*c0[b.v])
			return (LL)c0[a.v]*c1[b.v]>(LL)c1[a.v]*c0[b.v];
		return a.v<b.v;
	}
};
set <Node> S;
int main(){
	n=read();
	fa[1]=1;
	For(i,2,n)
		p[i]=read(),fa[i]=i;
	For(i,1,n)
		if (read())
			c1[i]=1;
		else
			c0[i]=1;
	For(i,2,n)
		S.insert(Node(i));
	while (!S.empty()){
		int x=(*S.begin()).v,f=getf(p[x]);
		S.erase(Node(x));
		if (f>1)
			S.erase(Node(f));
		assert(fa[x]==x);
		ans+=(LL)c1[f]*c0[x];
		c0[f]+=c0[x];
		c1[f]+=c1[x];
		fa[x]=f;
		if (f>1)
			S.insert(Node(f));
	}
	cout<<ans<<endl;
	return 0;
}


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

const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
  bool operator==(const mint a) const { return x == a.x; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

int n;
mint a[222222];

int main() {
  while (cin >> n) {
    mint sum = 0, x = 0;
    for (int i = 0; i < n; ++i) {
      ll t;
      cin >> t;
      a[i] = t;
      sum += a[i];
    }
    for (int i = 0; i < n; ++i) {
      x += a[i] * (sum - a[i]);
    }
    cout << x / 2 << endl;
  }
}

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

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

typedef long long ll;
// ll mod_pow(ll x, ll n, ll mod){//x^n % mod
//     if (n == 0)
//         return 1;
//     ll res = mod_pow(x * x % mod, n / 2, mod);
//     if (n & 1)
//         res = res * x % mod;
//     return res;
// }
int main(int argc, char const *argv[])
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    string S; cin >> S;
    int c = 0;
    for (auto x: S) {
        if (x == 'o') c++;
    }
    if (c + (15 - S.size()) > 7) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

class comb{
public:
    ll mod;
    ll mx;
    vector<ll> F;
    vector<ll> FR;
    

    comb(ll mod=1000000007,ll mx=20000000):mod(mod),mx(mx),F(mx+1,1),FR(mx+1,1){
        mk_F();
    }
    
    ll mod_pow(ll a,ll x){
        a%=mod;
        ll ans=1;
        while(x>0){
            if(x&1){ans*=a; ans%=mod;}
            a*=a;
            a%=mod;
            x>>=1;
        }
        return ans;
    }
    
    pll Ex_gcd(ll a,ll b){
        if(b==0){return {1,0};}
        pll ret=Ex_gcd(b,a%b);
        ret.F-=a/b*ret.S;
        return {ret.S,ret.F};
    }
    
    ll prime_R(ll a){
        return mod_pow(a,mod-2);
    }
    
    ll R(ll a){
        ll ret=Ex_gcd(a,mod).F;
        ret%=mod;
        if(ret<0){ret+=mod;}
        return ret;
    }
    
    void mk_F(){
        for(ll i=1;i<=mx;i++){F[i]=F[i-1]*i%mod; /*FR[i]=R(F[i]);*/}
    }
    
    ll c(ll n,ll k){
        if(n<k){return 0;}
        if(n==k || k==0){return 1;}
        return F[n]*R(F[n-k])%mod*R(F[k])%mod;
    }
    
    //mod must be prime
    ll Lucas_C(ll n,ll m){
        ll ret=1;
        while(n>0 || m>0){
            ret*=c(n%mod,m%mod);
            ret%=mod;
            n/=mod; m/=mod;
        }
        return ret;
    }
    
    ll Stirling(ll n,ll k){
        ll ret=0;
        for(ll i=1;i<=k;i++){
            if((k-i)%2){ret-=c(k,i)*mod_pow(i,n)%mod;}
            else{ret+=c(k,i)*mod_pow(i,n)%mod;}
            ret%=mod;
        }
        ret*=R(F[k]);
        ret%=mod;
        if(ret<0){ret+=mod;}
        return ret;
    }
    
    ll Bell(ll n,ll k){
        ll ret=0;
        for(ll i=1;i<=k;i++){ret+=Stirling(n,i); ret%=mod;}
        return ret;
    }
};



int main(){
    comb C;
    ll h,w,k;
    cin>>h>>w>>k;
    ll ans=0;
    const ll T=C.F[h]*C.F[w]%MOD*C.R(C.F[h+w-k])%MOD;
    const ll HW=C.c(h+w,h)*T%MOD;
    const ll MI=C.c(h+w-2,h-1)*T%MOD;
    ans+=k*(k+3)/2%MOD*HW%MOD;
    for(int i=1;i<=k;i++){
        ans+=MI*i%MOD*(i-1)%MOD;
    }
    cout<<ans%MOD<<endl;
    
    
    return 0;
}


Measured memory_bytes: 312832
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vb=vector<bool>;
using vvb=vector<vb>;
using vc=vector<char>;
using vvc=vector<vc>;
using pii = pair<int,int>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define rep2(i, s, n) for(int i=(s);i<(int)n;i++)
int INF=1e9+7,MOD=998244353;

int main() {
  int N,K;
  cin >> N >> K;
  vi L(K),R(K);
  rep(i,K) cin >> L[i] >> R[i];
  vl dp(N+1),sum(N+1);
  dp[1]=1;
  sum[1]=1;
  
  rep2(i,2,N+1) {
    rep(j,K) (dp[i]+=sum[max(0,i-L[j])]-sum[max(0,i-R[j]-1)]+MOD)%=MOD;
    (sum[i]=sum[i-1]+dp[i])%=MOD;
  }
  cout << dp[N] << endl;
}

Measured memory_bytes: 6360
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(int i = a;i < n;i++)
#define LINF (ll)1e17
#define INF 1e9
#define MOD 1e9+7
#define sMOD 1e5
#define fs first
#define sc second


signed main(){
	
	ll n,sum = 0;
	cin >> n;
	
	ll a[n];
	
	rep(i,0,n){
		cin >> a[i];
		sum += a[i];
	}
	
	sort(a,a+n,greater<ll>());
	
	if(sum - a[0] > a[0]){
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	
	return 0;

}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// スペース区切りの整数の入力
       int kazu=sc.nextInt();
       String moji = sc.nextLine();
	   moji = sc.nextLine();
      if(moji.length()<=kazu){
        System.out.println(moji);
      }else{
        System.out.println(moji.substring(0,kazu)+"...");
      }
}
}


Measured memory_bytes: 38644
#include <bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
int n;
string s;
int main()
{
    cin>>n>>s;
    for(int i=0;i<min(n,(int)s.size());i++)
        cout<<s[i];
    if(n<s.size()) cout<<"...";
    return 0;
}


Measured memory_bytes: 3632
n = int(input())
g_list = {}
for _ in range(n):
    n1, num, *cl = map(int, input().split())
    g_list[n1] = cl


# 深さ優先探索: クラス使って書く？
class Graph():
    def __init__(self, g_list):
        self.time = 0
        self.nodes = {}
        self.d = {}
        self.f = {}
        self.g_list = g_list

    def dfs(self, node):
        self.time += 1
        self.d[node] = self.time
        for node_ in self.g_list[node]:
            if node_ not in self.d:
                self.dfs(node_)
        self.time += 1
        self.f[node] = self.time


g = Graph(g_list)
for i in range(1, n+1):
    if i not in g.d:
        g.dfs(i)

for g, f in zip(sorted(g.d.items()), sorted(g.f.items())):
    print(g[0], g[1], f[1])



Measured memory_bytes: 5740