akhauriyash/Code-Regression huggingface dataset:
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

const int mod = 1e9+7;

struct edge{
    int to;
    int color;
    int weight;
};

int n;
int q;
vector < edge > adj[N];
int bl[N][20] , depth[N];


int getPBL(int u , int p){
    for(int i = 0; (1 << i) <= p; i++){
        if(p & (1 << i)){
            u = bl[u][i];
        }
    }
    return u;
}

int LCA(int u , int v){
    if(depth[u] < depth[v])
        swap(u , v);
    int must = depth[u] - depth[v];
    u = getPBL(u , must);
    if(u == v)
        return u;
    for(int i = 18; ~i; i--){
        if(bl[u][i] != bl[v][i]){
            u = bl[u][i];
            v = bl[v][i];
        }
    }
    return bl[u][0];
}

int t = 1;
int intime[N];

void dfs1(int u , int p){
     intime[u] = t++;
     bl[u][0] = p;
     depth[u] = depth[p] + 1;
     int h = 1;
     while( (1 << h) <= depth[p] ){
        bl[u][h] = bl[ bl[u][h-1] ][h-1];
        h++;
     }
    for(int i = 0; i < adj[u].size(); i++){
        int V = adj[u][i].to;
        if(V == p)
            continue;
        dfs1(V , u);
    }
}

struct inQuery{
    int x;
    int y;
    int time;
};

struct forLCA{
    int x;
    int y;
    int time;
};

int colorCnt[N];
int weightColor[N];
vector < inQuery > query[N];
vector < forLCA > tellLCA[N];

struct dataforLCA{
    int countColorX;
    int weightofcolorX;
    int distfromroottolca;
} LCAdata[N];

int ans[N];

void dfs2(int u , int p , int c , int w , int dist){
    colorCnt[c] ++;
    weightColor[c] += w;

    for(int i = 0; i < tellLCA[u].size(); i++){
        int x = tellLCA[u][i].x;
        int y = tellLCA[u][i].y;
        int time = tellLCA[u][i].time;
        LCAdata[time] = {colorCnt[x] , weightColor[x] , dist};
    }
    for(int i = 0; i < query[u].size(); i++){
        //calculate the answer from me to lca and store it in my time
        //my lca data locates at LCAdata[ my time ]
        int x = query[u][i].x;
        int y = query[u][i].y;
        int time = query[u][i].time;
        ans[time] += dist - LCAdata[time].distfromroottolca - (weightColor[x] - LCAdata[time].weightofcolorX);
        ans[time] += (colorCnt[x] - LCAdata[time].countColorX) * y;
    }
    for(int i = 0; i < adj[u].size(); i++){
        int V = adj[u][i].to;
        int W = adj[u][i].weight;
        int C = adj[u][i].color;
        if(V == p)
            continue;
        dfs2(V , u , C , W , dist + W);
    }
    colorCnt[c] --;
    weightColor[c] -= w;
}

int main(){
    scanf("%d%d" , &n , &q);
    for(int i = 1; i < n; i++){
        int u , v , c , w;
        scanf("%d%d%d%d" , &u , &v , &c , &w);
        adj[u].push_back({v , c , w});
        adj[v].push_back({u , c , w});
    }
    dfs1(1 , 0);
    for(int i = 1; i <= q; i++){
        int u , v , x , y;
        scanf("%d%d%d%d" , &x , &y , &u , &v);
        if(intime[u] > intime[v])
            swap(u , v);
        query[u].push_back({x , y , i});
        query[v].push_back({x , y , i});
        tellLCA[LCA(u , v)].push_back({x , y , i});
    }
    dfs2(1 , 0 , 0 , 0 , 0);
    for(int i = 1; i <= q; i++){
        printf("%d\n" , ans[i]);
    }

}


Measured memory_bytes: 34616
#include<iostream>
#include<cstdio>
#include<cstring>

namespace dytjml
{
	const int N=500100;
	int s[N],t[N];
	int n;
	void initialize()
	{
		static char tmp[N];
		scanf("%s",tmp+1);
		n=strlen(tmp+1);
		for(int i=1;i<=n;i++)s[i]=tmp[i]^48;
	}
	int tag;
	void work()
	{
		tag=0;
		for(int i=n-1,p;i;s[i]-=tag,i--)
		{
			if(s[i]<=s[i+1]+tag)continue;
			s[i]--;
			for(p=n;p>i+1 && s[p]-s[p-1]>=10;p--)s[p]-=9;
			s[p]++,tag+=9;
		}


		for(int i=1,p;i<n-1;t[i]=s[i]+tag,i++)
		{
			if(s[i]+10==s[i+1])
			{
				for(p=n;p>i+1 && s[p]==s[p-1];p--)s[p]+=9;
				tag-=9;

				if(p==i+1){s[i]+=9,s[i+1]+=9;break;}

				s[i]+=10,s[p]--;
				
				if(i>1)
				{
					s[i-1]=t[i-1]-tag;
					s[i-2]=t[i-2]-tag;
					i-=2;
				}
			}
		}
//		for(int i=1;i<n;i++)if(s[i]+10<=s[i+1])exit(-1);
	}
	void solve()
	{
		initialize();
		work();

		s[n]+=tag;
		printf("%d\n",(s[n]/9)+(s[n]%9!=0));
	}
}

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


Measured memory_bytes: 4608
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.10f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e10;
const ll MAX_N = 1010;

//最大公約数
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 dp[101010][110];
ll dx[4] = { 0,0,-1,1 };
ll dy[4] = { -1,1,0,0 };
ll c[110][110];

//long longしか使わない
//素数は1より大きい
int main() {
	ll h, w;
	cin >> h >> w;
	ll n;
	cin >> n;
	vector<ll>a(n);
	rep(i, n) {
		cin >> a[i];
	}
	rep(k, n) {
		for (ll i = 0;i < h;i += 2) {
			rep(j, w) {
				if (c[i][j] == 0&&a[k]>0){
					c[i][j] = k+1;
					a[k]--;
				}
			}
			for (ll j = w - 1;j >= 0;--j) {
				if (c[i+1][j] == 0 && a[k] > 0) {
					c[i+1][j] = k+1;
					a[k]--;
				}
			}
		}
	}
	rep(i, h) {
		rep(j, w) {
			cout << c[i][j];
			if (j != w - 1)cout << " ";
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3796
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=1000000007;
const llint big=2.19e18+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	llint n,q=0,w=0,e=0,r=0,t=0;cin>>n;
	while(n--){
		llint x;cin>>x;
		q+=x;w+=x%2;e+=(x+1)%2;r+=x%2;t+=x;
		if(x==0){w+=2;r+=2;}
		mineq(w,q);mineq(e,w);mineq(r,e);mineq(t,r);
	}
	cout<<t<<endl;
	return 0;
}


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

//def
#define debug(x) cout << #x << ": " << x << '\n'
#define out(x) cout << x << '\n'
#define repeat(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define revrepeat(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define foreach(e, v) for (auto &e : v)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
constexpr int MOD = 1e9 + 7;
constexpr int INF = __INT_MAX__;               // 2^31 - 1
constexpr long long INFLL = __LONG_LONG_MAX__; // 2^61 - 1
constexpr int MAX_N = 1e5 + 5;
constexpr double PI = acos(-1);

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

    int n;
    cin >> n;
    ll ans = 0;
    rep(i, n) {
        int idx = i + 1;
        if (idx % 3 == 0 or idx % 5 == 0)
            continue;
        else {
            ans += idx;
        }
    }

    out(ans);
    return 0;
}


Measured memory_bytes: 3648
R,G,B,N=(int(x) for x in input().split())
count=0
for r in range(0,N+1):
    if (r*R>N):
        break
    for g in range(0,N-r*R+1):
        if(r*R-g*G>N):
            break
        elif((N-r*R-g*G)%B==0 and (N-r*R-g*G)/B>=0):
            count+=1
print(count)

Measured memory_bytes: 41324
import java.io.*;
import java.util.*;
import java.math.*;
import java.awt.*;
import java.lang.*;

//AtCoder:
//ARC094 C: Same Integers  

public class Main {
	public int num(int a, int b, int c) {
		if (a<c) {
			return c-a;
		}
		else {
			int count = (a-c)/2;
			c+= (count+1)*2;
			return count+2;
			
		}
	}
	public void run() throws Exception {
		FastScanner sc = new FastScanner();
		
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		
		int min = Math.min(a, Math.min(b, c));
		a -= min;
		b -= min;
		c-=min;
		//System.out.println(a + " " + b  + " " + c);
		int max = Math.max(a, Math.max(b, c));
		int count =(max-a)/2 + (max-b)/2 + (max-c)/2;
		a += (max-a)/2 * 2;
		b += (max-b)/2 * 2;
		c += (max-c)/2 * 2;
		if (a == b && b == c) {
			System.out.println(count);
			return;
		}
		else if (a == b || b == c || c==a) {
			if (a == b) count+=num(a,b,c);
			else if (a == c) count+=num(a,c,b);
			else count+=num(b,c,a);
		}
		//System.out.println(a + " " + b  + " " + c);
		System.out.println(count);
	}
	static class FastScanner {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public FastScanner() {
			reader = new BufferedReader(new InputStreamReader(System.in), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}

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

Measured memory_bytes: 21460
#include <iostream>

using namespace std;

main(){
  int te[5];
  bool f[4];
  while(1){
    cin >> te[0];
    if(te[0]==0) break;
    for(int i=0;i<4;i++) f[i]=false;
    for(int i=1;i<5;i++){
      cin >> te[i];
    }
    for(int i=0;i<5;i++){
      f[te[i]]=true;
    }
    if(f[1] && f[2] && f[3]){
      for(int i=0;i<5;i++){
	cout << 3 << endl;
      }
    }else if(f[1] && f[2]){
      for(int i=0;i<5;i++){
	if(te[i]==1){
	  cout << 1 << endl;
	}else{
	  cout << 2 << endl;
	}
      }
    }else if(f[2] && f[3]){
      for(int i=0;i<5;i++){
	if(te[i]==2){
	  cout << 1 << endl;
	}else{
	  cout << 2 << endl;
	}
      }
    }else if(f[3] && f[1]){
      for(int i=0;i<5;i++){
	if(te[i]==3){
	  cout << 1 << endl;
	}else{
	  cout << 2 << endl;
	}
      }
    }else if(f[1]){
      for(int i=0;i<5;i++){
	cout << 3 << endl;
      }
    }else if(f[2]){
      for(int i=0;i<5;i++){
	cout << 3 << endl;
      }
    }else{
      for(int i=0;i<5;i++){
	cout << 3 << endl;
      }
    }
  }
  return 0;
}

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

using namespace std;

typedef long long ll;

int main() {
    ll x;
    cin >> x;
    ll k = (x + 10) / 11;
    ll r = x % 11;
    if (1 <= r && r <= 6) cout << 2 * k - 1 << endl;
    else cout << 2 * k << endl;
}

Measured memory_bytes: 256
import sys

N = int(input())
dp = [sys.maxsize] * N
steps = list(map(int, input().split()))

dp[0] = 0

for n in range(1, N):
    step1_diff = abs(steps[n] - steps[n-1]) + dp[n-1]
    dp[n] = step1_diff
    if n >= 2:
        step2_diff = abs(steps[n] - steps[n-2]) + dp[n-2]
        if dp[n] > step2_diff:
            dp[n] = step2_diff
print(dp[-1])

Measured memory_bytes: 14696
#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n; cin >> n;
    int m; cin >> m;
    int c; cin >> c;
    int count = 0;
    vector<int> b(m);
    vector<vector<int> > a(n,vector<int>(m));
    for (int i= 0; i < m; i++){
        cin >> b[i];
    }
    for (int i = 0; i < n; i++){
        for (int k = 0; k < m; k++){
            cin >> a[i][k];
        }
    }

    for (int i = 0; i < n; i++){
        int sum = c;
        for (int k = 0; k < m; k++){
            sum += b[k]*a[i][k];
        }
        if (sum > 0){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
import collections
N=int(input())
if N==1:
    print(0)
    exit()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
c = collections.Counter(prime_factorize(N)) 
s=list(set(prime_factorize(N)))
ans=0
def a(n):
    return (1/2)*n*(n+1)
def f(n):
    ans=0
    x=1
    while n>=a(x):
        x+=1
        ans+=1
    return ans
for i in s:
    x=c[i]
    ans+=f(x)
print(ans)

        










        

    









    

        




    















    



    





    






        






    
















        


























            
    


    


    
    














    


    














Measured memory_bytes: 9472
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

LL N, cou, res, ans;
std::vector<std::vector<std::vector<LL>>>F(112, std::vector<std::vector<LL>>(5, std::vector<LL>(2)));
std::vector<std::vector<LL>>P(112, std::vector<LL>(11));

int main()
{
	in >> N;
	rep(i, N) { rep(j, 5) { rep(k, 2) { in >> F[i][j][k]; } } }
	rep(i, N) { rep(j, 11) { in >> P[i][j]; } }

	ans = -11234567890;
	rep(bit, (1 << 10))
	{
		if (bit == 0) { continue; }
		res = 0;
		rep(i, N)
		{
			cou = 0;
			rep(j, 10)
			{
				if ((bit&(1 << j)) && F[i][j / 2][j % 2] == 1)
				{
					++cou;
				}
			}
			res += P[i][cou];
		}
		ans = std::max(ans, res);
	}

	out << ans << std::endl;
	return 0;
}

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

int main(){

    ll N;
    cin >> N;

    ll buf = N;
    map<ll, ll> divisor;
    ll div = 2;
    ll thr = sqrt(N);
    bool flg = false;

    // 素因数分解
    if (buf == 1) {
        cout << 0 << endl;
        return 0;
    }
    else {
        for (div=2; div<thr+1; div++){
            while (buf%div == 0){
                buf /= div;
                divisor[div]++;
                flg = true;
            }
        }

//        if (flg == false) {
//            divisor[N]++;
//        }
        if (buf != 1) {
            divisor[N]++;
        }
    }

    // 次数をカウント
    ll ans = 0;
    for (auto p: divisor){
        auto value = p.second;

        int sub = 1;
        while (value - sub >= 0){
            value -= sub;
            sub++;
            ans++;
        }
    }

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

Measured memory_bytes: 3740
# coding: utf-8

INF = 1 << 60
n = int(input().rstrip())
r = [0 for _ in range(n+10)]
c = [0 for _ in range(n+10)]
# i番目の行列からj番目の行列までの最小値
dp = [[INF for _ in range(n+10)] for _ in range(n+10)]
for i in range(n):
    line = input().rstrip().split()
    r[i] = int(line[0])
    c[i] = int(line[1])
    
for i in range(n):
    dp[i][i] = 0

# 行列の距離が近い方から計算しなくてはいけない！
for l in range(1,n):
    for i in range(n - l):
        j = i + l
        for k in range(i,j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + r[i]*c[k]*c[j])
            
print(dp[0][n-1])


Measured memory_bytes: 5772
import scala.annotation.tailrec

object Main{
	@tailrec
	def gcd(a:Int,b:Int):Int ={
		if(b==0) a else gcd(b,a % b)
	}
	def main(args:Array[String]){
		val s = new java.util.Scanner(System.in)
		val n = s.nextInt
		val a = Array.fill(n)(s.nextInt)
		val l,r = Array.fill(n + 2)(0)
		for(i <- 1 to n)
			l(i) = gcd(l(i - 1),a(i - 1))
		for(i <- n to 1 by -1)
			r(i) = gcd(r(i + 1),a(i - 1))
		println((1 to n).map(i => gcd(l(i - 1),r(i + 1))).max)
	}
}

Measured memory_bytes: 51788
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	ll mx=0;
	cin>>n;
	vl a(n+2);
	rep(i,n)cin>>a[i+1];
	vl sum(n+2);
	rep(i,n){
		ll t=(a[i+1]==0?-1:(a[i+1]+1)/2*2-1);
		sum[i+1]=sum[i]+t;
	}
	mx=accumulate(all(a),0LL);
	//cout<<sum<<endl;;
	vl rsum(n+2),lsum(n+2);
	ll cur=0,mn=0;
	rep(i,n){
		ll t=(a[i+1]==0?-2:a[i+1]/2*2);
		cur+=t;
		chmin(mn,cur);
		lsum[i+1]=cur-mn;
	}
	cur=0;mn=0;
	rrep(i,n){
		ll t=(a[i+1]==0?-2:a[i+1]/2*2);
		cur+=t;
		chmin(mn,cur);
		rsum[i+1]=cur-mn;
	}
	vl lans(n+2);
	vl rans(n+2);
	rep(i,n+2){
		lans[i]=rans[i]=sum[i];
	}
	rep(i,n){
		lans[i+1]-=lsum[i+1];
	}
	rep(i,n){
		rans[i+1]+=rsum[i+2];
	}
	ll ans=0;mn=LINF;
	ll ansmx=-LINF;
	ll l,r,rr;
	/*
	cout<<lsum<<endl;
	cout<<rsum<<endl;
	cout<<lans<<endl;
	cout<<rans<<endl;
	*/
	range(i,0,n+1){
		if(chmin(mn,lans[i]))rr=i;
		ll t=rans[i]-mn;
		if(ansmx<t){r=i;l=rr;ansmx=t;}
	}
	//cout<<l<<" "<<r<<endl;
	cout<<mx-ansmx<<endl;
}

Measured memory_bytes: 9600
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define REP(i, b, n) for (Int i = b; i < Int(n); i++)
#define rep(i, n) REP(i, 0, n)
using namespace std;
using Int = long long;
Int inf = 1000000000000000001LL;
using vi = vector<Int>;
using vvi = vector<vi>;
using pii = pair<Int,Int>;
using mapis = unordered_map<Int,string>;
using mapii = unordered_map<Int,Int>;

Int GCD(Int a, Int b){
    if(b==0) return a;
    if(a < b) return GCD(b, a);
    unsigned r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

Int LCM(Int a, Int b){
    return a*b/GCD(a,b);
}

int main() {
    Int N,M,P;
    cin >> N >> M >> P;

    // 頂点[i]はいくつかの[to,cost]の辺を持つ
    // usingで定義したら楽そう
    vector<vector<pair<Int,Int>>> edges = vector<vector<pair<Int,Int>>>(N+1);
    vector<Int> cost = vi(N+1,inf);

    // スタート地点のコストは0
    cost[1] = 0;

    // 初期化
    rep(i,M){
        Int a,b,c;
        cin >>a >>b >>c;
        // ここを -c にすると最短経路じゃなくて最長経路を求められる
        edges[a].push_back(make_pair(b,-c+P));
    }

    // ループ検出
    bool is_loop = false;

    // 経路たどり
    vi pre = vi(N+1);

    REP(i,1,N+1){
        REP(j,1,N+1){
            rep(k,edges[j].size()){
                pii now = edges[j][k];
                // 行き先のコスト > 今のとこまでのコスト+行き先までの辺のコスト
                if(cost[j] != inf && cost[now.first] > cost[j] + now.second ){
                    cost[now.first] = cost[j]+now.second;
                    pre[now.first] = j;
                    // iがN(頂点数)を超えるってことは、どこかに負の総和のループがある
                    if (i == N) {
                        is_loop = true;
                        break;
                    }
                }
            }
        }
    }

    // このチェックは、あるstartからgoalまでの間に限って負の経路があるかを調べる
    int check = N;
    for(int i = N; i>0; i--){
        check = pre[check];
        if(check == 0) break;
    }

    // 全体に負の経路が混じってる && それが今回調べたいゴール地点の間にあるかどうか
    if(is_loop && check!=0){
        cout << -1 << endl;
    }else{
        // Nまでの最短経路のコストを出せる
        Int ans = -1*cost[N];
        if(ans<0){
            ans = 0;
        }

        cout << ans << endl;
    }


    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
int main(void){
    int n,t[110],m,p[110],x[110],ans,sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&t[i]);
        sum+=t[i];
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        ans=sum;
        scanf("%d %d",&p[i],&x[i]);
        ans-=t[p[i]-1];
        ans+=x[i];
        printf("%d\n",ans);
    }
    return 0;
}


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

int main() {
    ll t1, t2, a1, a2, b1, b2;
    cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
    if (t1 * a1 + t2 * a2 == t1 * b1 + t2 * b2) {
        cout << "infinity" << endl;
        return 0;
    }
    ll max1, max2, min1, min2;
    if (t1 * a1 + t2 * a2 < t1 * b1 + t2 * b2) {
        max1 = b1;
        max2 = b2;
        min1 = a1;
        min2 = a2;
    } else {
        max1 = a1;
        max2 = a2;
        min1 = b1;
        min2 = b2;
    }
    if (min1 == max1) {
        cout << "infinity" << endl;
        return 0;
    }
    if (min1 < max1) {
        cout << 0 << endl;
        return 0;
    }

    // ll max_diff = (min1 - max1) * t1;
    // ll phase_diff = (max1 - min1) * t1 + (max2 - min2) * t2;
    // ll ans = (max_diff + phase_diff - 1) / phase_diff;

    ll max_diff = (min1 - max1) * t1;
    ll phase_diff = (max1 - min1) * t1 + (max2 - min2) * t2;
    ll ans = max_diff / phase_diff;

    ans *= 2;
    ans++;
    if (max_diff % phase_diff == 0) ans--;
    cout << ans << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-       
import itertools


a = input()
op = ['+','-']
pro = list(itertools.product(op, repeat=3))

for i in pro:
    c = a[0]+i[0]+a[1]+i[1]+a[2]+i[2]+a[3]
    if(eval(c)==7):
        print(c+'=7')
        break

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

struct edge{
    int to, id;
    edge(){}
    edge(int a, int b){to = a, id = b;}
};

vector<vector<edge> > G(50, vector<edge>(0));
vector<bool> used(50);
ll dfs(int v, int goal){
    if(v == goal) return 0;
    used[v] = true;
    for(edge e : G[v]){
        if(!used[e.to]){
            ll temp = dfs(e.to, goal);
            if(temp != -1) return temp | (1LL<<e.id);
        }
    }
    return -1;
}

ll fastpow(ll a, ll pw) {
	ll res = 1;
	while (pw) {
		if (pw & 1) res = res * a;
		a = a * a ;
		pw >>= 1;
	}
	return res;
}
int main(){
    cin>>N;
    rep(i,N-1){
        cin>>A>>B;
        --A; --B;
        G[A].emplace_back(B, i);
        G[B].emplace_back(A, i);
    }
    cin>>M;
    vec num(1LL<<M);
    rep(i,M){
        int a, b;
        cin>>a>>b;
        --a; --b;
        rep(j,50) used[j] = false;
        num[(1LL<<i)] = dfs(a, b);
    }
    ll ans = fastpow(2, N - 1);
    reps(i,1,(1LL<<M)){
        int e_num = 0, bit_num = 0;
        rep(j,M) bit_num += (i>>j)&1;
        if(bit_num != 1) {
            ll temp = i & (i - 1);
            num[i] = num[i ^ temp] | num[temp];
        }
        rep(j,N - 1) e_num += (num[i]>>j)&1;
        ll temp = fastpow(2, N - 1 - e_num);
        (ans += (bit_num&1 ? - temp : temp));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 8448
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

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

#define for01(k,n)  for (ll i=k; i<n; i++)
#define for02(k,n)  for (ll j=k; j<n; j++)
#define for03(k,n)  for (ll k=k; k<n; k++)
#define for11(k,n)  for (ll i=k; i<=n; i++)
#define for12(k,n)  for (ll j=k; j<=n; j++)
#define for13(k,n)  for (ll k=k; k<=n; k++)

#define pb push_back
#define mp make_pair
#define pf push_front
#define popf pop_front
#define popb pop_back
#define vll vector<ll>
#define f first
#define s second
#define pp pair <ll, ll>
#define lb lower_bound
#define ub upper_bound
#define emp empty()
#define beg begin()
#define en end()
#define si size()
#define bk back()
#define deci(n)  fixed<<setprecision(n)
#define mll map<ll,ll>
#define mint map<int,int>
#define mll_it map<ll,ll>::iterator
#define mint_it map<int,int>::iterator

#define p0(a) cout << a << " "
#define p1(a) cout << a << "\n"

#define mem(a,n) memset(a, n, sizeof(a)); // n = 0 OR -1 only

#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define MOD1 1000000007
#define MOD2 998244353

#define BOOST ios_base::sync_with_stdio(false); cin.tie(NULL)



// CUSTOM HASH FUNCTION - O(1)
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};


//gp_hash_table - Open Address Hash Table

//gp_hash_table<int, int> table;

const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
//gp_hash_table<key, int, chash> table;


// Indexed Set
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indSet;

/* FUNCTIONS:
1. The function "find_by_order" returns an iterator to the element at a given position:
2. The function "order_of_key" returns the position of a given element
	-> If the element does not appear in the set, we get the position that the element
	   would have in the set
	-> O(log n)*/

void swap(multimap<char, int>& mp1, multimap<char, int>&mp2, char c1, char c2)
{
    auto it1 = mp1.find(c1);
    auto it2 = mp2.find(c2);

    //p1(it1->s << " " << it2->s);
    mp1.erase(it1);
    mp2.erase(it2);

    mp1.insert(mp(c2, it2->s));
    mp2.insert(mp(c1, it1->s));
}


int main()
{
  BOOST;
  ll X;
  cin >> X;
  ll sum = 0;
  for(int i = 1; ; i++)
  {
     sum += i;
     if(sum >= X)
     {
       cout << i << endl;
  	   return 0;
     }
  }
  
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.regex.Pattern;
import java.util.stream.Stream;

public class Main {
  public static void main(String[] args) {

    new Main().run();
  }

  public void run() {
    
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      String line = br.readLine();
      final Pattern delim = Pattern.compile("\\s");
      int[] arrayS = delim
        .splitAsStream(line)
        .parallel()
        .mapToInt(Integer::parseInt)
        .toArray();

      OptionalInt max =
        Arrays.stream(arrayS).max();

      dispIntArray( countingSort(arrayS, max.getAsInt()) );
    }
    catch ( IOException e ) {
      System.out.println("IOException!");
    }

  }

  public int[] countingSort(int[] a, int k) {

    int   aLength = a.length;
    int[] result  = new int[aLength];
    int[] counter = new int[k+1];

    for (int var : a) {
      counter[var]++;
    }

    for (int i=1, max=k+1; i < max; i++) {
      counter[i] += counter[i-1];
    }

    for (int i=aLength-1, val=0; i>=0; i--) {
      val = a[i];
      result[counter[val]-1] = val;
      counter[val]--;
    }

    return result;
  }

  public void dispIntArray(int[] target) {
    StringBuilder s = new StringBuilder();

    for (int i : target) { s.append(i).append(" "); }
    s.setLength(s.length()-1);

    System.out.println(s);
  }
}


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

int main() {
	int first = 0;
	int second = 0;
	int third = 0;

	for (int i = 0; i < 10; i++) {
		int num;

		cin >> num;

		if (first <= num) {
			third = second;
			second = first;
			first = num;
		}
		else if ((second <= num) && (num < first)) {
			third = second;
			second = num;
		}
		else if ((third <= num) && (num < second)) {
			third = num;
		}
		else {
			//???????????????
		}
	}
	cout << first << endl;
	cout << second << endl;
	cout << third << endl;

	return 0;
}

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;

  if (A + B > C + D) {
    cout << "Left" << endl;
  }
  else if (A + B < C + D){
    cout << "Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
const ll mod = 1000000007;
// const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"
#define TO_STRING(VariableName) # VariableName

template <typename T>ostream &operator<<(ostream &out,const vector<T> &v) {rep(i,(int)v.size()-1)cout<<v[i]<<" ";cout<<v[(int)v.size()-1];return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const map<T1, T2> &p) {out << "(" << p.first << ", " << p.second << ")";return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const pair<T1, T2> &p){out << "(" << p.first << ", " << p.second << ")";return out;}
template<class T>void debag(const T &obj){cout<<obj<<endl;}

map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

ld f(vector<ll>a){
	sort(all(a));
	ll n=a.size();
	if(n%2==0)return (ld)((ld)a[n/2]+(ld)a[n/2-1])/(ld)2;
	else return a[n/2];
}


signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(30);
 ll n;cin>>n;
	vector<ll>a(n);
	vector<ll>b(n);
	rep(i,n)cin>>a[i]>>b[i];
	ld x=f(a);
	ld y=f(b);
	ld ans;
	if(n%2==0){
		ans=(y-x)/0.5+1;
	}else ans=(y-x)/1+1;
		
	cout<<(ll)ans<<endl;
}


Measured memory_bytes: 7928
#include <bits/stdc++.h>
#define N 1000005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("myfile.in","r",stdin);freopen ("myfile.out","w",stdout);
#define mod 1000000007
#define fs(x,y) for(int i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(int i=x;i<=y;i++)
using namespace std;

ll n,m,ar[N],sum;


int main()
{
	fast;
	// cin>>n;
	fs(ar,5);
	fo(i,1,5)
	{
		// ar[i]+=9;
		int x=ar[i]+9;
		ll k=x/10;
		k*=10;
		sum+=k;
	}
	ll mn=10;
	// cout<<sum<<endl;
	fo(i,1,5)
	{
		// cout<<ar[i]%10<<sp;
		if(ar[i]%10!=0)
		mn=min(mn,ar[i]%10);
	}
	// cout<<endl;
	if(mn!=10)
		sum-=(10-mn);
	cout<<sum;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>

using namespace std;

// http://d.hatena.ne.jp/Nekonyan/20110508 
// Nekonyanツつウツづアツづ個コツーツドツづーツ参ツ考ツづ可つオツづ慊つオツつスツ。

int table[10+1][9697];
int memo[10];

void numnum (int size, int depth, int sum )
{
	if (size + 1 == depth ) {
		table[size][sum]++;
	}else{
		for (int i = 0; i <= 9; ++i ){
			if ( memo[i] == 0 ) {
				memo[i] = 1;
				numnum (size, depth + 1, sum + i*depth );
				memo[i] = 0;
			} // end if
		} // end for
	} // end if
}

int main()
{
	memset(table, 0, sizeof (table ) );

	for (int i = 1; i <= 10; ++i ) {
		memset (memo, 0, sizeof (memo ) );
		numnum (i, 1, 0 );
	} // end for

	int n, s;
	while ( cin >> n >> s ) {
		cout << table[n][s] << endl;
	} // end while

	return 0;
}

Measured memory_bytes: 1168
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll N;
    cin >> N;
    ll M=N/100;
    if(4<=M&&M<=5)cout<<8<<endl;
    else if(6<=M&&M<=7)cout<<7<<endl;
    else if(8<=M&&M<=9)cout<<6<<endl;
    else if(10<=M&&M<=11)cout<<5<<endl;
    else if(12<=M&&M<=13)cout<<4<<endl;
    else if(14<=M&&M<=15)cout<<3<<endl;
    else if(16<=M&&M<=17)cout<<2<<endl;
    else if(18<=M&&M<=19)cout<<1<<endl;
    return 0;
}

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

typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define all(a) begin(a),end(a)
template<class T> inline void sort_uniq(T& c) { sort(ALL(c)); c.erase(unique(ALL(c)), c.end()); }
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_v(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << endl; }
template<class K, class V> void cout_v(map<K, V>& m)
{ for(auto it=m.begin();it!=m.end();it++)cout<<it->first<<":"<<it->second<<endl;}
template<class T> void cout_h(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
inline int powi(int x,int y) {int p=1; while(y--) p*=x; return p;}
template<class T> inline bool is_overlap(const T& a, const T& b, const T& p, const T& q)
{ return p <=b && a <= q; }
#define MOD = 1000000007;
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
void yes(bool f){cout<<(f?"yes":"no")<<endl;}
void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
void YES(bool f){cout<<(f?"YES":"NO")<<endl;}

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    int N, Q; cin >>N>>Q;
    string S; cin >> S;
    vector<int> T(N, 0);
    rep(i, S.size()-1) {
        T[i+1] = T[i] + ((S[i] == 'A' && S[i+1] == 'C') ? 1 : 0);
    }
    
    rep(i, Q) {
        int ans = 0;
        int l, r;
        cin >> l >> r;
        ans = T[r - 1] - T[l - 1];
        cout << ans << endl;
    }
}


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

#define int long long

int n,a,b,c,d;

inline int read(){
	int s=0,t=1;
	char c=getchar();
	while((c<'0'||c>'9')&&c!='-')c=getchar(),t=-1;
	if(c=='-')c=getchar(),t=-1;
	while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+(c^48),c=getchar();
	return s*t;
}

signed main(void){
	n=read();
	a=read();
	b=read();
	c=read();
	d=read();
	for(int i=1;i<n;i++){
		if(i*c-(n-1-i)*d<=b-a&&b-a<=i*d-(n-1-i)*c){
			printf("YES\n");
			return 0;
		}
	}
	printf("NO\n");
} 

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

int main(){
    long long n, k;

    cin >> n >> k;

    long double p[n+1];

    int a;
    for(long long i = 1; i <= n; i++){
        cin >> a;
        long double sum = 0;
        for(int j = 1; j <= a; j++){
            sum += j;
        }
        p[i] = sum/(long double)a;

    }

    vector<long double> S(n+1, 0);

    for(long long i = 1; i <= n; i++){
        S[i] = S[i-1] + p[i];
    }
    long double maxv = 0;
    for(long long i = 1; i + k-1 <= n; i++){
        maxv = max(S[i+k-1] - S[i-1], maxv);
    }

    printf("%.10Lf\n", maxv);

    return 0;
    
}

Measured memory_bytes: 6528
//
// Union-Find tree
//
// verified:
//   AOJ Course DSL_1_A Set - Disjoint Set: Union Find Tree
//     http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp
//

// root(x): root node of x
// size(x): the size of the group of x

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n) { for (int i = 0; i < n; ++i) par[i] = i;  }
    void init(int n) { par.resize(n); for (int i = 0; i < n; ++i) par[i] = i; }
    
    int root(int x) {
        if (par[x] == x) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        par[x] = y;
        return true;
    }
};



int main() {
    int N, Q; cin >> N >> Q;
    UnionFind uf(N);
    for (int q = 0; q < Q; ++q) {
        int com, x, y; cin >> com >> x >> y;
        if (com == 0) uf.merge(x, y);
        else {
            if (uf.issame(x, y)) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }
}


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

using namespace std;
typedef long long LL;

#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}
}star;
#define DEBUG if(0)
#endif

#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}

class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};
LL gcd(LL a, LL b) {
	return (b == 0) ? a : gcd(b, a%b);
}
int main() {
	int N;
	LL X;
	cin >> N >> X;
	LL g = 0;
	for (int i : range(N)) {
		LL y;
		cin >> y;
		g = gcd(g, abs(X - y));
	}
	cout << g << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <queue>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
typedef long long ll;
typedef pair<int,int> P;
int main() {
    int n,l;
    cin >> n >> l;
    vector<string>s(n);
    rep(i, 0, n){
        cin >> s[i];
    }
    sort(s.begin(), s.end());
    string ans = "";
    rep(i, 0, n){
        ans += s[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 3584
using System;
using System.Linq;

public class Hello
{
    public static void Main()
    {
        // Your code here!
        int[] input = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
        int N = input[0];
        int K = input[1];

        if(N % K == 0)
        {
            Console.WriteLine(0);
        }
        else
        {
            Console.WriteLine(1);
        }
    }
}

Measured memory_bytes: 13268
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
N, M = inpl()

E = []
for _ in range(M):
    E.append(inpl())

E = sorted(E, key=lambda x: [x[1], x[0]])

ans = 0
c = 0
for a, b in E:
    if a < c:
        continue
    else:
        ans += 1
        c = b
print(ans)

Measured memory_bytes: 38328
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int cnt[N] = {0}, n, m;

int main() {
    cin >> n >> m;
    while (m--) {
        int u, v; cin >> u >> v;
        cnt[u]++; cnt[v]++;
    }
    for (int i = 1; i <= n; i++) cout << cnt[i] << " ";
}


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

int main(){
  int a,b,c,x;
  cin>>a>>b>>c>>x;
  int d=0;
  rep(i,0,a+1){
    rep(j,0,b+1){
      rep(k,0,c+1){
        if(500*i+100*j+50*k==x) d++;
      }
    }
  }
  cout<<d<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#define cin (type == 0?cin:fin)
//#define cout (type == 0?cout:fout)
#define tcn cin.tie(0);
#define tct cout.tie(0);
#define r_0 return 0
#define ll long long
#define TIME ios_base::sync_with_stdio(0);
using namespace std;

const long long N = 2e5 + 7;
const long long MrBeast = 1e9;


ll T = 1, n, u[N], m, pluse, minuse, NAZSHO, cnt, ans;
vector < ll > v, t;
int type = 0;
set< ll > st;
pair< ll ,ll > p[N];
int main()
{
    TIME
    //ifstream  fin("swap.in");
    //ofstream  fout("swap.out");
    cin >> n;
    for ( int i=1; i<=n; i++ ){
        for ( int j=1; j<=n; j++ ){
            for ( int x=1; x<=n; x++ ){
                cnt += __gcd( i, __gcd(j, x) );
            }
        }
    }
    cout << cnt;
}


Measured memory_bytes: 3656
#include <fstream>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <random>

using namespace std;

int main(int argc, const char * argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int s;
    cin >> s;


int a,b;
if(s==2){
cin>>a>>b;
cout << a+b <<endl;
       }else{
cout << "Hello World" << endl;
}
    return 0;
}

Measured memory_bytes: 256
import itertools
h,w,k=map(int,input().split())
c=[list(input()) for _ in range(h)]
h_list=list(range(h))
w_list=list(range(w))
ans=0
cnt=0
for i in range(h):
  for j in range(w):
    if c[i][j]=="#":
      cnt+=1
if cnt==k:
  ans+=1
  
for i in range(1,h):
  for j in itertools.combinations(h_list, i):
    cnt=0
    for b in j: 
      cnt+=c[b].count("#")
    if cnt==k:
      ans+=1
      
for i in range(1,w):
  for j in itertools.combinations(w_list, i):
    cnt=0
    for b in j:
      for m in range(h):
        if c[m][b]=="#":
          cnt+=1
    if cnt==k:
      ans+=1

for i in range(1,h):
  for j in range(1,w):
    for l in itertools.combinations(h_list, i):
      for m in itertools.combinations(w_list, j):
        cnt=0
        for a in l:
          for b in m:
            if c[a][b]=="#":
              cnt+=1
        if cnt==k:
          ans+=1
print(ans)

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
ll N, W;
ll w[105];
ll v[105];
ll dp[105][105][305];
ll w0;

int main() {
    //cout.precision(10);
    cin >> N >> W;
    for(int i = 1; i <= N; i++) {
        cin >> w[i] >> v[i];
    }
    w0 = w[1];
    ll ans = 0;
    for(int i = 1; i <= N; i++) w[i] -= w0;
    for(int item = 1; item <= N; item++) {
        for(int num = 1; num <= N; num++) {
            for(int weight = 0; weight <= 300; weight++) {
                dp[item][num][weight] = dp[item-1][num][weight];
                if(weight >= w[item]) dp[item][num][weight] = max(dp[item][num][weight], dp[item-1][num-1][weight-w[item]] + v[item]);
                if(num * w0 + weight <= W) ans = max(ans, dp[item][num][weight]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 25216
n=int(input())
a=list(map(int,input().split()))
a.insert(0,0)
a.append(0)
total=0
for i in range(1,n+2):
    total+=abs(a[i]-a[i-1])
for i in range(1,n+1):
    print(total-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]))

Measured memory_bytes: 14044
n,m=map(int,input().split())
Ship_1,Ship_n=[False]*n,[False]*n
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        Ship_1[b-1]=True
    if a==n:
        Ship_n[b-1]=True
    if b==1:
        Ship_1[a-1]=True
    if b==n:
        Ship_n[a-1]=True
for i in range(n):
    if Ship_1[i] and Ship_n[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 6260
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

bool judge(ll X){
    for (ll i = 2; i * i <= X; ++i) if(X % i == 0) return false;
    return true;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    ll A, B;
    cin >> A >> B;

    set<ll> p;
    ll G = gcd(A,B);

    for (ll i = 1; i * i <= G; ++i){
        if(G % i == 0){
            p.insert(i);
            p.insert(G / i);
        }
    }

    ll ans = 0;
    for(auto P : p) ans += judge(P);
    print(ans);

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
 
int main(){

    int n;
    cin >> n;

    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        if(a %2 == 0 && a % 3 && a %5){
            cout << "DENIED" << endl;
            return 0;
        }
    }

    cout << "APPROVED" << endl;

}

Measured memory_bytes: 256