akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

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

  int n;
  cin >> n;

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

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());

  vector<ll> ab(n, 0), bc(n, 0);
  for (int i = 0; i < n; i++) {
    ab[i] = b.end() - upper_bound(b.begin(), b.end(), a[i]);
    bc[i] = c.end() - upper_bound(c.begin(), c.end(), b[i]);
  }

  reverse(bc.begin(), bc.end());

  vector<ll> acc(n + 1, 0);  // bcをreverseして後ろから見た累積和
  for (int i = 0; i < n; i++) {
    acc[i + 1] = acc[i] + bc[i];
  }

  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ans += acc[ab[i]];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> a(h);
    vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    for (int i = 0; i < h; i++) {
        cin >> a[i];
    }
    vector<vector<int>> d(h, vector<int>(w, 1e9));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (a[i][j] == 'S') {
                d[i][j] = 0;
                queue<pair<int, int>> que;
                que.emplace(i, j);
                for (int loop = 0; loop < k; loop++) {
                    for (int s = que.size(); s > 0; s--) {
                        int x, y;
                        tie(x, y) = que.front();
                        que.pop();
                        for (int id = 0; id < 4; id++) {
                            int nx = x + dx[id], ny = y + dy[id];
                            if (0 <= nx && nx < h && 0 <= ny && ny < w && a[nx][ny] != '#' && d[nx][ny] == 1e9) {
                                d[nx][ny] = d[x][y] + 1;
                                que.emplace(nx, ny);
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = 1e9;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (d[i][j] == 1e9) {
                continue;
            }
            int dist = min({i, j, w - 1 - j, h - 1 - i});
            // if (a[i][j] == 'S') {
            //     ans = min(ans, (dist + k - 1) / k);
            // }
            ans = min(ans, 1 + (dist + k - 1) / k);
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 6816
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <bitset>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;
// const ll mod =  998244353 ;
const ll mod =  1000000007 ;
const ll inf = 1e18;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define REP_REV(i, n) for (ll i = n-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())

template<typename T> void print_vec(vector<T> a) {int n = a.size();REP(i, n) {cout >> a[i]; if(i!=n-1) cout << " "; else cout << endl;}}
ll power(ll base, ll exponent){ if(exponent % 2){ return power(base, exponent - 1) * base % mod; }else if(exponent){ ll root_ans = power(base, exponent / 2); return root_ans * root_ans % mod; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
template<typename T> ll sum(T begin, T end) {return accumulate(begin, end, 0ll);}
struct combination{ vector<ll> 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); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

using Pair = pair<ll, ll>;


signed main() {
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int n, k;
  cin >> n >> k;
  vector<ll> h(n);
  REP(i, n) cin >> h[i];
  sort(all(h));
  ll ans = 0;
  REP(i, n-k) {
    ans += h[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
require 'prime'
#約数一覧
def divisors(n)
  n.prime_division.inject([1]) do |ary, (p, e)|
    (0..e).map{ |e1| p ** e1 }.product(ary).map{ |a, b| a * b }
  end.sort
end

N, K = gets.chomp.split(" ").map(&:to_i)
A = gets.chomp.split(" ").map(&:to_i)

sa = A.inject(:+)
ds = divisors(sa).reverse!
ans = 1
ds.each{|d|
  s = A.inject(0){|r, a| r + [a % d, d - (a % d)].min}
  if s <= 2 * K then
    dif = A.map{|a| ((a % d) > (d - (a % d)) ? (d - (a % d)) : (-(a % d)))}
    ss = dif.inject(:+)
    (ans = d; break) if ss == 0
    cnt = ss.abs / d
    if ss.positive? then
      df = dif.select{|di| di > 0}.sort.reverse[0, cnt]
      inc = df.inject(0){|r, x| r + d - 2 * x}
    else
      df = dif.select{|di| di < 0}.sort[0, cnt]
      inc = df.inject(0){|r, x| r + d + 2 * x}
    end
    (ans = d; break) if (s + inc) <= 2 * K
  end
}

puts ans


Measured memory_bytes: 2424
#include<iostream>
using namespace std;
#include<string>
#define REP(i,a,b) \
for(int i=a; i<b; i++)
#include<bits/stdc++.h>
#include<algorithm>
#define ll long long int
typedef vector<int> vi;
typedef pair<int,int> ii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define present(c,x) ((c).find(x) != (c).end())
#define tr(c,i) for(typeof(c.begin()) i = (c).begin(); i != (c).end();i++)
int main()
{
	int n;
	cin >> n;
	vector<double> arr(n);
	REP(i,0,n)cin >> arr[i];
	vector<double> dp[n+1];
	REP(i,0,n+1)dp[i].resize(n+1,0);
	dp[1][0] = 1-arr[0];
	dp[1][1] = arr[0];
	REP(i,2,n+1)
	{
		REP(j,0,n+1)
		{
			dp[i][j] = arr[i-1]*dp[i-1][j-1] + (1-arr[i-1])*dp[i-1][j];
		}
	}
	double ans = 0.0;
	REP(j,n/2+1,n+1)ans = ans+dp[n][j];
	cout << setprecision(11) << ans;
}





Measured memory_bytes: 70656
#include <stdio.h>

int sosuu_list_num;
int sosuu_list[2000];

void make_sosuu_list(void) {
	char is_sosuu[2000];
	int i,j;
	for(i=0;i<2000;i++)is_sosuu[i]=1;
	is_sosuu[0]=is_sosuu[1]=0;
	for(i=2;i<2000;i++) {
		if(is_sosuu[i]) {
			for(j=i+i;j<2000;j+=i)is_sosuu[j]=0;
		}
	}
	for(i=0;i<2000;i++) {
		if(is_sosuu[i])sosuu_list[sosuu_list_num++]=i;
	}
}

int memo[15][2000][1121];

int tansaku(int rest,int next_use,int rest_num) {
	int i;
	int result=0;
	if(rest<=0)return (rest_num==0)?1:0;
	if(rest_num<0)return 0;
	if(memo[rest][next_use][rest_num]>0) {
		return memo[rest][next_use][rest_num]-1;
	}
	for(i=next_use;i<sosuu_list_num && sosuu_list[i]<=rest_num;i++) {
		result+=tansaku(rest-1,i+1,rest_num-sosuu_list[i]);
	}
	memo[rest][next_use][rest_num]=result+1;
	return result;
}

int main(void) {
	int n,k;
	make_sosuu_list();
	while(1) {
		scanf("%d%d",&n,&k);
		if(n==0 && k==0)break;
		printf("%d\n",tansaku(k,0,n));
	}
	return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>

using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;
#define REP(i, a, b) for(int i = int(a); i <= int(b); i++)
#define LOOP(i, v) for(int i = 0; i < v.size(); i++)
#define EPS 1e-9
#define INF 1e12
#define debug(x) cerr << "DEBUG : " << (#x) << " => " << (x) << endl

int main()
{
  int x;
  string s;
  scanf("%d\n", &x);
  
  char letter[5] = {'M', 'A', 'R', 'C', 'H'};
  long long int combien[5];
  REP(i, 0, 4) combien[i] = 0;
  
  REP(i, 1, x)
  {
    getline(cin, s);
    REP(j, 0, 4)
    {
      if(letter[j] == s[0]) combien[j]++;
    }
  }
  
  long long int tot = 0;
  
  REP(b, 0, 31)
  {
    vi a;
    REP(i, 0, 4)
    {
      if(b & (1 << i)) a.push_back(i);
    }
    if(a.size() == 3)
    {
      tot = tot+combien[a[0]]*combien[a[1]]*combien[a[2]];
    }
  }
  
  cout << tot << endl;
  
  return 0;
}

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

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

	if((A + B) % 2 == 0){
  	cout << (A + B) / 2 << endl;
	}else{
		cout << "IMPOSSIBLE" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"

using namespace std;
using namespace __gnu_pbds;


#define ll long long int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()

typedef tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

int main(void)
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, ans = 2, i;
    cin>>n;
    if(n == 2) {
    	cout<<1<<'\n';
    	return 0;
    }
    ll num = n - 1;
    for(i = 2; i * i <= num; i++) {
    	if(num % i == 0) {
    		if(i * i == num) {
    			ans += 1;
    		} else {
    			ans += 2;
    		}
    	}
    }
    for(i = 2; i * i <= n; i++) {
    	if(n % i == 0) {
    		ll temp = n;
    		while(temp % i == 0) {
    			temp /= i;
    		}
    		if(temp == 1 || (temp - 1) % i == 0) {
    			ans ++;
    		}
    	}
    }
    cout<<ans<<"\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <stdexcept>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define x first
#define y second
#define pb push_back
#define pf push_front
#define debug(a) cout << (a) << endl
namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;
vector<vector<int>> xy(505, vector<int>(505, 0));
vector<vector<int>> c(505, vector<int>(505, 0));

void solve()
{
	int n, m, q;
	cin >> n >> m >> q;
	rep(i, m)
	{
		int l, r;
		cin >> l >> r;
		xy[l][r]++;
	}

	FOR(i,1, n+1)
	{
		int ssum=0;
		FOR(j,1, n+1)
		{	
			ssum+=xy[i][j];
			c[i][j]=ssum;
		}
	}
	rep(i, q)
	{
		int l, r;
		cin >> l >> r;
		int ans=0;
		FOR(j,l,r+1){
			ans+=c[j][r]-c[j][l-1];
		}
		cout<<ans<<endl;
	}
}

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


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

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    (a, b) = [int(e) for e in lines[0].split(" ")]

    return (a, b)


def solve(a, b):

    x = str(a) * b 
    y = str(b) * a
    
    result = x
    if y < x:
        result = y

    return result
    


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

Measured memory_bytes: 3064
n = int(input())
x = list(map(int, input().split()))

x_max = max(x)
x_min = min(x)
hp_min = 10000*100

for p in range(x_min, x_max + 1):
    hp = 0
    for x_i in x:
        hp += (x_i - p)**2
    if hp < hp_min:
        hp_min = hp
    
print(hp_min)

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

int main(){
int n,m,x;
cin >> n >> m >> x;

int a[15],cost;
int inf = 1100000000;
int ans = inf;

int v[15][15];

rep(i,n){
  rep(j,m+1) cin >> v[i][j];
}

rep(bit,1<<n){
  int cost =0;
  rep(i,n){
    if(bit&1<<i){
      cost +=v[i][0];
      rep(j,m) a[j]+=v[i][j+1];
    }
  }
  bool ok = true;
  rep(i,m){
    if(a[i]<x) ok = false;
  }
  if(ok) ans = min(ans,cost);
  rep(i,m) a[i]=0;
}

if(ans == inf) cout << -1 <<endl;
else cout << ans << endl;
return 0;
}


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

bool can(int delta_t,int delta_x,int delta_y){
    bool res;
    int s=delta_t-abs(delta_x)-abs(delta_y);
    res=(s>=0 && s%2==0)?true:false;
    return res;
}

int main(){
    int N;
    cin >> N;
    vector<int> t(N+1),x(N+1),y(N+1);
    string res="Yes";
    t[0]=x[0]=y[0]=0;
    for(int i=1;i<=N;i++){
        cin >> t[i] >> x[i] >> y[i];
    }  
    for(int i=0;i<N;i++){
        if (!can(t[i+1]-t[i],x[i+1]-x[i],y[i+1]-y[i])){
        res="No";
        break;
        }
    }
    cout << res;
}

Measured memory_bytes: 1408
//Hopcroft–Karp algorithm
//O(E*sqrt(v))
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<ll>

#ifndef ONLINE_JUDGE
#  define dbg(x) (cerr << #x << " = " << (x) << endl)
#else
#  define dbg(x) 0
#endif

#define MAX 100001
#define NIL 0
#define INF (1<<28)

vector< int > G[MAX];
int n,m,c,match[MAX],dist[MAX];
// n: number of nodes on left side, nodes are numbered 1 to n
// m: number of nodes on right side, nodes are numbered n+1 to n+m
// G = NIL[0] ∪ G1[G[1---n]] ∪ G2[G[n+1---n+m]]

bool bfs(){
    int i, u, v, len;
    queue<int>Q;
    for(i=1; i<=n; i++) {
        if(match[i]==NIL) {
            dist[i] = 0;
            Q.push(i);
        }
        else dist[i] = INF;
    }
    dist[NIL] = INF;
    while(!Q.empty()){
        u = Q.front(); Q.pop();
        if(u!=NIL) {
            len = G[u].size();
            for(i=0; i<len; i++) {
                v = G[u][i];
                if(dist[match[v]]==INF) {
                    dist[match[v]] = dist[u] + 1;
                    Q.push(match[v]);
                }
            }
        }
    }
    return (dist[NIL]!=INF);
}

bool dfs(int u){
    int i, v, len;
    if(u!=NIL) {
        len = G[u].size();
        for(i=0; i<len; i++) {
            v = G[u][i];
            if(dist[match[v]]==dist[u]+1) {
                if(dfs(match[v])) {
                    match[v] = u;
                    match[u] = v;
                    return true;
                }
            }
        }
        dist[u] = INF;
        return false;
    }
    return true;
}

int hopcroft_karp(){
    int matching = 0, i;
    // match[] is assumed NIL for all vertex in G
    while(bfs())
        for(i=1; i<=n; i++)
            if(match[i]==NIL && dfs(i))
                matching++;
    return matching;
}

int a[123], b[123], C[123], d[123];

void solve(){
    memset(G,0,sizeof(G));
    memset(dist,0,sizeof(dist));
    memset(match,0,sizeof(match));
    ll i,j;cin>>n;
    for(int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    for(int i = 1; i <= n; i++)
        cin >> C[i] >> d[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            if(a[i] < C[j] && b[i] < d[j]){
                G[i].emplace_back(n+j);
            }			
        }
    cout<<hopcroft_karp()<<endl;
}

int main(){
    solve();
}

Measured memory_bytes: 3328
#pragma once
#include <stdio.h>
#include <sstream>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const ll MAX = 210000;
const ll MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

int parent(int x) {
	if (x == pr[x]) return x;
	return pr[x] = parent(pr[x]);
}

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string & S) {
	int n = (int)S.size();
	vector<vector<int> > res(n + 1, vector<int>(26, n));
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];
		res[i][S[i] - 'a'] = i;
	}
	return res;
}
// mod 1000000007 の世界で a += b する関数
void add(long long& a, long long b) {
	a += b;
	if (a >= MOD) a -= MOD;
}
bool use[100010];
ll n, m;
ll a[100010];
ll sa[100010];
ll calc(int x,ll c) {

	if (x > n) {
		return c * (c + 1LL) / 2LL;
	}
	ll v = sa[x] - sa[x - 1];
	use[x] = true;

	if (v % m == 0) {
		return calc(x + 1, c + 1);
	}

	ll rem = m - (v % m);
	while (true)
	{
		ll nex = rem + sa[x];
		if (nex > sa[n]) {
			ll res = 0;
			return c * (c + 1LL) / 2LL;
		}
		ll* p = lower_bound(sa, sa + n, nex);

		if (*p == nex) {
			ll pos = p - sa;
			return calc(pos + 1, c + 1);
		}
		else {
			rem += m;
		}
	}


}

void solv() {
	
	cin >> n >> m;
	for (size_t i = 0; i < n; i++)
	{
		cin >> a[i];
		a[i] %= m;
	}

	sa[0] = 0;
	for (size_t i = 1; i <= n; i++)
		sa[i] = a[i - 1] + sa[i - 1];
	ll res = 0;
	
	for (size_t i = 1; i <= n; i++)
	{
		ll bas = a[i];
		if (use[i]) {
			continue;
		}
		res += calc(i,0);
	}

	cout << res << endl;
}

int main() {
	//COMinit();
	solv();

	return 0;
}


Measured memory_bytes: 1920
from math import sqrt
from itertools import accumulate

prime = [2]
more_prime = [0] * 100000
for i in range(3, 100000):
	j = 2
	while j <= sqrt(i):
		if i % j == 0:
			break
		j += 1
	else:
		prime.append(i)
		if (i + 1) // 2 in prime:
			more_prime[i-1] = 1

ans = list(accumulate(more_prime))

q = int(input())
for _ in range(q):
	l, r = map(int, input().split())
	if l == 1:
		l = 2
	if r == 1:
		r = 2
	print(ans[r-1] - ans[l-2])

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

int main() {
  int a,b;
  cin >> a >> b;
  int ans = 0;
  if(a>b) {
    ans = a;
    a--;
  }
  else {
    ans = b;
    b--;
  }
  if(a>b) ans += a;
  else ans += b;
  cout << ans;
}

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

int main()
{
	int n,sum=0,ans=0;
	string s;
	cin>>n>>s;
	
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='R')
		sum++;
	}
	for(int i=0;i<sum;i++)
	{
		if(s[i]=='W')
		 ans++;
	}
	
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3756
import sys
input=sys.stdin.readline
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):#selfとotherが同じグループに属するか
        return self.root()==other.root()

N=int(input())
X=[]
Y=[]
for i in range(N):
  x,y=map(int,input().split())
  X.append([x,i])
  Y.append([y,i])
X.sort()
Y.sort()
G=[]
for i in range(N-1):
  G.append([X[i+1][0]-X[i][0],X[i][1],X[i+1][1]])
  G.append([Y[i+1][0]-Y[i][0],Y[i][1],Y[i+1][1]])
G.sort()
U=[UnionFindNode(i) for i in range(N)]
ans=0
for i in range(len(G)):
    c,a,b=G[i]
    if U[a].is_group(U[b]):
        continue
    U[a].unite(U[b])
    ans+=c
    if U[0].size()==N:
        print(ans)
        quit()


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

using namespace std;

typedef long long ll;

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 (a>b) { a=b; return 1; } return 0; }

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

	int d, t,s;
	cin >> d >> t >> s;

	if(d <= t * s){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

}


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

int main(){
    std::string s;
    std::cin >> s;
    if(s == "Sunny"){
        std::cout << "Cloudy";
    }
    else if(s == "Cloudy"){
        std::cout << "Rainy";
    }
    else if(s == "Rainy"){
        std::cout << "Sunny";
    }
    else {
        std::cout << "unexpected input";
        return -1;
    }

    return 0;
}


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



int main() {

    int N;
    int A[100001];
    cin >> N;
    for (int i = 0; i < N + 1; i++) cin >> A[i];
    //今の深さの点の数
    long long now = 1;
    //int mae = 0;
    long long ans = 0;
    //末端の数
    long long sum = 0;
    //分岐した回数
    long long route = 1;
    
    for (int i = 0; i < N + 1; i++)
    {
        sum += A[i];
    }
    long long s = sum;
    //cout << sum << endl;
    for (int i = 0; i < N + 1; i++)
    {
        /*
        //cout << now <<route<< endl;
        ans += now;
        //cout << now<< " ";
        now -= A[i];
        sum -= A[i];
        now = min(now * 2, sum);

        //cout << now << endl;
        if (i != N && now <= 0)
        {
            cout << -1 << endl;
            return 0;
        }
        else if (i == N && now != 0)
        {
            cout << -1 << endl;
            return 0;
        }*/

        
        ans += now;
        now -= A[i];
        s -= A[i];
        //できるだけ早く分岐しておく
        long long a = now;
        
        //now 2倍ルート
        if (route + a < sum)
        {
            //新しい分岐はa個
            now += a;
            route += a;
        }
        //nowがそれ以降の和になるルート
        else
        {
            //基本的にrouteは1+枝の数
            //ある瞬間のroute-1がそれまでの葉の数と等しければいい
            //分岐した数だけ葉が増える、route+=nはA[i]=nを意味する
            //つまりrouteはそれまでのA[i]の和、route= sum-sumA[i]
            //now-A[i]（分岐＝葉の数）=葉以外の数、
            //葉の枚数＋全部の和-分岐の数（）

            //now=sum-sumA[i-1]なら、

            //新しい分岐はsum-route個
            //（最終的な道の数）ー（今の道の数）をnow（今の道の数）に足して（最終的な道の数）にする
            //now += sum - route;
            now = s;
            route += sum - route;
        }
        //now = min(a * 2, s);

        if (i != N && now <= 0)
        {
            cout << -1 << endl;
            return 0;
        }
        else if (i == N && now != 0)
        {
            cout << -1 << endl;
            return 0;
        }


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

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

int main() {
  int a, b, c;
  cin >> a >> b >> c;

  vector<int> v = {a, b, c};
  sort(v.begin(), v.end());

  cout << v.at(0) + v.at(1) << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, K = map(int, input().split())
V = list(map(int, input().split()))

ans = 0
for pick in range(min(K+1, N+1)):
    for right in range(pick+1):
        left = pick-right
        tmp_list = V[:right]+V[N-left:]
        tmp_list = sorted(tmp_list)
        tmp_ans = sum(tmp_list)
        rem = min(K-pick, len(tmp_list))
        for i in range(rem):
            if tmp_list[i] < 0:
                tmp_ans -= tmp_list[i]
            else:
                break
        ans = max(tmp_ans, ans)
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, n) for(int i = 1; i <= (int)(n); i++)
const long long INF = 1LL << 60;
const double PI=3.14159265358979323846;
int main() 
{
    int n;
    cin >> n;

    cout << (n-1)/2 << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
int i,n;
  long int max, min,sum;
  long int tmp;
  max = 0; min = 0; sum = 0;
  scanf("%d ",&n);
  for (i = 0;i < n;i++)
    {
      scanf("%ld",&tmp);
      if (i == 0)
        {
          min = tmp;
          max = tmp;
        }
      else{
      if(max < tmp)max = tmp;
      if(min > tmp)min = tmp;
      }
         sum += tmp;
    }
  printf("%ld %ld %ld\n",min,max,sum);
return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <utility>
#include <numeric>
#include <stdint.h>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int N, K;
  cin >> N >> K;
  vector<int> V;

  for (int n=0; n<N; ++n) {
    int v;
    cin >> v;
    V.push_back(v);
  }

  int max_v = 0;

  for (int get = 0; get<=K && get<=N; ++get) {
    for (int get_left = 0; get_left <= get; ++get_left) {
      int get_right = get - get_left;
      set<int> got_v;

      vector<int> got_v_v(got_v.begin(), got_v.end());

      got_v_v.insert(got_v_v.end(),V.begin(), V.begin()+get_left);
      got_v_v.insert(got_v_v.end(),V.end()-get_right, V.end());

      sort(got_v_v.begin(), got_v_v.end());
      
      for (int refund = 0; refund<K-get && refund<got_v_v.size(); ++refund) {
	got_v_v[refund] = max(0, got_v_v[refund]);
      }

      max_v = max(max_v, accumulate(got_v_v.begin(), got_v_v.end(), 0));
    }
  }

  cout << max_v << endl;

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>

using namespace std;
typedef long long ll;
#define INF int(1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define REPONE(i, n) for(int i = 1; i <= (int)(n); i++)
#define EACH(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)

int abc[3], n_min = INF, idx_min = 0, n_max = 0, idx_max = 0;

void solve() {
    int ans = 0;
    sort(abc, abc + 3);
    // max, minで偶奇一致
    if (abc[0] % 2 == abc[2] % 2) {
        if (abc[0] % 2 == abc[1] % 2) {
            int times1 = (abc[2] - abc[0]) / 2;
            int times2 = (abc[2] - abc[1]) / 2;
            ans += times1 + times2;
        } else {
            int times1 = (abc[2] - abc[0]) / 2;
            int times2 = (abc[2] + 1 - abc[1]) / 2;
            abc[1] = abc[2] + 1;
            ans += times1 + times2 + 1;
        }
    } else {
        if (abc[0] % 2 == abc[1] % 2) {
            int times = (abc[1] - abc[0]) / 2;
            ans += times, abc[0] = abc[1];
            ans += abc[2] - abc[0];
        } else {
            int times1 = (abc[2] - abc[1]) / 2;
            int times2 = (abc[2] + 1 - abc[0]) / 2;
            abc[0] = abc[2] + 1;
            ans += times1 + times2 + 1;
        }
    }
    cout << ans << endl;
}

int main() {
    REP(i, 3) {
        cin >> abc[i];
    }
    solve();
    return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextLong()
    val s = (0 until n).map { sc.next() }
    println(problem058c(n, s))
}

fun problem058c(n: Long, s: List<String>): String {
    var ans = ""
    ('a'..'z').forEach { char ->
        var count = Integer.MAX_VALUE
        s.forEach {
            val tmpCount = it.filter { it == char }.count()
            count = Math.min(count, tmpCount)
        }
        if (count != 0) {
            (1..count).forEach {
                ans += char
            }
        }
    }
    return ans
}

Measured memory_bytes: 29896
from heapq import heappush,heappop
from collections import deque

def main():
  n,m,s,t=map(int,input().split())
  INF=10**20
  G1,G2 = [{} for _ in range(n)],[{} for _ in range(n)]
  for i in range(m):
    u,v,a,b=map(int,input().split())
    G1[u-1][v-1] = G1[v-1][u-1] = a
    G2[u-1][v-1] = G2[v-1][u-1] = b

  def dijkstra(G,start = 0):
      d = [INF for i in range(len(G))]
      d[start] = 0
      que = []
      heappush(que, (0, start))

      while len(que):
          p = heappop(que)
          v = p[1]
          if d[v] < p[0]:
              continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, (d[u], u))
      return d

  d1 = dijkstra(G1,s-1)
  d2 = dijkstra(G2,t-1)

  ans=deque()
  MIN = INF
  for i in range(n-1,-1,-1):
    MIN = min(MIN,d1[i]+d2[i])
    if i == s-1:
      MIN = min(MIN,d2[s-1])
    if i == t-1:
      MIN = min(MIN,d1[t-1])

    ans.appendleft(10**15-MIN)

  print(*ans)
  
if __name__=="__main__":
  main()

Measured memory_bytes: 93128
#include<iostream>
using namespace std;
#define MAX 100
#define INFTY 2001
#define WHITE 0
#define GRAY 1
#define BLACK 2

int M[MAX][MAX], d[MAX];

void prim(int n){
  int color[MAX], u;

  // 初期化
  for(int i=0; i<n; i++){
    color[i] = WHITE;
    d[i] = INFTY;
  }
  d[0] = 0;
  //p[0] = -1;

  while(true){
    int mincost = INFTY;
    for(int i=0; i<n; i++){
      if(color[i] != BLACK && d[i] < mincost){
        mincost = d[i];
        u = i;
      }
    }

    if(mincost == INFTY) break;

    color[u] = BLACK;

    for(int v=0; v<n; v++){
      if(color[v] != BLACK && M[u][v] != INFTY){
        if(M[u][v] < d[v]){
          d[v] = M[u][v];
          //p[v] = u;
          color[v] = GRAY;
        }
      }
    }
  }
}

int main(void){
  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin >> M[i][j];
      if(M[i][j] == -1) M[i][j] = INFTY;
    }
  }

  prim(n);

  // 最小全域木の辺の重みの総和を計算
  int u = 0;
  int d_sum = 0;
  for(int i=0; i<n; i++){
    if(true){
      d_sum += d[i];
    }
  }
  cout << d_sum << endl;
  return 0;
}



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

int main(){
  int n, a, b; cin >> n >> a >> b;
  int hp[n];
  int high = 0;
  for(int i = 0; i < n; ++i) {
	cin >> hp[i];
    if(high < hp[i]) high = hp[i];
  }
  int max_turn = (high + b -1)/b;
  int left = 0;
  int right = max_turn;
  int addition = a-b;
  int ans;
  while(right > left){
    int center = (right + left) / 2;
    // cout << "center(Turns): " << center << endl;
    long long cnt = 0;
    for(int i = 0; i < n; ++i){
      if(hp[i] <= (long long)b * (long long)center) continue;
      else {
        cnt += (hp[i]-b*center + addition-1)/addition;
      }
    }
    if(cnt <= center) right = center;
    else left = center+1;
    
    center = (right + left)/2;
    ans = center;
  }
  cout << ans << endl;
  return 0; 
}

Measured memory_bytes: 4000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#ifdef cold66
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<", ";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}
template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=0x3f3f3f3f;

vector<ll> a,b,c;
ll d[MAXn];
int main(){
  IOS();
  ll n;
  cin >> n;
  REP (i,n) {
    cin >> d[i];
    if (d[i]%4 == 0) a.eb(i);
    else if (d[i]%2 == 0) b.eb(i);
    else c.eb(i);
  }

  if (!SZ(b) && SZ(c) > SZ(a)+1) cout << "No" << endl;
  else if (SZ(b) && SZ(c) > SZ(a)) cout << "No" << endl;
  else cout << "Yes" << endl;
}


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

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecbool vector<bool>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)

int main()
{
  ll n, a, c=0;
  cin >> n;
  forll(i, 0, n){
	cin >> a;
	c += (a-1);
  }
  cout << c << endl;
}

Measured memory_bytes: 256
#include <algorithm> // std::sort(begin,end), std::min, std::max
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <utility> // std::swap
#include <vector>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
//  << std::setprecision(15)

// NOTE:kModは素数！
const long long kMod = 1000000007; // 10^9 + 7
const int N = 1000000;
vector<long long> fac = {1ll};
// iの階乗( i! mod (kMod) )のメモ化用 // factorial

// O(log n) ただしnはmodを取られるので、ほぼ定数
ll modPower(ll k, ll n) { // k の n乗を計算
  k %= kMod;
  if (n == 0 || k == 1) {
    return 1;
  } else if (n < 0) {
    // k^(kMod - 1) = 1 (mod kMod) を活用
    n %= kMod - 1;
    n += kMod - 1;         // %は負の数のまま計算されるので
    return modPower(k, n); // 0 < n < kMod -1;
  } else if (n >= kMod - 1) {
    // k^(kMod - 1) = 1 (mod kMod)
    n %= kMod - 1;
    return modPower(k, n);
  } else if (n % 2) {
    return (modPower(k, n - 1) * k) % kMod;
  } else {
    ll tmp = modPower(k, n / 2);
    return (tmp * tmp) % kMod;
  }
}

// メモ化しつつnの階乗を計算
ll modFact(ll n) {
  if (n <= 0) {
    return 1;
  } else if ((ll)fac.size() > n && fac[n] != 0) {
    return fac[n];
  }

  if ((ll)fac.size() <= (ll)n) {
    fac.resize(2 * n);
  }

  ll i = 1;

  while (fac[i] != 0 && i <= n) // i<= n is for avoiding infinite loop
    i++;

  while (i <= n) {
    fac[i] = ((ll)fac[i - 1] * (ll)(i % (ll)kMod)) % kMod;
    i++;
  }

  return fac[n];
}

ll modIFact(ll n) { return modPower(modFact(n), -1); }

ll modComb(ll n, ll m) {
  ll tmp = modFact(n);
  ll tmp2 = modIFact(m);
  ll tmp3 = modIFact(n - m);
  tmp = (tmp * tmp2) % kMod;
  tmp = (tmp * tmp3) % kMod;
  return tmp;
}

int main() {
  ll x, y;
  cin >> x >> y;
  ll diff = abs(x - y);
  ll same = max(x, y) - diff * 2;
  if ((same % 3) || same < 0) {
    cout << 0 << endl;
    return 0;
  }
  same /= 3;

  cout << modComb(same * 2 + diff, same) << endl;
  return 0;
}


Measured memory_bytes: 10624
#include <stdio.h>
#include <stdlib.h>
#define INFINITY 1000000001
 
int pertition(int*, char*, int, int);
void quickSort(int*, char*,int, int);
int check(int,int*, char*, int*, char*);
void merge(int *, char *, int, int, int);
void mergeSort(int *, char *, int, int);
 
main(){
  int n, i, r, *Ad, *cpyAd;
  char *Ac, *cpyAc;
 
  scanf("%d", &n);
  Ad = malloc(sizeof(int)*n);
  Ac = malloc(sizeof(char)*n);
  cpyAd = malloc(sizeof(int)*n);
  cpyAc = malloc(sizeof(char)*n);
 
  for(i=0; i<n; i++){
    scanf(" %c", Ac+i);
    scanf("%d", Ad+i);
    cpyAc[i] = Ac[i];
    cpyAd[i] = Ad[i];
    //printf("i=%d\n", i);
  }
 
  quickSort(Ad, Ac, 0, n-1);
   
  if(check(n, Ad, Ac, cpyAd, cpyAc)) printf("Stable\n");
  else printf("Not stable\n");
  for(i=0; i<n; i++){
    printf("%c %d\n", Ac[i], Ad[i]);
  }
 
  return 0;
}
 
void quickSort(int *A, char *A2, int p, int r){
  int q;
 
  if(p < r){
    q = partition(A, A2, p, r);
    quickSort(A, A2, p, q-1);
    quickSort(A, A2, q+1, r);
  }
}
 
int partition(int *A, char *A2, int p, int r){
  int x = A[r];
  int i = p-1;
  int j, tmp;
  char tmp2;
 
  for(j=p; j<r; j++){
    if(A[j] <= x){
      i = i+1;
      tmp = A[i];
      tmp2 = A2[i];
      A[i] = A[j];
      A[j] = tmp;
      A2[i] = A2[j];
      A2[j] = tmp2;
    }
  }
  tmp = A[i+1];
  A[i+1] = A[r];
  A[r] = tmp;
  tmp2 = A2[i+1];
  A2[i+1] = A2[r];
  A2[r] = tmp2;
 
  return i+1;
}
 
int check(int n, int *Ad, char *Ac, int *oriAd, char *oriAc){
// 安定なソートであるMergeSortの結果と比較する
// 安定 : 1
// 安定でない : 0
  int i;
 
mergeSort(oriAd, oriAc, 0, n);
 
#ifdef DEBUG
  printf("\n****** MergeSort ******\n");
  for(i=0; i<n; i++) printf("%c %d\n", oriAc[i], oriAd[i]);
  printf("\n***********************\n");
#endif
 
  //アルファベットについて一致するか判定
  for(i=0; i<n; i++){
    if(/*QuickSort*/Ac[i] != /*MergeSort*/oriAc[i]) return 0;
  }
  return 1;
}
 
void merge(int *arryA, char *arryB, int left, int mid, int right){
  int n1, n2, i, j, k, *arryL, *arryR;
  char *arryLc, *arryRc;
 
  n1 = mid - left;
  n2 = right - mid;
 
  arryL = (int *)malloc(sizeof(int)*(n1 + 1));
  arryR = (int *)malloc(sizeof(int)*(n2 + 1));
  arryLc = (char *)malloc(sizeof(char)*(n1 + 1));
  arryRc = (char *)malloc(sizeof(char)*(n2 + 1));
  for(i=0; i<n1; i++){
    arryL[i] = arryA[left+i];
    arryLc[i] = arryB[left+i];
    //printf("++ arrLc[%d] = %c\n", i, arryB[left+i]);
  }
  for(i=0; i<n2; i++){
    arryR[i] = arryA[mid+i];
    arryRc[i] = arryB[mid+i];
    //printf("++ arrRc[%d] = %c\n", i, arryB[mid+i]);
  }
  arryL[n1] = INFINITY;
  arryR[n2] = INFINITY;
 
  i=0;//L
  j=0;//R
 
  for(k=left; k<right; k++){
    if(arryL[i] <= arryR[j]){
      arryA[k] = arryL[i];
      arryB[k] = arryLc[i];
      i++;
    }
    else{
      arryA[k] = arryR[j];
      arryB[k] = arryRc[j];
      j++;
    }
  }
 
  free(arryL);
  free(arryR);
  free(arryLc);
  free(arryRc);
}
 
void mergeSort(int *arryA, char *arryB,int left, int right){
  int mid;
 
  if(left+1 < right){
    mid = (right + left) / 2;
    mergeSort(arryA, arryB, left, mid);
    mergeSort(arryA, arryB, mid, right);
    merge(arryA, arryB, left, mid, right);
  }
}

Measured memory_bytes: 1916
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define YY cout << "Yes" << endl;
#define NN cout << "No" << endl;
#define ve vector
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
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); }
// *max_element(all(d))
// priority_queue<int,vector<int>,greater<int>>
int solve(){
  int h,w;
  cin >> h >> w;
  vector<string>s(h);
  rep(i,h){
    string tmp;
    cin >> tmp;
    s[i] = tmp;
  }
  Graph G(h * w);
  rep(i,h)rep(j,w){
    int now = i * w + j;
    if(j != w - 1)
    if(s[i][j] != '#' && s[i][j + 1] != '#'){
      G[now].push_back(now + 1);
      G[now + 1].push_back(now);
    }
    if(i != h - 1)
    if(s[i][j] != '#' && s[i + 1][j] != '#'){
      G[now].push_back(now + w);
      G[now + w].push_back(now);
    }
  }
  vector<int>back(h * w),dist(h * w, -1);
  queue<int>q;
  dist[0] = 0;
  q.push(0);
  while(!q.empty()){
    int now = q.front();
    q.pop();
    for(auto i : G[now]){
      if(dist[i] != -1)continue;
      q.push(i);
      dist[i] = dist[now] + 1;
      back[i] = now;
    }
  }
  int cnt[100000];
  int next = back[h * w - 1];
  cnt[0]++;
  cnt[h * w - 1]++;
  rep(i,dist[h * w - 1]){
    cnt[next]++;
    next = back[next];
  }
  ll ans = 0;
  rep(i,h)rep(j,w){
    int now = i * w + j;
    if(s[i][j] == '.' && (!cnt[now]))ans++;
  }
  if(dist[h * w - 1] != -1)cout << ans << endl;
  else cout << -1 << endl;
  return 0;
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  // cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

def bisearch_max(mn, mx, func):
    """ 条件を満たす最大値を見つける二分探索 """

    ok = mn
    ng = mx
    while ok+1 < ng:
        mid = (ok+ng) // 2
        if func(mid):
            # 上を探しに行く
            ok = mid
        else:
            # 下を探しに行く
            ng = mid
    return ok

class RollingHash:

    MOD = 2 ** 64
    b = 10 ** 8 + 7

    def __init__(self, S):
        # 各文字を数値に変換しておく
        S = [ord(s)-97 for s in S]

        self.len = len(S)
        self.pow = [1] * (self.len+1)
        for i in range(self.len):
            self.pow[i+1] = self.pow[i] * self.b
            self.pow[i+1] %= self.MOD
        # ハッシュの生成
        self.hash = [0] * (self.len+1)
        for i in range(self.len):
            self.hash[i+1] = self.hash[i] * self.b + S[i]
            self.hash[i+1] %= self.MOD
    
    # 区間[i,j)のハッシュ値を取得
    def get(self, l, r):
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.MOD

def calc(m):
    A = {}
    for i in range(N-m+1):
        a_hash = rh.get(i, i+m)
        if a_hash in A:
            # a_hashが2回目以降に出現したindex
            j = A[a_hash]
            # iとjがm以上離れているかどうか
            if i-j >= m:
                return True
        else:
            # a_hashが最初に出現したindex
            A[a_hash] = i
    return False

rh = RollingHash(S)
print(bisearch_max(0, N, calc))


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

int main() {
    int N;
    cin >> N;
    int x[N],y[N],v[9] = {0,1,2,3,4,5,6,7,8};
    for(int i=0;i<N;i++) cin >> x[i] >> y[i];
    double ans = 0;
    int c = 0;
    do
    {
        for(int i=0;i<N-1;i++) ans += sqrt(pow(x[v[i+1]]-x[v[i]], 2)+pow(y[v[i+1]]-y[v[i]],2));
        c++;
    } while (next_permutation(v,v+N));
    cout << fixed << setprecision(10) <<ans / c << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (X,Y,Z) = readIntList()

    println("$Z $X $Y")
}

fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)

Measured memory_bytes: 37856
#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 << a * b << endl;
    else if (a * b > c * d)
        cout << a * b << endl;
    else
        cout << c * d << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define F first
#define S second
#define pb emplace_back
#define mt make_tuple
#define gcd __gcd
#define PI 3.141592653589
// Input
#define in(a) scanf("%d",&a)
#define in2(a,b) scanf("%d%d",&a,&b)
#define in3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define llin(a) cin >> a
#define inl(a) scanf("%lld",&a)
#define read(v,i,n) for(i=0;i<n;i++)in(v[i])
#define twod(mat,i,j,n,m) rep(i,n){rep(j,m)in(mat[i][j]);}
#define sc(ch) scanf("%c",&ch)
#define sstr(str) scanf("%s",str)
// Output
#define pr(a) printf("%d ",a)
#define pr2(a,b) printf("%d %d\n",a,b)
#define pr3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out(a) printf("%d\n",a)
#define outl(a) printf("%lld\n",a)
#define llpr(a) cout << a << " "
#define llout(a) cout << a << "\n"
#define yes printf("YES\n")
#define no printf("NO\n")
#define lin printf("\n")
// Iterator
#define lp(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
#define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
#define tf(mytuple) get<0>(mytuple)
#define ts(mytuple) get<1>(mytuple)
#define tt(mytuple) get<2>(mytuple)
// Debug
#define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
#define what(x) cerr << #x << " : " << x << "\n"
#define ck printf("continue\n")
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
	cerr << *it << " = " << a << "\n";
	err(++it, args...);
}
// Data Type
#define ll long long int
#define ii pair<int,int>
#define pli pair<ll,int>
#define triple tuple<int,int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define viii vector<pair<pair<int,int>,int> >
#define vvii vector<vector<pair<int,int> > >
#define M 1000000000
#define N 200005  //check the limits, man
vvii ad(N);
int edge[N];
void dfs(int s,int p,int col)
{
    int i,a,x=ad[s].size(),k=1;
    rep(i,x)
    {
        a=ad[s][i].F;
        if(k==col)
            k++;
        if(a!=p)
            edge[ad[s][i].S]=k++;
    }
    rep(i,x)
    {
        a=ad[s][i].F;
        if(a!=p)
            dfs(a,s,edge[ad[s][i].S]);
    }
}
int main()
{
    int i,n,a,b;
    in(n);
    rep(i,n-1)
    {
        in2(a,b);
        a--,b--;
        ad[a].pb(b,i);
        ad[b].pb(a,i);
    }
    dfs(0,-1,-1);
    a=0;
    rep(i,n-1)
        a=max(a,edge[i]);
    out(a);
    rep(i,n-1)
        out(edge[i]);
}


Measured memory_bytes: 9856