akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

///******************************** C o n t a i n e r ********************************///

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;

///*********************************** C o n s t ***********************************///

const int       N=1e6+3;
const double    PI = acos(-1);
const ll        MOD=1000000007;                 ///1e9+7
ll dx[] = {+1, 0, -1, 0, +1, +1, -1, -1};       ///first 4 for adjacent
ll dy[] = {0, +1, 0, -1, +1, -1, +1, -1};
ll dx8[]= {+1, +1, -1, -1, +2, +2, -2, -2};    ///knights move
ll dy8[]= {+2, -2, +2, -2, +1, -1, +1, -1};

///********************************** M a r c o ***********************************///

#define pb push_back
#define F first
#define S second
#define test int tc; cin>>tc; while(tc--)
#define forn(i,n) for(i=0;i<n;i++)
#define rforn(i,n) for(i=n-1;i>=0;i--)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) x.size()
#define el <<'\n'
#define sp <<' '
#define print(a) {for(auto x:a)cout<<x<<" ";cout<<endl;}
#define mem(a,b) memset(a, b, sizeof(a))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define sqr(a) (a)*(a)

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

///*********************************** F u n c t i o n ***********************************///

ll powmod(ll a,ll b){ll p=MOD;a%=p;if(!a) return 0;ll pr=1;while(b>0){if(b&1){pr*=a;pr%=p;--b;}a*=a;a%=p;b/=2;}return pr;}
ll modinverse(ll a){return powmod(a,MOD-2);}
bool isPrime(ll n){ if(n<=1)return false;if(n<=3)return true;if(n%2==0 or n%3==0)return false;for(ll i=5;i*i<=n;i+=6){if(n%i==0 or n%(i+2)==0)return false;}return true;}
void seive(bool a[]){ll mx=sqrt(N),ii,jj;for(ii=3;ii<=mx;ii+=2)if(!a[ii])for(jj=ii*ii;jj<=N;jj+=2*ii)a[jj]=true;}
void numofdiv(ll a[]){ll mx=sqrt(N),ii,jj;for(ii=1;ii<=mx;ii++){for(jj=ii*ii;jj<=N;jj+=ii){if(jj==ii*ii) a[jj]++; else a[jj]+=2;}}}
void sumofdiv(ll a[]){ll mx=sqrt(N),ii,jj;for(ii=1;ii<=mx;ii++){for(jj=ii*ii;jj<=N;jj+=ii){if(jj==ii*ii) a[jj]+=ii; else a[jj]+=ii+jj/ii;}}}

///**************************************************** C o d e ****************************************************///
///-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=///


void _case()
{
    ll n,i,ans=0;
    cin>>n;
    ll a[n];
    forn(i,n) cin>>a[i];
    for(i=1;i<n;i++){
        ans+=max(0LL,a[i-1]-a[i]);
        if(a[i-1]>a[i]) a[i]=a[i-1];
    }
    cout<<ans el;
}

main()
{
    fastio();
    _case();

}


///Thank you.


///Brainless_Loco Terminates Here!


Measured memory_bytes: 5232
# -*- coding: utf-8 -*-

def do_binary_search(target_value, target_list, target_list_length=None):
    left = 0
    right = target_list_length

    while right - left > 0:
        mid = (right + left) / 2
        key = target_list[mid]
        if key == target_value:
            return True
        elif target_value < key:
            right = mid
        else:
            left = mid + 1
    return False



def main():
    s_length = int(raw_input())
    s = [int(x) for x in raw_input().strip().split(' ')]
    t_length = raw_input()
    t = [int(x) for x in raw_input().strip().split(' ')]

    counter = 0
    for value in t:
        counter += int(do_binary_search(value, s, s_length))

    print counter 

if __name__ == '__main__':
    main()

Measured memory_bytes: 15140
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		int N = nextInt();
		HashSet<Integer> used = new HashSet<Integer>();
		used.add(N);
		while(true){
			int ato = F(N);
			if(used.contains(ato)){
				myout(used.size() + 1);
				return;
			}
			used.add(ato);
			N = ato;
		}
	}
	//Method addition frame start

static int F(int v){
	if(v % 2 == 0){
		return v / 2;
	}else{
		return 3 * v + 1;
	}
}

	//Method addition frame end
}


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

using namespace std;
using ll = long long;

const int mx = 2e5 + 9;

int a[mx];
int pos[mx];

int main() {
    int n; ll k; scanf("%d %lld", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    memset(pos, -1, sizeof pos);
    vector <int> v;
    v.push_back(1);
    pos[1] = 0;

    int cycle_length = -1;
    int cycle_start = -1;
    while (true) {
        int x = v.back();
        if (pos[a[x]] != -1) {
            cycle_length = pos[x] - pos[a[x]] + 1;
            cycle_start = pos[a[x]];
            break;
        }

        pos[a[x]] = pos[x] + 1;
        v.push_back(a[x]);
    }

    ll sz = v.size();
    if (k < sz) {
        printf("%d\n", v[k]);
        return 0;
    }

    k -= cycle_start;
    k %= cycle_length;
    printf("%d\n", v[cycle_start + k]);
}

Measured memory_bytes: 5900
N = int(input())
d = N%10
if d == 2 or d == 4 or d == 5 or d == 7 or d == 9 :
    print("hon")
elif d == 0 or d == 1 or d == 6 or d == 8:
    print("pon")
else:
    print("bon")

Measured memory_bytes: 9128
S = int(input())
top = S // 100 #上2桁
bottom = S % 100 #下2桁

#flag 1→MMになれる 2:YYになれる(MMになれない)
topFlag = 2
bottomFlag = 2
if 1 <= top and top <= 12:
    topFlag = 1

if 1 <= bottom and bottom <= 12:
    bottomFlag = 1

#形式の判別
if topFlag == 1 and bottomFlag == 1:
    print("AMBIGUOUS")
elif topFlag == 1 and bottomFlag == 2:
    print("MMYY")
elif topFlag == 2 and bottomFlag == 1:
    print("YYMM")
else:
    print("NA")

Measured memory_bytes: 3064
a,b = map(int,input().split())

if a<0 and b>0:
    print("Zero")
    exit()

if a < 0 and b <= 0:
    if (a-b)%2 == 0:
        print("Negative")
    else:
        print("Positive")

if a>0 and b>0:
    print("Positive")


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

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

//C++14 (GCC 5.4.1)
int main() {
    int N,M;
    cin >>N>>M;

    vector<bool> DELOVE(M,true);
    int K,A;
    rep(i,N){
        cin >>K;
        vector<bool>HELOVE(M,false);
        rep(j,K){
            cin >> A;
            HELOVE[A-1]=true;
        }
        rep(i,M){
            DELOVE[i]=DELOVE[i] && HELOVE[i];
        }
        
    }
    
    //-----------------------------------
    int ans=0;
    rep(i,M){
        if(DELOVE[i])ans++;
    }


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

Measured memory_bytes: 256
def main():
    n = int(input())
    a = list(map(int,input().split()))
    cnt = 0
    for i in range(n):
        if (i+1) < a[i] and a[a[i]-1] == (i+1):
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()


Measured memory_bytes: 52912
N,K=$<.read.split.map(&:to_i)
MOD=10**9+7

fac = []
finv = []
inv = []
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
i = 2
while i < N
	fac[i] = fac[i - 1] * i % MOD
  inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD
  finv[i] = finv[i - 1] * inv[i] % MOD
  i += 1
end

def comb(n,k,fac,finv)
  return 0 if n < k
	return 0 if n < 0 || k < 0
  fac[n] * (finv[k] * finv[n-k] % MOD) % MOD
end

blue = K
red = N-K
1.upto(K) do |i|
    if red < i-1 
        puts 0
    else
        # p [comb(K-1,i-1,fac,finv), comb(K,i,fac,finv)]
        puts comb(K-1,i-1,fac,finv) * comb(N-K+1,i,fac,finv) % MOD
    end
end

# x = 3
# 1.upto(x) do |i|
#     puts comb(x,i,fac,finv)
# end

Measured memory_bytes: 14336
//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
#include<cstring>
#include<sstream>
#include <iomanip>

typedef long long ll ;
typedef double db;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define for0(i,n)          for(int i=0;i<n;i++)
#define for1(i,n)          for(int i=1;i<=n;i++)
#define forab(a,b)       for(int i=a;i<=b;i++)
//#define gcd(a, b)     __gcd(a, b)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
#define abs(x)		fabs(x)
#define pcase(z,x)     cout<<"Case "<<z<<": "<<x<<"\n"
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)
ll m=2019;
ll modexp(ll a,ll b,ll m)
{
    ll r=1;
    a=a%m;
    while(b>0)
    {
        if(b&1)r=(r*a)%m;
        b = b>>1;
        a=(a*a)%m;
    }
    return r%m;
}

using namespace std;

int main()
{
	string s;
	cin>>s;
	ll i,n=0;
	ll l = s.size();
	vector<ll>c(m,0);
	reverse(s.begin(),s.end());
	for(i=0 ; i<l ; i++){
		n= (n + (s[i]-'0')*modexp(10,i,m))%m;
		//mm[a[i]]++;
		//cout<<n<<nw;
		c[n]++;
		}
	ll ans = 0;
	for(i=0 ; i<m ; i++){
		ans += (c[i]* (c[i]-1))/2;
		}
	ans += c[0];
	cout<<ans<<nw;
	
	
	return 0;
}

Measured memory_bytes: 3760
N = int(input())
A = list(map(int, input().rstrip().split()))
B = list(map(int, input().rstrip().split()))
candy_max = 0
for i in range(N):
    if candy_max < (sum(A[:i + 1]) + sum(B[i:N])):
        candy_max = (sum(A[:i + 1]) + sum(B[i:N]))
print(candy_max)


Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

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

#define ll long long
#define ld long double
#define F first
#define S second
#define pb push_back
#define sqr(x) (x) * (x)

using namespace std;
using namespace __gnu_pbds;

mt19937_64 gen(time(0));

typedef tree<
pair <int, int>,
null_type,
less<pair <int, int>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

//const int inf = 2e9 + 34333;
//const ll mod = 1e9 + 7;
//const int maxn = 40;


signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif
    int n;
    cin >> n;
    cout << ((n + 999) / 1000) * 1000 - n;
    return 0;
}


Measured memory_bytes: 3636
import java.io.*;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) {		
		try {
			BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
			String ans = "Hoshina";
			String mis = "Hoshino";
			ArrayList<String> printStr = new ArrayList<String>();
			int i = Integer.parseInt(bf.readLine());
			while(i > 0){
				String str = bf.readLine();
				str = str.replaceAll(mis,ans);
				printStr.add(str);
				i--;
			}
			for(String str : printStr){
				System.out.println(str);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 24284
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int64_t D, G;
  cin >> D >> G;
  vector<vector<int64_t>> pc(D, vector<int64_t>(2));
  for (int i = 0; i < D; i++) {
    cin >> pc.at(i).at(0) >> pc.at(i).at(1);
  }
  int ans = 10000;
  for (int tmp = 0; tmp < (1 << D); tmp++) {
    bitset<10> s(tmp);
    int64_t memo = 0;
    int memo2 = 0;
    int M = 1;
    int M2 = 1;    
    int N = 0;
    for (int i = 0; i < D; i++) {
      if (s.test(i)) {
        memo += (i + 1) * 100 * pc.at(i).at(0) + pc.at(i).at(1);
        memo2 += pc.at(i).at(0);
      }
      else {
        M = M2;
        M = (i + 1) * 100;
        N = pc.at(i).at(0);
      }       
    }
    if (memo >= G) {
      ans = min(memo2, ans);
    }
    else {
      if (G - memo <= M * N) {
        if ((G - memo) % M == 0) {
          memo2 += (G - memo) / M;
        }
        else {
          memo2 += ((G - memo) / M) + 1;
        }
      }
      else {
        memo2 += N;
        if ((G - memo - M * N) % M2 == 0) {
          memo2 += (G - memo) / M2;
        }
        else {
          memo2 += ((G - memo - M * N) / M2) + 1;
        }
      }
      ans = min(memo2, ans);
    }
  }
  cout << ans << endl;
}
      
    

Measured memory_bytes: 3600
H, W = map(int, input().split())

Z = H * W % 2

if (H == 1) or (W == 1):
    print(1)
else:
    if Z == 1:
        print(int((H * W - 1) / 2 + 1))
    elif Z == 0:
        print(int((H * W) / 2))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
  
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll n; cin>>n;
  vector<ll> a(n);
  for(int i=0; i<n; i++) cin>>a[i];
  sort(a.begin(),a.end());
  cout<<a[n-1]-a[0]<<"\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#define ll long long
#define pii pair<ll, ll>
#define fst first
#define snd second
using namespace std;
const int md = (1e9) + 7;
ll mult = 1, rs = 0;
map<pii, pii> mp;
ll gcd(ll a, ll b) {return (b) ? gcd(b, a % b) : a;}
pii frc(ll a, ll b)
{
	if (a == 0) {return make_pair(0LL, 1LL);}
	if (b == 0) {return make_pair(-1LL, 0LL);}
	if (b < 0) {a = -a; b = -b;}
	ll g = gcd(abs(a), abs(b));
	a /= g; b /= g;
	return {a, b};
}
ll pw(ll b, ll e)
{
	ll t = 1;
	while (e)
	{
		if (e & 1) {t *= b; t %= md;}
		b *= b; b %= md; e >>= 1;
	}
	return t;
}
int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		ll a, b; cin >> a >> b;
		if (a == 0 && b == 0) {rs++; rs %= md;}
		else
		{
			pii frac = frc(b, a);
			if (frac.fst < 0) 
			{
				frac.fst = -frac.fst;
				swap(frac.fst, frac.snd);
				mult *= pw((-1 + pw(2, mp[frac].fst) + pw(2, mp[frac].snd)) % md, md - 2);
				mult %= md;
				rs += (mult * pw(2, mp[frac].snd)) % md;
				rs %= md;
				mp[frac].snd++;
			}
			else 
			{
				mult *= pw((-1 + pw(2, mp[frac].fst) + pw(2, mp[frac].snd)) % md, md - 2);
				mult %= md;
				rs += (mult * pw(2, mp[frac].fst)) % md;
				rs %= md;
				mp[frac].fst++;
			}
			mult *= (-1 + pw(2, mp[frac].fst) + pw(2, mp[frac].snd)) % md;
			mult %= md;
		}
	}
	cout << rs << "\n";
	return 0;
}

Measured memory_bytes: 19160
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi = acos(-1);
const int maxn = 200010;
vector<pair<int,int>> points;

int LIS() {
	if (points.empty()) return 0;
	vector<int> ret(points.size(), 1e9);
	for (auto t:points) {
		*lower_bound(ret.begin(), ret.end(), t.second) = t.second;
	}
	return find(ret.begin(), ret.end(), 1e9) - ret.begin();
}

int main() {
	int x1, y1, x2, y2, n;
	scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &n);
	double pval = 20 - 5 * pi, qval = 10 * pi - 20;
	double ans = 100.0 * (abs(x1 - x2) + abs(y1 - y2));
	int xs = x1 > x2 ? -1 : 1;
	int ys = y1 > y2 ? -1 : 1;
	x1 *= xs; x2 *= xs;
	y1 *= ys; y2 *= ys;
	for (int i = 1; i <= n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		x *= xs, y *= ys;
		if (x1 <= x && x <= x2 && y1 <= y && y <= y2) points.emplace_back(x, y);
	}
	sort(points.begin(), points.end());
	int k = LIS();
	if (k == min(x2 - x1, y2 - y1) + 1) {
		ans += -(k-1) * pval + qval;
	} else {
		ans += -k * pval;
	}
	printf("%.10f\n", ans);
	
	return 0;
}

Measured memory_bytes: 2544
#include <stdio.h>

int main(void){
  int N, A[100], i, j, c, s;
  c = 0;
 
  scanf("%d", &N);
 
  for(i = 0;i < N;i++) scanf("%d", &A[i]);
 
  for(i = 1;i <= N - 1;i++){
    for(j = 0;j < N - i;j++){
      if(A[j] > A[j+1]){
        s = A[j];
        A[j] = A[j+1];
        A[j+1] = s;
        c++;
      }
    }
  }
 
  for(i = 0;i < N;i++) {
    if(i != 0) printf(" ");
    printf("%d", A[i]);
  }

  printf("\n");
 
  printf("%d\n", c);
 
  return 0;
}

Measured memory_bytes: 1816
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#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; }
const ll INF = 1LL << 60;
int main(){
    int n;
    cin >> n;
    vector<pair<ll,ll>> lr(n);
    rep(i,n){
        int x,l;
        cin >> x >> l;
        lr[i].second = x-l;
        lr[i].first = x+l; //右端順でsortするので
    }
    sort(lr.begin(),lr.end());
    ll cur = -INF;
    int ans = 0;
    rep(i,n){
        if(lr[i].second >= cur){
            ans++;
            cur = lr[i].first;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define MOD 1000000007 //10^9+7
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
const int INF = numeric_limits<int>::max();
const ll INFL = numeric_limits<ll>::max();


// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

//greatest common divisor
long long gcd(ll a, ll b) 
{
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

//least common multiple
long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

ll factorial(ll n) {
    ll res = 1;
    for (ll i = 1; i <= n; i++) {
        res *= i;
    }
    return res;
}

int main()
{
    int x, a; cin >> x >> a;
    if (x < a)
        cout << 0 << endl;
    else
        cout << 10 << endl;
    return 0;
}


Measured memory_bytes: 3636
#include<iostream>

using namespace std;
int main(){
	int N;
	int a[100005], b[100005], c[100005];
	scanf("%d", &N);
	for(int i = 1; i<=N ; i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	for(int i = 2 ; i<=N ; i++){
		int aa = a[i-1];
		int bb = b[i-1];
		int cc = c[i-1];
		a[i] = a[i] + max(bb, cc);
		b[i] = b[i] + max(aa, cc);
		c[i] = c[i] + max(bb, aa);
	}
	cout << max(a[N], max(b[N], c[N])) << endl;

}

Measured memory_bytes: 4368
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <numeric>
#include <bitset>
#include <complex>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
using namespace std;

typedef long long ll;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
bool ISINT(double x){return fabs(x-(int)round(x))<EPS;}
bool ISEQ(double x,double y){return fabs(x-y)<EPS;}
string itos(ll x){stringstream ss;ss<<x;return ss.str();}
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

int main(void){
  int n;
  string s;

  while (cin >> n >> s) {
    int cnt[26];
    memset(cnt, 0, sizeof(cnt));
    
    for (int i = 0; i < n; i++) {
      if ('a' <= s[i] && s[i] <= 'z') {
        cnt[s[i] - 'a']++;
      }
    }

    int cnt2[10];
    memset(cnt2, 0, sizeof(cnt2));
    for (int i = 0; i < 26; i++) {
      cnt2[cnt[i]]++;
    }

    int ans = cnt2[1] * 2 - 1;
    for (int i = 2; i <= 9; i++) {
      if (cnt2[i] == 0) continue;
      
      if (cnt2[i] == 1) {
        ans += 3 + 1;
      } else {
        ans += cnt2[i] * 2 + 3 + 1;
      }
    }

    cout << ans << endl;
    
    /*
2*a

a+a+a+b+b+b+c+c+c
3*a+3*b+3*c
(a+b+c)*3

3*a+3*b
(a+b)*3


2*a+3*b
(a)

5*a+b*3+c*2
(a+b)*3+(c+a)*2
     */
  }
}

Measured memory_bytes: 1212
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

func main() {
	io, flash := NewIO()
	defer flash()

	n, maxTime := io.ScanInt2()
	var routeCosts []int
	for i := 0; i < n; i++ {
		c, t := io.ScanInt2()
		if t <= maxTime {
			routeCosts = append(routeCosts, c)
		}
	}

	if len(routeCosts) == 0 {
		fmt.Println("TLE")
	} else {
		sort.Ints(routeCosts)
		fmt.Println(routeCosts[0])
	}
}

type IO struct {
	scanner *bufio.Scanner
	writer  *bufio.Writer
}

func NewIO() (*IO, func()) {
	io := &IO{
		scanner: newScanner(),
		writer:  newWriter(),
	}
	return io, func() { io.writer.Flush() }
}

func newScanner() *bufio.Scanner {
	s := bufio.NewScanner(os.Stdin)
	s.Buffer(make([]byte, 10000000), 10000000)
	s.Split(bufio.ScanWords)
	return s
}

func newWriter() *bufio.Writer {
	return bufio.NewWriter(os.Stdout)
}

func (io *IO) ScanBytes() []byte {
	if !io.scanner.Scan() {
		panic("scan string failed")
	}
	return io.scanner.Bytes()
}

func (io *IO) ScanString() string {
	if !io.scanner.Scan() {
		panic("scan string failed")
	}
	return io.scanner.Text()
}

func (io *IO) ScanStrings(n int) []string {
	strs := make([]string, n)
	for i := 0; i < n; i++ {
		strs[i] = io.ScanString()
	}
	return strs
}

func (io *IO) Scan2DStrings(y, x int) [][]string {
	strings := make([][]string, y)
	for i := 0; i < y; i++ {
		strings[i] = io.ScanStrings(x)
	}
	return strings
}

func (io *IO) Scan2DGraph(y int) [][]string {
	strs := make([][]string, y)
	for i := 0; i < y; i++ {
		strs[i] = strings.Split(io.ScanString(), "")
	}
	return strs
}

func (io *IO) ScanInt() int {
	return int(io.ScanInt64())
}

func (io *IO) ScanInt2() (int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInt3() (int, int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInt4() (int, int, int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInts(n int) []int {
	ints := make([]int, n)
	for i := 0; i < n; i++ {
		ints[i] = io.ScanInt()
	}
	return ints
}

func (io *IO) Scan2DInts(y, x int) [][]int {
	ints := make([][]int, y)
	for i := 0; i < y; i++ {
		ints[i] = io.ScanInts(x)
	}
	return ints
}

func (io *IO) ScanInt64() int64 {
	i, err := strconv.ParseInt(io.ScanString(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *IO) ScanFloat64() float64 {
	i, _ := strconv.ParseFloat(io.ScanString(), 64)
	return i
}

func (io *IO) ScanFloat64s(n int) []float64 {
	floats := make([]float64, n)
	for i := 0; i < n; i++ {
		floats[i] = io.ScanFloat64()
	}
	return floats
}

func (io *IO) Println(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}


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

int main() {

  string S, S1, S2, S3;
  cin >> S;
  S1 = S[0];
  S2 = S[1];
  S3 = S[2];
  
  if (S1 == S2) {
    if (S2 == S3) {
      cout << "No";
    }
    else {
      cout << "Yes";
    }
  }
  else {
    cout << "Yes";
  }
  
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1'000'000'007;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

using Val = int;
const int MAX_N = 3030;
Val heap[MAX_N];
int sz = 0;
void push(Val x) {
	int v = sz++;
	while (v > 0) {
		int p = (v - 1) / 2;
		if (heap[p] >= x)break;
		heap[v] = heap[p];
		v = p;
	}
	heap[v] = x;
}
const Val pop() {
	Val ret = heap[0];
	Val back = heap[--sz];
	int v = 0;
	while (v * 2 + 1 < sz) {
		// l と r のうち小さいほうと交換したい
		int l = v * 2 + 1, r = v * 2 + 2;
		int u = (r >= sz || heap[l] > heap[r]) ? l : r;
		// もう逆転していない
		if (heap[u] <= back)break;
		heap[v] = heap[u];
		v = u;
	}
	heap[v] = back;
	return ret;
}
const Val top() {
	return heap[0];
}
const int size() {
	return sz;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int X, Y, Z, K; cin >> X >> Y >> Z >> K;
	vector<int> A(X); rep(i, 0, X) {
		cin >> A[i];
	}
	vector<int> B(Y); rep(i, 0, Y) {
		cin >> B[i];
	}
	vector<int> C(Z); rep(i, 0, Z) {
		cin >> C[i];
	}
	sort(all(A), greater<int>());
	sort(all(B), greater<int>());
	sort(all(C), greater<int>());
	rep(i, 0, X)rep(j, 0, Y)rep(k, 0, Z) {
		int x = A[i] + B[j] + C[k];
		if (size() >= K) {
			if (-top() >= x)
				break;
			push(-x);
			pop();
		}
		else {
			push(-x);
		}
	}
	vector<int> ans(K);
	rep(i, 0, K) {
		ans[i] = -top();
		pop();
	}
	reverse(all(ans));
	rep(i, 0, K) {
		cout << ans[i] << endl;
	}
	return 0;
}

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

int main() {
	string s;
	cin >> s;
	int ans = 0;
	rep(i, 3) if(s[i]=='1') ans++;
	cout << ans << endl;
	return 0;
}

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

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (to_string(i).size() % 2 != 0) ans++;
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3764
S = input()
K = int(input())

tmp = ""
cnt = 0
ans = 0
for s in S:
    if s == tmp:
        cnt += 1
    else:
        ans += cnt//2
        cnt = 1
    tmp = s

if cnt == len(S):
    ans += (cnt*K)//2
else:
    ans *= K
    
    first_cnt = 0
    if S[0] == S[-1]:
        for s in S:
            if s == S[0]:
                first_cnt += 1
            else:
                break
        ans -= first_cnt//2 * (K-1)
        ans += (cnt+first_cnt)//2 * (K-1)
        ans += cnt//2
    else:
        ans += cnt//2 * K

print(ans)

Measured memory_bytes: 3064
import java.io.*;

class Main {
	public static void main (String args[]) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String buf;
		String Index[] = {" ","',.!?","abcABC","defDEF","ghiGHI","jklJKL","mnoMNO","pqrsPQRS","tuvTUV","wxyzWXYZ"};

		try {
			while ((buf = br.readLine())!=null) {
				for (int i=0;i<buf.length();) {
					int k = 0;
					int j = Character.getNumericValue(buf.charAt(i));
					if (j==0) {
						i++;
						while (i<buf.length()&&Character.getNumericValue(buf.charAt(i))==j) {
							System.out.print(Index[j].charAt(0));
							i++;
						}
					} else {
						i++;
						while (i<buf.length()&&Character.getNumericValue(buf.charAt(i))==j) {
							i++;k++;
						}
						System.out.print(Index[j].charAt(k));
					}
				}
				System.out.println("");
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 16944
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }

int main(){
    int N;
    cin >> N;
    fcout <<  ((N + 1) / 2) / double(N) << endl;
}


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

int main() {
  int N, K; cin >> N >> K;
  int cnt = 0;
  while (N > 0) {
    N /= K;
    cnt++;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
#include<set>
using namespace std;

#define rip(i,n,s) for (int i=(s);i<(int)(n);i++)

int main() {
	int n,q;
	cin >> n >> q;
	int s, t, x;
	vector<pair<int, int>> da(n * 2 + q);
	rip(i, n, 0) {
		cin >> s >> t >> x;
		da[i * 2].first = s - x;
		da[i * 2].second = x;
		da[i * 2 + 1].first = t - x;
		da[i * 2 + 1].second = -x;
	}
	int d;
	rip(i, q, 0) {
		cin >> d;
		da[n * 2 + i].first = d;
		da[n * 2 + i].second = INT_MAX;
	}
	set<int> se;
	sort(da.begin(), da.end());
	vector<int> ans(q);
	int co = 0;
	rip(i, n * 2 + q, 0) {
		if (da[i].second == INT_MAX) {
			if (se.empty()) {
				ans[co] = -1;
			}
			else {
				ans[co] = *se.begin();
			}
			co++;
		}
		else {
			if (da[i].second < 0) {
				se.erase(-da[i].second);
			}
			else {
				se.insert(da[i].second);
			}
		}
	}
	rip(i, q, 0) {
		printf("%d\n", ans[i]);
	}
}


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

#define fr(i,n) _back
#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int T = 1e6+3;
const int N = 42;
bitset<T> bit[N];
bitset<T> my;
vector<ll> v;
int n,k;

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    vector<ll> ve(n);
    for(int i = 0; i < n; i++) cin >> ve[i];

    for(int i = 0; i < n; i++) {
        ll sum = 0;
        for(int j = i; j < n; j++) {
            sum += ve[j];
            v.pb(sum);
        }
    }

    for(int i = 0; i < v.size(); i++) {
        ll x = v[i];
        for(ll j = 1, casa = 0; j <= x; j <<= 1, casa++)
            if(x&j) bit[casa][i] = 1;
    }

    ll ans = 0;
    my.set();

    for(int ok = N-1; ok >= 0; ok--) {
        if(bit[ok].count() >= k) {
            bitset<T> tmp = my&bit[ok];
            if(tmp.count() >= k) {
                ans += (1ll << ok);
                my &= bit[ok];
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 8044
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
AB = [LIST() for _ in range(N)]

AB.extend([[0, INF], [INF, 0]])

AB.sort(key = lambda x:x[0])

ans = 0
for i in range(1, N+2):
	ans += min(AB[i][0]-AB[i-1][0], AB[i-1][1]-AB[i][1])

print(ans)

Measured memory_bytes: 30072
fun main(args: Array<String>) {
    val n = readLine()?.toInt() ?: return
    val p = readLine()?.split(" ")?.map(String::toInt) ?: return
    var min = p[0]
    val count = 0.until(n).count { i ->
        val pi = p[i]
        if (pi <= min) {
            min = pi
            true
        } else {
            false
        }
    }
    println(count)
}


Measured memory_bytes: 82764
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String S = sc.next();
		
		char[] ch = new char[S.length()];
		String ans = "";
		for(int i=0; i<ch.length; i++) {
			ch[i] = 'x';
			ans += ch[i];
		}
		
		System.out.println(ans);
	}

}

Measured memory_bytes: 38952
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<cstring>

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define P pair<ll, ll>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define print(x) cout << (x) << endl

class mint {
    long long x;
public:
    mint(long long x=0) : x((x%MOD+MOD)%MOD) {}
    mint operator-() const {
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

/* -- template -- */
const int MAX_Q = 51;
int N, M, Q;
int a[MAX_Q], b[MAX_Q], c[MAX_Q], d[MAX_Q];
int ans = 0;

int sum(vector<int> A) {
    int ret = 0;
    rep(i, Q) {
        if(A[b[i]] - A[a[i]] == c[i])
            ret += d[i];
    }
    return ret;
}

void dfs(vector<int> A, int x) {
    if(A.size() == N) {
        ans = max(ans, sum(A));
        return;
    }
    A.pb(x);
    for(int i = 0; i + x <= M ; ++i) {
        dfs(A, i + x);
    }
}

int main() {
    cin >> N >> M >> Q;
    rep(i, Q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i], --b[i];
    }
    vector<int> A;
    dfs(A, 1);

    cout << ans << endl;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    int a, b;
    cin >> a >> b;
    if (a > b) cout << "a > b" << endl;
    else if (a == b) cout << "a == b" << endl;
    else cout << "a < b" << endl;

    return 0;
}


Measured memory_bytes: 3056
import itertools

N = int(input())

P = input().split(" ")
Q = input().split(" ")

P = int(''.join(P))
Q = int(''.join(Q))

nums = []
for i in itertools.permutations(range(1, N + 1)):
    num = ''
    for j in i:
        num += str(j)
    num = int(num)
    nums.append(num)

print(abs(nums.index(P) - nums.index(Q)))

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

using namespace std;
typedef long long ll;

int main(){
  ll N;
  cin >> N;
  vector<ll> dp(N+1, 1);
  ll ans = 0;
  for (int i=1; i<=N; i++){
    //cerr << i << " " << dp[i] << "\n";
    ans += i * dp[i];
    for (int j=i * 2; j<=N; j += i){
      dp[j]++;
    }
  }
  cout << ans << "\n";
  return 0;
}

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

using namespace std;

//-----BEGIN union find tree-----
//complexity: -

// [0, n) をノードとする union find tree
class UnionFindTree {
	public:
		UnionFindTree(int n) : N_(n) {
			rank_ = std::vector<int>(n, 0);
			size_ = std::vector<int>(n, 1);
			for(int i = 0; i < n; ++i) {
				parent_.push_back(i);
			}
		}
		bool same(int x, int y) {
			assert(0 <= x && x < N_ && 0 <= y && y < N_);
			return findRoot(x) == findRoot(y);
		}
		bool unite(int x, int y) {
			assert(0 <= x && x < N_ && 0 <= y && y < N_);
			x = findRoot(x);
			y = findRoot(y);
			if(x == y) return false;
			if(rank_[x] < rank_[y]) {
				parent_[x] = y;
				size_[y] += size_[x];
			} else {
				parent_[y] = x;
				size_[x] += size_[y];
				if(rank_[x] == rank_[y]) ++rank_[x];
			}
			return true;
		}
		int getCardinalityOfEquivalenceClass(int x) { return size_[findRoot(x)]; }
	private:
		const int N_;
		std::vector<int> parent_;
		std::vector<int> rank_;
		std::vector<int> size_;
		int findRoot(int x) {
			if(parent_[x] == x) {
				return x;
			} else {
				return parent_[x] = findRoot(parent_[x]);
			}
		}
};
//-----END union find tree-----

int main(void) {
	long long N, M;
	cin >> N >> M;
	vector<long long> A, B;
	UnionFindTree tree(N);
	for(int i = 0; i < M; ++i) {
		long long a, b;
		cin >> a >> b;
		A.push_back(a - 1);
		B.push_back(b - 1);
	}
	reverse(A.begin(), A.end());
	reverse(B.begin(), B.end());
	vector<long long> ans;
	ans.push_back(N * (N - 1) / 2);
	for(int i = 0; i < M - 1; ++i) {
		int sizeA = tree.getCardinalityOfEquivalenceClass(A[i]);
		int sizeB = tree.getCardinalityOfEquivalenceClass(B[i]);
		if(tree.unite(A[i], B[i])) {
			ans.push_back(ans.back() - sizeA * sizeB);
		} else {
			ans.push_back(ans.back());
		}
	}
	reverse(ans.begin(), ans.end());
	for(int i = 0; i < M; ++i) {
		cout << ans[i] << '\n';
	}
	return 0;
}



Measured memory_bytes: 4980
#include<stdio.h>

typedef struct{
  int p;
  int color;
  int t;
} Ver;

int M[100][100];
Ver G[100];

int min(int a,int b){
  if(a > b) return b;
  else return a;
}

int count(int p,int sum){
  if(p == 0) return sum;
  sum += M[G[p].p][p];
  count(G[p].p,sum);
}

int main(){
  int n,i,j,m,p,q,r;
  int direction,parent,sum = 0;

  scanf("%d",&n);

  for(i = 0;i < n;i++)G[i].color = G[i].t = 0;

  for(i = 0;i < n;i++){
    for(j = 0;j < n;j++){
      M[i][j] = -1;
    }
  }

  M[0][0] = 0;

  for(i = 0;i < n;i++){
    scanf("%d",&p);
    scanf("%d",&m);
    for(j = 0;j < m;j++){
      scanf("%d",&q);
      scanf("%d",&r);
      M[p][q] = r;
    }
  }

  G[0].color = 1;
  G[0].p = 0;

  for(i=0;i<n;i++){
    G[i].color = 0;
    G[i].p = -1;
    G[i].t = 10000001;
  }
  G[0].t = 0;

  while(1){
    m = 10000001;
    for(i=0;i<n;i++){
      if(G[i].color != 2 && G[i].t < m){
        m = G[i].t;
        direction = i;
      }
    }
    if(m == 10000001) break;
    G[direction].color = 2;
    G[direction].p = parent;
    for(i=0;i<n;i++){
      if(M[direction][i] != -1 && G[i].color != 2 && (M[direction][i]+G[direction].t) < G[i].t){
	       G[i].p = direction;
	       G[i].t = M[direction][i] + G[direction].t;
	       G[i].color = 1;
      }
    }
  }

  for(i = 0;i < n;i++)printf("%d %d\n",i,G[i].t);

  return 0;
}



Measured memory_bytes: 2084
#include <iostream>
#include <cmath>
#include <iomanip>
#include <cstring>

using namespace std;

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


double max(int i, int j)
{
	if (i > j) return (double)i;
	else return (double)j;
}

int main(void)
{
	while(1) {
		int n, m, k;
		cin >> n >> m >> k;
		if (n == 0 && m == 0) break;
		double dp[30][20000];
		memset(dp, 0, sizeof dp);
		//dp[サイコロの個数][目の合計]
		dp[0][0] = 1;
		rep(i, n) {
			erep(j, m * i) {
				orep(l, m) {
					dp[i + 1][j + l] += dp[i][j] / m;
				}
			}
		}

		double ans = 0;
		erep(i, m * n) ans += max(1, i - k) * dp[n][i];
		cout << fixed << setprecision(9) << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 7888
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;
using static Prog;
using NX = System.Int64;

public class Solver
{
    public void Solve()
    {
        int H = NextInt(), W = NextInt(), K = NextInt();
        List<string> map = Enumerable.Range(0, H).Select(v => NextString()).ToList();
        List<int[]> ans = Enumerable.Range(0, H).Select(v => new int[W]).ToList();
        int count = 1, start = 0;
        for (int y = 0; y < H; y++)
        {
            if (map[y].Contains('#'))
            {
                //切る
                for (int x = 0; x < W; x++)
                {
                    for (int s = start; s <= y; s++)
                    {
                        ans[s][x] = count;
                    }
                    if (map[y][x] == '#' && map[y].Substring(x + 1, W - (x + 1)).Contains('#')) count++;
                }
                start = y + 1;
                count++;
            }
        }
        for (int y = 0; y < H; y++)
            if (ans[y][0] == 0)
                for (int x = 0; x < W; x++) ans[y][x] = ans[y - 1][x];

        for (int y = 0; y < H; y++, Console.WriteLine())
            for (int x = 0; x < W; x++) Console.Write(ans[y][x] + " ");
    }
}

public class Prog
{
    public struct Pair { public int x, y; public Pair(int a, int b) { x = a; y = b; } }

    static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        new Solver().Solve();
        Console.Out.Flush();
        return;
    }
}

public class Input
{
    public const long MOD = 1000000007;
    public const int INF = 1000000007;
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
    public long Abs(long a, long b) => Math.Abs(a - b);
}


Measured memory_bytes: 18648
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ull = unsigned long long;

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

    stack<pair<int, int>> dfs;
    dfs.push({1, 0});
    int ans = 999999999;
    while (!dfs.empty()) {
        auto n = dfs.top();
        dfs.pop();
        if (n.second < N) {
            dfs.push({2 * n.first, n.second + 1});
            dfs.push({n.first + K, n.second + 1});
        } else {
            ans = min(ans, n.first);
        }
    }
    cout << ans << endl;
}


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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int ST_MAX = (1 << 20);

template <class T> class ST{
	T x[ST_MAX * 2];
	
	T eval(T a , T b){			//評価
		return max(a,b);
	}
	
	void ren(int a){			//更新
		x[a] = eval(x[2 * a] , x[2 * a + 1]);
		if(a > 0) ren(a / 2);
	}
	
	T read_ST(int a , int b , int e , int s , int f){		//値の取得
		if(e <= s || f <= b) return 0;
		if(s <= b && e <= f) return x[a];
		return eval(read_ST(2 * a , b , (b + e) / 2 , s , f) , read_ST(2 * a + 1 , (b + e) / 2 , e , s , f));
	}
	
public:
	
	void dft(){					//初期化
		fill(x,x+ST_MAX*2,0);
	}
	
	void put(int a , T b){	//更新の開始
		if(x[a+ST_MAX] >= b) return;
		x[a + ST_MAX] = b;
		ren((a + ST_MAX) / 2);
	}
	
	T get(int s , int f){	//値の取得の開始
		return read_ST(1 , 0 , ST_MAX , s , f);
	}
};
ST<LL> solve;
const LL mod = 1e9+7;

int main(){
	int N; cin >> N;
	vector<int> h(N);
	repp(i,0,N) cin >> h[i];
	vector<LL> a(N);
	repp(i,0,N) cin >> a[i];
	solve.dft();
	repp(i,0,N){
		LL z = solve.get(0,h[i]);
		solve.put(h[i],z+a[i]);
	}
	cout << solve.get(0,ST_MAX) << endl;
	return 0;
}


Measured memory_bytes: 18944