akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
//#include <unordered_set>
//#include <unordered_map>
//#include <bits/stdc++.h>

#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second

using namespace std;

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }

typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod eps=1e-11;
const lod pi=acos(-1);
const int oo=1<<30;
const ll loo=1ll<<62;
const int mods=1e9+7;
const int MAXN=600005;
const int INF=0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{
	int f=1,x=0; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }
	while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
	return x*f;
}
struct anode{ll x,y;} a[105],q[10005];
int main()
{
    int n=read();
    for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) q[(i-1)*n+j]=(anode){a[i].x-a[j].x,a[i].y-a[j].y};
    
	int smin=INF;
    for (int i=1;i<=n*n;i++)
    {
    	int ans=0;
        for (int j=1;j<=n;j++)
        {
        	bool flag=1;
            for (int k=1;k<=n;k++) 
			    if (j!=k&&a[j].x+q[i].x==a[k].x&&a[j].y+q[i].y==a[k].y) flag=0;
			ans+=flag;
		}
        smin=min(smin,ans);
    }
    printf("%d\n",smin);
	return 0;
}

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

using namespace std;

typedef unsigned long long ll;

int main(){
  ll n;
  cin>>n;
  ll t,a;
  ll tv,av;
  cin>>tv>>av;
  
  for(int i=1;i<n;i++){
    cin>>t>>a;
       
   	ll aa=(tv+t-1)/t;
    ll bb=(av+a-1)/a;
    ll mx=bb;
    if(aa>bb){
      mx=aa;
    }

    tv=mx*t;
    av=mx*a;
  }
  
  cout<<(tv+av)<<endl;
  return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll x;
    cin >> x;
    ll L = 0, R = 1e9;
    while(R - L > 1){
        ll M = L + (R - L) / 2;
        if(M * (M+1) / 2 >= x) R = M;
        else L = M;
    }
    cout << R << endl;
    return 0;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
#include<string>
#include<vector>
using namespace std;
typedef pair<int, int>P;
typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll MOD = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 5010;
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)
//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//組み合わせの余りを求める
ll fac[MAX_N], finv[MAX_N], inv[MAX_N];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX_N; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll dx[4] = { 0,0,-1,1 };
ll dy[4] = { -1,1,0,0 };
ll dp[101010];

//union-find木について
ll par[101010];
ll rank2[101010];

void init(ll n) {
	rep(i, n) {
		par[i] = i;
		rank2[i] = 0;
	}
}

ll find(ll x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}

void unite(ll x, ll y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rank2[x] < rank2[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rank2[x] == rank2[y]) {
			rank2[x]++;
		}
	}
}

long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

char c[2010][2010];
bool flag[2010][2010];
ll cnt[2010][2010];

//long longしか使わない
//素数は1より大きい
int main() {
	ll n;
	cin >> n;
	vector<ll>x(n), y(n), h(n);
	rep(i, n) {
		cin >> x[i] >> y[i] >> h[i];
	}
	rep(i, 101) {
		rep(j, 101) {
			bool flag = true;
			ll dist = INF;
			ll high = 0;
			rep(k, n) {
				if (h[k] > 0) {
					high = h[k] + abs(i - x[k]) + abs(j - y[k]);
					break;
				}
			}
			rep(k, n) {
				ll target = high - abs(i - x[k]) - abs(j - y[k]);
				if (target >= 0) {
					if (target != h[k])flag = false;
				}
				else {
					if (h[k] != 0)flag = false;
				}
			}
			if (flag) {
				cout << i << " " << j << " " << high << endl;
				return 0;
			}
		}
	}
}

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

int lcs(string s1, string s2) {
    int n = s1.size(), m = s2.size();

    int c[n + 1][m + 1];
    for (int i = 0; i <= n; i++)
    {
        c[i][0] = 0;
    }
    for (int i = 0; i <= m; i++) {
        c[0][i] = 0;
    }

    // indexを合わせるため、各文字列に空白を挿入
    s1 = ' ' + s1;
    s2 = ' ' + s2;

    int maxl=0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++) {
            if (s1.at(i) == s2.at(j))
                c[i][j] = 1 + c[i - 1][j - 1];
            else
            {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
            maxl = max(maxl, c[i][j]);
        }
    }
    return maxl;
}

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

    for (int i = 0; i < q; i++)
    {
        string s1, s2;
        cin >> s1 >> s2;
        cout << lcs(s1, s2) << endl;
    }
}


Measured memory_bytes: 7112
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int> > Matrix;



int main(){
  double w, h, x, y;
  cin >> w >> h >> x >> y;
  double s = w * h / 2;
  bool ans = false;
  if (x == w/2 && y == h/2) ans = true;
  cout << fixed << setprecision(6) << (double)s << " " << ans << endl;
}

Measured memory_bytes: 256
#define DEBUG 0

/**
 * File    : D.cpp
 * Author  : Kazune Takahashi
 * Created : 2019-5-25 21:06:56
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <functional>
#include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(10101010));
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

int N, M;
typedef tuple<ll, ll> spell;
ll A[100010];
spell S[100010];

int main()
{
  cin >> N >> M;
  for (auto i = 0; i < N; i++)
  {
    cin >> A[i];
  }
  sort(A, A + N);
  for (auto i = 0; i < M; i++)
  {
    ll b, c;
    cin >> b >> c;
    S[i] = spell(c, b);
  }
  sort(S, S + M);
  reverse(S, S + M);
  int ind = 0;
  int ind_s = 0;
  ll now = 0;
  int cnt = 0;
  while (ind < N)
  {
    if (cnt == 0)
    {
      if (ind_s >= M)
      {
        break;
      }
      now = get<0>(S[ind_s]);
      cnt = get<1>(S[ind_s]);
      ind_s++;
    }
    if (A[ind] < now)
    {
      A[ind] = now;
      ind++;
      cnt--;
    }
    else
    {
      break;
    }
  }
  ll ans = 0;
  for (auto i = 0; i < N; i++)
  {
    ans += A[i];
  }
  cout << ans << endl;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MX_N = 1e5+5;

int N;
int A[MX_N], B[MX_N], o[MX_N], AA[MX_N], BB[MX_N], oo[MX_N], AP[MX_N];
bool vis[MX_N];

void dfs(int u) { vis[u] = 1; if (!vis[oo[u]]) dfs(oo[u]); }

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,0,N-1){ cin >> A[i]; }
    FOR(i,0,N-1){ cin >> B[i]; o[i] = i; }

    sort(o,o+N,[](int a, int b) { if (B[a] == B[b]) return a < b; return B[a] < B[b]; });
    FOR(i,0,N-1) {
        AA[i] = A[o[i]], BB[i] = B[o[i]];
        oo[i] = i;
    }

    sort(oo,oo+N,[](int a, int b) { if (AA[a] == AA[b]) return a < b; return AA[a] < AA[b]; });
    FOR(i,0,N-1) {
        AP[i] = AA[oo[i]];
        if (AP[i] > BB[i]) { cout << "No"; return 0; }
    }

    memset(vis,0,sizeof vis);
    int cnt = 0;
    FOR(i,0,N-1) if (!vis[i]) {
        ++cnt;
        dfs(i);
    }

    if (cnt >= 2) { cout << "Yes"; return 0; }
    else {
        FOR(i,0,N-2){
            if (BB[i] >= AP[i+1]) { cout << "Yes"; return 0; }
        }

        cout << "No";
    }
}



Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef pair<double,int>Q;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,t,e;
int x[100005];
struct segtree{
	#define s (1<<18)
	ll seg[s];
	void init(){ rep(i,s) seg[i] = 1e17; }
	void update(int k,ll a){
		k+=s/2-1; seg[k]=a;
		while(k>0){
			k=(k-1)/2;
			seg[k]=min(seg[k*2+1],seg[k*2+2]);
		}
	}
	ll query(int a,int b,int k,int l,int r){
		if(r<a || b<l || a>b) return 1e17;
		if(a<=l && r<=b) return seg[k];
		else{
			ll vl=query(a,b,k*2+1,l,(l+r)/2);
			ll vr=query(a,b,k*2+2,(l+r)/2+1,r);
			return min(vl,vr);
		}
	}
}rmq,rmq2;

int main(){
	cin>>n>>e>>t;
	for(int i=1;i<=n;i++) cin>>x[i];
	rmq.init(); rmq2.init();
	rmq.update(0,0);
	rmq2.update(0,-2LL*x[1]);
	for(int i=1;i<=n;i++){
		ll dp = 1e17;
		int y = x[i] - t/2;
		int f = lower_bound(x+1,x+n+1,y)-x;
		//f..i-1
		dp = min(dp,1LL*t+rmq.query(max(0,f-1),i-1,0,0,(1<<17)-1));
		dp = min(dp,2LL*x[i]+rmq2.query(0,f-2,0,0,(1<<17)-1));
		if(i==n){
			cout<<dp+1LL*e<<endl; return 0;
		}
		rmq.update(i,dp);
		rmq2.update(i,dp-2LL*x[i+1]);
	}
}

Measured memory_bytes: 4736
#include<stdio.h>

int main(void) {
	int x = 0;
	int y = 0;
	int a = 0;
	int b = 0;

	scanf("%d %d", &a, &b);

	if (a == b) {

		x = a + b;
	}
	else {
		if (a > b) {
			x = a+a-1;
			
		}
		else {
			x = b+b-1;
			
		}
	}
	printf("%d", x);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>

using namespace std;

int main(){
	for (int i = 1; i < 10; i++){
		for (int j = 1; j < 10; j++){
			cout << i << "x" << j << "=" << i*j << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1116
def getval():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    return n,k,a

def main(n,k,a):
    #Dp such that when the first takes the turn with i remaining stones,
    #0->Second, 1->First wins
    dp = [0 for i in range(k+1)]
    for i in range(1,k+1):
        for j in a:
            if j>i:
                break
            if not dp[i-j]:
                dp[i] = 1
    if dp[k]:
      print("First")
    else:
      print("Second")

if __name__=="__main__":
    n,k,a= getval()
    main(n,k,a)  

Measured memory_bytes: 78572
#include<iostream>
#include<vector>
#include<climits>

using namespace std;

int MaximumProfit ( vector<int> R )
{
	int max_profit = INT_MIN;
	int profit;
	
	int i,j,count=0;
	for ( i = R.size()-1 ; i > 0 ; i-- )
	{
		for ( j = 0 ; j < i ; j++ )
		{
			++count;
			profit = R[i] - R[j];
			if ( profit > max_profit )
				max_profit = profit;
		}
	}

	cout << count << endl;

	return max_profit;
}

int MaximumProfit_new ( vector<int> R )
{
	int max_profit = INT_MIN;
	int min_value;
	int i;

	min_value = R[0];

	for ( i=1 ; i < R.size() ; i++ )
	{
		if ( max_profit < (R[i]-min_value) )
		{
			max_profit = R[i]-min_value;
		}
		if ( min_value > R[i] )
		{
			min_value = R[i];
		}
	}

	return max_profit;

}

int main ()
{
	int n,r;
	vector<int> R;

	cin >> n;

	while ( n-- )
	{
		cin >> r;
		R.push_back ( r );
	}
	
	cout << MaximumProfit_new(R) << endl;

return 0;
}



Measured memory_bytes: 4704
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

#define rep(i,a,b) for(int i=a;i<b;i++)

const int inf = 1001001000;
const int mod = 1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int digitsum(int i){
    int t = i;
    int ret = 0;
    while(t){
        ret += t%10;
        t /= 10;
    }
    return ret;
}

int main(){
    int n;
    int ans = inf;
    cin >> n;
    while(n--){
        int t;
        cin >> t;
        int count = 0;
        while (t%2 == 0){
            count += 1;
            t /= 2;
        }
        ans = min(ans, count);
    }
    cout << ans << endl;
}




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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

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

struct Edge {
    ll to, rev;
    long double cap;
    Edge(ll _to, long double _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph &G, ll from, ll to, long double cap, bool revFlag,
              long double revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve() {
    ll h, w, k;
    cin >> h >> w >> k;
    vec<string> c(h);
    REP(i, h) { cin >> c[i]; }

    ll allh = 1LL << h;
    ll allw = 1LL << w;
    ll ans = 0;
    REP(bith, allh) {
        REP(bitw, allw) {
            ll con = 0;
            REP(i, h) {
                if((bith >> i) & 1)
                    continue;
                REP(j, w) {
                    if((bitw >> j) & 1)
                        continue;
                    if(c[i][j] == '#')
                        con++;
                }
            }
            if(con == k)
                ans++;
        }
    }
    cout << ans << en;
}

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

    solve();
    /*
    ll t;
    cin >> t;
    REP(i, t)
    solve();
    */

    return 0;
}


Measured memory_bytes: 3652
#include <stdio.h>

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


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

/*
code credits : ਜ਼ੈਲਦਾਰ
dashan jot singh
*/
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define inf LLONG_MAX
#define p pair<ll,ll>

int gcd(int a,int b){
	if(b==0){
		return a;
	}
	return gcd(b,a%b);
}
int main(){
	fast;
	int n;
	cin>>n;
	int arr[100010];
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	int ans=arr[0];
	for(int i=1;i<n;i++){
		ans=gcd(ans,arr[i]);
	}
	cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#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 ALL(a) (a).begin(), (a).end()

int main() {
    int N;
    cin >> N;
    ll A, B, S, X = 0;
    cin >> A >> B;
    S = A + B;
    REP(i, N - 2) {
        ll tmp; cin >> tmp;
        X ^= tmp;
    }

    if (S < X || (S - X) % 2 == 1) {
        cout << -1 << endl;
        return 0;
    }
    ll D = (S - X) / 2, y = 0;
    if ((D & X) != 0) {
        cout << -1 << endl;
        return 0;
    }

    if (D > A) {
        cout << -1 << endl;
        return 0;
    }
    RREP(i, 41) {
        ll ny = y | (1LL << i);
        if ((X >> i & 1) == 1 && (D ^ ny) <= A && (D ^ ny) > (D ^ y)) y = ny;
    }
    ll ans = D ^ y;
    if (ans == 0 || ans > A) cout << -1 << endl;
    else cout << A - ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#!/usr/bin/env python3
#F

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

dp = [inf]*n
ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(s, p, dp, num):
    for u in edges[s]:
        flag = False
        if u == p:
            continue
        if ans[u] != None:
            continue
        r = bl(dp, a[u])
        tmp = dp[r]
        if dp[r] == inf:
            num += 1
            flag = True
        ans[u] = num
        dp[r] = min(dp[r], a[u])
        dfs(u, s, dp, num)
        dp[r] = tmp
        if flag:
            num -= 1
    return
dfs(0, -1, dp, 1)

for i in ans:
    print(i)
        

Measured memory_bytes: 548288
import java.util.*;

class Main {
	Scanner sc = new Scanner(System.in);

	public void run() {
		while(true){
			int n=sc.nextInt();
			if(n==0)break;
			int[] val=new int[n];
			for(int i=0;i<n;i++){
				val[i]=sc.nextInt();
			}

			int max=-1000000000;
			for(int s=0;s<n;s++){
				int sum=0;
				for(int e=s;e<n;e++){
					sum+=val[e];
					if(sum>max){
						max=sum;
					}
				}
			}
			ln(max);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public static void pr(Object o) {
		System.out.print(o);
	}

	public static void ln(Object o) {
		System.out.println(o);
	}

	public static void ln() {
		System.out.println();
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
    int r,g,b;
    cin>>r>>g>>b;
    cout<<(((r*100+g*10+b)%4)?"NO":"YES")<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>

using namespace std;
int n,x,ans;
char s[105];
int main()
{
	scanf("%d",&n);
	scanf("%s",s);
	for(int i=0;i<n;i++){
		if(s[i]=='I') x++;
		else x--;
	ans=max(ans,x);
	}
	printf("%d\n",ans);
    return 0;
}

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

typedef pair<int, int> pa_i;

int main() {  
  int n, m; scanf("%d %d", &n, &m);
  
  pa_i demands[100000];
  for (int i = 0; i < m; i++) {
    int a, b; scanf("%d %d", &a, &b);
    demands[i].first = a;
    demands[i].second = b;
  }
  
  sort(demands, demands + m, [](pa_i l, pa_i r){return l.second < r.second;});
  
  int ans = 0;
  int line = 0;
  
  for (int i = 0; i < m; i++) {
    if (demands[i].first <= line) continue;
    ans++;
    line = demands[i].second - 1;
  }
    
  printf("%d\n", ans);
}

Measured memory_bytes: 896
N, K = map(int, input().split())
A = list(map(int, input().split()))

def p(length): # p = 1 => その長さに切り分けることは可能
    if length == 0:
        return 1

    tmp = 0
    for a in A:
        if a % length == 0:
            tmp += (a // length) - 1
        else:
            tmp += a // length
        if tmp > K:
            return 0
    
    # print("length", length, "tmp ", tmp)
    
    return 1
    

def bin_search(arr): #答え(最長の丸太の最小値)として取りうる最大値
    lb = 0
    ub = 1000000000

    while ub - lb > 1:
        mid = (ub + lb) // 2
        if p(mid) == 1:
            ub = mid
        else:
            lb = mid
    
    return lb

def just(num):
    if num == 0:
        return 0
        
    tmp = 0
    for a in A:
        if a % num != 0:
            return 0
        else:
            tmp += a // num
    if tmp != K:
        return 0
    else:
        return 1

ans_tmp = bin_search(A)
if just(ans_tmp) == 1:
    print(ans_tmp)
else:
    print(ans_tmp + 1)


Measured memory_bytes: 30780
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
       
        Scanner sc = new Scanner(System.in);
        int hoge1 = sc.nextInt();
        String hoge = sc.next();
        char[] array = new char[hoge.length()];
        for(int i = 0; i < hoge.length(); i++){
            array[i] = hoge.charAt(i);
        }
        for(int i = 0; i <hoge.length(); i++){
           int asc = (array[i] + hoge1);
           if(asc > 90){
               asc-=26;
           }
           array[i] = (char)asc;
        }
        for(int i = 0; i <hoge.length(); i++){
            System.out.print(array[i]);
        }
    }     
}

Measured memory_bytes: 26532
#include<iostream>
#include<string>
#include<vector>

#define CI cin >>
#define CO cout <<
#define E << endl;

using namespace std;

int main(void) {
	int temp = 0;
	int cost_input[10];
	int cost_return = 0;
	int num[10];
	int j = 0;

	for (int i = 0; i < 10; ++i) {
		CI temp;
		if (temp == 0) {
			j = i;
			break;
		}
		cost_input[i] = temp;

		cost_return = 1000 - cost_input[i];
		num[i] = 0;

		if (cost_return < 5) {
			num[i] = cost_return;
			continue;
		}
		else {
			if (cost_return < 10) {
				num[i] = 1 + cost_return - 5;
				continue;
			}
		}


		if (cost_return >= 500) {
			++num[i];
			cost_return -= 500;
		}
		while (1) {
			if (cost_return >= 100) {
				++num[i];
				cost_return -= 100;
			}
			if (cost_return < 100)break;
		}
		if (cost_return >= 50) {
			++num[i];
			cost_return -= 50;
		}
		while (1) {
			if (cost_return >= 10) {
				++num[i];
				cost_return -= 10;
				if (cost_return < 10)break;
			}
		}

		if (cost_return >= 5) {
			++num[i];
			cost_return -= 5;
		}
		while (1) {
			if (cost_return >= 1) {
				++num[i];
				cost_return -= 1;
			}
			if (cost_return < 1)break;
		}
		
	}
	
	for (int i = 0; i < j; ++i) {
		CO num[i] E
	}

	
}

Measured memory_bytes: 1160
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<map>
#include<algorithm>

using namespace std;

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

    vector<int> x(n, 0);
    vector<int> left;
    vector<int> right;
    for (int i = 0; i < n; i++) {
        int xi;
        cin >> xi;
        x[i] = xi;
        if (xi < 0) {
            left.push_back(xi);
        } else {
            right.push_back(xi);
        }
    }

    long long count_min = 0;
    for (int i = 0; i < n - k + 1; i++) {
        long long count = 0;
        int start = x[i];
        int end = x[i + k - 1];
        if (end < 0) {
            count = 0 - start;
        } else if (start < 0 && 0 <= end) {
            int count1 = 0 - start + (end - start);
            int count2 = end + (end - start);
            count = min(count1, count2);
        } else {
            count = end;
        }
        if (i == 0) {
            count_min = count;
        }
        count_min = min(count_min, count);
    }

    cout << count_min << endl;

    return 0;
}


Measured memory_bytes: 1404
import math
import itertools

N = int(input())
XY = [list(map(int, input().split())) for x in range(N)]

P = list(itertools.permutations(XY, N))

total = 0
for p in P:
  for i in range(1, N):
    a = p[i-1]
    b = p[i]
    total += math.sqrt((a[0]-b[0])**2+(a[1]-b[1])**2)

print(total / len(P))

Measured memory_bytes: 45168
N, M, Q = map(int, input().split())

lst = []
for i in range(Q):
  lst.append(list(map(int, input().split())))
  
  
import itertools

## product 順番あり 重複あり（全て）
## premutations 順番あり 重複なし
## combinations 順番なし　重複なし
## combinations_with_replacement 順番なし　重複あり

A_pattern = itertools.combinations_with_replacement(range(1, M+1), N)
ans = 0

for a in A_pattern:
  point = 0
  
  for l in lst:
    if a[l[1]-1] - a[l[0]-1] == l[2]:
      point += l[3]
      
  if ans < point:
    ans = point
    
print(ans)

Measured memory_bytes: 9168
#include <iostream>

using namespace std;
int main() {

	int n;

	bool odd = false;
	bool even = false;

	cin >> n;

	for (int i = 0; i < n; i++) {
		int a;

		cin >> a;

		if ((a & 1) == 1) {
			if (odd) {
				odd = false;
				a = 0;
			} else {
				odd = true;
			}
		}

		if ((a & 0) == 0) {
			even = true;
		}
	}

	if (even ^ odd) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}

	return 0;
}

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

vector<long long> num_divisors_table(long long n){
    vector<long long> table(n+1, 0);

    for(long long i = 1; i <= n; i++){
        for(long long j = i; j <= n; j = j+ i){
            table[j] += 1;
        }
    }
    return table;
}

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

    vector<long long> table;
    table = num_divisors_table(n);
    long long ans = 0;

    for(long long i = 1; i <= n; i++){
        ans += i * table[i];
    }

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

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

int main() {
    int h, w;
    cin >> h >> w;
    int s[h+2][w+2] = {0};

     for (int i = 1; i < h+1; i++) {
        for (int j = 1; j < w+1; j++) {
            char ch; cin >> ch;
            if (ch == '#') {
                s[i-1][j-1]++;
                s[i-1][j]++;
                s[i-1][j+1]++;
                s[i][j-1]++;
                s[i][j] = 9;
                s[i][j+1]++;
                s[i+1][j-1]++;
                s[i+1][j]++;
                s[i+1][j+1]++;
            }
        }
    }

    for (int i = 1; i < h+1; i++) {
        for (int j = 1; j < w+1; j++) {
            if(s[i][j] >= 9) {
                cout << '#';
            } else {
                cout << s[i][j];
            }
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
int v[105];
long long f[100005],w[105],W;
int main()
{
	scanf("%d%lld",&n,&W);
	for(int i=1;i<=100000;i++)
		f[i]=1e18;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%d",&w[i],&v[i]);
		for(int j=100000;j>=v[i];j--)
			f[j]=min(f[j],f[j-v[i]]+w[i]);
	}
	for(int i=100000;i>=0;i--)
		if(f[i]<=W)
		{
			printf("%d",i);
			return 0;
		}
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
int main()
{
    double a,b,h,m,angle,x,dis,pi,p;
    pi=acos(-1);
    cin>>a>>b>>h>>m;
    x=180.0-abs(180.0-abs((m*6.0)-((h*30.0)+(m*0.5))));
    angle=x*pi/180.0;
    dis=(a*a)+(b*b)-(2*a*b*cos(angle));
    p=sqrt(dis);
    cout<<showpoint;
    cout<<fixed;
    cout<<setprecision(15);
    cout<<p<<endl;
}


Measured memory_bytes: 4192
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define VSORT(v) sort(v.begin(), v.end())
#define DVSORT(v) sort(v.begin(), v.end(),greater<int>())
#define SORT(v, n) sort(v, v+n)
#define DSORT(v,n) sort(v, v+n,greater<int>())
#define vi vector<int>
#define pb push_back
#define P pair<int,int>
#define Pll pair<ll,ll>

template <class T> void chmin(T&a,const T&b) { a = min(a,b); }
template <class T> void chmax(T&a,const T&b) { a = max(a,b); }
 
void print(){cout<<endl;}
template <class Head, class... Tail>
void print(Head&& h,Tail&&... t){ 
	if(sizeof...(t)==0)
		cout<<h;
	else
		cout<<h<<' ';
	print(move(t)...);
}
 
const double EPS =1e-9;
const long INF =2147483647;//32bit 2*1e+9
const long MOD =1e+9+7;
#define PI 3.14159265258979

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

int main(void){
	int N,t=0,C[500],S[500],F[500];
	
	cin>>N;
	REP(i,N-1) 
		cin>>C[i]>>S[i]>>F[i];

	REP(i,N){
		t=0;
		FOR(j,i,N-1){
			if(t<=S[j]){
				t=S[j]+C[j];
			}else{
				double tem=ceil((t-S[j])/(double)(F[j]))*F[j];
				t=S[j]+C[j]+(int)tem;
			}	
		}
		print(t);
	}
	return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES


#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <numeric>
#include <array>
#include <set>
#include <sstream>
#include <cmath>

using namespace std;

typedef long long LL;


vector<vector<LL>> creat_matrix(LL h, LL w) {
	LL _temp;
	vector<vector<LL>> mat;
	for (LL i = 0; i < h; ++i) {
		vector<LL> vec;
		for (LL j = 0; j < w; ++j) {
			cin >> _temp;
			vec.emplace_back(_temp);
		}
		mat.emplace_back(vec);
	}
	return mat;
}


vector<vector<LL>> inner_product(vector<vector<LL>> X, vector<vector<LL>> Y) {
	size_t n = X.size();
	size_t m = X[0].size();
	size_t l = Y[0].size();

	vector<vector<LL>> mat(n, vector<LL>(l, 0));
	for (LL i = 0; i < n; ++i) {
		for (LL j = 0; j < m; ++j) {
			for (LL k = 0; k < l; ++k) {
				mat[i][k] += X[i][j] * Y[j][k];
			}
		}
	}
	return mat;
}


void show_matrix(vector<vector<LL>> mat) {
	size_t len = mat[0].size();
	for (auto&& t : mat) {
		for (LL i = 0; i < len; ++i) {
			printf("%d", t[i]);
			if (i != (len - 1)) printf(" ");
		}
		printf("\n");
	}
}


vector<string> split(const string& s, char delim) {
	vector<string> elems;
	stringstream ss(s);
	string item;

	while (getline(ss, item, delim)) {
		if (!item.empty()) {
			elems.push_back(item);
		}
	}

	return elems;
}


vector<string> results;

string run_command(string& str, vector<string>& commands) {
	auto _str = str;
	int a = stoi(commands[1]);
	int b = stoi(commands[2]);
	int print_num = b - a + 1;
	
	if (commands[0] == "print") {
		results.emplace_back(_str.substr(a, print_num));
	}
	else if (commands[0] == "reverse") {
		reverse(_str.begin() + a, _str.begin() + b + 1);
	}
	else if (commands[0] == "replace") {
		_str.replace(_str.begin() + a, _str.begin() + b + 1, commands[3]);
	}

	return _str;
}


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

	int q;
	cin >> q;

	string whole_com;
	for (int i = 0; i < q + 1; ++i) {
		getline(cin, whole_com);
		auto commands = split(whole_com, ' ');
		auto len = commands.size();

		if (len) {
			str = run_command(str, commands);
		}
	}

	for (auto&& r : results) {
		cout << r << endl;
	}
	return 0;
}



Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long int N, A, B;
  cin >> N >> A >> B;
  long long int C = A + B;
  if(C == 0){
    cout << 0 << endl;
  }
  else{
    long long int p = N / C;
    long long int res = p*A;
    if(A <= N-C*p){
      res += A;
    }
    else{
      res += N-C*p;
    }
    cout << res << endl;
  }
}

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

class rolling_hash2 {
	static const ull b1 = 9973, b2 = 100000007;
	const int h, w;
	vector<ull> rh, rw;
	vector<vector<ull>> hs;
public:
	template <class T> rolling_hash2(const vector<vector<T>>& a)
		: h(a.size()), w(a[0].size()), rh(h + 1), rw(w + 1), hs(h + 1, vector<ull>(w + 1))
	{
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++)
				hs[i + 1][j + 1] = hs[i + 1][j] * b2 + a[i][j];
			for (int j = 0; j < w; j++)
				hs[i + 1][j + 1] += hs[i][j + 1] * b1;
		}
		rh[0] = rw[0] = 1;
		for (int i = 0; i < h; i++) rh[i + 1] = rh[i] * b1;
		for (int i = 0; i < w; i++) rw[i + 1] = rw[i] * b2;
	}
	ull get(int li, int lj, int ri, int rj) {
		assert(0 <= li && li <= ri && ri <= h);
		assert(0 <= lj && lj <= rj && rj <= w);
		ull u = hs[ri][rj] - hs[ri][lj] * rw[rj - lj];
		ull d = hs[li][rj] - hs[li][lj] * rw[rj - lj];
		return u - d * rh[ri - li];
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int H, W;
	cin >> H >> W;
	vector<vector<char>> A(H, vector<char>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> A[i][j];
		}
	}
	int R, C;
	cin >> R >> C;
	vector<vector<char>> B(R, vector<char>(C));
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> B[i][j];
		}
	}
	rolling_hash2 rha(A), rhb(B);
	ull h = rhb.get(0, 0, R, C);
	for (int i = 0; i + R <= H; i++) {
		for (int j = 0; j + C <= W; j++) {
			if (rha.get(i, j, i + R, j + C) == h) {
				printf("%d %d\n", i, j);
			}
		}
	}
	return 0;
}



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

int main(){
  int n;
  cin >> n;
  int ans=n%1000;
  if(ans!=0)cout << 1000-ans << endl;
  else cout << ans << endl;
}


Measured memory_bytes: 3632
#include <stdio.h>

int main()
{
   int N;
   scanf("%d", &N);

   int A[N];
   int max = 0;
   int max_sec = 0;
   int count;

   for (int i = 0; i < N; i++) {
      scanf("%d", &A[i]);

      if (A[i] > max) {
         max = A[i];
         count = i;
      } else if (A[i] <= max && max_sec < A[i])
         max_sec = A[i];

   }

   for (int i = 0; i < N; i++) {
      if (i == count)
         printf("%d\n", max_sec);
      else
         printf("%d\n", max);

   }

   return 0;
}


Measured memory_bytes: 2304
#include <iostream>
#include <vector>
#include<algorithm>
#include <string>
#include <cmath>
#include<queue>
#define PI 3.141592653589793238
#define INF -1
#define ll long long
using namespace std;

int main()
{
	int n;
	int list[10];

	for (int i = 0; i < 10; i++)
	{
		list[i] = 0;
	}

	for (int i = 0; i < 3; i++) {
		cin >> n;
		list[n]++;
	}

	for (int i = 0; i < 10; i++) {
		if (list[i] == 2) {
			printf("Yes");
			return 0;
		}
	}

	printf("No");

	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stack>
#define debug(a) cout << "*" << a << "*" << endl
using namespace std;
typedef long long ll;
int n, a[100005], k;
int main()
{	
	while (~scanf("%d%d", &n, &k))
	{
		int mx = 1000000000;
		for (int i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
		}
		sort(a, a + n);
		for (int i = 0; i < n - k + 1; i++)
			if (mx > a[i + k - 1] - a[i])
				mx = a[i + k - 1] - a[i];
		printf("%d\n", mx);
	}
}

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

int main(){
	int n,t;
  int c[1005];
  int b[1005];
	cin>>n>>t;
	for(int i=0;i<n;i++){
	cin>>c[i]>>b[i];
	}
	int a=1001;
	for(int i=0;i<n;i++){
		if(c[i]<=a&&b[i]<=t){
			a=c[i];
			}
}
if(a==1001)cout<<"TLE"<<endl;
else cout<<a<<endl;

	return 0;
	}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

const int NMAX = 132005;

vector<pair<int, int>> G[NMAX];

vector<pair<int64_t, int64_t>> getChains(int node, int64_t costLimit) {
    if (G[node].empty()) {
        return {{0, 0}};
    }

    vector<pair<int64_t, int64_t>> leftSon = getChains(G[node][0].first, costLimit);
    vector<pair<int64_t, int64_t>> rightSon = getChains(G[node][1].first, costLimit);
    int64_t costLeft = G[node][0].second;
    int64_t costRight = G[node][1].second;
    int64_t addCost = G[node][0].second + G[node][1].second;
    if (SZ(leftSon) > SZ(rightSon)) {
        leftSon.swap(rightSon);
        swap(costLeft, costRight);
    }
    vector<pair<int64_t, int64_t>> chains1, chains2;
    for (int i = 0, j = SZ(rightSon) - 1; i < SZ(leftSon); ++i) {
        while (j >= 0 && rightSon[j].first + leftSon[i].first + addCost > costLimit) {
            j--;
        }
        if (j < 0) {
            break;
        }
        chains1.push_back(make_pair(leftSon[i].second + costLeft,
                    rightSon[j].second + costRight));
        chains2.push_back(make_pair(rightSon[j].second + costRight,
                    leftSon[i].second + costLeft));
    }
    reverse(chains1.begin(), chains1.end());
    vector<pair<int64_t, int64_t>> chains(SZ(chains1) + SZ(chains2));
    merge(chains1.begin(), chains1.end(), chains2.begin(), chains2.end(),
            chains.begin());
    for (int i = 1; i < SZ(chains); ++i) {
        chains[i].second = min(chains[i].second, chains[i - 1].second);
    }
    return chains;
}

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 2; i <= n; ++i) {
        int father, cost;
        cin >> father >> cost;
        G[father].push_back(make_pair(i, cost));
    }

    int64_t finalCostLimit = 1LL << 35;
    for (int64_t step = 1LL << 35; step > 0; step /= 2) {
        int64_t costLimit = finalCostLimit - step;
        if (costLimit < 0) {
            continue;
        }
        vector<pair<int64_t, int64_t>> chains = getChains(1, costLimit);
        if (!chains.empty()) {
            finalCostLimit = costLimit;
        }
    }
    cout << finalCostLimit << '\n';
}

Measured memory_bytes: 22784
#include <stdio.h>
 
int main(void) {
    int a, b, xy, i, m;
    scanf("%d %d", &a, &b);
    /* 整数 x, y について、1 < y < x ならば
       x と y の最大公約数は y と x%y の
       最大公約数に等しい。
       ここで a%b は a を b で割った余りである。 */
        
    if(1 < a && 1 < b) {
        if(a == b) {
            printf("%d\n", a);
            return 0;
        }
        
        if(a < b) {
        	m = a;
        	a = b;
        	b = m;
        }
        do{
        	m = b % a;
        	if(m == 0) {
        		printf("%d\n", a);
        		return 0;
        	}
        	b = a; a = m;
        }while(1);
    }
     
    return 0;
}

Measured memory_bytes: 592
import scala.collection.mutable
object Main extends App {
  import scala.io.StdIn._
  val mod = 1000000
  val n = readInt()
  val combination = Array.tabulate(n + 1){i ⇒ Array.fill(i + 1){1}}
  for (i ← 2 to n) {
    for (j ← 1 until i) {
      combination(i)(j) = (combination(i - 1)(j - 1) + combination(i - 1)(j)) % mod
    }
  }
  val winCount = Array.fill(n){0}
  val loseBy = Array.fill(n){-1}
  for (_ ← 1 until n){
    val Array(a, b) = readLine.trim.split(' ').map(_.toInt - 1)
    winCount(a) += 1
    loseBy(b) = a
  }
  val pattern = Array.fill(n){1L}
  val matchCount = Array.fill(n){0}
  val queue = mutable.Queue[Int](winCount.indices.filter(i ⇒ winCount(i) == 0):_*)
  while(queue.nonEmpty) {
    val i = queue.dequeue()
    if (loseBy(i) != -1) {
      matchCount(i) += 1
      pattern(loseBy(i)) = pattern(loseBy(i)) * pattern(i) % mod * combination(matchCount(i) + matchCount(loseBy(i)))(matchCount(i)) % mod
      matchCount(loseBy(i)) += matchCount(i)
      winCount(loseBy(i)) -= 1
      if (winCount(loseBy(i)) == 0) {
        queue.enqueue(loseBy(i))
      }
    }
  }
  println(pattern(loseBy.indexOf(-1)))
}


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

using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const ll LIM = 1e13;
int main(){
    string s;
    cin >> s;
    ll ss = s.size();
    ll i;
    bool ch = 0;
    ll cnt = 0;
    vector<ll> v,t;
    for(i=0;i<ss;i++){
        if(ch == 0 && s[i]=='R')cnt++;
        else if(ch == 0 && s[i] == 'L'){
            ch^=1;
            t.push_back(cnt);
            cnt=1;
        }
        else if(ch == 1 && s[i] == 'L') cnt++;
        else if(ch == 1 && s[i] == 'R') {
            ch ^= 1;
            t.push_back(cnt);
            cnt = 1;
        }
    }
    t.push_back(cnt);

    for(i=0;i<ss-1;i++){
        if(s[i] == 'R' && s[i + 1] == 'L') v.push_back(i);
    }
    ll j;
    i=0;
    cnt=0;
    for(j=0;j<v.size();j++){
        while(cnt<v[j]){
            cout << 0 << " ";
            cnt++;
        }
        cnt+=2;
        if(t[i]%2 == t[i+1]%2){
            cout << (t[i]+t[i+1])/2 << " " << (t[i]+t[i+1])/2 << " ";
        }else{
            ll x = t[i]+t[i+1];
            x/=2;
            if(t[i] < t[i+1]){
                ll num = t[i+1]-1;
                if(num%2==0){
                    cout << x << " " << x+1 << " ";
                }else {
                    cout << x+1 << " " << x << " ";
                }
            }else{
                ll num = t[i]-1;
                if(num % 2 == 0) {
                    cout << x+1 << " " << x << " ";
                } else {
                    cout << x << " " << x+1 << " ";
                }
            }
        }
        i+=2;
    }
    while(cnt<ss){
        cout << 0 << " ";
        cnt++;
    }
    cout << endl;
    /* for(i=0;i<t.size();i++){
        cout << t[i] << " ";
    }
    cout << endl;*/
    return 0;
}

Measured memory_bytes: 2292
# https://atcoder.jp/contests/abc131/tasks/abc131_c



A, B, C, D = gets.split.map(&:to_i)

multiple_c = B / C - (A - 1) / C
multiple_d = B / D - (A - 1) / D
multiple_cd = B / C.lcm(D) - (A - 1) / C.lcm(D)

puts B - A + 1 - multiple_c - multiple_d + multiple_cd


Measured memory_bytes: 1788
#include <stdio.h>
int main(void){
    // Your code here!
    int n;
    int C[20],V[20];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d ",&V[i]);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&C[i]);
    }
    int max=0;
     for(int i=0;i<n;i++)
    {
      int M=V[i]-C[i]; 
      //printf("%d %d\n",V[i],C[i]);
      if(M>0){
          max+=M;
      }
      
    }
    printf("%d\n",max);
    
}


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

using namespace std;

int main() {
	int n, m, p; cin >> n >> m >> p;
	vector<int> d(m);
	for (int i = 0; i < m; ++i) {
		int tmp; cin >> tmp;
		d[i] = (tmp - p + n) % n;
	}
	sort(d.begin(), d.end());
	int ans = min(n - d[0], d[m - 1]);
	for (int i = 0; i < m - 1; ++i)
		ans = min(ans, min(2 * d[i] + n - d[i + 1], 2 * (n - d[i + 1]) + d[i]));
	cout << ans * 100 << endl;

	return 0;
}


Measured memory_bytes: 3176
######################
# AC: ms(PyPy)
# AC: ms(Python3)
######################

from bisect import bisect_left
import sys
input = sys.stdin.readline


def main():
    N,M = map(int, input().split())
    A = [int(i) for i in input().split()]

    A.sort()

    left = 0
    right = A[-1] * 2 + 5
    while right - left > 1:
        X = (left + right) // 2

        count = 0
        for a in A:
            i = bisect_left(A, X-a)
            count += (N - i)

        if count >= M:
            left = X
        else:
            right = X

    count = 0
    num = []
    append = num.append
    for a in A:
        i = bisect_left(A, left-a)
        count += (N - i)
        append(N - i)

    diff = count - M
    ans = 0
    for i, a in zip(num, A):
        ans += i * a

    print(ans * 2 - diff * left)


if __name__ == "__main__":
    main()


Measured memory_bytes: 14268
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
 
int main(void) {
    std::string a, b, c;
    std::cin >> a >> b >> c;
    int x = -1, y = -1, z = -1;
    char next = 'a';
    while (true) {
        if (next == 'a') {
            if (++x < a.length()) {
                next = a[x];
            }
            else {
                break;
            }
        }
        else if (next == 'b') {
            if (++y < b.length()) {
                next = b[y];
            }
            else {
                break;
            }
        }
        else if (next == 'c') {
            if (++z < c.length()) {
                next = c[z];
            }
            else {
                break;
            }
        }
    }
    std::cout << (char)(next - 32) << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define all(V) (V).begin(), (V).end() 
#define x first
#define y second

using namespace std;

typedef long long ll;
template <typename T> using V = vector <T>;

int main() {fio;
	int n, k = 2;
	cin >> n;
	V <int> H(n), dp(n, 1e9 + 2);
	for(int &u : H) {
		cin >> u;
	}
	dp[0] = 0;
	for(int i = 1; i < n; i++) {
		for(int j = 1; j <= k; j++) {
			if(i - j >= 0) {
				dp[i] = min(dp[i], dp[i - j] + abs(H[i] - H[i - j]));
			}
		}
	}
	cout << dp[n - 1];
	
    return 0;
}

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

#define rep(i,n) for(ll i = 0; i < n; i++)
#define Rep(i,n) for(ll i = 0; i <= n; i++)
#define REp(i,n) for(ll i = 1; i < n; i++)
#define REP(i,n) for(ll i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



int main(){
  int n, m;
  cin >> n >> m;
  V<V<int>> d(m,V<int>(m));
  V<V<int>> c(n,V<int>(n));
  rep(i,m)rep(j,m) cin >> d[i][j];
  rep(i,n)rep(j,n) cin >> c[i][j];
  // iwa[i][j] = グループjが色iの時に感じる違和感の総和
  // j = (x + y) % 3
  V<V<int>> iwa(m,V<int>(3));
  rep(i,n) {
    rep(j,n) {
      rep(ci,m) {
        iwa[ci][(i+j)%3] += d[c[i][j]-1][ci];
      }
    }
  }
  int ans = inf;
  rep(i,m)rep(j,m)rep(k,m) {
    if(i == j || j == k || k == i) continue;
    int tmp = iwa[i][0] + iwa[j][1] + iwa[k][2];
    chmin(ans, tmp);
  }
  cout << ans << endl;
}

Measured memory_bytes: 4572