akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define INF ((1LL<<62)-(1LL<<31))
#define min(p,q)((p)<(q)?(p):(q))

//辺の情報を個別に持つタイプ
typedef struct edge{ll s,g,c;}E;
typedef struct graph{
	int vcnt,ecnt;
	E  e[200010];//適宜変える(ecnt)
	int inv[200010];//逆辺のindex(ecnt)
	int id[100010];//適宜変える(vcnt)
}G;

int esort(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).s<(*q).s)return -1;
	if((*p).s>(*q).s)return  1;
	if((*p).g<(*q).g)return -1;
	return 1;
}
int csort(const void*a,const void*b){
	ll p=(*(E*)a).c,q=(*(E*)b).c;
	return p<q?-1:p>q?1:0;
}

G g;
void readgraph(){
	//適宜変える
	ll n,m;
	scanf("%lld%lld",&n,&m);
	rep(i,0,m){
		ll x,y,c;
		scanf("%lld%lld%lld",&x,&y,&c);
		g.e[2*i].s=x;
		g.e[2*i].g=y;
		g.e[2*i].c=c;
		g.e[2*i+1].s=y;
		g.e[2*i+1].g=x;
		g.e[2*i+1].c=0;
	}
	g.vcnt=n;
	g.ecnt=2*m;
	qsort(g.e,g.ecnt,sizeof(E),esort);
//	qsort(g.e,g.ecnt,sizeof(E),csort);

	int p=0;
	rep(i,0,g.vcnt){
		while(p<g.ecnt&&g.e[p].s<i)p++;
		g.id[i]=p;
	}
	g.id[g.vcnt]=g.ecnt;//番兵

	//逆辺のidx
	rep(i,0,g.ecnt){
		int l=0,r=g.ecnt;
		while(r-l>1){
			int m=(l+r)/2;
			if(g.e[m].s<g.e[i].g||(g.e[m].s==g.e[i].g&&g.e[m].g<=g.e[i].s))l=m;
			else r=m;
		}
		g.inv[i]=l;
	}
}




//dinic ただしO(VVE)ではなくO(V^4)
//有向グラフの隣接行列capaと、ソースs,シンクtを引いてsからtへの最大流を返す
//*
int dist[1010];//ソースからの距離
int checked[1010];//dfsの行き止まりフラグ
void dinicbfs(int s){
	rep(i,0,g.vcnt)dist[i]=-1;
	dist[s]=0;
	//まだ流せる辺だけを使ってbfs
	int que[1010],qcnt=0;
	que[qcnt++]=s;
	rep(q,0,qcnt){
		int v=que[q];
		rep(i,g.id[v],g.id[v+1])if(g.e[i].c>0&&dist[g.e[i].g]==-1){
			dist[g.e[i].g]=dist[v]+1;
			que[qcnt++]=g.e[i].g;
		}
	}
}
ll dinicdfs(int a,int t,ll m){
	//aはm受け取ってる(⇔aから最大m流せる)
	//いくら流せるかを返す
	if(a==t)return m;
	if(checked[a])return 0;
	ll ans=0;
	checked[a]=1;
	rep(i,g.id[a],g.id[a+1])if(g.e[i].c>0&&dist[g.e[i].g]>dist[a]){
		int b=g.e[i].g;
		ll addedflow=dinicdfs(b,t,min(m,g.e[i].c));
		if(addedflow){
			g.e[i].c-=addedflow;
			g.e[g.inv[i]].c+=addedflow;
			checked[a]=0;
			ans+=addedflow;
			m-=addedflow;
			if(m<=0)break;
		}
	}
	return ans;
}
//ソース,シンク
ll dinic(int s,int t){
	ll ans=0;
	int flag=1;
	while(flag){
		flag=0;//更新フラグ
		dinicbfs(s);
		while(!checked[s]){
			ll addedflow=dinicdfs(s,t,INF);
			ans+=addedflow;
			if(addedflow)flag=1;
		}
		rep(i,0,g.vcnt)checked[i]=0;
	}
	return ans;
}
//*/

int main(){
	readgraph();
	printf("%lld\n",dinic(0,g.vcnt-1));
}


Measured memory_bytes: 2148
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define ll long long
int main() {

	long double n, k;
	cin >> n >> k;
	long double p = 0.0;
	for (int i = 1; i <= n; i++) {
		int a = i;
		long double pi = 1.0 / (long double) n;
		while (a < k) {
			pi *= 0.5;
			a *= 2;
		}
		p += pi;
	}
	cout << fixed << setprecision(9) << p << endl;
}


Measured memory_bytes: 3780
#include<bits/stdc++.h>
#include<algorithm>
#include<string>

using namespace std;


/*
    FILE *f=fopen("data.txt","w");
    fprintf(f,);
    fclose(f);
*/

#define FASTER ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pi acos(-1.0)
#define scan(a) scanf("%d",&a)
#define scanll(a) scanf("%lld",&a)
#define print(a) printf("%d\n",a)
#define printll(a) printf("%lld\n",a)
#define stll(a) stoll(a,nullptr,10)
#define PII pair<ll,ll>
#define mp(a,b) make_pair(a,b)
#define EL printf("\n")
#define ff first
#define ss second

typedef long long ll;
typedef unsigned long long ull;

vector<ll>ar;
int main()
{
    ll n,ans=0,tmp;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>tmp;
        ar.push_back(tmp);
    }

    sort(ar.begin(),ar.end());

    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            ll mx=lower_bound(ar.begin(),ar.end(),ar[i]+ar[j])-ar.begin();
            for(int k=j+1;k<mx;k++)
            {
                if(ar[i]+ar[j]>ar[k] && ar[j]+ar[k]>ar[i] && ar[k]+ar[i]>ar[j])
                    ans++;
            }
        }
    }
    cout<<ans<<endl;
}






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

typedef unsigned long long int ull;
typedef long double ldb;
typedef long long int ll;

#define MOD1        1000000007
#define MOD2        998244353
#define PI          3.1415926535897932384626433832795
#define FILL(a, value) memset(a, value, sizeof(a))
#define BOOST       ios_base::sync_with_stdio(false); cin.tie(NULL)
#define what_is(x)  cerr << #x << " is " << x << endl;
#define ASSERT(left,operator,right) { if(!((left) operator (right))){ std::cerr << "ASSERT FAILED: " << #left << #operator << #right << " @ " << __FILE__ << " (" << __LINE__ << "). " << #left << "=" << (left) << "; " << #right << "=" << (right) << std::endl; } }

#define rep01(k,n)      for (ll i=k; i<n; i++)
#define rep02(k,n)      for (ll j=k; j<n; j++)
#define rep03(k,n)      for (ll k=k; k<n; k++)
#define rep11(k,n)      for (ll i=k; i<=n; i++)
#define rep12(k,n)      for (ll j=k; j<=n; j++)
#define rep13(k,n)      for (ll k=k; k<=n; k++)
#define repIT(c,it)     for(typeof(c.begin()) it = c.begin(); it != c.end(); ++it)
#define all(c)      c.begin(), c.end()

using namespace std;

const double pi = acos(-1.0);
const double epsilon = 1e-9;        // Add epsilon when casting double to int to avoid rounding pitfall issues, eg, 0.94*8178 in int
const int maxn = 1e6+10;


void solve()
{
    ll n;
    cin >> n;
    
    ll ans = floor((n+1)/1.08);

    if((int)(ans*1.08) == n)
        cout << ans;
    else
        cout << ":(";

}

int main()
{
    int t = 1;
    //cin >> t;
    while(t--)
        solve();

    cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
    return 0;
}

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

using namespace std;

long long counter(long long n, long long x){
  if(n==-1)return 0;
  else return n/x+1;
}


int main(){
  long long a, b, x, ans;
  cin >> a >> b >> x;
  ans = counter(b, x) - counter(a-1, x);

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include<math.h>
int main(void){
	int n,i,j,sosu=0,not_sosu=0;
	int N[10000];
	
	//最初の行読み込み
	scanf("%d",&n);
	
	//続くn個の読み込み
	for(i=1; i<=n; i++){
		scanf("%d",&N[i]);
	}
	//素数判定
	
	for(i=1; i<=n; i++){
		for(j=2; j<=(int)(sqrt(N[i])); j++){
			not_sosu = 0;
			if(N[i]%j==0){	
				not_sosu=1;
				break;
			}
		}
		if(not_sosu==0)	sosu++;
	}
		//printf("%d番目の%dは%d\n",i,N[i],not_sosu);
		
	printf("%d\n", sosu);
	return 0;

}


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

using namespace std;

#define ll long long

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int x,n;
    cin>>x>>n;
    set<int> st;
    int y;
    for(int i = 0;i<n;i++){
        cin>>y;
        st.insert(y);
    }
    if(n == 0){
        cout<<x;
        return 0;
    }
    int ans = 10000;
    int idx = -1;
    for(int i = -101;i<=101;i++){
        if(st.find(i) == st.end()){
            int d = abs(x-i);
            if(d < ans){
                ans = d;
                idx = i;
            }else if(d == ans){
                idx = min(i,idx);
            }
        }
    }
    cout<<idx;
    return 0;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int type[maxn],dis[maxn];
int find(int a)
{
	if(type[a]==a) return a;
	else 
	{
		int pre=type[a];
		type[a]=find(type[a]);
		dis[a]+=dis[pre];
		return type[a];
	}
}
void fl()
{
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
int main()
{
//	  fl();
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		type[i]=i;
	bool check=true;
	for(int i=1;i<=m;i++)
	{
		int l,r,d;
		cin>>l>>r>>d;
		if(!check) continue;
		int l_=find(l),r_=find(r);
		if(l_==r_)
		{
			if(dis[r]-dis[l]!=d) check=false;
		}
		else 
		{
			type[r_]=l_;
			dis[r_]=dis[l]+d-dis[r];
		}
	}
	if(check) puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define fu(a,b,c) for(int a=b;a<=(int)c;++a)
#define fd(a,b,c) for(int a=b;a>=(int)c;--a)
#define cu(a,b,c) for(int a=b;a<(int)c;++a)
#define cd(a,b,c) for(int a=(b)-1;a>=(int)c;--a)
#define gcd(a,b) __gcd(a,b) 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAXN 52
#define MAXH 20
#define MAXM 52
#define INF 100000000
#define ll long long
#define ull unsigned long long
#define RNG rng mt19937(time(NULL))
#define udist(a,b) uniform_int_distribution<uint32_t> distribution(a,b)
#define max3(a,b,c) max(a, max(b, c))
#define min3(a,b,c) min(a, min(b, c))
#define gmax(a,b) a = max(a, b)
#define gmin(a,b) a = min(a, b)
#define whatis(x) cerr << #x << " is " << x << endl;
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI 3.1415926535897932384626433
using namespace std;

int main(){
	ll x;
	cin >> x;
	cout << min(2*((x+10)/11), 2*((x-6 + 10)/11) + 1) << endl;
}


Measured memory_bytes: 256
n, m, x = [int(i) for i in input().split()]
arr = []

for _ in range(n):
    arr.append([int(i) for i in input().split()])

min_amount = float('+inf')
has_sol = False

def dfs(idx, amt, skills):
    global arr
    global min_amount
    global x
    global has_sol

    if idx == len(arr):
        ok = all(j >= x for j in skills)

        if ok:
            has_sol = True
            min_amount = min(min_amount, amt)
        return

    dfs(idx+1, amt, skills)
    dfs(idx+1, amt+arr[idx][0], [j+arr[idx][i+1] for i, j in enumerate(skills)])

dfs(0, 0, [0]*m)

if not has_sol:
    print('-1')
else:
    print(min_amount)


Measured memory_bytes: 71724
n, k, q = map(int,input().split())
a = dict((i,0) for i in range(1,n+1))

for _ in range(q):
    a[int(input())] += 1

for i in range(1, n + 1):
    print('Yes' if k - q + a[i] > 0 else 'No')

Measured memory_bytes: 19420
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']

require 'prime'

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def sum(a) a.inject(:+) end

def big(a,b) return (a>b)? a:b end

def small(a,b) return (a<b)? a:b end
x = inp[0]
l = 0
sum = 0
(1000000).times do |i|
  sum += i
  if(sum >= x)
    l = i
    break
  else
    l = i
  end
end
p l

Measured memory_bytes: 2044
#include<stdio.h>

int main(){
	int a,b,ans;
	char op;
	while(1){
		scanf("%d %c %d",&a,&op,&b);
		if(op=='+'){
			ans=a+b;
		} else if (op=='-'){
			ans=a-b;
		} else if (op=='*'){
			ans=a*b;
		} else if (op=='/'){
			ans=a/b;
		} else if (op=='?'){
			break;
		}
		printf("%d\n",ans);
	}
	return 0;
}



Measured memory_bytes: 2104
N,W=map(int,input().split())
WV=[]
for _ in range(N):
    WV.append(tuple(map(int,input().split())))
#i番目までの品物をコストw以下になるように選ぶ
dp=[[0]*(N+1) for _ in range(W+1)]
for i in range(1,N+1):
    for w in range(1,W+1):
        if w<WV[i-1][0]:
            dp[w][i]=dp[w][i-1]
        else:
            dp[w][i]=max(dp[w][i-1],dp[w-WV[i-1][0]][i-1]+WV[i-1][1])
print(dp[W][N])

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

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[2][405][405];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    VVI v;
    REP(i, n) {
      int l, r, w;
      cin >> l >> r >> w;
      v.PB({r, l, w});
    }

    sort(ALL(v));

    memset(dp, -1, sizeof(dp));
    int cur = 0, nxt = 1;
    dp[cur][0][0] = 0;
    REP(i, n) {
      REP(j, 366) REP(k, 366) {
        if(dp[cur][j][k] == -1) continue;
        // cout << i << " " << j << " " << k << " " << dp[i][j][k] << endl;
        int l = v[i][1], r = v[i][0], w = v[i][2];
        // iを使う
        if(l > j) {
          int nj = l <= k ? k : j;
          chmax(dp[nxt][nj][r], dp[cur][j][k] + w);
        }
        // iを使わない
        chmax(dp[nxt][j][k], dp[cur][j][k]);
      }
      // curとnxtをうまくやるやつ
      swap(cur, nxt);
      REP(j, 366) REP(k, 366) dp[nxt][j][k] = -1;
    }

    int ans = 0;
    REP(i, 366) REP(k, 366) chmax(ans, dp[cur][i][k]);
    cout << ans << endl;
  }

  return 0;
}



Measured memory_bytes: 5744
// ABC169B - Multiplication 2

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;

int main() {
	int N;
	cin >> N;
	ull A[N];

	for (int i = 0; i < N; i++) {
		cin >> A[i];
		if (A[i] == 0) {
			cout << 0 << endl;
			return 0;
		}
	}

	ull ans = 1;

	for (int i = 0; i < N; i++) {
		if ((long double)ans * (long double)A[i] > 1000000000000000000.0) {
			cout << -1 << endl;
			return 0;
		}
		ans = ans * A[i];
	}

	cout << ans << endl;

	return 0;
}


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



int main(){
    string S, T;

    cin >> S >> T;
    int cnt = 0;
    for(int i=0; i < 3; i++){
        if(S.at(i) == T.at(i)){
            cnt ++;
        }
    }
    cout << cnt << endl;
    return 0;


}


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

int main(){
    int a[10000],min,max,n,i;
    long long sum=0;
    cin >> n;
    for(i=0 ;i<n;i++){
        cin >> a[i];
        sum += a[i];
    }
    max = min = a[0];
    for(i = 1; i < n; i++){
        if(a[i] > max ) max = a[i];
        if(a[i] < min ) min = a[i];
    }
    cout << min << " "<< max <<" " <<sum << endl;
} 


Measured memory_bytes: 3120
S=input()
N=len(S)
def chk(s):
  n=len(s)
  for i in range(n//2):
    if s[i]!=s[n-1-i]:
      return False
  return True
if chk(S) and chk(S[:((N-1)//2)]) and chk(S[(N+3)//2-1:]):
  print('Yes')
else:
  print('No')

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

using namespace std;

typedef long long ll;

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

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

	int k;
	cin >> k;

	cout << a[k-1] << endl;
}


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

using namespace std;

int main()
{
    int w,h,x,y;
    long long sum;
    double m;
    cin>>w>>h>>x>>y;
    sum=(long long)w*h;
    m=(double)sum/2;
    printf("%.9f ",m);
    if(x*2==w&&y*2==h)
        cout<<'1'<<endl;
    else
        cout<<'0'<<endl;
    return 0;
}


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

long long int N, K, A[364364], B, L;

int main(){
    scanf("%lld%lld", &K, &N);
    if(K == 1){
        for(int i = 0; i < (N + 1) / 2; ++i)cout << "1 ";
        return 0;
    }
    if(K & 1){
        fill(A, A + 364364, K / 2 + 1);
        B = N / 2;
        L = N;
        for(int i = 0; i < B; ++i){
            if(--A[L - 1]){
                for(; L < N; ++L){
                    A[L] = K;
                }
            }else{
                --L;
            }
        }
        for(int i = 0; i < N; ++i){
            if(A[i] == 0)return 0 & puts("");
            cout << A[i] << " ";
        }
    }else{
        cout << (K >> 1) << " ";
        for(int i = 0; ++i < N;)cout << K << " ";
    }
    return 0;
}


Measured memory_bytes: 5120
#include <stdio.h>
int main(int argc, char *argv[])
{
	int x,a,b,y;
	while((scanf("%d %d %d",&x,&a,&b))!=EOF)
	{
		y=a-b;
		if(y<0)y=-y;
		if(y>x)printf("dangerous\n");
		else{
			if(a>=b)printf("delicious\n");
			else printf("safe\n");
		} 		
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(int i=int(m-1); i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << endl; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;

VV G;
V c;
Vll ans;

pair<ll, map<int, ll>> dfs(int u, int p=-1) {
  map<int, ll> res;
  ll sz = 1;
  for (auto v : G[u]) {
    if (v == p) continue;
    auto [sz_v, res_v] = dfs(v, u);
    ll x = sz_v - res_v[c[u]];
    ans[c[u]] -= x*(x+1)/2;
    if (res.size() < res_v.size()) swap(res, res_v);
    for (auto &[a, b] : res_v) res[a] += b;
    sz += sz_v;
  }
  res[c[u]] = sz;
  return {sz, move(res)};
}

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

  G.assign(n, V());
  c.assign(n, 0);
  ans.assign(n, n*(n+1)/2);

  rep(i, n) {
    cin >> c[i];
    --c[i];
  }
  rep(i, n-1) {
    int a, b; cin >> a >> b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  auto [sz, res] = dfs(0);
  rep(i, n) {
    ll x = sz - res[i];
    ans[i] -= x*(x+1)/2;
  }

  cout << ans;
  return 0;
}


Measured memory_bytes: 78948
k = int(input())
l = set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
l1 = [[[] for i in range(10)] for i in range(10)]
for i in range(10):
  l1[0][i].append(i)
for i in range(1, 10):
  for j in range(0, 10):
    if j == 0:
      l1[i][j] = l1[i-1][0] + l1[i-1][1]
    elif j == 1:
      l1[i][j] = l1[i-1][0] + l1[i-1][1] + l1[i-1][2]
    elif j == 2:
      l1[i][j] = l1[i-1][3] + l1[i-1][1] + l1[i-1][2]
    elif j == 3:
      l1[i][j] = l1[i-1][3] + l1[i-1][4] + l1[i-1][2]
    elif j == 4:
      l1[i][j] = l1[i-1][3] + l1[i-1][4] + l1[i-1][5]
    elif j == 5:
      l1[i][j] = l1[i-1][6] + l1[i-1][5] + l1[i-1][4]
    elif j == 6:
      l1[i][j] = l1[i-1][7] + l1[i-1][6] + l1[i-1][5]
    elif j == 7:
      l1[i][j] = l1[i-1][8] + l1[i-1][7] + l1[i-1][6]
    elif j == 8:
      l1[i][j] = l1[i-1][9] + l1[i-1][8] + l1[i-1][7]
    else:
      l1[i][j] = l1[i-1][9] + l1[i-1][8]
    l1[i][j] = [x + j * 10**i for x in l1[i][j]]
    l = l | set(l1[i][j])
l2 = list(l)
l2.sort()
print(l2[k])

Measured memory_bytes: 29608
#include<iostream>
#include<sstream>

using namespace std;


int main() {
	int a;
	cin >> a;
	unsigned long int i, z;
	int x;
	int y;
	z = 0;

	for (i = 1; i <= a; i++) {
		
		x = i % 3;
		y = i % 5;
		if (!((x == 0) || (y == 0))) {
			z += i;
		}
	}

	cout << z << endl;

	return 0;

}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
    
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;

int main(){

    string s;
    cin >> s;

    if(s == "KIHBR") cout << "YES" << endl;
    else if(s == "KIHBRA") cout << "YES" << endl;
    else if(s == "KIHBAR") cout << "YES" << endl;
    else if(s == "KIHBARA") cout << "YES" << endl;
    else if(s == "KIHABR") cout << "YES" << endl;
    else if(s == "KIHABRA") cout << "YES" << endl;
    else if(s == "KIHABAR") cout << "YES" << endl;
    else if(s == "KIHABARA") cout << "YES" << endl;
    else if(s == "AKIHBR") cout << "YES" << endl;
    else if(s == "AKIHBRA") cout << "YES" << endl;
    else if(s == "AKIHBAR") cout << "YES" << endl;
    else if(s == "AKIHBARA") cout << "YES" << endl;
    else if(s == "AKIHABR") cout << "YES" << endl;
    else if(s == "AKIHABRA") cout << "YES" << endl;
    else if(s == "AKIHABAR") cout << "YES" << endl;
    else if(s == "AKIHABARA") cout << "YES" << endl;
    else cout <<"NO" << endl;



}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}




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

  int ans = 0;
  REP(i, s.size()) {
    ans += (s[i] - '0');
    ans %= 9;
  }
  cout << (ans % 9 == 0 ? "Yes":"No") << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 3708
import java.util.*;

public class Main {

	@SuppressWarnings("resource")
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int W = sc.nextInt();
		int H = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int r = sc.nextInt();
		if(x-r >= 0 && x+r <= W && y-r >= 0 && y+r <= H){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 26404
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#define REP(i,n) for(long (i)=0;(i)<(n);(i)++)
#define REPI(i,a,b) for(long (i)=(a);(i)<(b);(i)++)
#define INF numeric_limits<double>::infinity()
constexpr long MOD = 1e9 + 7;
using namespace std;
using P = pair<long, long>;
using VI = vector<long>;

long pw(long a, long b) {
    if (b == 0) return 1;
    if (b % 2 == 0) {
        long c = pw(a, b / 2);
        return c * c;
    }
    return a * pw(a, b - 1);
}

int main() {
    long n, m;
    cin >> n >> m;
    
    cout << (1900l * m + 100l * (n - m)) * pw(2, m) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;

int main() {
	int N, * X, sumX=0, sum1 = 0, sum2 = 0, P=0;

	cin >> N;

	X = new int[N];

	for (int i = 0; i < N; i++) {
		cin >> X[i];
		sumX += X[i];
	}

	P = sumX / N;


	for (int i = 0; i < N; i++) {
		sum1 += pow(X[i] - P, 2);
	}

	for (int i = 0; i < N; i++) {
		sum2 += pow(X[i] - P-1, 2);
	}

	if (sum1 < sum2) cout << sum1;
	else cout << sum2;

	return 0;
}


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

int main() {
  int a, b;
  cin >> a >> b;
  string s;
  cin >> s;
  if(s[b-1] == 'A'){
    s[b-1] = 'a';
  }
  if(s[b-1] == 'B'){
    s[b-1] = 'b';
  }
  if(s[b-1] == 'C'){
    s[b-1] = 'c';
  }
  cout << s;
  return 0;
}

Measured memory_bytes: 256
n=int(input())
l=[None for i in range(n)]
for i in range(n):
    l[i]=input()
l.sort()
m=0
now=l[0]
cnt=1
ll=[[] for i in range(n+1)]
for i in range(1,n):
    if l[i]!=now:
        m=max(m,cnt)
        ll[cnt].append(now)
        now=l[i]
        cnt=1
    else:
        cnt+=1
m=max(m,cnt)
ll[cnt].append(now)
for s in ll[m]:
    print(s)


Measured memory_bytes: 88652
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String S = in.next();
        if (S.matches("A[a-z]+C[a-z]+")) {
            System.out.println("AC");
        } else {
            System.out.println("WA");
        }
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#include <cctype>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template<typename key, typename val>
//using ordered_tree =
//  tree<key, val, std::less<>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
typedef complex<double> comp;
const double pi = 3.14159265358979323846;
const int inf = (int)1e+9 + 2;
const int64 inf64 = (int64)1e+18 + 2;
const double dinf = 1e+20;
const int mod = 1'000'000'007;//*/998244353;
const int base = 2187;
const double eps = 1e-9;
const int N = 300'000;
const int LOGN = 19;

int n, m, k;

void solve(int) {
  string s;
  cin >> s;
  char ok = 1;
  n = (int)s.size();
  for (int i = 0; i < n; ++i) {
    ok &= s[i] == s[n - 1 - i];
  }
  for (int i = 0; i < n / 2; ++i) {
    ok &= s[i] == s[n / 2 - 1 - i];
    ok &= s[n - 1 - i] == s[n / 2 + 1 + i];
  }
  if (ok) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}

void precalc() {
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  precalc();
  int test = 1;
  //cin >> test;
  //auto start = chrono::high_resolution_clock::now();
  for (int i = 1; i <= test; ++i) {
    solve(i);
  }
  //cerr << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << '\n';
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int a;
	string s;

	cin >> a >> s;

	if (a >= 3200) {
		cout << s << endl;
		return 0;
	}
	cout << "red" << endl;



}

Measured memory_bytes: 256
# coding: utf-8

# import numpy as np

"""
20191118
"""


# def max_pair(abc, start, unavailable=None):
#     pair = [0, 0]
#     for i in range(3):
#         if unavailable is not None:
#             if i == unavailable:
#                 continue
#         for j in range(3):
#             if j != i and abc[i][start] + abc[j][start+1] > abc[pair[0]][start] + abc[pair[1]][start+1]:
#                 pair = [i, j]

#     return pair


# def main():
#     N = int(input())
#     a = [None for _ in range(N)]
#     b = [None for _ in range(N)]
#     c = [None for _ in range(N)]
#     for i in range(N):
#         a[i], b[i], c[i] = map(int, input().split())
#     abc = [a, b, c]

#     if N == 1:
#         print(max(a[0], b[0], c[0]))
#         return None

#     first_pair = max_pair(abc, 0)

#     # first_pair = [0, 0]
#     # for i in range(3):
#     #     for j in range(3):
#     #         if j != i and abc[i][0] + abc[j][1] > abc[first_pair[0]][0] + abc[first_pair[1]][0]:
#     #             first_pair = [i, j]

#     max_sat = [None for _ in range(N)]
#     max_sat[0] = {"sat": max(a[0], b[0], c[0]), "use": np.argmax([a[0], b[0], c[0]])}
#     max_sat[1] = {"sat": abc[first_pair[0]][0] + abc[first_pair[1]][1], "use": first_pair[1]}

#     for i in range(2, N):
#         pre = max_sat[i-1]["use"]
#         available = [0, 1, 2]
#         available.remove(pre)

#         if i == 2:
#             pair = max_pair(abc, i-1)
#         else:
#             pair = max_pair(abc, i-1, max_sat[i-3]["use"])

#         candidates = [max_sat[i-1]["sat"]+abc[k][i] for k in available]
#         candidates.append(max_sat[i-2]["sat"]+abc[pair[0]][i-1]+abc[pair[1]][i])
#         max_idx = np.argmax(candidates)
#         if max_idx == 2:  # i-2から変更
#             use = pair[1]
#             max_sat[i-2] = {"sat": max_sat[i-3]["sat"]+abc[pair[0]][]}
#         else:
#             use = available[max_idx]

#         max_sat[i] = {
#             "sat": candidates[max_idx],
#             "use": use
#         }
#     print(max_sat[-1]["sat"])
#     for i in range(N):
#         print(max_sat[i])


def main():
    N = int(input())
    a = [None for _ in range(N)]
    b = [None for _ in range(N)]
    c = [None for _ in range(N)]
    for i in range(N):
        a[i], b[i], c[i] = map(int, input().split())

    satisfaction = [[0 for _ in range(N)] for _ in range(3)]
    satisfaction[0][0] = a[0]
    satisfaction[1][0] = b[0]
    satisfaction[2][0] = c[0]

    for i in range(1, N):
        satisfaction[0][i] = max(satisfaction[1][i-1], satisfaction[2][i-1]) + a[i]
        satisfaction[1][i] = max(satisfaction[0][i-1], satisfaction[2][i-1]) + b[i]
        satisfaction[2][i] = max(satisfaction[0][i-1], satisfaction[1][i-1]) + c[i]

    return max(satisfaction[0][-1], satisfaction[1][-1], satisfaction[2][-1])


if __name__ == "__main__":
    print(main())

Measured memory_bytes: 26928
import java.util.Scanner;

public class Main {

	private static Node3[] nodes;

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		nodes = new Node3[n];

		for (int i = 0; i < n; i++) {
			nodes[i] = new Node3(-1, -1, -1);
		}

		for (int i = 0; i < n; i++) {
			int id = sc.nextInt();
			int left = sc.nextInt();
			int right = sc.nextInt();

			nodes[id].left = left;
			nodes[id].right = right;

			if (left != -1 && right != -1) {
				nodes[left].parent = id;
				nodes[right].parent = id;
			} else if (left != -1) {
				nodes[left].parent = id;
			} else if (right != -1) {
				nodes[right].parent = id;
			}
		}

		int root = -1;

		for (int i = 0; i < n; i++) {
			if (nodes[i].parent == -1) {
				root = i;
			}
		}

		System.out.println("Preorder");
		preorder(root);
		System.out.println("");
		System.out.println("Inorder");
		inorder(root);
		System.out.println("");
		System.out.println("Postorder");
		postorder(root);
		System.out.println("");
	}

	public static int searchMaxLeft(int u) {
		if (nodes[u].left == -1) {
			return u;
		} else {
			return searchMaxLeft(nodes[u].left);
		}
	}

	public static void preorder(int u) {

		System.out.print(" " + u);

		if (nodes[u].left != -1) {
			preorder(nodes[u].left);
		}
		if (nodes[u].right != -1) {
			preorder(nodes[u].right);
		}
	}

	public static void inorder(int u) {

		if (nodes[u].left != -1) {
			inorder(nodes[u].left);
		}

		System.out.print(" " + u);

		if (nodes[u].right != -1) {
			inorder(nodes[u].right);
		}
	}

	public static void postorder(int u) {

		if (nodes[u].left != -1) {
			postorder(nodes[u].left);
		}

		if (nodes[u].right != -1) {
			postorder(nodes[u].right);
		}

		System.out.print(" " + u);
	}
}

class Node3 {
	int parent;
	int left;
	int right;

	public Node3(int parent, int left, int right) {
		this.parent = parent;
		this.left = left;
		this.right = right;
	}

}

Measured memory_bytes: 26188
#include<stdio.h>
#include<string.h>
int main(void){
    char code[5];
    int cnt=0;
    for(int j=0;j<4;j++){scanf("%s",code);}
    for(int i=0;i<4;i++){
        if(code[i]==code[i+1]){cnt++;}
        
    }
    if(cnt==0)printf("Good\n");
    else printf("Bad\n");
    return 0;
    }

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

using namespace std;

const int INF = 1e9 + 7;

void solve()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for(auto& i : a) {
    cin >> i;
  }
  sort(a.begin(), a.end());
  set<int> s;
  auto i = a.begin();
  for (; *i < 3200 && i != a.end(); ++i) {
    s.insert(*i / 400);
  }
  cout << (s.size() ? s.size() : 1) << " " << static_cast<int>(s.size() + (a.end() - i)) << "\n";
}

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

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

int main(){
	ll x,y;
	cin>>x>>y;
	ll count=0;
	while(x<=y){
		x*=2;
		count++;
	}
	puts(count);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define rrep(i,n) for(int i=(n-1); i>=0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define to_s to_string
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define pr(x) cout<<(x)<<'\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
#define yes "Yes"
#define no "No"
using namespace std;
using ll = long long;
using Edge = pair<int,long long>;
using Graph = vector<vector<Edge> >;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
 
int N;
Graph G;
 
vector<int> dir;
void dfs(int v, int p, int c) {
    dir[v] = c;
    for (auto e : G[v]) {
        if (e.first == p) continue;
        if (e.second & 1) dfs(e.first, v, 1-c);
        else dfs(e.first, v, c);
    }
}
 
int main() {
    cin >> N;
    G.assign(N, vector<Edge>());
    for (int i = 0; i < N-1; ++i) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        --u, --v;
        G[u].push_back(Edge(v, w));
        G[v].push_back(Edge(u, w));
    }
    dir.assign(N, 0);
    dfs(0, -1, 1);
    for (auto v : dir) cout << v << endl;
}

Measured memory_bytes: 10496
def has_no(s, digits):
    for ch in s:
        if ch in digits:
            return False
    return True

def digit():
    N, K = [int(n) for n in input().split()]
    digits = input().split()

    for i in range(N, N*10):
        s = str(i)
        if has_no(s, digits):
            print(s)
            break

digit()

Measured memory_bytes: 9100
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
	char S[1000]; scanf("%s", S);
	if ('S' == S[0]){
		printf("Cloudy");

	}
	else if ('C' == S[0]){
		printf("Rainy");
		
	}
	else{
		printf("Sunny");
	}

	return 0;
}

Measured memory_bytes: 128
from collections import Counter

N = int(input())
V = list(map(int, input().split()))

# 奇数
O = V[0::2]
#print(O)

# 偶数
E = V[1::2]
#print(E)

co = Counter(O)
ce = Counter(E)

# これをいれとかないと、最頻値が１しか無い時に２つめを取得できなくなる
co[0] = 0
ce[0] = 0

co1 = co.most_common(1)
ce1 = ce.most_common(1)

co2 = co.most_common(2)
ce2 = ce.most_common(2)

if co1[0][0] == ce1[0][0]:
    print(min(N - co1[0][1] - ce2[1][1], N - co2[1][1] - ce1[0][1]))
else:
    print(N - co1[0][1] - ce1[0][1])

Measured memory_bytes: 19040
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=1e5+10;
int n,k,sum=0,count[N],q[N],h=1,t=0,fa[N],ll[N];
int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}
    return ans*f;
}
int main(){
    n=read();k=read();
    int a=read();if(a!=1)sum++;
    for(int i=2;i<=n;i++){
        a=read();fa[i]=a;count[a]++;
    }
    for(int i=2;i<=n;i++)if(!count[i])q[++t]=i;
    while(h<=t){
        int x=q[h];h++;
        if(x==1)break;
        if(fa[x]!=1&&ll[x]==k-1)sum++;
        else ll[fa[x]]=std::max(ll[fa[x]],ll[x]+1);
        count[fa[x]]--;
        if(!count[fa[x]])q[++t]=fa[x];
    }
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL sol;
int n,m,a,u;
priority_queue<int,vector<int>,less<int> > Pq1;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        sol+=(LL)a;
        Pq1.push(a);
    }
    while(m--){
        int x=Pq1.top()/2,y=Pq1.top();
        sol-=(LL)(y-x);
        Pq1.pop();
        Pq1.push(x);
    }
    cout<<sol;
    return 0;
}


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

int main() {
	int n;
	int input;

	cin >> n;

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

		if (input % 2 == 0) {
			if (!(input % 3 == 0 || input % 5 == 0)) {
				cout << "DENIED";
				return 0;
			}
		}
	}

	cout << "APPROVED";
}

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

int main(void) {
    int i, n, seki=0;
    cin >> n;
    int l[n], r[n];
    for(i=0; i<n; i++) {
        cin >> l[i] >> r[i];
        seki+=r[i]-l[i]+1;
    }
    cout << seki << endl;
}

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

start, end = 1, n
for _ in range(m):
  l, r = map(int, input().split())
  if r < start or l > end:
    start, end = 1, 0
    break
  elif l <= start and start <= r <= end:
    end = r
  elif start <= l <= end and end <= r:
    start = l
  elif l <= start and r >= end:
    pass
  else:
    start, end = l, r

print(end - start + 1)

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

struct XorShift { // Reference: http://yukicoder.me/submissions/44108
    unsigned z;
    XorShift() : z((unsigned)time(NULL)) {}
    XorShift(int seed) : z(z) {}
    unsigned next() {
        z ^= z << 13;
        z ^= z >> 17;
        z ^= z << 5;
        return z;
    }
    unsigned nextInt(unsigned a, unsigned b) {
        return next() % (b - a + 1) + a;
    }
    double nextDouble() {
        return next() / (double)(1ll << 32);
    }
};

int D;
vector<ll> C;
vector<vector<ll>> S;
vector<int> T;

struct state {
    int d, c;
    vector<ll> pen, cpen;
    vector<int> TT;
    ll ans;
};

state incremental(ll ans, vector<ll> pen, vector<ll> cpen, vector<int> TT, int d, int c) {
    int prev = TT[d];
    int cur = c;
    ans += cpen[prev] + cpen[cur];
    ans -= S[d][prev];
    ans += S[d][cur];
    pen[prev] = 0;
    pen[cur] = 0;
    cpen[prev] = 0;
    cpen[cur] = 0;
    TT[d] = c;
    rep(i, D) {
        pen[prev] += C[prev];
        pen[cur] += C[cur];
        if(TT[i] == prev) pen[prev] = 0;
        if(TT[i] == cur) pen[cur] = 0;
        cpen[prev] += pen[prev];
        cpen[cur] += pen[cur];
    }
    ans -= cpen[prev] + cpen[cur];
    return {d, c, pen, cpen, TT, ans};
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    cin >> D;
    C.resize(26);
    rep(i, 26) cin >> C[i];
    S.resize(D, vector<ll>(26));
    rep(i, D) rep(j, 26) cin >> S[i][j];
    T.resize(D);
    rep(i, D) {
        T[i] = i % 26;
    }
    
    ll ans = 0;
    vector<ll> pen(26);
    vector<ll> cpen(26);
    rep(i, D) {
        ans += S[i][T[i]];
        rep(j, 26) pen[j] += C[j];
        pen[T[i]] = 0;
        rep(j, 26) {
            cpen[j] += pen[j];
            ans -= pen[j];
        }
    }
    
    
    state F = {0, 0, pen, cpen, T, ans};
    
    
    XorShift xs;
//    vector<state> FB(10);
    rep(xx, 550000) {
        pair<int, int> m1 = mp(xs.nextInt(0, D - 1), xs.nextInt(0, 25));
        pair<int, int> m2 = mp(xs.nextInt(0, D - 1), xs.nextInt(0, 25));
        state FS = incremental(F.ans, F.pen, F.cpen, F.TT, m1.first, m1.second);
        state FSS = incremental(FS.ans, FS.pen, FS.cpen, FS.TT, m2.first, m2.second);
        if(FSS.ans > F.ans) {
            F = FSS;
        }
    }
    
    rep(i, D) {
        output(F.TT[i] + 1);
    }
    
    return 0;
}


Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
#define all(c) c.begin(),c.end()
#define init(c) memset(c,0,sizeof c)
#define S second
#define F first
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=20000005;
int n,k,x,t,a,b,m,c;
string s;
vi v;
int main(){

	cin >> a >> b >> c >> k;
	if(k<=a){
		cout << min(a,k);
	}else if(k<=a+b){
		cout << min(a,k);
	}else{
		cout << a-(k-a-b);
	}
	
	return 0;
}

Measured memory_bytes: 3636
import java.util.*;
import static java.lang.Math.*;
public class Main {
	final Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		new Main().init();
	}
	void init(){
		new AOJ2005();
	}
	class AOJ2005{
		AOJ2005(){
			while(sc.hasNext()){
				int n=sc.nextInt(),m=sc.nextInt(),s=sc.nextInt(),g1=sc.nextInt(),g2=sc.nextInt();
				if(n==0)	break;
				--s; --g1; --g2;
				solve(n,m,s,g1,g2);
			}
		}
		final int INF=Integer.MAX_VALUE/4;
		void solve(int n,int m,int s,int g1,int g2){
			int[][] g=new int[n][n];
			for(int i=0; i<n; ++i)for(int j=0; j<n; ++j)	g[i][j]=(i==j?0 :INF);
			for(int i=0; i<m; ++i){
				int a=sc.nextInt(),b=sc.nextInt(),c=sc.nextInt();
				--a; --b;
				g[a][b]=c;
			}
			
			for(int j=0; j<n; ++j)for(int i=0; i<n; ++i)for(int k=0; k<n; ++k)g[i][k]=min(g[i][k], g[i][j]+g[j][k]);
			
			int ans=INF;
			for(int i=0; i<n; ++i)	ans=min(ans, g[s][i]+g[i][g1]+g[i][g2]);
			System.out.println(ans);
		}
	}
}

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

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define MIN(a,b) ((a)>(b)? (b): (a))
#define MAX(a,b) ((a)<(b)? (b): (a))

const long long INF = 1LL << 60;

typedef unsigned long long ll;

const long long MOD = 1000000000 + 7;

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(){
    int a,b,h;
    cin >> a >> b >> h;
    ll sqare = (a + b) * h / 2;
    cout << sqare << endl;
    return 0;
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/abc128/tasks/abc128_c

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<string, int> PSI;
#define INF (1e9)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOREACH(x, a) for (auto &(x) : (a))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
// int gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// int lcm(long a, long b) { return a * b / gcd(a, b); }

int n, m;
vector<unsigned int> vi; // 入力値のビット列（例：1, 3なら101）
vector<unsigned int> vp; // ビット列の総和の偶数・奇数
bool check(unsigned int arg) {
    int ans = 0, cnt;
    bool flag = true;
    // スイッチが未接続なら点灯しない
    if (arg == 0)
        return false;
    // 全部のスイッチで点灯するか確認
    REP(i, m) {
        cnt = __builtin_popcount(vi[i] & arg);
        if (cnt % 2 != vp[i]) {
            flag = false;
            break;
        }
    }
    return flag;
}
int ok(int light) {
    for (int i = 0; i < m; ++i) {
        int cnt = 0;
        cnt = __builtin_popcount(vi[i] & light);
        if (vp[i] != (cnt & 1))
            return false;
    }
    return true;
}
int dfs(int idx, unsigned int arg) {
    if (idx == n) {
        return ok(arg);
    }
    int ans = dfs(idx + 1, arg);
    arg |= (1 << idx); // nビット目を1にする
    ans += dfs(idx + 1, arg);
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    vi.resize(m);
    vp.resize(m);
    REP(i, m) {
        int k, l;
        cin >> k;
        // 入力値をビット列にする（例：1, 3なら101）
        unsigned int t = 0;
        REP(j, k) {
            cin >> l;
            t |= (1 << (--l));
        }
        vi[i] = t;
    }
    REP(i, m) { cin >> vp[i]; }
    cout << dfs(0, 0) << endl;
    return 0;
}

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

int main(){
  int n,k;
  cin>>n>>k;
  vector<int>a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  int an=0;
  for(int i=0;i<k;i++){
    an+=a[n-1-i];
  }
  cout<<an<<endl;
  
}
  


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

int main() {
  int N, K;
  cin >> N >> K;
  vector<bool> v(N);
  int d, ex;
  for (int i = 0; i < K; i++) {
    cin >> d;
    for (int j = 0; j < d; j++) {
      cin >> ex;
      v[ex - 1] = true;
    }
  }
  int cnt = 0;
  for (int i = 0; i < N; i++) {
      if(v[i]==false) cnt++;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3612
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr

A,B=map(int,input().split())
l=factorization(A)
c=0
for x in l:
    c += 1 if B%x==0 else 0
print(1 if l==[1] else c+1)

Measured memory_bytes: 38512