akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<math.h>
#include<stdlib.h>
#include <iomanip>
using namespace std;
#define int long long
//#define double long double
typedef pair<int, int> pii;
typedef pair<pii, int> ppi;
typedef pair<int, pii > pip;
typedef pair<pii, pii > piipii;
typedef pair<double, double> pdd;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define all(vec) vec.begin(), vec.end()
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60)
#define mod 1000000007
#define se second
#define fi first

string N;
int K;
int dp[110][10][2];

int intpow(int a, int b){
    if(b == 0)return 1;
    if(b == 1)return a;
    if(b % 2 == 0){
        int tmp = intpow(a, b / 2);
        return tmp * tmp;
    }
    else {
        return a * intpow(a, b - 1);
    }
}

int digitN(int k){
    //return (N % intpow(10, k + 1)) / intpow(10, k);
    k = N.size() - k;
    return N.c_str()[k] - '0';
}

int dfs(int a, int b, bool isMax){
    if(~dp[a][b][isMax]){
        return dp[a][b][isMax];
    }
    if(b == K){
        return dp[a][b][isMax] = 1;
    }
    if(a == 1){
        return dp[a][b][isMax] = 0;
    }
    int res = 0;
    int dn = digitN(a - 1);
    if(isMax){
        for(int i = 0; i <= dn; i++){
            bool nextisMax = (i == dn);
            int nextb = b + (i != 0);
            res += dfs(a - 1, nextb, nextisMax);
        }
    }
    else{
        for(int i = 0; i <= 9; i++){
            int nextb = b + (i != 0);
            res += dfs(a - 1, nextb, isMax);
        }
    }
    return dp[a][b][isMax] = res;
}

signed main(){
    cin >> N >> K;
    memset(dp, -1, sizeof(dp));
    int ketaMax = N.size();
    int dn = digitN(ketaMax);
    int res = 0;
    //cout << dn << endl;
    for(int i = 0; i <= dn; i++){
        bool nextisMax = (i == dn);
        int nextb = (i != 0);
        res += dfs(ketaMax, nextb, nextisMax);
    }
    cout << res << endl;
}


/*
状態
今の桁数　先頭の数字の桁　先頭の数字　0以外の個数　
dp[i][j][k][l]
dp[0~100][0~100][0~9][0~3]

状態遷移　配るdp dp[a][b][c][d]から配る

次の桁の数字が0の時
dp[a + 1][b][c][d] += dp[a][b][c][d];

0以外のnの時
dp[a + 1][a + 1][n][d + 1] += dp[a][b][c][d];

for(int i = 0; i < Maxketa; i++){
    for(int j = 0; j < 9; j++){

    }
}

Nの境界判定は上からずっと一致しているかでできる
一致ならNより大きくなれないので遷移に制限がある
不一致なら自由

桁がNより大きくなることはないのでNと同じ桁から始める
i = 0->dN

再帰が楽

今の桁数　0以外の個数　ここまでNと全一致しているか

*/

Measured memory_bytes: 256
#
import sys
import math
import numpy as np
import itertools


# いくつか入力
n, m = (int(i) for i in input().split())  

# リストに入れる
a = [int(i) for i in input().split()] 

# n行複数列の数をリストに
bc = [[int(i) for i in input().split()] for i in range(m)] 

bc=sorted(bc, key=lambda x: -x[1])
a=sorted(a)
x = []

for i in range(m):
    for j in range(bc[i][0]):
        x.append(bc[i][1])
        if len(x)>=n:
            break
    if len(x)>=n:
        break
pmax = min(n,len(x))
z=0
y=0
# no replace
for i in range(n):
    y += a[i]
z=y
# replacing one by one
for i in range(pmax):
    y += x[i]
    y -= a[i]
    z=max(y,z)

print(z)


Measured memory_bytes: 39904
n, m = map(int, input().split())

if abs(n-m)>1:
    ans = 0
else:
    if m < n:
        n, m = m, n

    total_n = 1
    for i in range(1,n+1):
        total_n *= i
        if total_n >= 1000000007:
            total_n = total_n % 1000000007

    if n != m:
        ans = (total_n * total_n * m) % 1000000007
    else:
        ans = (total_n * total_n * 2) % 1000000007

print(int(ans))


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

#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, n, m) for(int (i) = (n); (i) < (m); ++(i))

constexpr int INF = 1e9;
//constexpr ll INF = 1LL<<61;
constexpr ll mod = 1e9+7;

struct UnionFind {
  vector<int> data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
  
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  bool same(int a, int b){
    return find(a) == find(b);
  }

  int size(int k) {
    return (-data[find(k)]);
  }
};

int main(){
  int N, M;
  cin >> N >> M;
  UnionFind uf(N);
  REP(i, M){
    int A, B;
    cin >> A >> B;
    A--, B--;
    uf.unite(A, B);
  }
  int ans = 0;
  REP(i, N){
    ans = max(ans, uf.size(i));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4052
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PSI pair<string,int>
#define PIII pair< int, pair<int,int> >
const int MXN = 1e6+5;
vector<int> p;
bool vis[MXN+5];
int L,R;

void sieve(){

    vis[0] = 1;
    vis[1] = 1;

    for(int i=4; i<MXN; i+=2)
        vis[i] = 1;

    for(int i=3; i*i<MXN; i+=2)
        if(!vis[i])
            for(int j=i*i; j<MXN; j+=2*i)
                vis[j]=1;

    p.push_back(2);
    for(int i=3; i<MXN; i+=2)
        if(!vis[i])
            p.push_back(i);
}

int divisor(int num){

    int res = 0;
    for(int i=0; (ll) p[i]*p[i]<=num && i<p.size() ; i++){
        while(num%p[i]==0){
            res++;
            num/=p[i];
        }
    }

    if(num!=1) res++;
    return vis[res]==0;
}

void solve(){

    cin>>L>>R;
    ll ans = 0;
    for(int i=L; i<=R; i++)
        ans+= divisor(i);

    cout<<ans<<"\n";
}

int main(){

    //freopen("input.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve();
    solve();
    return 0;
}



Measured memory_bytes: 4416
package main

import (
	"fmt"
)

func main() {
	var n, c int
	var bars []int

	fmt.Scan(&n)

	if n <= 2 {
		fmt.Print("0")
		return
	}

	for l := 0; l < n; l++ {
		var t int
		fmt.Scan(&t)
		bars = append(bars, t)
	}

	c = 0
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			for k := 0; k < n; k++ {
				if i >= j || j >= k || i >= k {
					continue
				}
				if bars[i] == bars[j] || bars[j] == bars[k] || bars[i] == bars[k] {
					continue
				}
				if bars[i]+bars[j] > bars[k] && bars[j]+bars[k] > bars[i] && bars[k]+bars[i] > bars[j] {
					c++
				}
			}
		}
	}

	fmt.Printf("%d", c)
}


Measured memory_bytes: 1856
import math
n = int(input())
ar = []

for i in range(n):
    x, y = map(int, input().split())
    ar.append([x, y])

sum_ = 0
for i in range(n):
    for j in range(n):
        sum_ += math.sqrt((ar[i][0] - ar[j][0]) ** 2 + (ar[i][1] - ar[j][1]) ** 2)

print(sum_ / n)



Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll a[100001];
ll b[100001];
const int MOD = 1e9 + 7;
ll fact[100001];

ll modpow(ll a, ll b)
{
	a %= MOD;
	ll r = 1;
	while(b)
	{
		if(b % 2)
		{
			r = (r*a)%MOD;
		}
		a = (a*a)%MOD;
		b /= 2;
	}
	if(r < 0) r += MOD;
	return r;
}


ll choose(ll n, ll r)
{
	if(r == 0)
	{
		return 1;
	}
	if(n == r)
	{
		return 1;
	}
	ll denom = 1;
	for (ll i = 2; i <= r; i++)
	{
		denom = (denom * i) % MOD;
	}
	ll res = 1;
	for (ll i = n; i > n - r; i--) 
	{
		res = (res * i) % MOD;
	}
	res = (res * modpow(denom, MOD - 2)) % MOD;
	if(res < 0) res += MOD;
	return res;
}


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	fact[0]=1;
	for(int i = 1; i <= n; i++)
	{
		fact[i]=(fact[i-1]*i)%MOD;
	}
	ll sum = 0;
	for(int i =0;i<n;i++) 
	{
		cin>>a[i];
		sum+=a[i];
	}
	for(int i=0;i<n;i++) 
	{
		cin>>b[i];
		sum-=b[i];
	}
	if(sum<0) swap(a,b);
	sort(a,a+n);
	sort(b,b+n);
	ll ans = 1;
	/*
	int ptr = 0;
	ll avi = 0;
	ll cnt = 0;
	for(int i = 0; i < n; i++)
	{
		while(ptr<n&&b[ptr]<a[i])
		{
			ptr++;
			avi++;
		}
		if(avi>0)
		{
			ans=(ans*fact[cnt])%MOD;
			avi-=cnt;
			cnt=0;
		}
		if(avi>0)
		{
			ans=(ans*avi)%MOD;
			avi--;
			cnt=0;
		}
		else
		{
			cnt++;
		}
	}
	ans=(ans*fact[cnt])%MOD;
	*/
	/*
	ll run = 1;
	for(int i = 1; i < n; i++)
	{
		if((a[i]>b[i])==(a[i-1]>b[i-1]))
		{
			run++;
		}
		else
		{
			ans=(ans*fact[run])%MOD;
			run = 1;
		}
	}
	*/
	vector<ii> vec2;
	for(int i = 0; i < n; i++) vec2.pb(mp(a[i],0));
	for(int i = 0; i < n; i++) vec2.pb(mp(b[i],1));
	sort(vec2.begin(),vec2.end());
	ll cur=0;
	for(int i = 0; i < 2*n; i++)
	{
		int curb = cur;
		if(vec2[i].se==1) cur++;
		else cur--;
		if(abs(cur)<abs(curb)) ans=(ans*abs(curb))%MOD;
	}
	cout<<ans<<'\n';
	return 0;

}


Measured memory_bytes: 6896
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 500050
const int mod=1e9+7;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,fac[N],inv[N],ans;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=1LL*fac[i-1]*i%mod;
	}
	inv[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i){
		inv[i]=1LL*inv[i+1]*(i+1)%mod;
	}
} 
inline int A(int n,int m){
	return 1LL*fac[n]*inv[n-m]%mod;
}
inline int C(int n,int m){
	return 1LL*fac[n]*inv[n-m]%mod*inv[m]%mod;
}
int main(){
	n=read(),m=read();
	init(m);
	for(int i=0;i<=n;++i){
		ans=(ans+(i&1?-1:1)*1LL*A(m,i)*A(m-i,n-i)%mod*A(m-i,n-i)%mod*C(n,i)%mod)%mod;
	}
	cout<<(ans%mod+mod)%mod<<endl;
	return 0;
}


Measured memory_bytes: 7472
A = [list(map(int,input().split())) for i in range(3)]
N = int(input())
bingo = [[False]*3 for _ in range(3)]
for _ in range(N):
    b = int(input())
    for i in range(3):
        for j in range(3):
            if b == A[i][j]:
                bingo[i][j] = True

ans = False
# for k in range(3):
#     print(bingo[k])
for i in range(3):
    if all(bingo[i]):
        print('Yes')
        exit()

for i in range(3):
    if all([bingo[0][i],bingo[1][i],bingo[2][i]]):
        print('Yes')
        exit()

if all([bingo[0][0],bingo[1][1],bingo[2][2]]):
    print('Yes')
    exit()

if all([bingo[0][2],bingo[1][1],bingo[2][0]]):
    print('Yes')
    exit()
print('No')

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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


def main():
    rr = []

    def f(s):
        g, y, m, d = s.split()
        y = int(y)
        m = int(m)
        d = int(d)
        if (y,m,d) >= (31, 5, 1):
            g = '?'
            y = y - 30
        return '{} {} {} {}'.format(g,y,m,d)

    while 1:
        s = S()
        if s == '#':
            break
        rr.append(f(s))

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


print(main())



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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef pair<int, int> pi;

const int maxn = 105;

int n, m;
int col[maxn][maxn], row[maxn][maxn];
int f[maxn][maxn][maxn][maxn];
string a[maxn];

void upd(int &a, int b){
    if(b > a)
        a = b;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int ex, ey;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        for(int j = 1;j <= m;j++){
            if(a[i][j - 1] == 'E'){
                ex = i, ey = j;
            }else if(a[i][j - 1] == 'o'){
                col[i][j]++;
                row[i][j]++;
            } 
            row[i][j] += row[i][j - 1];
        }
    }
    for(int j = 1;j <= m;j++){
        for(int i = 1;i <= n;i++){
            col[i][j] += col[i - 1][j];
        }
    }
    int ans = 0;
    for(int l = 0;ex - l >= 1;l++){
        for(int r = 0;ex + r <= n;r++){
            for(int u = 0;ey - u >= 1;u++){
                for(int d = 0;ey + d <= m;d++){
                    int del;
                    upd(ans, f[l][r][u][d]);
                    if(ex - l > 1 and ex - l - 1 > r){
                        int U = max(ey - u, d + 1);
                        int D = min(ey + d, m - u);
                        if(U <= D)
                            del = row[ex - l - 1][D] - row[ex - l - 1][U - 1];
                        else
                            del = 0;
                        upd(f[l + 1][r][u][d], f[l][r][u][d] + del);     
                    }
                    if(ex + r < n and ex + r < n - l){
                        int U = max(ey - u, d + 1);
                        int D = min(ey + d, m - u);
                        if(U <= D)
                            del = row[ex + r + 1][D] - row[ex + r + 1][U - 1];
                        else
                            del = 0;
                        upd(f[l][r + 1][u][d], f[l][r][u][d] + del);
                    } 
                    if(ey - u > 1 and ey - u - 1 > d){
                        int L = max(ex - l, r + 1);
                        int R = min(ex + r, n - l);
                        if(L <= R)
                            del = col[R][ey - u - 1] - col[L - 1][ey - u - 1];
                        else
                            del = 0;
                        upd(f[l][r][u + 1][d], f[l][r][u][d] + del);
                    }
                    if(ey + d < m and ey + d < m - u){
                        int L = max(ex - l, r + 1);
                        int R = min(ex + r, n - l);
                        if(L <= R)
                            del = col[R][ey + d + 1] - col[L - 1][ey + d + 1];
                        else
                            del = 0;
                        upd(f[l][r][u][d + 1], f[l][r][u][d] + del);
                    }
                }
            }
        } 
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 230144
#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long

int n;
double p[3001];
double dp[3001][3001];

int main(){
	IOS;
	memset(dp,0,sizeof(dp));
	cin >> n;
	for(int i=1;i<=n ; ++i){
		cin >> p[i];
	}
	dp[0][0] = 1;
	double ans = 0;

	for(int i=1;i<=n ; ++i){
		for(int j = 0 ; j <= i ; ++j){
			if(j==0){
				dp[i][j] = (1-p[i]) * dp[i-1][j];
				continue;
			}
			dp[i][j] = p[i]* dp[i-1][j-1] + (1-p[i]) * dp[i-1][j];
		}
	}

	for(int i= (n+1)/2 ; i<=n ; ++i){
		ans += dp[n][i];
	}


	cout << fixed << setprecision(10) <<  ans << endl;
}

Measured memory_bytes: 70656
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrep(i,a,b) for(int i=(int)(a);i>=(int)(b);--i)
#define fore(i,a) for(auto &i:a)
#define all(a) (a).begin(),(a).end()
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
using ll = long long; constexpr int inf = INT_MAX / 2; constexpr ll infl = 1LL << 60;
template<class T>void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T>void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T>void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T>void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
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 (b<a) { a = b; return 1; } return 0; }
template<class T>T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }}
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }

void _main() {
  int N;
  cin >> N;
  vector<int> H(N);
  rep(i, 0, N) cin >> H[i];

  int ans = 1;
  int max_h = H[0];
  rep(i, 1, N) {
    if (H[i] >= max_h) {
      ans++;
      max_h = H[i];
    }
  }

  cout << ans << endl;
}

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

int main(){
    int d, t, s;
    cin >> d >> t >> s;
    if(d <= t*s) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3628
#include <stdio.h>
#include <string.h>
int main(){
    char s[1001];
    scanf("%s",s);
    char t[1001];
    scanf("%s",t);
    
    int ans=0;
    for(int i=0;i<strlen(s)-strlen(t)+1;i++){
        int tmp = 0;
        for(int j = 0;j < strlen(t);j++){
            if(s[i+j] == t[j]){
                tmp++;
            }
        }
        if(ans<tmp)ans = tmp;
    }
    printf("%d",strlen(t)-ans);
}

Measured memory_bytes: 1704
#C-118
n = int(input())
a = [int(i) for i in input().split()]
min_HP = min(a) 
while True:
  for ni in range(n):
    if a[ni]%min_HP!=0:
      a[ni] = a[ni]%min_HP
  if min_HP > min(a):
    min_HP = min(a)
  else:
    break
print(min_HP)

Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[100005];
int main(){
    memset(dp, -1, sizeof(dp));
    int n, w, a, b;
    scanf("%d%d", &n, &w);
    dp[w] = 0;
    for(int i=1;i<=n;i++){
        scanf("%d%d", &a, &b);
        for(int j=0;j<=w;j++){
            if(dp[j] == -1) continue;
            if(j-a < 0) continue;
            dp[j-a] = max(dp[j-a], dp[j] + b);
        }
    }
    ll ans = 0;
    for(int i=0;i<=w;i++) ans = max(ans, dp[i]);
    printf("%lld\n", ans);
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
	double a, b, c, d, e, f;
	double x, y;
	
	while (scanf("%lf %lf %lf %lf %lf %lf", 
		&a, &b, &c, &d, &e, &f) != EOF){
		
		x = (c * e - b * f) / (a * e - b * d);
		y = (c * d - a * f) / (b * d - a * e);
		
		x += 0.0001;
		y += 0.0001;
		printf("%.3f %.3f\n", x, y);
	}
	
	return 0;
}

Measured memory_bytes: 656
//list index out of rangeエラー表示用
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep1(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

int main(){
  int n;
  cin >> n;
  cout << (1000-n%1000)%1000;
}



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

int n;

struct node
{
	int id, pid, k, d;
	int* cid;
	string type;
}N[100005];

void GetDepth(node& GN)
{
	GN.d = 0;
	node temp = GN;

	while (temp.pid != -1)
	{
		GN.d++;
		temp = N[temp.pid];
	}
}

void GetType(node& GN)
{
	if (GN.pid == -1)
		GN.type = "root";
	else if (GN.k == 0)
		GN.type = "leaf";
	else
		GN.type = "internal node";
}

void print()
{
	for (int i = 0; i < n; i++)
	{
		cout << "node " << N[i].id << ": " << "parent = " << N[i].pid << ", " << "depth = " << N[i].d << ", " << N[i].type << ", " << "[";

		if (N[i].k != 0)
		{
			for (int j = 0; j < N[i].k - 1; j++)
				cout << N[i].cid[j] << ", ";
			cout << N[i].cid[N[i].k - 1];
		}

		cout << "]" << endl;
	}	
}

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

	int place;
	cin >> n;
	
	for (int i = 0; i < n; i++)
		N[i].pid = -1;
	
	for (int i = 0; i < n; i++)
	{
		cin >> place;
		N[place].id = place;
		cin >> N[place].k;

		if (N[place].k > 0)
			N[place].cid = new int[N[place].k];

		for (int j = 0; j < N[place].k; j++)
		{
			cin >> N[place].cid[j];
			N[N[place].cid[j]].pid = N[place].id;
		}			
	}

	for (int i = 0; i < n; i++)
		GetDepth(N[i]);

	for (int i = 0; i < n; i++)
		GetType(N[i]);	

	print();

	return 0;
}



Measured memory_bytes: 11416
def main():
    N, W = (int(i) for i in input().split())
    WV = [[int(i) for i in input().split()] for j in range(N)]
    for i in range(1, N):
        WV[i][0] -= WV[0][0]
    w_base = WV[0][0]
    WV[0][0] = 0
    V = {i: [0] for i in range(4)}
    for w, v in WV:
        V[w].append(v)
    for i in range(4):
        V[i].sort(reverse=True)
    ans = 0
    from itertools import product
    for p in product(range(len(V[0])), range(len(V[1])),
                     range(len(V[2])), range(len(V[3]))):
        w_cur = w_base*p[0] + (w_base+1)*p[1] + \
            (w_base+2)*p[2] + (w_base+3)*p[3]
        if W < w_cur:
            continue
        ans = max(ans, sum(sum(V[i][:min(p[i], len(V[i]))]) for i in range(4)))
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 49884
#include <stdio.h>

int main(void){
  int a,b,c;
  scanf("%d %d %d",&a,&b,&c);
  if(a>b){
    int t = a;
    a=b;
    b=t;
  }
  if(b>c){
    int t = b;
    b=c;
    c=t;
  }
  if(a>b){
    int t = a;
    a=b;
    b=t;
  }

  printf("%d %d %d\n",a,b,c);
  return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
#define rep(shoki,i,n) for(int i=shoki; i<n; i++)
#define _GLIBCXX_DEBUG
using ll = long long;
using vi = vector<int>;
int main(){
    int n; cin>>n;
    int sum = 0;
    if(n%10 != 0){
        while(n>0){
            sum+=n%10;
            n/=10;
        }
    }else{
        sum = 10;
    }

    cout << sum << endl;
}

Measured memory_bytes: 256
import sys

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    N = NI()
    a = [LI() for _ in range(N)]
    dp = [[0] * (2**N) for _ in range(N)]

    q = [[] for _ in range(N)]
    b = 1
    for i in range(N):
        if a[0][i]:
            dp[0][b] = 1
            q[0].append(b)
        b <<= 1

    for i in range(1,N):
        for k in q[i-1]:
            v = dp[i-1][k]
            b = 1
            for l in a[i]:
                if l and k & b == 0:
                    m = k | b
                    if dp[i][m] == 0: q[i].append(m)
                    dp[i][m] = (dp[i][m] + v) % MOD
                b <<= 1

    print(dp[-1][2**N-1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 433272
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
typedef long long int ll;
int main(void){
	int n, t; cin >> n >> t;
	int x, y, result=1000;
	bool flag = false;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		if (y <= t && result>=x) {
			result = x;
			flag = true;
		}
	}
	if (flag)cout << result << endl;
	else cout << "TLE" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51},i,k;
    scanf("%d",&k);
    printf("%d\n",a[k-1]);
}


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

using namespace std;

int res;

int fastPower(int a,int b){
    if(b==0)return 1;
    res =  fastPower(a,b/2)%10;
    if(b%2==1)res = (res*a)%10;
    return res;

}



int main() {

    int h,w;
    cin>>h>>w;
    string s;
    while(h--){
        cin>>s;
        cout<<s<<endl<<s<<endl;
    }

    return 0;
}


Measured memory_bytes: 3612
#include <algorithm>
#include <array>
#include <climits> // INT_MAX, LONG_MAX, LLONG_MAX, UINT_MAX, ULONG_MAX, ULLONG_MAX
#include <cmath>
#include <cstdint>
#include <cstring> // memset
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define ALL(x) (x).begin(), (x).end()
#define INF 1e9
#define LOG(x) cout << #x << " = " << (x) << endl
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    string sn = to_string(n);

    int fx = 0;
    REP(i, sn.size()) {
        fx += sn[i] - '0';
    }

    cout << ((n % fx == 0) ? "Yes" : "No") << endl;
    
    return 0;
}


Measured memory_bytes: 256
import math as m

a,b,c=input().split()
a=int(a)
b=int(b)
c=int(c)
c=m.radians(c)
S=0.5*a*b*m.sin(c)
L=a+b+m.sqrt(a*a+b*b-2*a*b*m.cos(c))
H=b*m.sin(c)
print(S)
print(L)
print(H)


Measured memory_bytes: 5712
#include <bits/stdc++.h> 
#include <chrono>
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a)  (a).begin(),(a).end()
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))


int main(){
    LL N,K;
    cin>>N>>K;
    vector<LL>A(N);
    REP(i,N)cin>>A[i];
    REP(k,K){
        vector<LL>nextA(N+2,0);
        REP(a,N){
            nextA[max(0LL,a-A[a])]++;
            nextA[min(a+A[a],N)+1]--;
        }
        int now=0;
        bool flag=true;
        REP(a,N){
            now+=nextA[a];
            A[a]=now;
            if(now<N)flag=false;
        }
        if(flag)break;
    }
    REP(a,N){
        cout<<A[a]<<" ";
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 6376
// #include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <string>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <ctime>
#include <cassert>
#include <fstream>
#include<unordered_map>
#include <stack>
#include <random>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mapa make_pair
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
void vdeb(std::vector<T> &da) {
    for (int i = 0;i < da.size();i++) {
        if (i == da.size() - 1) std::cout << da[i];
        else std::cout << da[i] << ' ';
    }
    std::cout << std::endl;
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
    for (int i = 0;i < da.size();i++) vdeb(da[i]);
    std::cout << std::endl;
}

using namespace std;

int main(){
    int n,m; cin >> n>> m;
    vector<int> da(n);
    rip(i,n,0) cin >> da[i];
    vector<bool> ju(n);
    rip(i,m,0){
        int a,b; cin >> a >> b;
        --a;--b;
        if(da[a] == da[b])ju[a] = true, ju[b] = true;
        else if(da[a] < da[b]) ju[a] = true;
        else ju[b] = true;
    }
    int ans = 0;
    rip(i,n,0) if(!ju[i]) ans++;
    cout << ans << endl;
}

Measured memory_bytes: 3732
var lines = [];
var readline = require('readline');

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', function (x) {
    lines.push(x);
});

rl.on('close', function () {
    var MOD = Math.pow(10, 9) + 7;

    var N = lines[0];
    var S = lines[1].split("");

    var alphabet = {};

    var result = 1;

    // baa   = 2C1 * 3C1 - 1 =  5
    // baaa  = 2C1 * 4C1 - 1 = 7
    // bcaaa = 2C1 * 2C1 * 4C1 -1 = 15
    // aabbc = 3C1 * 3C1 * 2C1 -1 = 17


    for (var i = 0; i < N; i++) { alphabet[S[i]] === undefined ? alphabet[S[i]] = 1 : alphabet[S[i]]++ }
    Object.keys(alphabet).forEach(function (key) {
        result *= alphabet[key] + 1;
        result %= MOD;  
    });
    console.log(result - 1);

});

Measured memory_bytes: 8652
N = int(input())

S = []
for i in range(N):
    S.append(list(map(str,input().split())))

B = []
for i in range(N):
    B.append([int(S[i][1]),S[i][0],i+1])

C = sorted(B, key=lambda x:(x[1],-x[0]))

for c in C:
    print(c[2])

Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
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(){
    ll n,k;cin >> n >>k;
    vl a(n);rep(i,n){
        cin >> a[i];a[i]--;
    }
    vl seen(n,-1);
    seen[0]=0;
    ll p=0;
    ll dist=0;
    while(true){
        p=a[p];
        if(seen[p]!=-1)break;
        else {
            dist++;
            seen[p]=dist;
        }
    }
    //rep(i,n)cout << seen[i] <<endl;
    ll roop=0;
    ll start=p;
    while(true){
        p=a[p];
        roop++;
        if(p==start)break;
    }
    if(dist>=k){
        rep(i,n){
            if(seen[i]==k){
                cout << i+1 <<endl;
                return 0;
            }
        }
    }
    k-=dist+1;
    ll part=k%roop;
    //cout << part <<endl;
    rep(i,part){
        start=a[start];
    }
    cout << start+1 <<endl;
}

Measured memory_bytes: 6428
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
map<string, int> mp;
#define ll long long

int main() {
    int n;
    cin >> n;
    int ans=0;

    rep(i, n) {
        int a;
        cin >> a;
        if (a % 2 == 0)ans++;
    }
    cout << ans << endl;
    return 0;
}


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

namespace CSharp_AtCoder
{


    class Program
    {
        static int N;
        static int[] A;

        // nの約数をリストの形で返す
        static List<int> DivisorList(int n)
        {
            List<int> divisors = new List<int>();

            for(int i = 1; i <= Math.Sqrt(n); i++)
            {
                if (n % i != 0) continue;

                int quotient = n / i;
                divisors.Add(i);
                if (i != quotient) divisors.Add(quotient);
            }

            return divisors;
        }

        // Aの中でdivisorを約数とする値の個数
        static int ShareNum(int divisor)
        {
            int cnt = 0;

            for(int i = 0; i < N; i++)
            {
                if (A[i] % divisor == 0) cnt++;
            }

            return cnt;
        }

        static void Main(string[] args)
        {
            N = int.Parse(Console.ReadLine());
            A = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            // 最大約数の候補を求める
            HashSet<int> hs = new HashSet<int>();
            for(int i = 0; i < 2; i++)
            {
                foreach(var divisor in DivisorList(A[i]))
                {
                    hs.Add(divisor);
                }
            }

            // N or N - 1 回共通する約数候補の値のうち最大のものを求める
            int max_divisor = -1;
            foreach(int divisor in hs)
            {
                if(ShareNum(divisor) >= N - 1)
                {
                    max_divisor = Math.Max(max_divisor, divisor);
                }
            }

            Console.WriteLine(max_divisor);
        }
    }
}


Measured memory_bytes: 26588
import java.awt.*;
import java.awt.geom.*;
import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int c = sc.nextInt();
			int n = sc.nextInt();
			int m = sc.nextInt();
			int s = sc.nextInt();
			int d = sc.nextInt();
			if(c == 0 && n == 0 && m == 0 && s == 0 && d == 0) break;
			
			int[][][] map = new int[n][n][c+2];
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					Arrays.fill(map[i][j],2 << 28);
				}
			}
			
			for(int i = 0; i < m; i++) {
				int a = sc.nextInt()-1;
				int b = sc.nextInt()-1;
				int f = sc.nextInt();
				map[a][b][c+1] = f;
				map[b][a][c+1] = f;
			}

			PriorityQueue<Data> queue = new PriorityQueue<Data>();
			queue.add(new Data(s-1,c,0));
			int ans = 0;
			
			while(!queue.isEmpty()) {
				Data data = queue.poll();
				if(data.place == d-1) {
					ans = data.money;
					queue.clear();
					break;
				}
				for(int i = 0; i < n; i++) {
					if(map[data.place][i][c+1] == 2<<28) continue;
					if(map[data.place][i][data.ticket] <= data.money + map[data.place][i][c+1]) continue;
					
					map[data.place][i][data.ticket] = data.money + map[data.place][i][c+1];
					queue.add(new Data(i,data.ticket,data.money + map[data.place][i][c+1]));
					if(data.ticket != 0) {
						map[data.place][i][data.ticket-1] = data.money + map[data.place][i][c+1];
						queue.add(new Data(i,data.ticket-1,data.money + map[data.place][i][c+1]/2));
					}
				}
			}
			
			System.out.println(ans);
			
		}
	} 	
	
	static class Data implements Comparable<Data>{
		int place;
		int ticket;
		int money;
		Data(int a, int b, int c) {
			place = a;
			ticket = b;
			money = c;
		}
		@Override
		public int compareTo(Data o) {
			return this.money - o.money;
		}
	}
	
}

Measured memory_bytes: 61400
#include <iostream>
#include <string>
#include <stack>
#include <exception>

using namespace std;

int main(){
    string S; cin >> S;
    stack<char> ST;

    for (int i = 0; i < S.size(); i++){
        try {
            if (ST.empty()) throw "empty stack!";
            if (ST.top() != S[i]) ST.pop();
            else                  ST.push(S[i]);
        } catch (const char *error) {
            ST.push(S[i]);
        }
    }

    cout << S.size()-ST.size() << endl;
    return 0;
}


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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

ll attacks(ll H)
{
    if (H == 1)
        return 1;

    return 1 + 2*attacks(H/2);
}

ll solve(ll H)
{
    return attacks(H);
}

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

    ll H;
    cin >> H;

    auto ans = solve(H);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;

int main(int argc, const char *argv[])
{
  // 赤，緑，無色のリンゴ
  int x, y, a, b, c;
  cin >> x >> y >> a >> b >> c;
  vector<ll> p(a);
  vector<ll> q(b);
  vector<ll> r(c);
  for (int i = 0; i < a; i++) cin >> p[i];
  for (int i = 0; i < b; i++) cin >> q[i];
  for (int i = 0; i < c; i++) cin >> r[i];

  sort(p.begin(), p.end(), greater<ll>());
  sort(q.begin(), q.end(), greater<ll>());
  sort(r.begin(), r.end(), greater<ll>());

  vector<ll> apples;
  for (int i = 0; i < x; i++) apples.push_back(p[i]);
  for (int i = 0; i < y; i++) apples.push_back(q[i]);

  // 小さい順に並んでる
  sort(apples.begin(), apples.end());

  for (int i = 0, j = 0; i < r.size() && j < apples.size();) {
    if (apples[j] < r[i]) {
      apples[j] = r[i];
      i++;
      j++;
    } else {
      break;
    }
  }

  cout << accumulate(apples.begin(), apples.end(), 0ll) << "\n";
  return 0;
}

Measured memory_bytes: 4724
#include <iostream>
//#include <set>
#include <map>
//#include <iomanip>
//#include <algorithm>
//#include <numeric>
//#include <queue>
//#include <stack>
//#include <math.h>
//#include <vector>
//#include <unordered_map>
#include <string>
//typedef long long LL;
//typedef long double LD;
using namespace std;

//#define MOD 1000000007

int main() {
    int n;
    map<string, int> s;
    int num_max=0;
    string tmp_s;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> tmp_s;
        s[tmp_s]++;
        num_max = max(num_max, s[tmp_s]);
    }

    for(auto i : s){
        if(num_max == i.second){
            cout << i.first << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 27264
// "include" {{{
#include <deque>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <utility>
// }}}
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long 
#define pii pair<int,int> 
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

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

vector<int> t;
vector<int> a;

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b;
	cin >> a >> b;
	cout << (a-1) * (b-1) << '\n';
	return 0;
}


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

int main() {
  int N, sum=0;
  cin >> N;
  int  d[N];
  for(int i=0; i<N; i++) {
    cin >> d[i];
  }
  for(int i=0; i<N-1; i++) {
    for(int j=i+1; j<N; j++) {
       sum += d[i]*d[j];
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a+b == c+d){
        cout << "Balanced" << endl;
    }else if(a+b > c+d){
        cout << "Left" << endl;
    }else{
        cout << "Right " << endl;
    }
    return 0;
}

Measured memory_bytes: 256
from itertools import combinations_with_replacement


def main():
    N, M, Q = map(int, input().split())
    Qs = [list(map(int, input().split())) for _ in range(Q)]
    seq = [i for i in range(1, M+1)]
    As = combinations_with_replacement(seq, N)
    max_score = 0
    for A in As:
        A = sorted(A)
        score = 0
        for q in Qs:
            if A[q[1]-1] - A[q[0]-1] == q[2]:
                score += q[3]
        max_score = max(score, max_score)

    print(max_score)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9232
n,k = map(int, input().split())
R,S,P = map(int, input().split())
t = input()

r_flg, s_flg, p_flg = [0]*k,[0]*k,[0]*k

r_cnt,s_cnt,p_cnt = 0,0,0

for i in range(n):
	if t[i] == "r":
		if r_flg[i%k] == 0:
			r_cnt += 1
			r_flg[i%k] = 1
			s_flg[i%k] = 0
			p_flg[i%k] = 0
		else:
			r_flg[i%k] = 0
			s_flg[i%k] = 0
			p_flg[i%k] = 0
	if t[i] == "s":
		if s_flg[i%k] == 0:
			s_cnt += 1
			r_flg[i%k] = 0
			s_flg[i%k] = 1
			p_flg[i%k] = 0
		else:
			r_flg[i%k] = 0
			s_flg[i%k] = 0
			p_flg[i%k] = 0
	if t[i] == "p":
		if p_flg[i%k] == 0:
			p_cnt += 1
			r_flg[i%k] = 0
			s_flg[i%k] = 0
			p_flg[i%k] = 1
		else:
			r_flg[i%k] = 0
			s_flg[i%k] = 0
			p_flg[i%k] = 0

ans = r_cnt*P + s_cnt*R + p_cnt*S
print(ans)

Measured memory_bytes: 5364
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int X[1001], B[1001], W[1001];
vi G[1001];

bool solve(int u) {
	vector<int> dp[2][5005];
	int n = G[u].size();
	for (int i = 0; i <= n; ++i) {
		dp[0][i].resize(X[u] + 1, 1e9);
		dp[1][i].resize(X[u] + 1, 1e9);
	}
	dp[0][0][0] = dp[1][0][0] = 0;
	for (int i = 0; i < n; ++i) {
		int v = G[u][i];
		if (!solve(v)) return false;
		if (B[v] < 1e9) {
			for (int j = 0; j <= X[u] - X[v]; ++j) {
				if (dp[0][i][j] < 1e9) dp[0][i + 1][j + X[v]] = min(B[v] + dp[0][i][j], dp[0][i + 1][j + X[v]]);
			}
			for (int j = 0; j <= X[u] - B[v]; ++j) {
				if (dp[1][i][j] < 1e9) dp[1][i + 1][j + B[v]] = min(X[v] + dp[1][i][j], dp[1][i + 1][j + B[v]]);
			}
		}
		if (W[v] < 1e9) {
			for (int j = 0; j <= X[u] - X[v]; ++j) {
				if (dp[1][i][j] < 1e9) dp[1][i + 1][j + X[v]] = min(W[v] + dp[1][i][j], dp[1][i + 1][j + X[v]]);
			}
			for (int j = 0; j <= X[u] - W[v]; ++j) {
				if (dp[0][i][j] < 1e9) dp[0][i + 1][j + W[v]] = min(X[v] + dp[0][i][j], dp[0][i + 1][j + W[v]]);
			}
		}
	}
	B[u] = *min_element(dp[0][n].begin(), dp[0][n].end());
	W[u] = *min_element(dp[1][n].begin(), dp[1][n].end());
	return B[u] < 1e9 || W[u] < 1e9;
}

int main() {
	int N;
	cin >> N;
	for (int i = 1; i < N; ++i) {
		int p;
		cin >> p;
		G[p].push_back(i + 1);
	}
	for (int i = 1; i <= N; ++i) cin >> X[i];
	cout << (solve(1) ? "POSSIBLE\n" : "IMPOSSIBLE\n");
}

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

int main(){
	int b, f, r, v, a[4][3][10] = {}, i, j, k, n;

	cin>>n;

	for(i = 0; i < n; i++){
		cin>>b>>f>>r>>v;
		a[b-1][f-1][r-1] += v;
	}

	for(i = 0; i < 4; i++){
		for(j = 0; j < 3; j++){
			for(k = 0; k < 10; k++) {
				cout<<" ";
				cout<<a[i][j][k];
			}
			cout<<endl;
		}
		if(i < 3) cout<<"####################"<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define ll long long int
#define pf push_front
#define mod  1000000007
#define inf  1000000000000000000
#define pi  acos(-1.0)
#define maxn  1000009
#define sorted(s)  sort(s.begin(),s.end())
#define sortarr(a) sort(a,a+n)
#define slc(n) scanf("%I64d", &n)
#define sl(n)  scanf("%lld", &n)
#define sf(n)  scanf("%lf", &n)
#define si(n)  scanf("%d", &n)
#define sch(n)  scanf(" %c", &n)
#define ss(n)  scanf("%s", n)
#define prf printf
#define pb  push_back
#define fr first
#define sc second
#define all(a)  a.begin(),a.end()
#define forl(n) for(i=0;i<n;i++)


using namespace std;

int main()
{

 ll n,m;
 cin>>n>>m;
 if(n==m)
    cout<<"Yes"<<endl;
 else
    cout<<"No"<<endl;

    return 0;
}






Measured memory_bytes: 256
N=int(input())

D={}

for i in range(N):
    s=input()
    s="".join(sorted(s))
    if s not in D:
        D[s]=1
    else:
        D[s]+=1
ans=0
for v in D.values():
    ans+=v*(v-1)//2

print(ans)

Measured memory_bytes: 17808
#include <iostream>
#include <cstdio>
typedef long long ll;
using namespace std;
#define what(x) cerr<<(#x)<<" is "<<x<<endl
int main()
{
  ll w,h,x,y;
  cin>>w>>h>>x>>y;
  double area=(w*h)/2.0;
  printf("%0.6lf %d\n",area, x+x==w&&y+y==h);

  return 0;
}

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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;

int main() {
    string s; cin >> s;
    map<char, int> m;
    for(int i = 0; i < s.size(); i++){
        m[s[i]]++;
    }

    for(auto p : m){
        if(p.second > 1){
            cout << "no" << endl;
            return 0;
        }
    }
    cout << "yes" << endl;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
Asum = [0]
for i in range(N):
  Asum.append(Asum[i] + A[i])
Diff = Asum[N]
m = 0; n = 2
for i in range(N-3):
  flag = True
  P = Asum[m]; Q = Asum[i+2] - Asum[m]
  while flag:
    m += 1
    if abs(Asum[i+2]-Asum[m]*2) < abs(P-Q):
      P = Asum[m]; Q = Asum[i+2] - Asum[m]
    else:
      flag = False
      m -= 1
  flag = True
  R = Asum[n] - Asum[i+2]; S = Asum[N] - Asum[n]
  while flag:
    n += 1
    if abs(Asum[N]-Asum[n]*2+Asum[i+2]) < abs(R-S):
      R = Asum[n] - Asum[i+2]; S = Asum[N] - Asum[n]
    else:
      flag = False
      n -= 1
  if max(P,Q,R,S)-min(P,Q,R,S) < Diff:
    Diff = max(P,Q,R,S)-min(P,Q,R,S)
print(Diff)

Measured memory_bytes: 25672
#include <iostream>
#define ll long long
using namespace std;

ll wt[101], vl[101], dp[101][100001];

int main() {
    int n, w; cin >> n >> w;
    for(int i=0; i<n; ++i) cin >> wt[i] >> vl[i];

    for(int i=0; i<101; ++i) dp[i][0] = 0;
    for(int i=0; i<100001; ++i) dp[0][i] = 0;

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= w; ++j) {
            if(j - wt[i-1] < 0) dp[i][j] = dp[i-1][j];
            else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + vl[i-1]);
            }
        }
    }

    cout << dp[n][w];
    
    return 0;
}

Measured memory_bytes: 79104
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        for (int i = 1; (str = br.readLine()) != null; i++) {
            if (str.equals("0")) break;
            System.out.println("Case " + i + ": " + str);
    }
  }
}

Measured memory_bytes: 26136
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// container util
#define all(x) (x).begin(), (x).end()

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                         \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
       << " " << __FILE__ << endl;

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
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;
}
//

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

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

  vector<int> ans(N + 1, 0);
  rep(i, M) {
    int l, r;
    cin >> l >> r;
    ans[l]++;
    ans[r + 1]--;
  }
  rep(i, N + 1) { ans[i + 1] += ans[i]; }

  int res = 0;
  FOR(i, 1, N + 1) {
    if (ans[i] == M) res++;
  }

  cout << res << endl;

  return 0;
}

Measured memory_bytes: 640
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, ans[int(1e4 + 5)];

int main(){
  for (int i = 1; i <= 100; i++){
    for (int j = 1; j <= 100; j++){
      for (int k = 1; k <= 100; k++){
        int sum = i*i+i*j+i*k+j*j+j*k+k*k;
        if (sum > 10000) break;
        ans[sum]++;
      }
    }
  }

  int N; cin >> N;
  for (int i = 1; i <= N; i++) cout << ans[i] << endl;

  return 0;
}


Measured memory_bytes: 3580