akhauriyash/Code-Regression huggingface dataset:
import math

n,m,s = map(int,input().split())

road = []
for i in range(m):
    u,v,a,b = map(int,input().split())
    road.append([u,v,a,b])

change = []
for i in range(n):
    c,d = map(int,input().split())
    change.append([c,d])

tree = [[] for _ in range(n+1)]

for i in range(m):  
    r = road[i]
    tree[r[0]].append([r[0],r[1],r[2],r[3]])
    tree[r[1]].append([r[1],r[0],r[2],r[3]])

least_cost = [[] for _ in range(n+1)]
for l in range(n+1):
    least_cost[l] = [math.inf]*2501


def insort_queue(q,v):
    len_a = len(q)    
    if len_a == 0:
        q.append(v)
        return
    
    min = 0
    max_1 = len_a

    if max_1 == 1:
        if v[2] > q[0][2]:
            min = 1
        else:
            min = 0
    while max_1 - min > 1:
        mid = (max_1 + min) //2
        if v[2] > q[mid][2]:
            min = mid
        else:
            max_1 = mid
    index = max_1
    q.insert(index,v)

queue = []

#hwd [location, money, time]
def dijakstra(q):
    while q != []:
        hwd = q.pop(0)

        if least_cost[hwd[0]][hwd[1]] > hwd[2]:
            least_cost[hwd[0]][hwd[1]] = hwd[2]
            
            for node in tree[hwd[0]]:
                # from node, to node , money, time
                if hwd[1] - node[2] >= 0:
                    insort_queue(q,[node[1],hwd[1]-node[2],hwd[2]+node[3]])
            if hwd[1] + change[hwd[0]-1][0] <= 500:
                insort_queue(q,[hwd[0],hwd[1]+change[hwd[0]-1][0],hwd[2]+change[hwd[0]-1][1]])
    return least_cost

if s > 2500:
    s = 2500
queue.append([1,s,0])

ans = dijakstra(queue)

for i in range(2,n+1):
    print(min(ans[i]))

Measured memory_bytes: 19060
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
    for (int i = 1 ; i <= 9 ; i++)
    {
        for (int g = 1 ; g <= 9 ; g++)
        {
            printf("%dx%d=%d\n",i,g,i*g);
        }
    }
}

Measured memory_bytes: 1096
// 何これ
// ほんとにわかりません

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0;
    string str;
    ll x,k;
    cin>>x>>k>>d;
    x=abs(x);
    if((double)x/d<k) {
        k-=x/d;
        ll ans = x%d;
        if(k%2==0){
            cout<<ans<<endl;
        }else{
            cout<<abs(ans-d)<<endl;
        }
    }
    else{
        cout<<abs(x-k*d)<<endl;
    }
    

    return 0;
}


Measured memory_bytes: 3560
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>   //PBDS
#include <ext/pb_ds/tree_policy.hpp>       //PBDS
#define int long long int
#define vi vector<int>
#define vii vector<pair<int,int>>
#define pi pair<int,int>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define mi map<int,int>
#define PI   3.141592653589
#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define f(i,x,n) for(int i=x;i<n;i++)
#define rf(i,x,n) for(int i=n-1;i>=x;i--)
#define check(x)   cerr<<#x<<" : "<<x<<endl;
#define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define fbo find_by_order                    //return iterator PBDS
#define ook order_of_key                     //return number :)) PBDS
#define baar exit(0)
#define INF 1000000000000000000
using namespace __gnu_pbds;
using namespace std;
int powmod(int base,int exponent,int mod)
{
	int ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
signed main()
{
	fast
	int n,k;
	cin>>n>>k;
	vi dp(n+1),v(n+1);
	f(i,1,n+1)
	{
		cin>>v[i];
		if(i==1) continue;
		int j=k,ans=LLONG_MAX;
		f(j,1,min(i,k+1))
		{
		   	ans=min(ans,abs(v[i]-v[i-j])+dp[i-j]);
		}
		dp[i]=ans;
	}
	cout<<dp[n];
	return 0;
}

Measured memory_bytes: 4760
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=1000000009;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-11;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 11100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	inline long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
int p[210000];
int main(){
	int a;scanf("%d",&a);
	long long ret=0;
	for(int i=0;i<a;i++){
		int t;scanf("%d",&t);
		p[t]++;
		ret+=t;
	}
	int b;scanf("%d",&b);
	for(int i=0;i<b;i++){
		int s,t;scanf("%d%d",&s,&t);
		ret-=(long long)p[s]*s;
		ret+=(long long)p[s]*t;
		p[t]+=p[s];
		p[s]=0;
		printf("%lld\n",ret);
	}
}

Measured memory_bytes: 2116
#include <iostream>
using namespace std;
int N, M, C;
int B[20];
int ans = 0;



int main(void) {
    // insert code here...
    cin >> N >> M >> C;
    for(int i = 0; i < M; i++){
        cin >> B[i];
    }
    
    for(int i = 0; i < N; i++){
        int total = 0;
        for(int j = 0; j < M; j++){
            int A;
            cin >> A;
            total += A*B[j];
        }
        total += C;
        if(total > 0){
            ans++;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)
#define INF 1000000000

int main()
{
	int n;
	while (cin >> n, n) {
		vector<int> a;
		REP(i, 0, n) {
			int in;
			cin >> in;
			a.push_back(in);
		}

		sort(a.begin(), a.end());
		int ans = INF;
		REP(i, 0, a.size() - 1) {
			ans = min(ans, a[i + 1] - a[i]);
		}

		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3132
// ATcoder
// Problem Statement
// Given is a three-digit integer 
// N
// . Does 
// N
//  contain the digit 
// 7
// ?

// If so, print Yes; otherwise, print No.

// Input
// Input is given from Standard Input in the following format:

// N

// Output
// If 
// N
//  contains the digit 
// 7
// , print Yes; otherwise, print No.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int flag=0;
    for(int i=0;i<3;i++){
        int x=n%10;
        n=n/10;
        if(x==7) {
            ++flag;
        }
    }
    if(flag>0) cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;

int main() {
  int N; cin>>N;
  vector<int> a(N);
  REP(i,N) {
    cin>>a[i];
  }
  sort(a.begin(), a.end());
  int ans = N-1;
  double dd = 10000000000.0;

  for(int i = 0; i < N-1; i++) {
    double d = abs(a[N-1]/2.0 -	a[i]);
    if(d < dd) {
      ans = i;
      dd = d;
    }
  }
  cout << a[N-1] << " "	<< a[ans] << endl;
  return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;
class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        if(a>b)System.out.println("a > b");
        else if(a<b)System.out.println("a < b");
        else System.out.println("a == b");
    }
}



Measured memory_bytes: 26156
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma comment(linker, "/STACK:268435456")
#pragma warning( disable : 6031)
#pragma warning( disable : 4244)
#pragma warning( disable : 26451)
#ifndef _MSC_VER
#pragma GCC target ("sse4.2")
#endif
#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#  define __builtin_popcountll __popcnt64
#endif
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdint>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <numeric>
#include <algorithm>
#include <random>
#include <utility>
#include <bitset>
#include <cmath>
#include <sstream>
#include <functional>
#include <iomanip>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <chrono>

#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define eps (1e-15)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<double> vd;
typedef vector< vd > vvd;
typedef vector< string > vs;
typedef pair< int, int > pii;
typedef pair<ll, ll> pll;
typedef vector< pii > vpii;
typedef vector< pll > vpll;
typedef vector<ll> vl;
typedef vector<vector<long long>> vvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef tuple<int, int, int> tiii;
const long long mod = int(1e9) + 7;
const int INF = 1e9;
const ll LINF = 1e18;


int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << setprecision(18) << fixed;
#ifdef LOCAL_MACHINE
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
#endif
	int n, m, x;
	cin >> n >> m >> x;
	vvi a(n, vi(m + 1));
	for (auto& v : a)
		for (auto& x : v)
			cin >> x;
	int res = INT_MAX;
	for (int mask = 0; mask < (1 << n); mask++)
	{
		vi cur(m);
		int sum = 0;
		for (int i = 0; i < n; i++)
		{
			if (mask & (1 << i))
			{
				for (int j = 0; j < m; j++)
					cur[j] += a[i][j + 1];
				sum += a[i][0];
			}
		}
		bool ok = true;
		for (int i = 0; i < m; i++)
			if (cur[i] < x)
				ok = false;
		if (ok)
			res = min(res, sum);
	}
	cout << (res == INT_MAX ? -1 : res);
	return 0;
}

Measured memory_bytes: 3664
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)



bool comp(pair<ll, ll> a, pair<ll, ll> b){
    if(a.first != b.first){
        return a.first < b.first;
    }
    else{
        return a.second > b.second;
    }
}


int main() {
    ll n, m;
    cin >> n >> m;
    
    vector<pair<ll, ll>> v(m);
    REP(i, m){
        ll a, b;
        cin >> a >> b;
        
        v[i] = {a, b};
    }
    
    sort(v.begin(), v.end(), comp);
    
    ll ans = 1, mx = INF;
    REP(i, m){
        if(mx <= v[i].first){
            ans++;
            mx = v[i].second;
        }
        else{
            mx = min(mx, v[i].second);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
N, D = gets.split.map(&:to_i)
ds = [-1] + gets.split.map(&:to_i)
pos = [D]
(1..N).each do |i|
    d1 = pos[i-1]
    d2 = (d1-ds[i]).abs
    pos[i] = d1 < d2 ? d1 : d2
end
max = Array.new(N+1)
max[N] = 0
N.downto(1) do |i|
    if ds[i] <= 2*max[i] + 1
        max[i-1] = max[i] + ds[i]
    else
        max[i-1] = max[i]
    end
end

Q = gets.to_i
qs = gets.split.map(&:to_i)
qs.each do |q|
    if pos[q-1] > max[q]
        puts 'YES'
    else
        puts 'NO'
    end
end



Measured memory_bytes: 74500
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 9999999999999
signed main(){
	int l,r;
	cin>>l>>r;
	if(abs(r-l)>2020){
		cout<<"0";return 0;
	}
	l%=2019;r%=2019;
	if(l>r) swap(l,r);
	int ans=inf;
	for(int i=l;i<=r;i++){
		for(int j=i+1;j<=r;j++){
			ans=min(ans,(i*j)%2019);
		}
	}
	cout<<ans;
	return 0;
}

/*
54
55
*/

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

int ara[111111];

int main()
{
    int n,k,q,i,j,l;
    cin>>n>>k>>q;
    for (i=1; i<=n; i++)
    {
        ara[i]=k;
    }
    for (i=1; i<=q; i++)
    {
        cin>>l;
        ara[l]++;
    }
    for (i=1; i<=n; i++)
    {
        ara[i]=ara[i]-q;
    }

    for (i=1; i<=n; i++)
    {
        if (ara[i]<=0)
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }

    return 0;
}



Measured memory_bytes: 1024
#include <stdio.h>
typedef long long ll;

ll gcd(ll a, ll b) {
  ll t;
  while(b) {
    t = a % b, a = b, b = t;
  }
  return a;
}

int main(void) {
  ll n, i, t, ans = 1;
  scanf("%lld", &n);
  for(i = 0; i < n; ++i) {
    scanf("%lld", &t);
    ans = ans / gcd(ans, t) * t;;
  }
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int LL;
typedef LL ll;
typedef string str;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef stringstream strs;
 
#define X first
#define Y second
#define PB push_back
#define For(i,a,b) for (int i=a;i<b;i++)
#define Ford(i,a,b) for (int i=a;i>=b;i--)
#define smax(a,b) a=max(a,b)
#define smin(a,b) a=min(a,b)
#define SZ(a) ((ll)a.size())
#define ER(a) cout << #a << ' ' << a << endl
#define LB(a,n,x) (lower_bound(a,(a)+(n),x)-(a))
#define RET(x) { cout << x; exit(0); } 
const ll M=1e2+5,LG=19,SM=4000+5,inf=1e18+1;
ll mod=1e9+7;

str s;

int main()
{
	ios::sync_with_stdio(0);
    cin >> s;
    ll res=SZ(s);
    ll st=0;
    for (char c:s)
    {
        if (c=='S') st++;
        else if (st!=0)
        {
            st--;
            res-=2;
        }
    }
    RET(res);   
}

Measured memory_bytes: 720
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
using P = std::pair<ll, int>;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD =  924844033ll;

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll dp[5050][5050][2];
bool done[5050][2];

int main(void){
	int m=0,i,j,n,k,t,p,q;
	bool flag;
	ll ans = 0ll,tmp=1ll,fc=1ll;
	dp[0][0][0] = 1ll;
	std::cin >> n >> t;
	for(i=0; i<n; ++i){
		for(j=0; j<2; ++j){
			if(done[i][j]){
				continue;
			}
			p = i; q = j; flag = true;
			while(true){
				p += t; q = (!q);
				if(p>=n){
					break;
				}
				done[p][q] = true;
				for(k=0; k<=n; ++k){
					add_mod(dp[m+1][k][0],dp[m][k][0]);
					add_mod(dp[m+1][k][0],dp[m][k][1]);
					add_mod(dp[m+1][k+1][1],dp[m][k][0]);
					if(flag){
						add_mod(dp[m+1][k+1][1],dp[m][k][1]);
					}
				}
				flag = false;
				++m;
			}
		}
	}
	for(i=0; i<=n; ++i){
		if(i){
			mul_mod(fc,i);
		}
		tmp = fc;
		mul_mod(tmp,(dp[m][n-i][0]+dp[m][n-i][1])%MOD);
		add_mod(ans,((n-i)%2)?(MOD-tmp):tmp);
	}
	std::cout << ans << std::endl;
	return 0;
}


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

/*
int main() {
    string S, T;
    int AC=0;
    std::cin >> S >> T;
    for(int i=0; i<3; i++){
        if(S[i]==T[i]){
            AC++;
        }
    }
    std::cout << AC << std::endl;
    return 0;
}
 */

/*
int main(){
    int A,B;
    int hole=1;
    int tap=0;
    std::cin >> A >> B;
    while(hole<B){
        hole+=A-1;
        tap++;
    }
    std::cout << tap << std::endl;
    return 0;
}
 */

int main(){
    int N;
    std::cin >> N;
    int a[N];
    int max=0;
    for(int i=0; i<N; i++){
        std::cin >> a[i];
    }
    for(int i=0; i<N-1; i++){
        if(a[i]>=a[i+1]){
            a[i]=1;
        }
        else{
            a[i]=0;
        }
    }
    a[N-1]=0;
    for(int i=0; i<N; i++){
        if(a[i]==1){
            int max_tmp=0;
            while(a[i]==1){
                max_tmp++;
                i++;
            }
            if(max_tmp>max){
                max=max_tmp;
            }
        }
    }
    std::cout << max << std::endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

const long INF = LLONG_MAX / 3;

vector<int> G[100005];
int deg[100005];

int main(){
  int n, m;
  cin>>n>>m;
  fill(deg, deg+n, 0);
  rep(i,m){
    int a,b;
    cin>>a>>b;
    a--;b--;
    G[a].pb(b);
    deg[b]++;
  }

  queue<int> que;
  rep(i,n) if(deg[i]==0) que.push(i);

  vector<int> d(n,0);

  while(!que.empty()){
    int v = que.front(); que.pop();

    for(auto to : G[v]){
      deg[to]--;
      d[to] = max(d[to], d[v] + 1);
      if(deg[to]== 0) que.push(to);
    }
  }

  cout << *max_element(all(d)) << endl;


  return 0;
}


Measured memory_bytes: 6528
# ??\?????????
N = int(input())
r = [int(input()) for i in range(N)]

# ?????§????¨????
max_profit = (-1) * (10 ** 9)
min_value = r[0]
for j in range(1, len(r)):
    max_profit = max(max_profit, r[j] - min_value)
    min_value = min(min_value, r[j])
print(max_profit)

Measured memory_bytes: 15756
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main(){
    LL N,K;
    cin >> N >> K;
    vector<LL> A(N);
    vector<LL> F(N);


    rep(i,N)cin >> A[i];
    rep(i,N)cin >> F[i];

    sort(all(A));

    sort(rall(F));

    vector<LL> AF(N);
    rep(i,N)AF[i] = A[i]*F[i];

    //解の存在範囲を初期化
    LL lb = 0,ub = INF;

//    rep(i,N)cout << A[i] << "|" << F[i] << " ";
    LL sum = 0;
    rep(i,N)sum += A[i];

    if(sum <= K){
        cout << 0 << endl;

    }
    else{

    //解の存在範囲が1より大きい間、繰り返す
  while (ub-lb > 1){
        LL mid = (lb + ub)/2;
        LL cost = 0;

        rep(i,N)if(AF[i] > mid)cost += (AF[i] - mid + F[i] - 1)/F[i];     // (a[i]-b) / F[i] の切り上げ
        if(cost > K){
            lb = mid;
        }
        else{
            ub = mid;
        }

    }

    cout << ub << endl;
    }

}



Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    char[] D = scanner.next().toCharArray();
    int[] digits = new int[4];
    for (int i = 0; i < 4; i++) digits[i] = D[i] - '0';

    for (int i = -1; i < 2; i += 2) {
      for (int j = -1; j < 2; j += 2) {
        for (int k = -1; k < 2; k += 2) {
          int sum = digits[0] + i * digits[1] + j * digits[2] + k * digits[3];
          if (sum == 7) {
            System.out.printf("%d%c%d%c%d%c%d=7\n", digits[0], i < 0 ? '-' : '+', digits[1], j < 0 ? '-' : '+', digits[2], k < 0 ? '-' : '+', digits[3]);
            return;
          }
        }
      }
    }
  }
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
long long int lcm(long long int a,long long int b){
  long long int n;
  n=a*b/__gcd(a,b);
  return n;
}
using ll =long long int;
#define ci(a) cin>>a
#define co(a) cout<<a<<endl
#define gcd(a,b) __gcd(a,b)
#define vec vector<ll>
#define For(i,a,b) for(int i=a;i<b;i++)
#define rFor(i,a,b) for(int i=a;i>b;i--)
#define sort(a,b) sort(a.begin(),b.end())
//gcd 最大公約数
//lcm 最小公倍数
//double 少数（変数）
//string 文字列（変数）
//sqrt 平方根
//ceil 天井関数
//floor 床関数
//abs 絶対値
//pow 累乗
//cbrt  立方根
//hypot 平方和の平方根
//(string-'0') 文字列を数字に変換
//vector<vector<int>> data(a,vector<b>(b)) a×b行列
//for(int i=0;i<a;i++)
//for(int j=0;j<b;j++)
//cin>>data.at(i).at(j)  a×b行列の入力
//floor(log10(a)+1) aの10進法での桁数
//ceil(log10(a)) aの10進法での桁数

int main() {
  string a,b;
  ci(a>>b);
  string c;
  For(i,0,b.size()){
    c+=a[i];
    c+=b[i];
  }
  if(a.size()>b.size())
    c+=a[b.size()];
  co(c);
}

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

bool binarySearch(int [], int, int);

int main(void)
{
    int i, n, q, k, A[100000];

    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", A + i);
    
    scanf("%d", &q);
    while (q--) {
        scanf("%d", &k);
        printf("%d\n", binarySearch(A, n, k));
    }
    
    return 0;
}

bool binarySearch(int A[], int N, int k)
{
    int low, mid, high;
    low = 0;
    high = N;
    while (low < high) {
        mid = (low + high) / 2;
        if (A[mid] == k)
            return true;
        else if (A[mid] < k)
            low = mid + 1;
        else
            high = mid;
    }
    return false;
}


Measured memory_bytes: 2252
#include<bits/stdc++.h>
 using namespace std;
 typedef long long ll;
 ll dp[100005],inf=(ll)1e18;
 int main(){
    ll n,W,i,j,w,v,sum=0;
    cin>>n>>W;
    for(i=0;i<100005;i++)dp[i]=inf;
    dp[0]=0;
    for(i=0;i<n;i++){
        cin>>w>>v;
        sum+=v;
        for(j=sum;j>=v;j--)
         dp[j]=min(dp[j],w+dp[j-v]);
    }
    for(i=100000;i>=0;i--)
     if(dp[i]<=W){
         cout<<i;
         return 0;
     }
}

Measured memory_bytes: 1024
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = sc.nextInt();
			if(n==0) break;
			
			int[] m = new int[10000];
			int[] t = new int[1];
			int a, b;
			int max = 0;
			for(int i=0;i<n;i++){
				Arrays.fill(m, 0);
				t[0] = 1;
				a = sc.nextInt();
				b = sc.nextInt();
				for(int j=0;j<=a*b;j+=a){
					for(int k=0;k<=max;k++){
						if(t[k]>0) m[j+k] += t[k];
					}
				}
				max += a*b;
				t = m.clone();
			}
			
			int s = sc.nextInt();
			for(int i=0;i<s;i++) System.out.println(m[sc.nextInt()]);
		}	
	}	
}

Measured memory_bytes: 23132
#include <cstdio>
char s[200001];
long long a[26], S = 1;
int main()
{
	scanf("%s", s);
	for (int i = 0; s[i]; i++)
		a[s[i] - 'a']++;
	for (int i = 0; i < 26; i++)
		for (int j = i + 1; j < 26; j++)
			S += a[i] * a[j];
	printf("%lld\n", S);
	return 0;
}


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

def num2alpha(num):
    if num <= 26:
        return chr(96+num)
    elif num%26 == 0:
        return num2alpha(num//26 - 1) + chr(122)
    else:
        return num2alpha(num//26) + chr(96+num%26)

print(num2alpha(N))

Measured memory_bytes: 9176
#include <cstdio>
using namespace std;

int main() {
        int n, k;
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n; i ++) {
                int a;
                scanf("%d", &a);
        }
        printf("%d\n", (n + k - 3) / (k - 1));
        return 0;
}



Measured memory_bytes: 128
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String c = sc.next();

		if(c.equals("a") || c.equals("i")|| c.equals("u")|| c.equals("e")|| c.equals("o"))
			System.out.println("vowel");
		else
			System.out.println("consonant");
	}

}


Measured memory_bytes: 21844
/* kadai3_3
   reo012 */

#include<stdio.h>

int main(void){
  int num, base;
  // 整数numと進法baseを取得
  scanf("%d %d", &num, &base);

  // while文を用いて桁数digits計算。
  int digits = 0;
  while(1){
    num /= base;
    digits++;  // numをdigitsで割れたらdigitsを1足す
    if(num==0){ // 商が0になったらbreak
      break;
    }
  }
  printf("%d\n", digits);
  return 0;
}


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

using namespace std;

int main(){


	int n,k;
  	cin >> n;
    cin >> k;

    int cnt = 0;
    for(int i = 0;i<n;i++){
        int x;
        cin >> x;
        cnt += min(x,k-x);
    }

  	cout << 2*cnt;


    return 0;
}

Measured memory_bytes: 256
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    B = LI()
    ans = 0
    for i in range(N):
        if i == 0:
            ans += B[i]
        elif i==N-1:
            ans += B[i-1]
        else:
            ans += min(B[i], B[i-1])
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define double long double
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
signed main() {
	int cnt=0,memo=0;
	string s;
	cin>>s;
	for(int i=2;i<s.size()-1;i++){
		if(s[i]=='C')cnt++;
	}
	for(int i=0;i<s.size();i++){
		if(s[i]-'a'>=0)memo++;
	}
	if(s[0]!='A')puts("WA");
	else if(cnt!=1)puts("WA");
	else if(memo!=s.size()-2)puts("WA");
	else puts("AC");
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

a=int(input())
print(a+a**2+a**3)

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

int main() {
  int N,Ans=1;
  cin>>N;
  
  vector<string> vec(N);
  rep(i,N){cin >> vec.at(i);}
  sort(vec.begin(), vec.end());
  
  rep(i,N-1){if(vec.at(i+1)!=vec.at(i)){Ans++;}}
  cout<<Ans<<endl;
}


Measured memory_bytes: 9516
#include <stdio.h>          // printf(), getc()
#include <ctype.h>          // isdigit()

#define MAX_N 100000
#define swap(x, y) { card_t t = x; x = y; y = t; }

typedef struct card_tbl
{
	char mark;
	int val;
	int seq;
} card_t;

card_t a[MAX_N];

int
partition(int p, int r)
{
	int j;

	int x = a[r].val;
	int i = p - 1;
	for (j = p; j < r; ++j)
	{
		if (a[j].val <= x)
		{
			i++;
			swap(a[i], a[j]);
		}
	}

	swap(a[i + 1], a[r]);
	return i + 1;
}

void
quicksort(int p, int r)
{
	if (p < r)
	{
		int q = partition(p, r);
		quicksort(p, q - 1);
		quicksort(q + 1, r);
	}
}

int
main(int argc, char** argv)
{
	int n, m;
	int i;
	int c;

	c = getc(stdin);
	n = 0;
	while (isdigit(c))
	{
		n = n * 10 + c - '0';
		c = getc(stdin);
	}

	for (i = 0; i < n; ++i)
	{
		while (c == ' ' || c == '\n')
			c = getc(stdin);

		a[i].mark = c;
		c = getc(stdin);
		while (c == ' ')
			c = getc(stdin);

		m = 0;
		while (isdigit(c))
		{
			m = m * 10 + c - '0';
			c = getc(stdin);
		}

		a[i].val = m;
		a[i].seq = i;
	}

	quicksort(0, n - 1);

	for (i = 0; i < n - 1; ++i)
	{
		if (a[i].val == a[i + 1].val && a[i].seq > a[i + 1].seq)
			break;
	}

	if (i >= n - 1)
		printf("Stable\n");
	else
		printf("Not stable\n");

	for (i = 0; i < n; ++i)
		printf("%c %d\n", a[i].mark, a[i].val);

	return 0;
}

Measured memory_bytes: 1692
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 1005
#define ll long long
const ll mod=1e9+7;
using namespace std;
int n;
int p[maxn];
int num[maxn];
int vis[maxn];
int cnt;
ll cal(ll a,ll b)
{
    if(a<b)
        return 0;
    else return a/b+cal(a/b,b);
}
void init()
{memset(vis,0,sizeof(vis));
cnt=0;
    vis[0]=vis[1]=1;

    for(int i=2;i<maxn;i++)
    {
     if(!vis[i])
     {
         p[cnt++]=i;
     }
     for(int j=0;j<cnt&&i*p[j]<maxn;j++)
        {vis[i*p[j]]=1;
        if(i%p[j]==0)
            break;
    }
    }
}
int main()
{
    scanf("%d",&n);
    init();
    ll ans=1;
    for(int i=0;i<cnt;i++)
        if(p[i]<=n)
            ans=(ans%mod*(cal(n,p[i])%mod+1)%mod)%mod;
            else
                break;
        printf("%lld\n",ans);

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<string>
#include<deque>
#include<stack>
#include<map>
#include<random>
#include<queue>
#include<iterator>
#include<bitset>
#include<unordered_set>
#include<set>

using namespace std;
#define ll long long
#define endl "\n"
const int dx[] = { -1 , -1 , -1 , 0 , 0 , 0 , 1 , 1 , 1 };
const int dy[] = { -1 , 0 , 1 , -1 , 0 , 1 , -1 , 0 , 1 };
const ll integer = pow(2, 32) - 1; // 4294967295
#define N 8010000
#define TC int t;cin>>t;for(int T=1;T<=t;T++)
#define mod 1000000007
#define PI acos(-1)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
void AIA() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
bool isprime(ll n) {
	for (ll i = 2; i * i <= n; i++) {
		if (n % i == 0)return 0;
	}
	return 1;
}
ll prim(ll n) {
	for (int i = 2; i * i <= n; i++) {
		if (i % n == 0) {
			return i;
		}
	}
}
//cout<<fixed<<setprecision(20);
// freopen("stand.in","r",stdin);
// freopen("stand.out","w",stdout);

/*
 _____________              __                ___        ___       ___________________________     ____        ____
|             |            /\ \              |   |      |   |     |                           |    \   \      /   /
|   __________|           / /\ \             |   |      |   |     |      _____      _____     |     \   \    /   /
|  |                     / /  \ \            |   |      |   |     |     |     |    |     |    |      \   \  /   /
|  |                    / /    \ \           |   |      |   |     |     |     |    |     |    |       \   \/   /
|  |______             / /      \ \          |   |______|   |     |     |     |    |     |    |        \      /
|         |           / /        \ \         |              |     |     |     |    |     |    |         \    /
|   ______|          / /          \ \        |    ______    |     |     |     |    |     |    |          |  |
|  |                / /============\ \       |   |      |   |     |     |     |    |     |    |          |  |
|  |               / /==============\ \      |   |      |   |     |     |     |    |     |    |          |  |
|  |              / /                \ \     |   |      |   |     |     |     |    |     |    |          |  |
|  |             / /                  \ \    |   |      |   |     |     |     |    |     |    |          |  |
|__|            /_/                    \_\   |___|      |___|     |_____|     |____|     |____|          |__|

										  <<<<<<<<<<< NEVER GIVE UP !! >>>>>>>>>>>
										<<<<<<<< YOU CAN DO IT IF YOU WANT !! >>>>>>>>
										 <<<<<<<<< BELIEVE IN YOURSELF !! >>>>>>>>>

*/

int  main() {
	//cout << fixed << setprecision(9);
	//freopen("stand.in","r",stdin);
	//freopen("stand.out","w",stdout);

	AIA();

	ll h1, m1, h2, m2, k;
	cin >> h1 >> m1 >> h2 >> m2 >> k;

	ll t1, t2;
	t1 = (h1 * 60) + m1;
	t2 = (h2 * 60) + m2;

	t1 = abs(t1 - t2);

	cout << abs(t1 - k);
	return 0;
}


Measured memory_bytes: 3656
#include <stdio.h>

char s[100005];

int main(){
    scanf("%s", s);
    if(s[0] == s[1]){ printf("1 2"); return 0; }
    for(int i=0; s[i+2]; i++){
        if(s[i] == s[i+1] || s[i] == s[i+2] || s[i+1] == s[i+2]){
            printf("%d %d", i+1, i+3);
            return 0;
        }
    }
    printf("-1 -1");
    return 0;
}

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

int main(){
    int a, b;
    string op;
    vector<int> data;
    
    while(1){
        cin >> a >> op >> b;
        if(op == "+"){
            //cout << a + b << endl;
            data.push_back(a+b);
        }
        if(op == "-"){
            //cout << a - b << endl;
            data.push_back(a-b);
        }
        if(op == "*"){
            //cout << a * b << endl;
            data.push_back(a*b);
        }
        if(op == "/"){
            //cout << a / b << endl;
            data.push_back(a/b);
        }
        if(op == "?"){
            break;
        }
    }
    for (int i = 0; i<data.size(); i++){
        cout << data.at(i) << endl;
    }
}




Measured memory_bytes: 3216
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n = 200005;
int n, c[max_n];
vector<int> G[max_n];
int cur[max_n], sz[max_n];
ll ans[max_n];
void dfs(int u, int fa) {
    int x = cur[c[u]];
    sz[u] = 1;
    for(auto v : G[u]) {
        if(v == fa) continue;
        int pre = cur[c[u]];
        dfs(v, u);
        sz[u] += sz[v];
        int suf = cur[c[u]];
        suf -= pre;
        int t = sz[v] - suf;
        ans[c[u]] -= 1ll * t * (t + 1) / 2;
    }
    x += sz[u];
    cur[c[u]] = x;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i<= n; i++) scanf("%d", c + i);
    for(int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i++) {
        int t = n - cur[i];
        ans[i] -= 1ll * t * (t + 1) / 2;
    }
    for(int i = 1; i <= n; i++) ans[i] += 1ll * n * (n + 1) / 2;
    for(int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
    return 0;
}

Measured memory_bytes: 37176
#include<bits/stdc++.h>
#define mod 1000000007
#define fr first
#define se second
#define ll long long
#define PI 3.1415926535 
#define pb push_back
#define mpr make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Senky_Bansal ios_base::sync_with_stdio(false);
#define IIIT_ALLAHABAD    cin.tie(NULL);cout.tie(NULL);
using namespace std;
signed main()
{   
    Senky_Bansal
    IIIT_ALLAHABAD

     string s,t;
  cin>>s>>t;
  ll ans=0;
  for(int i=0;i<3;i++)
    if(s[i]==t[i])
      ans++;
  cout<<ans;


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t;
    }
    return n*rep_jijo(n,x-1);
}

int main(){
    int n;
    cin >> n;
    int odd=0;
    int even=0;
    rep(i,n){
        ll a;
        cin >> a;
        if(a%2==0) even++;
        else odd++;
    }
    if(odd%2==1){
        cout << "NO" <<endl;
      
    }
    else {
        cout << "YES" <<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def floor_sum_1(n, m, a, b):
    ret = 0
    if a >= m:
        ret += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        ret += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return ret
    ret += (n - (x_max + a - 1) // a) * y_max
    ret += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return ret


def floor_sum(n, m, a, b):
    ret = 0
    while True:
        if a >= m:
            ret += (n - 1) * n * (a // m) // 2
            a %= m
        if b >= m:
            ret += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        x_max = y_max * m - b
        if y_max == 0:
            return ret
        ret += (n - (x_max + a - 1) // a) * y_max
        n = y_max
        m, a, b = a, m, (a - x_max % a) % a


def debug(*x):
    print(*x, file=sys.stderr)


def solve(SOLVE_PARAMS):
    pass


def main():
    # parse input
    T = int(input())
    for _t in range(T):
        N, M, A, B = map(int, input().split())
        print(floor_sum(N, M, A, B))


# tests
T1 = """
5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
13
0
314095480
499999999500000000
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()


Measured memory_bytes: 70336
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int am = 0;
        int r = 360;
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        sc.close();

        for(int i = 1;i < 10000; i++){
            am = (r*i)%x;
            if(am == 0){
                System.out.println((r*i)/x);
                i = 10000;
            }
        }
    }
}

Measured memory_bytes: 27068
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+7;
int n,p,k,f[N],w[N];
inline int inc(int a,int b){
	if(a+b>=p) return a+b-p; return a+b;
}
int main(){
	cin>>n>>p,f[0]=1,k=(n-1)/2,w[n+1]=1; int sum=0;
	for(int i=1;i<=k;i++) w[i+1]=-1,w[n-i+1]=1;
	for(int i=n;i>=1;i--) w[i]+=w[i+1];
	for(int i=2;i<=n;i++)
		for(int x=0;x+w[i]<=n;x++) f[x+w[i]]=inc(f[x+w[i]],f[x]);
	for(int i=0;i<n;i++) sum=(sum+1ll*(n-i)*f[i])%p; cout<<sum<<endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long a = sc.nextLong();
    long b = sc.nextLong();
    long k = sc.nextLong();
    long ans1 = a;
    long ans2 = b;
    ans1 -= Math.min(a, k);
    ans2 -= Math.min(b, k - Math.min(a, k));
    System.out.println(ans1 + " " + ans2);
  }
}

Measured memory_bytes: 23764
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			n = scanner.nextInt();
			if (n == 0)
				break;
			d = new int[n][n];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					d[i][j] = scanner.nextInt();
			int max = 0;
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++) {
					d[i][j] = Math.max(d[i][j], d[j][i]);
					max = Math.max(max, d[i][j]);
				}
			ans = INF;
			used = new boolean[n];
			pos = new int[n];
			dfs(0, 0);
			System.out.println(ans);
		}
	}

	private void dfs(int right, int bit) {
		if (ans <= right)
			return;

		if (Integer.bitCount(bit) == n) {
			ans = right;
			return;
		}
		for (int i = 0; i < n; i++) {
			if (((bit >> i) & 1) == 1)
				continue;
			int nbit = bit | 1 << i;
			for (int j = 0; j < n; j++) {
				if (((bit >> j) & 1) == 0)
					continue;
				pos[i] = Math.max(pos[i], pos[j] + d[j][i]);
			}
			dfs(pos[i], nbit);
			pos[i] = 0;
		}
	}

	int n, ans;
	int[] pos;
	int[][] d;
	int INF = 1 << 30;
	boolean[] used;
}

Measured memory_bytes: 26260
//C - City Savers
#include <iostream>
using namespace std;

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

  int a[n+1];
  int b[n];

  for (int i = 0; i < n+1; i++){
    cin >> a[i];
  }
  for (int i = 0; i < n; i++){
    cin >> b[i];
  }

  long long cnt = 0;
  int defeated = 0;
  for (int i = 0; i < n; i++){
    //i番目の町のモンスターを倒せるだけ倒す
    defeated = min(a[i], b[i]);
    cnt += defeated;
    a[i] = a[i] - defeated;
    b[i] = b[i] - defeated;
    //全部倒せたらi+1も
    defeated = min(a[i+1], b[i]);
    cnt += defeated;
    a[i+1] = a[i+1] - defeated;

    //b[i]はi+2以降は倒せないので情報更新しなくて良い
    //b[i] = b[i] - defeated;

  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 1024
from collections import Counter
N = int(input())
List = list(map(str, input().split()))
Q = int(input())
x = [0] * Q
y = [0] * Q
for i in range(Q):
    x[i], y[i] = map(str, input().split())
    y[i]=int(y[i])

wa=0
for i in List:
    wa+=int(i)
c =Counter(List)
for i in range(Q):
    num=c['{}'.format(x[i])]
    wa+=num*(y[i]-int(x[i]))
    c['{}'.format(x[i])]=0
    c['{}'.format(str(y[i]))]+=num
    print(wa)

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

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

int main() {
    long long N, P, ans = 1;
    cin >> N >> P;

    vector<pair<long long, long long> > ress;

    for(long long i = 2; i * i <= P; ++i) {
        if (P % i != 0) {
            continue;
        }

        long long ex = 0; // 指数
        while (P % i == 0) {
            ++ex;
            P /= i;
        }
        // 結果を保存
        ress.push_back({i, ex});
    }
    // 残った数字の処理
    if (P != 0) {
        ress.push_back({P, 1});
    }

    for (pair<long long, long long> res : ress) {
        if (res.second >= N ) {
            ans *= pow(res.first, (res.second / N));
        }
    }
    cout << ans << endl;



    return 0;
}


Measured memory_bytes: 3908
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp(a,b) make_pair(a,b)
#define maxn 400005
#define pb(x) push_back(x)
using namespace std;

vector<pll > v[maxn];

pll nx[maxn],ny[maxn];

int n;

struct note{
	int lson,rson,lv,rv;
}a[maxn];

ll ans,chk;

int sx,sy;

void ins(int x,pll y){
	if (v[x].size()==0) {
		v[x].pb(y);
		return;
	}
	int siz=v[x].size();
	if (v[x][siz-1].se<=y.se) return;
	v[x].pb(y);
}

bool dfs(int x){
	if (a[x].lson==0) {
		v[x].pb(mp(0,0));
		return 1;
	}
	if (!dfs(a[x].lson)) return 0;
	if (!dfs(a[x].rson)) return 0;
	sx=sy=0;
	int lson=a[x].lson,rson=a[x].rson,add=a[x].lv+a[x].rv;
	//
	int wz=v[rson].size()-1;
	fd(i,v[lson].size()-1,0) {
		while (wz>=0 && v[lson][i].se+v[rson][wz].fi+add>chk) wz--;
		if (wz<0) break;
		sx++;
		nx[sx]=mp(v[lson][i].fi+a[x].lv,v[rson][wz].se+a[x].rv);
	}
	//
	wz=v[lson].size()-1;
	fd(i,v[rson].size()-1,0) {
		while (wz>=0 && v[rson][i].se+v[lson][wz].fi+add>chk) wz--;
		if (wz<0) break;
		sy++;
		ny[sy]=mp(v[rson][i].fi+a[x].rv,v[lson][wz].se+a[x].lv);
	}
	//
	int wz1=sx,wz2=sy;
	while (wz1 && wz2) {
		if (nx[wz1].fi<ny[wz2].fi) ins(x,nx[wz1]),wz1--;
		else ins(x,ny[wz2]),wz2--;
	}
	while (wz1) ins(x,nx[wz1]),wz1--;
	while (wz2) ins(x,ny[wz2]),wz2--;
	return v[x].size();
}

int main(){
	scanf("%d",&n);
	fo(i,2,n) {
		int father,len;
		scanf("%d%d",&father,&len);
		if (a[father].lson==0) {
			a[father].lson=i;
			a[father].lv=len;
		}
		else {
			a[father].rson=i;
			a[father].rv=len;
		}
	}
	ll l=0,r=1e12;
	while (l<=r) {
		ll mid=(l+r) >> 1;
		chk=mid;
		fo(i,1,n) v[i].clear();
		if (dfs(1)) {
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 40052
#include <iostream>
#include <string>

using namespace std;

int main() {
    string b;
    cin >> b;

    if (b == "A") { cout << "T" << endl; }
    if (b == "C") { cout << "G" << endl; }
    if (b == "G") { cout << "C" << endl; }
    if (b == "T") { cout << "A" << endl; }
}


Measured memory_bytes: 256
def solve():
    n = list(input())
    n = [ord(c) - ord('0') for c in n]
    sign = ['-', '+']

    for i in range(2):
        for j in range(2):
            for k in range(2):
                t = n[0]
                t += n[1] * (i * 2 - 1)
                t += n[2] * (j * 2 - 1)
                t += n[3] * (k * 2 - 1)
                if t == 7:
                    print('{}{}{}{}{}{}{}=7'.format(n[0], sign[i], n[1], sign[j], n[2], sign[k], n[3]))
                    return


if __name__ == "__main__":
    solve()


Measured memory_bytes: 3064