akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int const inf=1e8;
int n,target[800005],pre[800005],last[200005],cap[800005],tot=1,maxflow,
cur[200005],s,t,dis[200005],ans[200005],ans2[200005];
bool visited[200005];
queue<int>q;
void add(int x,int y,int z)
{
	target[++tot]=y;
	pre[tot]=last[x];
	last[x]=tot;
	cap[tot]=z;
	target[++tot]=x;
	pre[tot]=last[y];
	last[y]=tot;
}
bool bfs()
{
	for(int i=1;i<=t;i++)dis[i]=inf,cur[i]=last[i];
	cur[0]=last[0];
	q.push(0);
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=last[now];i;i=pre[i])
		{
			if(cap[i]&&dis[target[i]]==inf)
			{
				dis[target[i]]=dis[now]+1;
				q.push(target[i]);
			}
		}
	}
	return dis[t]!=inf;
}
int dfs(int x,int lim)
{
	if((!lim)||x==t)return lim;
	int flow=0;
	for(int i=cur[x];i;cur[x]=i,i=pre[i])
	{
		int tar=target[i];
		if(cap[i]&&dis[target[i]]==dis[x]+1)
		{
			int d=dfs(target[i],min(lim,cap[i]));
			cap[i]-=d;
			cap[i^1]+=d;
			flow+=d;
			lim-=d;
			if(!lim)return flow;
		}
	}
	return flow;
}
void dinic()
{
	while(bfs())maxflow+=dfs(s,inf);
}
void getans(int x,int fa)
{
	//cout<<x<<endl;
	visited[x]=1;
	for(int i=last[x];i;i=pre[i])
	{
		int tar=target[i];
		if(x<=n)
		{
			if(tar==s||tar==t)continue;
			if(!visited[tar])
			{
				getans(tar,x);
				//return;
			}
		}
		else
		{
			if(tar==t||(!cap[i]))continue;
			++ans[0];
			ans[x-n]=fa;
			ans2[x-n]=tar;
			getans(tar,tar);
			return;
		}
	}
}
int main()
{
	int x,T;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d",&T);
		while(T--)
		{
			scanf("%d",&x);
			add(x,i+n,1);
		}
	}
	for(int i=1;i<=n;i++)add(0,i,1);
	for(int i=n+1;i<n*2;i++)add(i,n*2,1);
	t=n*2,s=0;
	dinic();
	if(maxflow<n-1)
	{
		puts("-1");
		return 0;
	}
	int st;
	for(int i=1;i<=n;i++)
	{
		bool flag=1;
		for(int j=last[i];j;j=pre[j])
		{
			//cout<<i<<" "<<target[j]<<" "<<cap[j]<<endl;
			if(target[j]>n&&(!cap[j]))
			{
				flag=0;
				break;
			}
		}
		if(flag)
		{
			st=i;
			break;
		}
	}
	getans(st,st);
	if(ans[0]!=n-1)
	{
		puts("-1");
		return 0;
	}
	for(int i=1;i<=ans[0];i++)printf("%d %d\n",ans[i],ans2[i]);
	return 0;
}

Measured memory_bytes: 17792
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
using namespace std;

int main() {
	int N, A, a[100001] = {}, ans = 0;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A;
		if (A > N)ans++;
		else a[A]++;
	}
	for (int i = 0; i < N+1; i++)
	{
		if (a[i] != 0)
		{
			ans += abs(((a[i]>=i)?a[i]-i:a[i]-0));
		}
	}
	cout << ans;
}


Measured memory_bytes: 640
A, B, C, D = map(int, raw_input().strip().split())

def gcd(x, y):
    if x < y:
        return gcd(y, x)
    if y == 0:
        return x
    return gcd(y, x%y)

def lcm(x, y):
    return (x*y)/gcd(x, y)

L = lcm(C, D)

def interval(l, r, d):
    return (r/d) - (l-1)/d

ans = interval(A, B, 1) - interval(A, B, C) - interval(A, B, D) + interval(A, B, lcm(C, D))
print ans

Measured memory_bytes: 2568
#include<iostream>
using namespace std;
int  main()
{
	int a,b;
	cin>>a>>b;
	if(a<b)
		cout<<"a < b"<<endl;
	else if(a>b)
		cout<<"a > b"<<endl;
	else
		cout<<"a == b"<<endl;
	return 0;
}


Measured memory_bytes: 3136
import java.util.*;
public class Main{
   public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);
     long  N = sc.nextLong();
     long ans=0,test=10;
     if(N%2==0){
       while(N>=test){
         ans+=N/test;
         test*=5;
       }
     }else{
       ans=0;
     }
     System.out.println(ans);
   }
}


Measured memory_bytes: 23764
#include <iostream>
#include <string.h>

using namespace std;
bool IsPrime[1000001];

void calc()
{
	memset(IsPrime, 1, sizeof(IsPrime));
	IsPrime[0] = false;
	IsPrime[1] = false;
	for(int i = 2; i < 1000001; ++i)
	{
		if(IsPrime[i])
		{
			for(int j = 2 * i; j < 1000001; j += i)
			{
				IsPrime[j] = false;
			}
		}
	}
}

void solve()
{
	calc();
	int a, d, n;
	while(cin >> a >> d >> n, a || d || n)
	{
		int count = 0;
		while(true)
		{
			if(count == n)
			{
				break;
			}
			if(IsPrime[a])
			{
				count++;
			}
			a += d;			
		}
		cout << a - d << endl;
	}
}

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

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

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

  int ma=0,mi=1000;
  int a;
  for(int i=0;i<N;i++) {
    cin >> a;
    ma=max(ma,a);
    mi=min(mi,a);
  }
  cout << ma-mi << endl;
}


Measured memory_bytes: 256
/*
[dp] O - Matching
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAX_N = 21;
const ll MOD = 1e9 + 7;

int N;
int a[MAX_N][MAX_N];
ll dp[MAX_N + 1][1 << MAX_N];

ll solve() {
    dp[0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int pat = 0; pat < (1 << N); pat++) {
                if (a[i][j] && (pat & (1 << j)) == 0) {
                    (dp[i + 1][pat | (1 << j)] += dp[i][pat]) %= MOD;
                }
            }
        }
    }

    return dp[N][(1 << N) - 1];
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> a[i][j];
        }
    }
    cout << solve() << endl;

    return 0;
}


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

int main(){
  int n;cin>>n;
  int p[n],m=0,sum=0;
  for(int i=0;i<n;i++){
    cin>>p[i];
    sum+=p[i];
    m=max(m,p[i]);
    // cout<<m<<endl;
  }
  cout<<sum-m/2<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String S=sc.next();
    int N=S.length();
    String Moto[]=S.split("");
    String Hantai[]=new String[N];
    String H2[]=new String[(N-1)/2];
    String H3[]=new String[(N+5)/2];
    boolean first=true;
    boolean second=true;
    boolean third=true;
    for(int i=0;i<N;i++){
      Hantai[i]=Moto[N-1-i];
    }
    for(int i=0;i<(N-1)/2;i++){
      H2[i]=Moto[(N-1)/2-1-i];
    }
    for(int i=0;i<(N+5)/2;i++){
      if(N==(N+3)/2){
        break;
      }
      H3[i]=Moto[N-1-i];
    }
    for(int i=0; i<N-1; i++){
      if(!(Moto[i].equals(Hantai[i]))) {first=false;
        break;}
      }
      for(int i=0;i<(N-1)/2-1;i++){
        if(!(Moto[i].equals(H2[i]))) {second=false;
          break;}

        }
        for(int i=0;i<(N+5)/2-1;i++){
          if(N==(N+3)/2){
            break;
          }
          if(!(Moto[i].equals(H3[i]))) {third=false;
            break;}
          }
          if(first&&second&&third){
            System.out.println("Yes");
          }else{
            System.out.println("No");
          }
        }
      }


Measured memory_bytes: 21844
#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 15;
const int inf = 1e9 + 9;

int n, m;
int cost[maxn][maxn];

int f[(1 << maxn) + 5][maxn];

int dp[(1 << maxn) + 5][maxn];

void read_input()
{
    cin >> n >> m;
    fill_n(&cost[0][0], sizeof(cost) / sizeof(cost[0][0]), 0);
    for(int i = 1; i <= m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        cost[u][v] = cost[v][u] = w;
    }
}

void solve()
{
    for(int mask = 0; mask < (1 << n); ++mask)
        for(int i = 0; i < n; ++i)
        {
            if(mask >> i & 1) continue;
            for(int j = 0; j < n; ++j)
                if(mask >> j & 1) f[mask][i] += cost[i][j];
        }

    fill_n(&dp[0][0], sizeof(dp) / sizeof(dp[0][0]), inf);
    dp[1][0] = 0;
    for(int mask = 0; mask < (1 << n); ++mask)
    {
        for(int i = 0; i < n; ++i)
            if((mask >> i & 1) && dp[mask][i] != inf)
            {
                for(int ni = 0; ni < n; ++ni)
                    if(!(mask >> ni & 1) && cost[i][ni])
                    {
                        int nmask = (mask ^ (1 << ni));
                        dp[nmask][ni] = min(dp[nmask][ni],
                                            dp[mask][i] + f[mask ^ (1 << i)][ni]);
                    }
            }
        for(int i = 0; i < n; ++i)
            if((mask >> i & 1) && dp[mask][i] != inf)
            {
                int otr = (1 << n) - 1 - mask;
                for(int nmask = otr; nmask > 0; nmask = (nmask - 1) & otr)
                {
                    int sum = 0;
                    for(int j = 0; j < n; ++j)
                        if(nmask >> j & 1) sum += f[mask ^ (1 << i)][j];
                    dp[nmask | mask][i] = min(dp[nmask | mask][i],
                                              dp[mask][i] + sum);
                }
            }
    }
    cout << dp[(1 << n) - 1][n - 1] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    solve();
}



Measured memory_bytes: 7480
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#include<bitset>
#include<stdio.h>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const int INF = 100000000;

bool isOK(int a[],int index,int key){
    if(a[index] >= key){
        return true;
    }else{
        return false;
    }
}

int binary_search(int a[],int n,int key){
    int left = -1;
    int right = n;

    while(right-left>1){
        int mid = left + (right - left)/2;
        if(isOK(a,mid,key)){
            right = mid;
        }else{
            left = mid;
        }
    }
    return right;
}

int factrial(int n){
    if(n==0){
        return 1;
    }else{
        return n*factrial(n-1);
    }
}

int main(void){
    char c;
    cin >> c;
    cout << (char)(c+1) << endl;
    return 0;
}


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

int n, pos;
vector<int> pre, in, post;

void rec(int l, int r) {
    if ( l >= r ) return;
     int root = pre[pos++];
     int m = distance(in.begin(), find(in.begin(), in.end(), root));
     rec(l, m);
     rec(m + 1, r);
     post.push_back(root);
     }

void solve() {
     pos = 0;
     rec(0, pre.size());
     for ( int i = 0; i < n; i++ ) {
        if ( i ) cout << " ";
         cout << post[i];
         }
     cout << endl;
}

int main(){
    int k; cin >> n;
    for ( int i = 0; i < n; i++ ) {
        cin >> k;
        pre.push_back(k);
    }
    for ( int i = 0; i < n; i++ ) {
        cin >> k;
        in.push_back(k);
}
    
    solve();
    return 0;
}


Measured memory_bytes: 3152
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>

using namespace std;

int main() {
	int N, D; cin >> N >> D;
	D = D * 2 + 1;
	cout << (N + D - 1) / D << endl;
	return 0;
}


Measured memory_bytes: 256
//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<cstring>
//using namespace std;
//const int M = 100010;
//int x,cnt,ans,p,k,t,l,n;
//int a[M],b[M];
//bool f[M];
//char s[M];
//int main()
//{
//	memset(f,0,sizeof(f));
//	memset(a,0,sizeof(a));
//	memset(b,0,sizeof(b));
//	ans = 0;
//	scanf("%d",&n);
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d",&a[i]);
//		//b[i]= 1;
//	}
//	for (int i = 0; i < n; i++)
//	{
//		memset(b,0,sizeof(b));
//		for (int j = 0; j < n; j++)
//		{
//			if(a[j] + 1 == a[i] || a[j] - 1 == a[i] || a[i] == a[j])
//			{
//				b[a[i]] ++;
//			}
//		}
//		if(b[a[i]] > ans)
//			ans = b[a[i]];
//	}
//	printf("%d\n",ans);
//	return 0;
//}

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int M = 100010;
int x,cnt,ans,p,k,t,l,n;
int a[M],b[M];
bool f[M];
char s[M];
int main()
{
	memset(f,0,sizeof(f));
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	ans = 0;
	scanf("%d",&n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d",&a[i]);
		b[a[i]]++;
		b[a[i]+1]++;
		b[a[i]-1]++;
	}
	for (int i = 0; i < n; i++)
		ans = max(ans,b[a[i]]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1152
data Dice = Dice {top :: Int,
                  south :: Int,
                  east :: Int,
                  west :: Int,
                  north :: Int,
                  bottom :: Int}
fromList :: [Int] -> Dice
fromList [t,s,e,w,n,b] = Dice t s e w n b

rotate :: Dice -> Char -> Dice
rotate d 'N' = d {bottom = north d,
                  north = top d,
                  top = south d,
                  south = bottom d}
rotate d 'S' = d {bottom = south d,
                  south = top d,
                  top = north d,
                  north = bottom d}
rotate d 'E' = d {bottom = east d,
                  east = top d,
                  top = west d,
                  west = bottom d}
rotate d 'W' = d {bottom = west d,
                  west = top d,
                  top = east d,
                  east = bottom d}

rotateAll :: Dice -> [Char] -> Int
rotateAll d [] = top d
rotateAll d (op:ops) = rotateAll (rotate d op) ops

main :: IO ()
main = do
  d <- fmap (fromList . map read . words) getLine
  ops <- getLine
  print $ rotateAll d ops

Measured memory_bytes: 3492
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	h := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&h[i])
	}
	var cnt int
	var ans int
	for i := 0; i < n-1; i++ {
		if h[i] >= h[i+1] {
			cnt++
			ans = max(cnt, ans)
		} else {
			cnt = 0
		}
	}
	fmt.Println(ans)
}

func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}


Measured memory_bytes: 5504
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
/*#include <boost/multiprecision/cpp_int.hpp> 
using boost::multiprecision::cpp_int;*/
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int              long long int
#define pb              push_back
#define mp12            make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pq1             priority_queue<int>
#define pqr1            priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zerobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
// mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void fast()
{
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

}
void file(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}

int modInv(int a,int b,int m)
{
    int res=1;
    a=a%m;
    while(b>0){
        if(b&1){
            res=(res*a)%m;
        }
        a=(a*a)%m;
        b=b>>1;
    }
    return res;
}


int p[1000006];
vi prime;
//int mrp[1000000];
void seive(){
    for(int i=2;i<1000006;i++) {
        if(p[i]){
            prime.pb(i);
            for(int j=i*i;j<=1000006;j=j+i){
                p[j]=0;
            }
        }
    }

}
// int c;
int dp[3001][3001];
int solve(int i,int j,int a[]){
    if(i>j) return 0;
    if(dp[i][j]!=-1) return dp[i][j];

    int op1=0;
    int op2=0;
    op1=a[i]+min((solve(i+2,j,a)),(solve(i+1,j-1,a)));
    op2=a[j]+min((solve(i+1,j-1,a)),(solve(i,j-2,a)));
    return dp[i][j]=max(op1,op2);
}


int32_t main()
{
    // memset(prime,0,sizeof(prime));
    //memset(p,1,sizeof(p));   
    //seive();
   // file();
    fast();
    //int mo=1000000007;
   int n;
   cin>>n;
   int a[n];
   int s=0;
   for(int i=0;i<n;i++) {
        cin>>a[i];
        s+=a[i];
   }
    memset(dp,-1,sizeof(dp));
    int X=solve(0,n-1,a);
    int Y=s-X;
    cout<<(X-Y);



    return 0;
    
    
}



Measured memory_bytes: 74116
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;

int n;
int a[2011];
int dp[2011][2011];

int f[2011],g[2011];
int main()
{
    int i,j,k;
    
    cin>>n>>a[1]>>a[2];
    for(i=3;i<=n+2;i++)
    {
        cin>>a[i];
    }
    n+=2;
    
    
    memset(dp,-1,sizeof(dp));
    memset(f,0x3f,sizeof(f));
    memset(g,-1,sizeof(g));
    
    
    for(i=1;i<n;i++)
    {
        dp[i][n]=abs(a[i]-a[n]);
        dp[n][i]=abs(a[n]-a[i]);
    }
    
    for(i=1;i<=n-1;i++)
    {
        f[i]=dp[i][n];
        g[i]=dp[n][i];
    }
    
    //f[n-1]=dp[n-1][n];
    //g[n-1]=dp[n][n-1];
    
    for(i=n-1;i>=1;i--)
    {
        for(j=n-1;j>=1;j--)
        {
            if(i==j)continue;
            
            //cout<<i<<' '<<j<<"   ddd"<<endl;
            if(i<j)
            {
                if(dp[i][j]==-1 || dp[i][j]<g[j])
                {
                    dp[i][j]=g[j];
                    f[i]=min(f[i],dp[i][j]);
                }
            }
            else
            {
                if(dp[i][j]==-1 || dp[i][j]>f[i])
                {
                    dp[i][j]=f[i];
                    g[j]=max(g[j],dp[i][j]);
                }
            }
            
            //cout<<dp[i][j]<<' '<<f[i]<<' '<<g[j]<<"   t"<<endl;
            
        }
    }
    /*
    cout<<endl;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cout<<dp[i][j]<<' ';
        }
        cout<<endl;
    }
    */
    cout<<dp[1][2]<<endl;
    
    return 0;
} 


Measured memory_bytes: 16128
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;

int main() {
  int d[3];
  scanf("%d%d%d", &d[0], &d[1], &d[2]);
  sort(d, d+3);
  printf("%d\n", d[2] * 10 + d[1] + d[0]);
}


Measured memory_bytes: 128
#include<iostream>
#include<string>
using namespace std;
int ask(int x)
{
	cout<<x<<endl;
	cout.flush();
	string ret;
	cin>>ret;
	if(ret=="Male")
		return 0;
	if(ret=="Female")
		return 1;
	return 2;
}
int main()
{
	int n;
	cin>>n;
	int lf=ask(0);
	if(lf==2)
		return 0;
	int l=0,r=n-1;
	while(l<r-1)
	{
		int m=(l+r+1)/2;
		int tmp=ask(m);
		if(tmp==2)
			return 0;
		if((((m-l)%2)^tmp^lf)==0)
		{
			lf=tmp;
			l=m;
		}
		else
			r=m-1;
	}
	ask(r);
	return 0;
}

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

def fn(x):
    return x * (x + 1) / 2

lo = 1
hi = 100000

while abs(lo - hi) > 1:
    md = (lo + hi) // 2
    if fn(md) >= N:
        hi = md
    else:
        lo = md
if N == 1:
    x = 1
else:
    x = hi
rem = N
now = x

while rem != 0:
    if now <= rem:
        print(now)
        rem -= now
    now -= 1


Measured memory_bytes: 3316
N,K = map(int,input().split())
ans = 0
if N<K:
  for i in range(1,N+1):
    j = 0
    while i*(2**j) < K:
      j += 1
    ans += 1/((2**j)*N)
else:
  for g in range(1,K):
    s = 0
    while g*(2**s) < K:
      s += 1
    ans += 1/((2**s)*N)
  ans += (N-K+1)/N
print(ans)

Measured memory_bytes: 3064
def partition(A, p, r):
 x = A[r]
 i  = p-1
 for j in range(p,r):
  if A[j] <= x:
   i += 1
   A[i],A[j] = A[j],A[i]
 A[i+1],A[r] = A[r],A[i+1]
 return i+1

n = int(input())
A = list(map(int, input().split()))
x = A[n-1]
q = partition(A, 0, n-1)
print(" ".join(map(str,A[0:q])) + " [" + str(x) + "] " + " ".join(map(str,A[q+1:n])) )

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

#define NREP() for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define IPT(x) ll t; cin >> t; x.push_back(t);
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<string> vvs;

const static ll MOD = 1e9 + 7;

int main(int argc, char *argv[]) {
    ll r;
    cin >> r;

    MSG(fixed << setprecision(15) << 2*r*3.14159265358979323846)
}


Measured memory_bytes: 3800
// @prefix atcoder
// @description atcoder template

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

// typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// rep
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << #x << ": " << x << '\n'
#define DEBUGP(x) cerr << #x << ": " << x.first << " \t" << x.second << '\n'
#define INF (1ll<<60)

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; }
const int MOD = 1e9 + 7;


int a, b, c, k;

signed main()
{
	cin >> a >> b >> c >> k;

	int res = 0;
	if (k <= a){
		res = k;
	} else if (k <= a + b){
		res = a;
	} else {
		res = a - (c - (a + b + c - k));
	}

	cout << res << endl;
	return 0;
}


Measured memory_bytes: 3624
// vvvvvvvvvvvvvvvvv Library code start


#define NDEBUG
NDEBUG


#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <random>


#define all(c) c.begin(), c.end()


using namespace std;

/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);


namespace template_util {
    

    constexpr int bytecount(uint64_t x) {
        return x ? 1 + bytecount(x >> 8) : 0;
    }

    /// caide keep
    template<int N>
    struct bytetype {
        
    };

    /// caide keep
    template<>
    struct bytetype<4> {
        
    };

    /// caide keep
    template<>
    struct bytetype<3> {
        
    };

    /// caide keep
    template<>
    struct bytetype<2> {
        
    };

    /// caide keep
    template<>
    struct bytetype<1> {
        
    };

    /// caide keep
    template<>
    struct bytetype<0> {
        
    };

    /// caide keep
    template<uint64_t N>
    struct minimal_uint : bytetype<bytecount(N)> {
    };
}


template<class T>
T next(istream& in) {
    T ret;
    in >> ret;
    return ret;
}

template<class T>
vector<T> next_vector(istream& in, size_t n) {
    vector<T> ret(n);
    for (size_t i = 0; i < n; ++i) {
        ret[i] = next<T>(in);
    }
    return ret;
}

template<class T>
vector<T> next_vector(istream& in) {
    auto n = next<size_t>(in);
    return next_vector<T>(in, n);
}


// ^^^^^^^^^^^^^^^^^ Library code end

void solve(istream& in, ostream& out) {
    auto as = next_vector<int>(in);
    sort(all(as));
    reverse(all(as));
    int cur = 0;
    while (cur + 1 < as.size() && cur + 1 < as[cur + 1]) {
        ++cur;
    }
    int d1 = as[cur] - cur - 1;
    int d2 = 0;
    while (cur + d2 + 1 < as.size() && cur + 1 == as[cur + d2 + 1]) {
        ++d2;
    }
    int ans;
    if (cur + 1 == as.size()) {
        ans = d1;
    } else if (cur + 1 == as[cur]) {
        ans = d2;
    } else {
        ans = d1 | d2;
    }
    out << (ans & 1 ? "First\n" : "Second\n");
}


int main() {
    solve(cin, cout);
    return 0;
}



Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
#include<limits.h>
#include<algorithm>
#include<queue>
#include<set>
#include<math.h>
#include<random>
#include<set>

#define lli long long int
#define MOD 1000000007

using namespace std;

long long int modpow(long long int a, long long int n) {
	if (n == 0)return 1;
	if (n == 1)return (a % MOD);

	long long int hanbun = n / 2;
	long long int amari = n % 2;

	long long int ans = (a * a) % MOD;
	ans = modpow(ans, hanbun);

	if (amari == 1)ans *= a;

	ans %= MOD;

	return ans;

}

long long int gcd(long long int a, long long int b) {
	if (a < b) {
		long long int tmp = a;
		a = b;
		b = tmp;
	}

	long long int amari = a % b;

	if (amari == 0)return b;

	return gcd(b, amari);
}

long long int lcm(long long int a, long long int b) {
	long long int ans = (a * b) % MOD;
	long long int wari = modpow(gcd(a, b), MOD - 2);
	ans = (ans * wari) % MOD;
	return ans;
}

long long int factElement[10000] = { 0 };

long long int factrial(int n) {

	if (factElement[n] != 0)return factElement[n];

	if (n == 0) {
		factElement[0] = 1;
		return factElement[n];
	}

	long long int ans = n * factrial(n - 1);
	factElement[n] = ans;
	return factElement[n];

}

struct SegmentTree {
private:
	int n;
	vector<long long int> node;
	int TANNI;

	long long int Func(long long int a, long long int b) {
		return min(a,b);
	}

public:
	//元配列ｖをセグメント木で表現する。
	SegmentTree(vector<long long int> v, long long int tanni) {
		//最下段のノード数は元配列のサイズ以上になる最小の2冪→これをｎとおく。
		//セグメント木全体で必要なノード数は2n-1個である。
		int sz = v.size();
		n = 1;
		while (n < sz)n *= 2;

		TANNI = tanni;
		node.resize(2 * n - 1, TANNI);

//最下段に値を入れた後に、下の段から順番に値を入れる。
//値を入れるには、自分の子の２値を参照すればよい。
for (int i = 0; i < sz; i++)node[i + n - 1] = v[i];
for (int i = n - 2; i >= 0; i--)node[i] = Func(node[2 * i + 1], node[2 * i + 2]);
	}

	void update(long long int x, long long int val) {
		//最下段のノードにアクセスする。
		x += (n - 1);

		//最下段のノードを更新したら、あとは親に上って更新していく。
		node[x] = val;

		while (x > 0) {
			x = (x - 1) / 2;
			node[x] = Func(node[2 * x + 1], node[2 * x + 2]);
		}
	}

	long long int getVal(int x) {
		x += (n - 1);
		return node[x];
	}

	long long int getAns(int a, int b, int k = 0, int l = 0, int r = -1) {
		//最初に呼び出された時の区間は[0,n)
		if (r < 0)r = n;

		//要求区間と対象区間が交わらない→単位元を返す。
		if (r <= a || b <= l) return TANNI;

		//要求区間が対象区間を完全に被覆する→対象区間を答えの計算に使う。
		if (a <= l && r <= b) return node[k];

		//要求区間が対象区間の一部を被覆→子をよびだす。
		//左の子をvl、右の子をvrとしている。
		//新しい対象区間は現在の対象区間を半分に割ったもの。
		int vl = getAns(a, b, 2 * k + 1, l, (l + r) / 2);
		int vr = getAns(a, b, 2 * k + 2, (l + r) / 2, r);
		return Func(vl, vr);


	}



};



int main()
{
	long long int x;
	cin >> x;

	long long int a, b;

	long long int range = 1000;
	long long int minrange = -1000;

	bool flg = false;
	for (long long int i = minrange; i < range; i++) {
		for (long long int j = minrange; j < range; j++) {
			if (pow(i, 5) - pow(j, 5) == x) {
				a = i;
				b = j;
				flg = true;
				break;

			}




		}

		if (flg)break;
	}

	cout << a << " " << b << endl;




	return 0;

}



Measured memory_bytes: 4068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<60;

int main() {
    int K,N;
    cin>>K>>N;
    if(K%2==0) {
        cout<<K/2;
        for(int i=1;i<N;i++) cout<<" "<<K;
        cout<<endl;
    }else {
        vector<int> v(N, (K + 1) / 2);
        for (int i = 0; i < N / 2; i++) {
            if (v.back() == 1) {
                v.pop_back();
            } else {
                v.back()--;
                int cnt=N-v.size();
                for (int j = 0; j < cnt; j++) v.push_back(K);
            }
        }
        for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
        cout<<endl;
    }
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,a,b) for(int i=(int)(a-1);i>=b;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define INF INT_MAX/3

int main(){
    cin.sync_with_stdio(false);
    int n;
    cin >> n;
    cout << ((n % 10 == 9 || n / 10 == 9) ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define per(i,n,j) for(int i=(n);i>=(j);i--)
using ll=long long;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF=1LL<<60;

int n;

int main(){
    cin>>n;
    vector<int> a(n),ans(1);
    rep(i,0,n) cin>>a[i];
    if(n%2==0){
        ans[0]=a[0];
        rep(i,1,n){
            if(i%2!=0) ans.insert(ans.begin(),a[i]);
            else ans.insert(ans.end(),a[i]);
        }
    }
    else{
        ans[0]=a[0];
        rep(i,1,n){
            if(i%2!=0) ans.insert(ans.end(),a[i]);
            else ans.insert(ans.begin(),a[i]);
        }
    }
    rep(i,0,n) cout<<ans[i]<<" ";
    return 0;
}


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

int main() {
  int N, K;
  vector<int> h(N);
  cin >> N >> K;
  int a = 0;
  for (int i = 0; i < N; i++) {
    cin >> h.at(i);
    if (h.at(i) >= K) {
      ++a;
    }
  }
  cout << a << endl;
}


Measured memory_bytes: 16640
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int n[]={0,1,2,1,3,1,3,1,1,3,1,3,1};
main(){
	int a,b,c;
	cin>>a>>b;
	if(a>b)swap(a,b);
	if(n[a]==n[b])cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

Measured memory_bytes: 384
#include <stdio.h>

int main(void){
  int x,a,b;
  scanf("%d %d %d",&x,&a,&b);
  if (b-a<=0){
    printf("delicious\n");
  }
  else if (b-a<x+1){
    printf("safe\n");
  }
  else{
    printf("dangerous\n");
  }
  return 0;
}


Measured memory_bytes: 128
//verma_ankit484

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define pb push_back
const ll mod = (ll) 1e9+7;

using namespace std;
//using namespace __gnu_pbds;

//#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>

//0 based LCA
ll n, l;
vector<vector<pair<ll, ll>>> adj;
set<ll> st[20];

ll timer;
vector<ll> tin, tout;
vector<vector<ll>> up;

void dfs(ll v, ll p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (ll i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for (auto u : adj[v]) {
        if (u.first != p)
            dfs(u.first, v);
    }

    tout[v] = ++timer;
}

bool is_ancestor(ll u, ll v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

ll lca(ll u, ll v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (ll i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

void preprocess(ll root) {
    tin.resize(n);
    tout.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n, vector<ll>(l + 1));
    dfs(root, root);
}

ll r;

bool dfs2(ll s, ll p, ll a, ll b, ll q) {
  bool chk = false;
  bool foo = false;
  if (((s == a or s == b) and (s != r)) or (s == a and s == b)) return true;
  for (auto i : adj[s]) {
    if (i.first == p) continue;
    chk = dfs2(i.first, s, a, b, q);
    if (chk) {
      foo = true;
      st[q].insert(i.second);
      // return true;
    }
  }
  return foo;
}
vector<vector<ll>> info;

void dfs3(ll s, ll p) {
  for (auto i : adj[s]) {
    if (i.first == p) continue;
    for (ll k = 0; k < 20; k++) {
      if (st[k].find(i.second) != st[k].end()) {
        info[i.second].pb(k);
      }
    }
    dfs3(i.first, s);
  }
}

ll dp[50][1ll << 20];

ll N;

ll rec(ll idx, ll mask) {
  if (idx == N) {
    if (mask == 0) return 1;
    else return 0;
  }
  ll &ans = dp[idx][mask];
  if (ans != -1) return ans;
  ans = 0;
  ans = rec(idx+1, mask);
  ll newmask = mask;
  for (ll i = 0; i < (ll) info[idx].size(); i++) {
    newmask &= ~(1 << info[idx][i]);
  }
  ans += rec(idx+1, newmask);
  return ans;
}

int main() {
  IOS
  #ifdef AV
  freopen("input.txt", "r", stdin);
  #endif
  cin >> n;
  adj.resize(n);
  info.resize(n);
  ll root;
  N = n-1;
  for (ll i = 0; i < n-1; i++) {
    ll a, b;
    cin >> a >> b;
    adj[a-1].pb({b-1, i});
    adj[b-1].pb({a-1, i});
  }
  for (ll i = 0; i < n; i++) {
    if (adj[i].size() == 1) root = i;
  }
  preprocess(root);
  ll q;
  cin >> q;
  vector<pair<ll, ll>> queries(q);
  for (ll i = 0; i < q; i++) {
    cin >> queries[i].first >> queries[i].second;
    queries[i].first--, queries[i].second--;
  }
  for (ll i = 0; i < q; i++) {
    ll llccaa = lca(queries[i].first, queries[i].second);
    r = llccaa;
    dfs2(llccaa, -1, queries[i].first, queries[i].second, i);
  }
  dfs3(root, -1);
  memset(dp, -1, sizeof(dp));
  cout << rec(0, ((1 << q)-1)) << endl;
  return 0;
}


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

int main() {
  int k, a, b; cin >> k >> a >> b;
  string ans = "NG";
  for (int i = a; i<=b;i++) {
    if (i%k==0) {
      ans = "OK";
      break;
    }
  }
  cout << ans << endl;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod = int(1e9)+7;
using V = vector<ll>;
using P = pair<ll,ll>;

int main()
{
   ll n,y;cin >>n >>y;
   rep(a,n+1)rep(b,n+1){
    if(a+b>n)continue;
   int  c=n-a-b;
    if(y==10000*a+5000*b+1000*c){
        cout <<a<< " "<<b<<" "<<c<< endl;
        return 0;
    }
   }
   cout <<-1<< " "<<-1<< " "<<-1<< endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vd=vector<double>;
using vvd=vector<vd>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using vs=vector<string>;
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.141592653589793

template<class S,class T>ostream& operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	int n;
	cin>>n;
	
	vl a(n),b(n);
	rep(i,n)cin>>a[i];
	sort(all(a));
	b=a;
	partial_sum(all(a),b.begin());

    int ans=n;
    rep(i,n-1){
        if(b[i]*2<a[i+1]){
            ans=n-i-1;
        }
    }
    cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include <cmath>
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <numeric>
#include <map>   
#include <stdio.h>

#define FOR(i,a,b) for(i=(a);i<(b);++i) 
#define FORR(i,a,b) for(i=(a);i>(b);--i)
#define REP(i,n) for(i=0;i<(n);++i)
#define REPR(i,n) for(i=(n);i>0;--i)
#define PB push_back
#define ull unsigned long long
#define ll long long
#define INT_MAX 2147483647
#define LL_MAX 9223372036854775807
#define sortR(a,b) sort(a, b, greater<int>())

using namespace std;

int main() {
	int N, K, i, one_saisyo, one_saigo, zero_saisyo, zero_saigo, before;
	string S;
	vector<pair<int, int>> zero, one;
	cin >> N>>K>>S;
	before = S[0]-'0';
	if (S[0] == '0')
		zero_saisyo = 0;
	else
		one_saisyo = 0;
	REP(i, N) {
		if (before != (S[i] - '0'))//0と1の境
			if (before == 1) {//1の連続について
				one.push_back(make_pair(one_saisyo, i - 1));
				zero_saisyo = i;
			}
			else { //0の連続について
				zero.push_back(make_pair(zero_saisyo, i - 1));
				one_saisyo = i;
			}
		else //0または1が連続している
			;
		before = S[i] - '0';
	}
	if(S[i-1]=='1')
		one.push_back(make_pair(one_saisyo, i - 1));
	else
		zero.push_back(make_pair(zero_saisyo, i - 1));
	if (zero.size() <= K) {//全部帰られる時
		cout << N << endl;
		return 0;
	}
	int MAX = 0;

	if (S[0] == '1' && S[N - 1] == '1') {
		REP(i, zero.size() - K + 1) {
			MAX = max(MAX, one[i + K].second - one[i].first + 1);
		}
	}
	else if (S[0] == '1' && S[N - 1] == '0') {
		for (i = 0; i < zero.size() - K; i++) {
			MAX = max(MAX, one[i + K].second - one[i].first + 1);
		}
		MAX = max(MAX, zero[zero.size() - 1].second - one[i].first + 1);
	}
	else if (S[0] == '0' && S[N - 1] == '1') {
		MAX = max(MAX, one[K-1].second - zero[0].first + 1);
		for (i = 1; i < zero.size() - K; i++) {
			MAX = max(MAX, one[i + K].second - one[i].first + 1);
		}
	}
	else if (S[0] == '0' && S[N - 1] == '0') {
		MAX = max(MAX, one[K-1].second - zero[0].first + 1);
		for (i = 1; i < zero.size() - K; i++) {
			MAX = max(MAX, one[i + K-1].second - one[i-1].first + 1);
		}
		MAX = max(MAX, zero[zero.size() - 1].second - one[i-1].first + 1);
	}
	cout << MAX << endl;
	return 0;
}



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

int main() {
    size_t n;
    std::cin >> n;
    std::vector<int> a(n);
    for (size_t i = 0; i < n; ++i) std::cin >> a[i];
    size_t m;
    std::cin >> m;
    std::vector<int> b(m);
    for (size_t i = 0; i < m; ++i) std::cin >> b[i];
    std::vector<int> c;
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
    for (int x : c) std::cout << x << std::endl;
}



Measured memory_bytes: 5452
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

vector<int> z_algorithm(string s) {
	vector<int> res(s.size());
	
	res[0] = s.size();
	
	int i = 1, j = 0;
	
	while (i < s.size()) {
		while (i + j < s.size() && s[j] == s[i + j]) j++;
		res[i] = j;
		if (j == 0) { i++; continue; }
		int k = 1;
		while (i + k < s.size() && k + res[k] < j) res[i + k] = res[k], k++;
		i += k;
		j -= k;
	}
	
	return res;
}

vector<int> g[1123456];
int indeg[1123456];
int dp[1123456];

int main() {
	string S, T;
	cin >> S >> T;
	
	while (T.size() > S.size()) S += S;
	
	string str = T + S + S;
	vector<int> v = z_algorithm(str);

	FOR(i, T.size(), T.size() + S.size()) {
		if (v[i] >= T.size()) {
			g[i - T.size()].emplace_back(i % S.size());
			++indeg[i % S.size()];
		}
	}
	
	queue<int> que;
	REP(i, S.size()) if (indeg[i] == 0) que.push(i);
	
	int ans = 0;
	while (!que.empty()) {
		int u = que.front();
		que.pop();
		chmax(ans, dp[u]);
		
		for (int v : g[u]) {
			chmax(dp[v], dp[u] + 1);
			if (--indeg[v] == 0) que.push(v);
		}
	}
	
	REP(i, S.size()) if (indeg[i]) ans = -1;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 76244
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int f(int x) {
  int s = 0;

  while (x) {
    s += x % 10;
    x /= 10;
  }

  return s;
}

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

  int n; cin >> n;

  if (n % f(n) == 0) cout << "Yes" << "\n";
  else cout << "No" << "\n";
}


Measured memory_bytes: 3616
l=int(input())
c=list(map(int,input().split()))
ans='OK'
cat=[]
for i in range(l):
    if c[i]>0:
        if c[i] in cat:
            ans=i+1
            break
        else:
            cat.append(c[i])
    else:
        if len(cat)==0:
            ans=i+1
            break
        elif abs(c[i])!=cat[-1]:
            ans=i+1
            break
        else:
            cat.pop(-1)
print(ans)


Measured memory_bytes: 5616
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long 
const int MAX = 510000;
const ll mod = 1000000007;
int main() {
  int n;
  cin >> n;
  int ta,tb;
  int flg = 0;
  string res = "No";
  for(int i = 0;i<n;i++){
    cin >> ta >> tb;
    if(ta == tb){
      flg++;
    }else{
      flg = 0;
    }
    
    if(flg >= 3){
      res = "Yes";
      break;
    }
  }
  cout << res;
}


Measured memory_bytes: 3620
#include <iostream>

using namespace std;

int main() {
  while (true) {
    int a, b;
    char op;

    cin >> a >> op >> b;

    if (op == '?') {
      break;
    } else if (op == '+') {
      cout << a + b << endl;
    } else if (op == '-') {
      cout << a - b << endl;
    } else if (op == '*') {
      cout << a * b << endl;
    } else if (op == '/') {
      cout << a / b << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 1164
#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    int a, b, c;
    cin >> a >> b >> c;
    cout << max(a * 10 + b + c, max(b * 10 + a + c, c * 10 + a + b));
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
  {
    
     int n;
     cin>>n;
     if(n%1000==0)
     cout<<0<<endl;
     else
     {
       int  r = n/1000;
       cout<<((r+1)*1000)-n<<endl;
     }
  }

Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

signed main() {
	int N, K;
	cin >> N >> K;
	N %= K;
	
	cout << min(N, abs(N - K)) << endl;
	return 0;
}

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

using Int = unsigned long long;
using namespace std;

#define ARC(i, a, b) for(Int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(Int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)
template<class T> T ant(const T &a, const T &b){ return a > b ? a : b; };
template<class T> T ont(const T &a, const T &b){ return a < b ? a : b; };
template<class T> T th(T &a, const T &b, T (*f)(const T &, const T &)){ a = f(a, b); }
#define anth(a, b) th(a, b, ant)
#define onth(a, b) th(a, b, ont)

constexpr Int MOD = 1000000007;

Int n, k;
Int a[2123];
Int b[2123];
Int ans;

int main(){
	cin >> n >> k;
	RC(i, n){
		cin >> a[i];
		++b[a[i]];
	}

	RC(i, n) RC(j, i){
		if(a[j] > a[i]) ++ans;
	}

	ans %= MOD;
	ans *= k;
	ans %= MOD;

	Int tmp = 0, sum = 0;
	RC(i, 2019){
		sum += b[i] * tmp;
		sum %= MOD;
		tmp += b[i];
	}

	k = k * (k - 1) / 2 % MOD;
	ans += sum * k;

	cout << ans % MOD << endl;
}


Measured memory_bytes: 256
from collections import defaultdict
from functools import reduce

n, k = map(int, input().split())

MOD = 10 ** 9 + 7

def mul(a, b):
  return a * b % MOD

def power(x, y):
  res = 1
  while True:
    if y & 1:
      res = res * x % MOD
    if y == 1:
      return res
    x = x * x % MOD
    y >>= 1

def div(a, b):
  return a * power(b, MOD - 2) % MOD

def dict1():
  return {0: 1}

numer_cache = defaultdict(dict1)
denom_inv_cache = dict1()

def combinations_count(n, r):
  r = min(r, n - r)
  numer_cache_n = numer_cache[n]
  if r not in numer_cache_n:
    numer_cache_n[r] = mul(numer_cache_n[r - 1], n - r + 1)
  if r not in denom_inv_cache:
    denom_inv_cache[r] = div(denom_inv_cache[r - 1], r)
  return mul(numer_cache_n[r], denom_inv_cache[r])

print(sum(mul(combinations_count(n, i), combinations_count(n - 1, i)) for i in range(min(n, k + 1))) % MOD)


Measured memory_bytes: 36296
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <functional>
#include <cstring>
#include <array>
#include <vector>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#include <complex>
#include <bitset>
#define full(c) c.begin(), c.end()
#define vector2d(name,type,h,w,init) vector<vector<type>> name(h,vector<type>(w,init)) 
const int PRIME = 1000000007;
const int INF = (int) 1e9;
const int INT_INF = 2147483647;
const long long int LL_INF = 9223372036854775807;
const double PI = acos(-1);
const double EPS = 0.00001;
typedef unsigned long long int ull;
typedef long long int ll;
using namespace std;

int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);
	int h, w;
	cin >> h >> w;
	vector2d(grid, char, h, w, 0);
	vector2d(dp, ll, h, w, 0);
	for (int k = 0; k < h; k++) {
		string s;
		cin >> s;
		for (int i = 0; i < w; i++) grid[k][i] = s[i];
	}
	for (int i = 0; i < h; i++) {
		if (grid[i][0] == '#') break;
		else dp[i][0] = 1;
	}
	for (int i = 0; i < w; i++) {
		if (grid[0][i] == '#') break;
		else dp[0][i] = 1;
	}
	for (int i = 1; i < h; i++) {
		for (int j = 1; j < w; j++) {
			if (grid[i][j] == '#') dp[i][j] = 0;
			else dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % PRIME;
		}
	}
	cout << dp[h - 1][w - 1] << endl;
	return 0;
}


Measured memory_bytes: 9088
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long N, A[1<<18], B[1<<18], S, cnt;
vector<int> X[1<<18];
bool used[1<<18];

void dfs(int pos) {
  used[pos] = true;
  for(int i = 0; i < X[pos].size(); i++) {
    if(used[X[pos][i]] == true) continue;
    dfs(X[pos][i]);
  }
  B[pos] = A[cnt];
  cnt++;
}

int main() {
  cin >> N;
  for(int i = 1; i <= N-1; i++) {
    int p, q; cin >> p >> q;
    X[p].push_back(q);
    X[q].push_back(p);
  }

  for(int i = 0; i < N; i++) cin >> A[i];
  sort(A, A+N);
  for(int i = 0; i < N-1; i++) S += A[i];

  dfs(1);

  cout << S << endl;
  for(int i = 1; i <= N; i++) {
    cout << B[i];
    if(i == N) cout << endl;
    else cout << " ";
  }
  return 0;
}


Measured memory_bytes: 11008
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int a,b,c,d;
int main()
	{
		cin>>a>>b>>c>>d;
	 	if((abs(a-b)-d<=0&&abs(b-c)-d<=0)||abs(a-c)-d<=0) cout<<"Yes"<<endl;
	 	else cout<<"No"<<endl;
	 	return 0;
	 }
	  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define dump1d_arr(array,i) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array,i,j) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define loINF (long)10000000000
#define shINF (short)10000
#define SORT(c) sort((c).begin(),(c).end())

using namespace std;
typedef vector<short> VI;
typedef vector<VI> VVI;
typedef map<short,VI> mp;

VI ver_oreder; //辺の通った順番 ==> 辺の値
VVI vertex;	// 辺の lowと番号を持ってる。
mp edge;

void update_low(short low,short i){ // low:更新する値 i:通った順番
	#ifdef DEBUG
		cout << "update_low_run" << endl;
		dump(low);
		dump(i);
	#endif

	if (low != i){
		vertex[i][1] = min({low,vertex[i][1]});
		update_low(low,vertex[i][0]-1);
	}
}

void dfs(short i,short j){ // i:頂点の番号 j:頂点の番号(一個前)
	#ifdef DEBUG
		dump(i);
		dump(j);
	#endif

	if (vertex[i][0] == shINF) {
		vertex[i][0] = vertex[j][0] + 1;
		vertex[i][1] = vertex[j][0] + 1;
		ver_oreder[vertex[i][0]] = i;

		REP(k,edge[i].size()){
			if (edge[i][k] != j) dfs(edge[i][k],i);
		}
 		return;
	}

	else {
		if (vertex[i][1] == vertex[j][1]) return;
		vertex[j][1] = min({vertex[i][1],vertex[j][1]});
		short low = vertex[i][1];
		for(int k = vertex[j][0] - 1;k > low;k--){
			vertex[ver_oreder[k]][1] = min({low,vertex[ver_oreder[k]][1]}); 
		}
	}
}


int main (void){
	short N,M;
	long ans = 0;
	cin >> N >> M;
	vertex = VVI(N+1,VI(2,shINF)); //配列[0]が何番目をみているか、配列[1]が最小の到達元。(初期値は配列[0])
	ver_oreder = VI(N+1,0);
	vertex[0][0] = 0;
	vertex[0][1] = 0;

	REP(i,M) {
		short a,b;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	#ifdef DEBUG
	cout << "INPUT CHECK" << endl;
		REP(i,N+1) REP(j,2) dump2d_arr(vertex,i,j);
		REP(i,N+1) REP(j,edge[i].size()) dump2d_arr(edge,i,j);
	#endif

	dfs(1,0);

	#ifdef DEBUG
	cout << "dfs CHECK" << endl;
		REP(i,N+1) REP(j,2) dump2d_arr(vertex,i,j);
		REP(i,N+1) dump1d_arr(ver_oreder,i);
	#endif

	FOR(i,2,N+1){
		if (vertex[i][0] == vertex[i][1]) ans++;
	}
	cout << ans << endl;
	return 0;

}


Measured memory_bytes: 256