akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 210
#define inf 2147483647
using namespace std;
struct edge{int x, y, l, next;}a[100010];
int n, m, l, p[N], T, x1, y1, x2, y2, lev[N], q[N], ans;
char S[N];
inline void add(int x, int y, int z){
	a[++l].x=x; a[l].y=y; a[l].l=z; a[l].next=p[x]; p[x]=l;
	a[++l].x=y; a[l].y=x; a[l].l=0; a[l].next=p[y]; p[y]=l;
}
inline int bfs(){
	queue<int>q; q.push(0);
	memset(lev, 0, sizeof(lev)); lev[0]=1;
	while(!q.empty()){
		int v=q.front(); q.pop();
		for(int i=p[v]; i; i=a[i].next)
			if(a[i].l&&!lev[a[i].y]){
				lev[a[i].y]=lev[v]+1;
				if(a[i].y==T)return 1;
				q.push(a[i].y);
			}
	}
	return 0;
}
inline int dfs(int x, int ss){
	if(x==T||!ss)return ss;
	int s1=ss;
	for(int i=q[x]; i&&ss; i=a[i].next)
		if(lev[a[i].y]==lev[x]+1){
			int tt=dfs(a[i].y, min(ss, a[i].l));
			q[x]=i; ss-=tt; a[i].l-=tt; a[i^1].l+=tt;
		}
	if(s1==ss)lev[x]=-1;
	return s1-ss;
}
int main(){
	scanf("%d%d", &n, &m);
	l=1; memset(p, 0, sizeof(p)); T=n+m+1;
	for(int i=1; i<=n; i++){
		scanf("%s", S+1);
		for(int j=1; j<=m; j++){
			if(S[j]=='o'){add(i, n+j, 1); add(n+j, i, 1);}
			if(S[j]=='S'){x1=i; y1=j;}
			if(S[j]=='T'){x2=i; y2=j;}
		}
	}
	if(x1==x2||y1==y2){printf("-1"); return 0;}
	add(0, x1, inf); add(0, n+y1, inf);
	add(x2, T, inf); add(n+y2, T, inf);
	ans=0; while(bfs()){memcpy(q, p, sizeof(q)); ans+=dfs(0, inf);}
	printf("%d", ans);
	return 0;
}

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

#define INF 1e9
using namespace std;
typedef long long ll;

int main() {

    int n; cin >> n;

    int ans = INF;

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

        if (a % 2 != 0) {
            ans = 0;
            break;
        }

        int tmp = 0;

        while (a % 2 == 0) {
            a /= 2;
            ++tmp;
        }

        ans = min(ans, tmp);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
A = []
for _ in range(5):
    A.append(int(input()))
ans = 0
maxx = 0
for i in A:
    x = 0
    if str(i)[-1] != '0':
        x = 10 - int(str(i)[-1])
        if x > maxx:
            maxx = x
    ans += (i + x)
print(ans - maxx)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++) //for文マクロ
using namespace std;

typedef unsigned long ul;
typedef long long ll;
typedef pair<ul, ul> P; //ペア　タイプでふ

int main()
{
    int n = 0;
    cin >> n;
    vector<int> vec(n);
    REP(i, n)
    {
        cin >> vec[i];
    }
    int count = 0;
    for (int i = 1; i < n - 1; i++)
    {
        if ((vec[i - 1] < vec[i] && vec[i] < vec[i + 1]) || (vec[i + 1] < vec[i] && vec[i] < vec[i - 1]))
        {
            count++;
        }
    }
    cout << count;
}


Measured memory_bytes: 256
H, W = gets.chomp.split.map(&:to_i)
s = []
ans = Array.new(H).map{Array.new(W)}
H.times do
    s << gets.chomp.split("")
end

H.times do |h|
    W.times do |w|
        if s[h][w] == "#" then
            ans[h][w] = "#"
            next
        else 
            res = 0
            [-1, 0, 1].each do |i|
               [-1, 0, 1].each do |j|
                   next if h+i < 0 || w+j < 0 || h+i >= H || w+j >= W
                   res += 1 if s[h+i][w+j] == "#"
               end
           end
           ans[h][w] = res
        end
    end
end

ans.each do |row|
    puts row.join("")
end

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

using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VS = vector<string>;
using PII = pair<int, int>;
using VPII = vector<PII>;

#define sz(var) (int)var.size()
#define REP(var, start, end) for(int var = start; var < (int)end; ++var)

/*
    
*/


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
	//freopen("tmp.in", "r", stdin);
//	freopen("tmp.out", "w", stderr);
#endif
    string odd, even;
    cin >> odd >> even;

    int n = sz(odd) + sz(even), oddidx = 0, evenidx = 0;

    string ans;
    for(int i = 0; i < n; ++i)
    {
        if(i % 2 == 0){
            ans += odd[oddidx];
            ++oddidx;
        }
        else
        {
            ans += even[evenidx];
            ++evenidx;
        }
    }

  //  assert(ans == "aattccooddeerrbreeggiunlnaerrccoonntteesstt");
    cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define sz 1000009
int main()
{
// 	bitset<sz>bs;
// 	bs.reset();
	int n;scanf("%d",&n);
	long long int sum = 0;
	for(int i=1;i<=n;i++)
	{
		if(i%3 == 0)continue;
		if(i%5 ==0)continue;
		sum+=i;
	}
	printf("%lld\n",sum);
	return 0;
}

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

int main() {
    long long result = 1;
    int n;
    string s1, s2;
    //scanf("%d", &n);
    cin >> n >> s1 >> s2;
    int len = s1.size();
    int oldtype = 0, type = 0;
    for (int i = 0; i < len; i++) {
        oldtype = type;
        if (s1[i] == s1[i+1]) {
            type = 1;
            i++;
            if (oldtype == 1) result *= 3;
            else if (oldtype == 2) result *= 2;
            else result *= 6;
        } else {
            type = 2;
            if (oldtype == 1) result *= 1;
            else if (oldtype == 2) result *= 2;
            else result *= 3;
        }
        result %= 1000000007;
    }
    printf("%lld\n", result);
    return 0;
}


Measured memory_bytes: 256
def poland(input)
  num = []
  ope = ''

  loop do
    break if input.empty?
    ope = input.shift
    case ope
    when '+'
      a = num.pop
      b = num.pop
      num << a + b
    when '-'
      a = num.pop
      b = num.pop
      num << b - a
    when '*'
      a = num.pop
      b = num.pop
      num << a*b
    when '/'
      a = num.pop
      b = num.pop
      num << a/b
    else
      num << ope.to_i
    end
  end

  p num[0]
end

if __FILE__ == $0
  poland gets.chomp.split
end

Measured memory_bytes: 6108
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int cnt = 0;
    int tmpN = N;
    while (tmpN > 0)
    {
        cnt += tmpN % 10;
        tmpN /= 10;
    }
    if (N % cnt == 0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
//ヘッダー
#include<bits/stdc++.h>
using namespace std;
 
//型定義
typedef long long ll;
 
//定数
const int INF=1e+9;
const int MOD=1e+9+7;
 
//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)
 
//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値
 
//グローバル変数
 
vector<long long> fact, fact_inv, inv;
//ライブラリ挿入
//二項係数前処理計算量O(SIZE)
void init_nCk(int SIZE) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
}
    
//nCk　計算量(1)
long long nCk(int n, int k) {
    assert(!(n < k));
    assert(!(n < 0 || k < 0));
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;
}
 
int main(){
    int N,K;
    cin>>N>>K;
    vector<ll> A(N);
    REP(i,N)cin>>A[i];
    sort(A.begin(),A.end());
    ll ans=0;
    ll tmp;
 
    init_nCk(N);
    if(K==1){
        cout<<0<<endl;
        return 0;
    }

    vector<ll> g(N,0),h(N,0);

    REP(i,N){
        if(i>=K-1) g[i]=(A[i]*nCk(i,K-1))%MOD;
        if(i<=N-K) h[i]=(A[i]*nCk(N-i-1,K-1))%MOD;
    }

    REP(i,N){
        ans+=(g[i]-h[i]);
        while(ans<0){
            ans+=MOD;
        }
        ans%=MOD;
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 4992
n = int(input())
a = list(map(int, input().split()))

ans = [0 for _ in range(n)]

for i in range(n):
    p = False
    for j in range(len(a)-1, -1, -1):
        if a[j] == j+1:
            ans[n-1-i] = a.pop(j)
            p = True
            break

    if not p:
        print(-1)
        exit()

for ai in ans:
    print(ai)

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

#define int long long
#define fast_io(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(x) x.begin(),x.end()
#define us unordered_set
#define um unordered_map
#define ms multiset
#define mm multimap
#define pb push_back
#define pf push_front
#define ins insert
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define _max max_element
#define _min min_element
#define tc(T) int T; cin>>T; while(T--)
#define q(q) int q; cin>>q; while(q--)
#define pi 3.1415926535897932384626433832
const int pinf=((int)9e18);
const int ninf=((int)-9e18);
const int mod=1000000007;

using namespace std;

int32_t main()
{
    fast_io();

    //FILE *fptr1=freopen("in.txt","r",stdin);
    //FILE *fptr2=freopen("out.txt","w",stdout);
    
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    
    if(a==12)
        a=1;
    else
        a++;
    
    if(a==c) cout<< "1";
    else cout<< "0";
    

    return 0;
}


Measured memory_bytes: 3696
import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import deque
def main():
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    maze = []
    dummy_row = ['#'] * (w + 4)
    maze.append(dummy_row)
    maze.append(dummy_row)
    for _ in range(h):
        row = ['#'] * 2 + list(input()) + ['#'] * 2
        maze.append(row)
    maze.append(dummy_row)
    maze.append(dummy_row)
    maze[ch + 1][cw + 1] = 0
    maze[dh + 1][dw + 1] = 'G'
    q = deque()
    q.append((ch+1, cw+1))
    r = float('inf')
    move_y = [-1, 0, 1, 0]
    move_x = [0, 1, 0, -1]
    while q:
        koko = q.popleft()
        koko_y = koko[0]
        koko_x = koko[1]
        koko_num = maze[koko_y][koko_x]
        for k1 in range(4):
            j1 = koko_y + move_y[k1]
            j2 = koko_x + move_x[k1]
            if maze[j1][j2] == 'G':
                r = min(r, koko_num)
            elif maze[j1][j2] == '.':
                maze[j1][j2] = koko_num
                q.appendleft((j1, j2))
            elif type(maze[j1][j2]) == int:
                if maze[j1][j2] > koko_num:
                    maze[j1][j2] = koko_num
                    q.appendleft((j1, j2))
        for i1 in range(koko_y - 2, koko_y + 3):
            for i2 in range(koko_x - 2, koko_x + 3):
                if maze[i1][i2] == 'G':
                    r = min(r, koko_num + 1)
                elif maze[i1][i2] == '.':
                    maze[i1][i2] = koko_num + 1
                    q.append((i1, i2))
                elif type(maze[i1][i2]) == int:
                    if maze[i1][i2] > koko_num + 1:
                        maze[i1][i2] = koko_num + 1
                        q.append((i1, i2))
    if r == float('inf'):
        print(-1)
    else:
        print(r)

if __name__ == '__main__':
    main()

Measured memory_bytes: 163872
program main
    character(len=3) :: s
    integer :: ans = 0
    read *, s
    
    if(s(1:1) == '1') then
        ans = ans + 1
    end if
    if(s(2:2) == '1') then
        ans = ans + 1
    end if
    if(s(3:3) == '1') then
        ans = ans + 1
    end if
    
    print *, ans
end program main


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const int nmax = 8;
bool graph[nmax][nmax];
const int INF = 1e9;
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

const string YES = "Possible";
const string NO = "Impossible";
char m[8][8];
int main()
{
    int H, W;
    cin >> H >> W;
    int cnt = 0;
    for (int i = 0; i < H; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < W; j++)
        {
            if (str[j] == '#')
            {
                cnt++;
            }
        }
    }
    if (cnt == H + W - 1)
    {
        cout << YES << endl;
    }
    else
    {
        cout << NO << endl;
    }
    return 0;
}


Measured memory_bytes: 256
a,b = map(int, input().split())
res = 1
if b == 1:
    print(0)
    exit(0)
while a *res - (res -1 ) < b  :
 res = res + 1
 #print(a,"個口を",res,"つ使うと未使用は、",a *res - (res -1 ))
print(res)



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

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

using namespace std;

int main(){
	string s; cin>>s;
	if(s=="hi" || s=="hihi" || s=="hihihi" || s=="hihihihi" || s=="hihihihihi") cout<<"Yes\n";
	else cout<<"No\n";

	return 0;
}


Measured memory_bytes: 256
import sys
# N=5
# A=[6, 7, 9, 10, 31]
N=map(int,input())
A=list(map(int, input().split()))

A_even=[]
for i in A:
    if  (i%2)==0:
        A_even.append(i)
for i in A_even:
    if (i%3)!=0 and (i%5)!=0:
        print("DENIED")
        sys.exit()
print("APPROVED")
        


Measured memory_bytes: 38384
N = int(input())
S = input()

ans = 0
for i in range(1000):
    s = str(i).zfill(3)

    index = 0
    for j in range(N):
        if s[index] == S[j]:
            index += 1
        if index == 3:
            ans += 1
            break

print(ans)


Measured memory_bytes: 41052
input = require('fs').readFileSync('/dev/stdin', 'utf8')
lines = input.split('\n')
N = lines.shift() * 1
line = lines.shift().split(' ')
sum = 0
for (i=0; i<N; i++) {
    sum += line[i] * 1
}
ave = Math.round(sum / N)
ans = 0
for (i=0; i<N; i++) {
    ans += Math.pow(line[i] * 1 - ave, 2)
}
console.log(ans)

Measured memory_bytes: 7372
N, K = map(int, input().split())
S = input()


def counthappy(s):
    happy = 0
    for i in range(0, len(s)):
        if i != 0 and s[i] == 'L':
            if s[i - 1] == 'L':
                happy += 1
        elif i != len(s) - 1 and s[i] == 'R':
            if s[i + 1] == 'R':
                happy += 1
    return happy


flag = 0
S = S + 'J'
s_ = []
for i in range(0, N):
    if S[i] != S[i + 1]:
        s_.append(S[flag:i + 1])
        flag = i + 1

count = 0
for i in range(1, len(s_), 2):
    count += 1
    if s_[i][0] == 'L':
        s_[i] = s_[i].replace('L', 'R')
    elif s_[i][0] == 'R':
        s_[i] = s_[i].replace('R', 'L')

    if count == K:
        break

s_join = ''.join(s_)

happy = counthappy(s_join)
print(happy)

Measured memory_bytes: 6524
def modc(a,b,m):
    c = 1
    for i in range(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

x, y = map(int, input().split())

if (x+y) % 3 != 0:
    print(0)
    exit()

if x/2 > y or y/2 > x:
    print(0)
    exit()

maxi = max(x, y)
mini = min(x, y)

tate = 0
yoko = 0
while mini/2 != maxi:
    tate += 1
    maxi -= 2
    mini -= 1
yoko = maxi

print(modc(yoko+tate, yoko, 10**9+7))

Measured memory_bytes: 3188
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
int main()
{
    string str;
    int i=0;
    cin>>str;
    while(i<str.size()){
    	if(str[i]=='A') {str[i]='X';}
    	else if(str[i]=='B') {str[i]='Y';}
    	else if(str[i]=='C') {str[i]='Z';}
    	else str[i]=str[i]-3;
    	i++;
    }
    cout<<str<<endl;
	return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
     
    #define rep(i,n) for(int i=0;i<n;i++)
    #define ll long long
    #define MX 3005
     
    using namespace std;
     
    int main(){
        int N;
        long double p[MX];
        long double d[2][MX],ans;
        cin>>N;
        rep(i,N)cin>>p[i];
        d[0][0]=1;
        rep(i,N)d[0][i+1]=0;
        for(int i=1;i<N+1;i++){
            d[i%2][0]=(1-p[N-i])*d[(i-1)%2][0];
            for(int j=1;j<N+1;j++){
                d[i%2][j]=p[N-i]*d[(i-1)%2][j-1]+(1-p[N-i])*d[(i-1)%2][j];
            }
        }
        ans=0;
        for(int i=(N+1)/2;i<=N;i++){
            ans+=d[N%2][i];
            //cout<<d[N%2][i]<<endl;
        }
        cout<<setprecision(10)<<ans<<endl;
        return 0;
    }

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

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ll long long
#define vi vector <int>
#define pb push_back
using namespace std;

#define bs 1000000007

int tests;
map<int,int> mapp;
int n;
vector<int> order;
map<int,int> ::iterator it;

int main(){
    //ios_base::sync_with_stdio(0);

    int n1; 
    cin>>n1;
    int a[n1+1];
    for(int i=0;i<n1+1; i++){a[i]=0;}
    for(int i=1; i<n1; i++){
        int k;
        cin>>k;
        a[k]++;
    }
    for(int i=1; i<=n1; i++){
        cout<<a[i]<<"\n";
    }

}



Measured memory_bytes: 4364
h,w=list(map(int,input().split()))

def area(h,w,p):
    if p==1:
        return h*w,h*w
    cmin=10**10+1
    hh=h//p
    if hh>0:
        sh=hh*w
        smax,smin=area(h-hh,w,p-1)

        tmax=max(sh,smax)
        tmin=min(sh,smin)

        if tmax-tmin<cmin:
            retmax=tmax
            retmin=tmin
            cmin=retmax-retmin

    hh+=1
    if hh<h:
        sh=hh*w
        smax,smin=area(h-hh,w,p-1)

        tmax=max(sh,smax)
        tmin=min(sh,smin)

        if tmax-tmin<cmin:
            retmax=tmax
            retmin=tmin
            cmin=retmax-retmin

    ww=w//p
    if ww>0:
        sw=ww*h
        smax,smin=area(h,w-ww,p-1)

        tmax=max(sw,smax)
        tmin=min(sw,smin)

        if tmax-tmin<cmin:
            retmax=tmax
            retmin=tmin
            cmin=retmax-retmin

    ww+=1
    if ww<w:
        sw=ww*h
        smax,smin=area(h,w-ww,p-1)

        tmax=max(sw,smax)
        tmin=min(sw,smin)

        if tmax-tmin<cmin:
            retmax=tmax
            retmin=tmin
            cmin=retmax-retmin
    
    return retmax,retmin

smax,smin=area(h,w,3)
print(smax-smin)

Measured memory_bytes: 3064
import math
N,a,b = (int(x) for x in input().split())
z = 0
for I in range (N):
    o = 0
    i = I+1
    while True:
        o += i%10
        i = math.floor(i/10) 
        if i == 0:
            if a <= o <= b:
                z += I+1
            break
print (z)

Measured memory_bytes: 9096
# coding: utf-8

N, M = map(int, input().split())
A = list(map(int, input().split()))
# print(A)
A.sort(reverse=True)
# print(A)

for i in range(M):
    if A[i] < sum(A) / (4 * M):
        print('No')
        exit()
else:
    print('Yes')

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <map>

#ifdef _XCODE_DEBUG
    #include <fstream>
#endif

class UnionFind {
private:
    std::vector<int> par; // 各元の親を表す配列
    std::vector<int> siz;
public:
    // メンバイニシャライザ
    UnionFind(int sz_): par(sz_), siz(sz_) {
        for (int i=0; i<sz_; ++i) {par[i]=i; siz[i]=1;} // 初期では親は自分自身
    }
//    void init(int sz_) {
//        par.resize(sz_);
//        siz.resize(sz_);
//        for (int i=0; i<sz_; ++i) {par[i]=i; siz[i]=0;}
//    }

    // Find
    int root(int x) {
        if (x==par[x]) return x;
        else return par[x] = root(par[x]); // 経路圧縮
    }

    // Union
    bool union_by_size(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique
        if (siz[x] < siz[y]) std::swap(x, y);
          siz[x] += siz[y];
          par[y] = x;
          return true;
    }
    // 連結判定
    bool is_same(int x, int y) {
        return root(x) == root(y);
    }
    // sizeを表示する
    int get_size(int x) {
        return siz[root(x)];
    }
};

int main() {
    #ifdef _XCODE_DEBUG
        std::ifstream in("input.txt");
        std::cin.rdbuf(in.rdbuf());
    #endif
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // input data
    int N, K, L, p, q, r, s;
    std::cin >> N >> K >> L;
    UnionFind uf_road(N+1);
    UnionFind uf_rail(N+1);
    
    // union find
    for (int i=0; i<K; ++i) {
        std::cin >> p >> q;
        uf_road.union_by_size(p, q);
    }
    for (int i=0; i<L; ++i) {
        std::cin >> r >> s;
        uf_rail.union_by_size(r, s);
    }
    
    // show ans
    std::map<std::pair<int, int>, int> mp;
    for (int i=1; i<=N; ++i) {
        auto key = std::make_pair(uf_road.root(i), uf_rail.root(i));
        if (mp.count(key)) ++mp[key];
        else mp[key]=1;
    }
    for (int i=1; i<=N; ++i) {
        auto key = std::make_pair(uf_road.root(i), uf_rail.root(i));
        std::cout << mp[key] << " ";
    }
    return 0;
}

Measured memory_bytes: 12288
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int main() {
  // Put your favorite codes here
  int a, b;
  cin >> a >> b;
  if(b % a == 0) {
    cout << a + b << endl;
  } else {
    cout << b - a << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s1,s2,s3;
    int l1,l2,l3,i=0,j=0,k=0;
    char c,ans;
    s1.clear(),s2.clear(),s3.clear();
    cin>>s1>>s2>>s3;
    l1=s1.size();l2=s2.size();l3=s3.size();
    i=1;l1--;c=s1[0];
    while(1)
    {
        if(c=='a')
        {
            l1--;
            ans='A';
            if(l1==-1)
                break;
            c=s1[i];
            i++;


        }
       else if(c=='b')
        {
            l2--;
            ans='B';
            if(l2==-1)
                break;
            c=s2[j];
            j++;


        }
        else
        {
            l3--;
            ans='C';
            if(l3==-1)
                break;
            c=s3[k];
            k++;


        }

    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	//nを入力
	int n;
	scanf("%d", &n);
	long long h[n + 1];
	h[0] = 0;
	for(int i= 1; i <= n; i++){
		scanf("%lld", &h[i]);
	}
	//計算
	int flg = 0;
	for(int i = 1; i < n; i++){
		if(h[i - 1] <= h[i] && h[i] <= h[i + 1]){
			if(h[i - 1] < h[i] && h[i] == h[i + 1]){
				h[i]--;
			}
		}else{
			if(h[i - 1] < h[i] && (h[i] - h[i + 1]) == 1){
				h[i]--;
			}else{
				flg = 1;
				i = n;
			}
		}
	}
	//表示
	if(flg == 0){
		printf("Yes\n");
	}else{
		printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 896
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
	int *array, n, i, j, tmp, c;
	
	while(1){
		scanf("%d", &n);
		if(n == 0){
			break;
		}
		
		array = (int *)calloc(n, sizeof(int));
		for(i = 0; i < n; i++){
			scanf("%d", &array[i]);
		}
		
		for(i = n-1, c = 0; i > 0; i--){
			for(j = 1; j <= i; j++){
				if(array[j-1] > array[j]){
					tmp = array[j-1];
					array[j-1] = array[j];
					array[j] = tmp;
					c++;
				}
			}
		}
		free(array);
		printf("%d\n", c);
	}
	
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <queue>
#include <numeric>
#include <ctype.h>
#include <limits>
#include <iomanip>

#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

typedef long long ll;

int main()
{
	/*int r;
	cin >> r;
	cout << 2 * r * acos(-1);*/


	/*int n, m;
	cin >> n >> m;
	int sum = 0;
	int a;
	rep(i, m) {
		cin >> a;
		sum += a;
	}
	if (sum > n)cout << -1;
	else cout << n - sum;*/


	/*int n;
	cin >> n;
	vector<int>ans(n);
	int a;
	rep(i, n-1) {
		cin >> a;
		a--;
		ans[a]++;
	}
	rep(i, n)cout << ans[i] << "\n";*/


	ll n, k;
	cin >> n >> k;
	ll mod = 1e9 + 7;
	ll mini;
	ll maxi;
	ll ans = 0;
	for (ll i = k; i <= n; i++) {
		mini = i * (i - 1) / 2;
		maxi = i * (2 * n - i + 1) / 2;
		ans += maxi - mini + 1;
		ans %= mod;
	}
	ans++;
	ans %= mod;
	cout << ans;
	return 0;
}

Measured memory_bytes: 3192
# -*- coding: utf-8 -*-
h,w = map(int, input().split())

c = []
for _ in range(10):
    line = list(map(int, input().split()))
    c.append(line)

for k in range(10):
    for i in range(10):
        for j in range(10):
            c[i][j] = min(c[i][j], c[i][k]+c[k][j])

ret = 0
for _ in range(h):
    for a in map(int, input().split()):
        if a>=0:
            ret += c[a][1]

print(ret)


Measured memory_bytes: 3064
#pragma GCC optimize "-O3"
#pragma GCC target ("avx")
#define _USE_MATH_DEFINES
#include<numeric>
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())
#define SPEED ios::sync_with_stdio(false);cin.tie(0);cout<<fixed<<setprecision(12)
signed gcd(int a, int b){return b?gcd(b,a%b):a;}
signed lcm(int a, int b){return a*b/gcd(a,b);}
//priority_queue<int, vi, greater<int> > que;//æ˜‡é †

using namespace std;

const int mod=1e9+7;

signed dis(int x1,int y1, int x2, int y2){
    return abs(x1 - x2) + abs(y1 - y2);
}

signed main(){
    SPEED;
    int n,m;
    cin >> n >> m;
    vector<pair<int,int>> student(n*2);
    int a, b;
    rep(i,n)
    {
        cin >> a >> b;
        student[i].fi = a;
        student[i].se = b;
    }
    vector<pair<int,int>> checkPoint(m*2);
    int c,d;
    rep(i,m)
    {
        cin >> c >> d;
        checkPoint[i].fi = c;
        checkPoint[i].se = d;
    }

    rep(i,n)
    {
        int ans = inf;
        int old = ans;
        int out = 0;
        rep(j,m)
        {
            ans = min(ans,(int)dis(student[i].fi,student[i].se,checkPoint[j].fi,checkPoint[j].se));
            if(old != ans)
            {
                old = ans;
                out = j+1;
            }
        }
        cout << out << endl;
    }
}


Measured memory_bytes: 256
K = int(input())

table = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in table:
	if len(table) > K:
		break
	x = i % 10
	if x != 0 and x != 9:
		for j in range(x - 1, x + 2):
			table.append(i * 10 + j)
	elif x == 0:
		for j in range(x, x + 2):
			table.append(i * 10 + j)
	else:
		for j in range(x - 1, x + 1):
				table.append(i * 10 + j)

print(table[K - 1])

Measured memory_bytes: 7316
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;


int main()
{
	int n;
	cin>>n;
	char ch[100];
	int f[26];
	int g[26];
	memset(f,0,sizeof f);
	scanf("%s",ch+1);
	for(int i=1;i<=strlen(ch+1);i++) f[ch[i]-'a']++;
	n--;
	while(n--)
	{
		memset(g,0,sizeof g);
		scanf("%s",ch+1);
		for(int i=1;i<=strlen(ch+1);i++) g[ch[i]-'a']++;
		for(int i=0;i<26;i++) f[i]=min(f[i],g[i]);
	}
	for(int i=0;i<26;i++)
		for(int j=1;j<=f[i];j++) putchar('a'+i);
}

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

int main()
{
    int n;
    scanf("%d", &n);
    int v[n], c[n];
    int i;
    int ans = 0;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &v[i]);
    }
    for (i = 0; i < n; i++)
    {
        scanf("%d", &c[i]);
        if (v[i] - c[i] > 0)
        {
            ans += v[i] - c[i];
        }
    }
    printf("%d\n", ans);
    return 0;
}	

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef vector<int> vi;
typedef long long lint;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
typedef unsigned long long ulint;
#define endl '\n'
#define fst first
#define sed second
#define pb push_back
#define mp make_pair
#define rint register int
#define SZ(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define reveal(x) cerr << #x << " = " << (x) << endl
#define rep(it, f, e) for (rint it = (f); it <= (e); ++it)
#define per(it, f, e) for (rint it = (f); it >= (e); --it)
#define repe(it, x) for (auto it = (x).begin(); it != (x).end(); ++it)
map<lint, vector<pll> > vec;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	lint n, x, d;
	cin >> n >> x >> d;
	auto calc1 = [&] (const lint & x) {
		return x ? x * (x - 1) / 2 : 0;
	};
	auto calc2 = [&] (const lint & x) {
		return x ? x * (n + n - x - 1) / 2 : 0;
	};
	if (d == 0) {
		if (x == 0) {
			cout << 1 << endl;
		} else {
			cout << n + 1 << endl;
		}
		return 0;
	}
	if (d < 0) {
		x += d * n - d;
		d = -d;
	}
	rep (i, 0, n) {
		lint a = i;
		lint b = n - i;
		lint sl = calc1(a) - calc2(b);
		lint bg = calc2(a) - calc1(b);
		lint t = (a - b) * x + sl * d;
		lint p = (t % (d << 1) + (d << 1)) % (d << 1);
		lint L = (t - p) / (d << 1);
		vec[p].emplace_back(L, L + (bg - sl) / 2);
	}
	lint res = 0;
	for (auto v : vec) {
		sort(all(v.sed));
		lint las = -1e18;
		for (auto p : v.sed) {
			lint l = p.fst;
			lint r = p.sed;
			if (r > las) {
				res += min(r - l + 1, r - las);
				las = r;
			}
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 22144
A = [list(map(int,input().split())) for _ in range(3)]
N = int(input())
B = [int(input()) for _ in range(N)]
C = [[0,0,0],[0,0,0],[0,0,0]]
for i in range(N):
  b = B[i]
  for j in range(3):
    for k in range(3):
      if A[j][k] == b:
        C[j][k] = 1
c = 0
for i in range(3):
  if C[i][0] == 1 and C[i][1] == 1 and C[i][2] == 1:
    c += 1
  if C[0][i] == 1 and C[1][i] == 1 and C[2][i] == 1:
    c += 1
if C[0][0] == 1 and C[1][1] == 1 and C[2][2] == 1:
  c += 1
if C[2][0] == 1 and C[1][1] == 1 and C[0][2] == 1:
  c += 1
if c > 0:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 200010;
const int INF = 2147483600;

int H,W,N;
vector<int> vec[MAXN+1];
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	H=read(),W=read(),N=read();
	for(int i=1;i<=N;i++){
		int x=read(),y=read();
		vec[y].push_back(x);
	}
	for(int i=1;i<=W;i++) sort(vec[i].begin(),vec[i].end());
	int now=0,ans=H;
	for(int i=1;i<=W;i++){
		++now; int sz=vec[i].size(),dv=0; 
		while(dv<sz&&vec[i][dv]<now) ++dv; int pre=now-1;
		while(dv<sz&&vec[i][dv]==pre+1) pre=vec[i][dv],++dv,++now;
		for(;dv<sz;dv++){
			if(dv&&vec[i][dv]==vec[i][dv-1]+1) continue;
			ans=min(ans,vec[i][dv]-1); break;
		}
	}
	cout<<ans<<endl;
	return 0;
}




Measured memory_bytes: 8704
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <tuple>
#include <vector>
#include <map>
#include <iterator>
#include <cmath>

using namespace std;
using lint = long long int;

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

	int start = max(x - k + 1, -1000000);
	int end = min(x + k - 1, 1000000);
	cout << start;
	for (int c = start + 1; c <= end; c++) {
		cout << " " << c;
	}

	return 0;
}


Measured memory_bytes: 256
n = gets.to_i
a = gets.split.map(&:to_i)

c = Array.new(2*10**5+1,0)
a.each{ |k| c[k] += 1 }
s = c.map{ |k| res = k * (k-1)/2 }.inject(:+)

a.each{ |k| puts s - (c[k]-1) }


Measured memory_bytes: 24836
#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
int main() {
    
    //ifstream cin("input.txt");
    //ofstream cout("output.txt");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    /*-----------------Code Begins Here------------------*/
    
    ll x,n;
    cin>>x>>n;
    ll p[n];
    for(ll i=0;i<n;i++) cin>>p[i];
    sort(p,p+n);
    if(!(binary_search(p,p+n,x))) cout<<x;
    else{
        ll c,d;
        for(ll i=x-1;;i--){
            if(!(binary_search(p,p+n,i))){
                c=i;
                break;
            }
        }
        for(ll i=x+1;;i++){
            if(!(binary_search(p,p+n,i))){
                d=i;
                break;
            }
        }
        min(x-c,d-x)==(x-c) ? cout<<c : cout<<d;
    }
    
    /*------------------Code Ends Here-------------------*/
    
    return 0;
}

Measured memory_bytes: 3576
import java.util.Scanner;
import java.util.Stack;

public class Main {

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

        int ans = solve(s);
        System.out.println(ans);
    }

    static int solve(String s) {
        char[] c = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        int remainT = 0;
        for (int i = 0; i < s.length(); i++) {
            if (c[i] == 'S') {
                stack.add(c[i]);
            } else {
                if (!stack.isEmpty() && stack.peek() == 'S') {
                    stack.pop();
                } else {
                    remainT++;
                }
            }
        }
        return stack.size() + remainT;
    }
}


Measured memory_bytes: 26252
import sys

ERROR_INPUT = 'input is invalid'


def main():
    num = int(input())
    if num < 2 or 200000 < num:
        print(ERROR_INPUT)
        sys.exit(1)

    prices = [check_price(price=int(input())) for _ in range(num)]

    print(calc_max_diff(prices=prices))
    return 0


def check_price(price):
    if price < 1 or price > 10 ** 9:
        print(ERROR_INPUT)
        sys.exit(1)
    else:
        return price


def calc_max_diff(prices):
    min_price = prices[0]
    max_diff = prices[1] - prices[0]

    for p in prices[1:]:
        if max_diff < p - min_price:
            max_diff = p - min_price
        if p < min_price:
            min_price = p

    return max_diff


if __name__ == '__main__':
    main()

Measured memory_bytes: 14944
#pragma region RegionDefs
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,l,r) for(int i=(l),i##_len=(r);i<i##_len;++i)
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
const ll INF = 1e9;
template<class T=ll> using V = vector<T>;
template<class T=ll> using PQ = priority_queue<T>;
template<class T=ll> using PQG = priority_queue<T, V<T>, greater<T>>;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
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;}
#define y0 y__0
#define y1 y__1
#define j0 j__0
#define j1 j__1
#define YN(e) cout << ((e) ? "YES" : "NO") << endl
#define yn(e) cout << ((e) ? "Yes" : "No") << endl
#pragma endregion RegionDefs

vector<bool> IsPrime;
void sieve(ll max)
{
    if (max+1 > IsPrime.size())
        IsPrime.resize(max+1,true);
    IsPrime[0] = false;
    IsPrime[1] = false;
    for (ll i=2; i*i<=max; ++i)
        if (IsPrime[i])
            for (ll j=2; i*j<=max; ++j)
                IsPrime[i*j] = false;
}

void solve()
{
    IN(n);
    vector<ll> v;
    for (ll i=2; i*i<=n; ++i)
        if (n % i == 0) {
            ll s = 0;
            while (n % i == 0) {
                n /= i;
                s ++;
            }
            v.push_back(s);
        }
    if (n > 1) {
        v.push_back(1);
    }
    ll res = 0;
    rep(i, v.size()) {
        rep(j, 100) {
            if (j*(j+1)/2 <= v[i] && v[i] < (j+1)*(j+2)/2) {
                res += j;
            }
        }
    }
    cout << res << endl;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

Measured memory_bytes: 3660
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main()
{
	ll N, T; cin >> N >> T;
	vector<ll> t(N);
	for(int i = 0; i < N; i++) cin >> t[i];
	ll time = 0; //何秒までお湯が出るか
	ll cnt = 0; //これまでに何秒お湯が出たか
	for(int i = 0; i < N; i++) {
		if(t[i] <= time) cnt += t[i]+T-time;
		else cnt += T;
		time = t[i] + T;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
ll inf = LLONG_MAX;
long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  ll n, m, p = 1000000007;
  cin >> n >> m;
  if (abs(n - m) > 1) cout << 0 << endl;
  else {
    if (n < m) swap(n, m);
    ll x = 1, y = 1;
    for (ll i = 0; i < n; i++) {
      x *= i + 1;
      x %= p;
    }
    for (ll i = 0; i < m; i++) {
      y *= i + 1;
      y %= p;
    }
    if (n == m) {
      x *= 2;
      x %= p;
    }
    cout << x * y % p << endl;
  }
}

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

typedef unsigned long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define maxn 100001
#define int ll
int N,K,A[maxn];

int dp[maxn][2];
int num[50][2];
bool vis[maxn][2];

int dpf(int idx,bool same){
	if (vis[idx][same]) return dp[idx][same];
	vis[idx][same] = 1;
	if (idx < 0) return 0;
	
	int lim = 1;
	
	bool val = ((ll)K & ((ll)1<<(ll)idx));
	
	if (same){
		if (!val) lim = 0;
	}
	
	dp[idx][same] = 0;
	FOR(i,0,lim){
		if (idx == 0) dp[idx][same] = max(dp[idx][same],(ll)num[idx][(i+1)%2] * (ll)((ll)1<<(ll)idx));
		else dp[idx][same] = max(dp[idx][same],dpf(idx-1,same && (i == val)) + (ll)num[idx][(i+1)%2] * (ll)((ll)1<<(ll)idx));
	}
	return dp[idx][same];
}
		
int32_t main(){
	fast;
	
	cin>>N>>K;
	
	FOR(i,0,N-1){
		cin>>A[i];
		
		FOR(j,0,40){
			if (A[i] & (ll)((ll)1<<(ll)j)) num[j][1]++;
			else num[j][0]++;
		}
	}
	
	int ans = 0;
	FOR(j,0,40) ans += (ll(1)<<(ll)j) * num[j][1];
	//cout<<ans;

	
	cout<<dpf(40,1);
	
	
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> tri;

class UnionFind{
public:
  vi p,r;
  UnionFind(int n):p(n,-1), r(n,0){ }
  int find(int x){ return (p[x]<0)?x:(p[x] = find(p[x])); }
  bool same(int x,int y){ return find(x)==find(y); }
  void unite(int x, int y){
    x = find(x); y = find(y);
    if(x == y) return;

    if(r[x] < r[y]){
      p[x] = y;
    }else{
      p[y] = x;
    }
    if(r[x] == r[y]) r[x]++;
  }
};

int main(){
  int n,m;
  cin >> n >> m;
  vector<tri> e;
  rep(i,m){
    int a,b,c;
    cin >> a >> b >> c;
    a--; b--;
    e.push_back( tri(c, pii(a,b)) );
  }

  sort(e.begin(), e.end());

  int ans = -1;
  UnionFind uf(n);
  rep(x,m){
    int c = e[x].first;
    map<int, vector<int> > g;
    queue<int> q;
    
    g[e[x].second.first].push_back(e[x].second.second);
    if(uf.same(0, e[x].second.first)) q.push(e[x].second.second);
    while(x+1 < m && c == e[x+1].first){
      x++;
      g[e[x].second.first].push_back(e[x].second.second);
      if(uf.same(0, e[x].second.first)) q.push(e[x].second.second);
    }

    while(q.size()){
      int v = q.front(); q.pop();
      if(v == n-1) ans = c;

      if(!uf.same(0,v)){
	uf.unite(0,v);
	for(int u : g[v]){
	  q.push(u);
	}
      }
    }    
  }

  cout << ans << endl;
}

Measured memory_bytes: 11724
#include <stdio.h>

int main(void){
 int n,i,buf=0,m=-1;
 int num[200];
 
 scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&num[i]);
  }
  
while(buf<1){
  for(i=0;i<n;i++){
   if(num[i]%2 == 1){
     buf = 10;
     break;
   }
    num[i] = num[i]/2;
  }
  m++;
}
  printf("%d",m);
 return 0;
}

Measured memory_bytes: 128
(defun solve (n m)
  (let ((a (make-array (1+ n))))
    (dotimes (i m)
      (let ((l (1- (read)))
            (r (read)))
        (incf (aref a l))
        (decf (aref a r))))
    (let ((x 0))
      (loop for i below n
          do (incf x (aref a i))
          count (= x m)))))
(princ (solve (read) (read)))

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

typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int k, n;
    cin >> k >> n;
    int seg[n];
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        if (i == n-1) {
            seg[i] = k + a[0] - a[i];
        }
        else {
            seg[i] = a[i+1] - a[i];
        }
    }
    sort(seg, seg+n);
    int dist = 0;
    for (int i = 0; i < n-1; i++) {
        dist += seg[i];
    }
    cout << dist;
}


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

int main() {
	int n, x;
	cin >> n >> x;
	int l[n];
	int h = 0;
	int cnt = 1;
	for (int i = 0; i < n; i++) {
		cin >> l[i];
		h += l[i];
		if (h <= x) {
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a,b,c,k;
  cin>>a>>b>>c;
  cin>>k;
  for(int i=0;i<k;i++){
    if(a>=b)
      b=b*2;
    else if(b>=c)
      c=c*2;
  }
  if(a<b && b<c)cout<<"Yes";
  else cout<<"No";
}

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<long long> a(n);
	int ans = 0;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) {
	    for(int j = i + 1; j < n; j++) {
	        for(int k = j + 1; k < n; k++) {
	            if((a[i] + a[j] > a[k]) && (a[j] + a[k] > a[i]) && (a[k] + a[i] > a[j]) &&
	            a[i] != a[j] && a[j] != a[k] && a[k] != a[i]) ans++;
	        }
	    }
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 3660
n, m = map(int, input().split())
lr = [list(map(int,input().split())) for _ in range(m)]
min2 = 1
max2= n

for llrr in lr:
  min2 = max(min2, llrr[0])
  max2 = min(max2, llrr[1])

if max2-min2 >= 0:
  print(max2-min2+1)
else:
  print(0)


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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;

const int MAX_N = 1e5+5;
const int M = 1e6;
const ll INF = (ll)(1e18);
const int inf = 1e9;
const ll MOD = 1000000007LL;

void solve() {

}



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

    int n;
    string s;

    cin >> n >> s;

    int ans = 0;
    for (int i = 0; i < n-2; i++) {
        string tmp = s.substr(i, 3);
        if (tmp == "ABC") ans++;
    }

    cout << ans;


    return 0;
}


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

void trace(int A[],int N){
  int i;
  for(i=0;i<N;i++){
    if(i>0) printf(" ");
    printf("%d",A[i]);
  }
  printf("\n");
}

void insertionSort(int A[],int N){
  int j,i,v;
  for(i=1;i<N;i++){
    v=A[i];
    j=i-1;
    while(j>=0&&A[j]>v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1] = v;
    trace(A,N);
  }
}

int main(){
  int N,i,j;
  int A[100];
  cin >> N;
  for(i=0;i<N;i++) cin >> A[i];
  trace(A,N);
  insertionSort(A,N);
  return 0;
}


Measured memory_bytes: 3220
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define INF 1000000007
#define mod 1005
#define ll long long int
const double mx = 2e6 + 5 ;

void solve()
{
	string s;
	cin>>s;
	bool isPos = 1;
	REP(i, s.length())
	{
		int pos = i+1;
//		cout<<pos<<" char: "<<s[i]<<"\n";
		if(pos%2==0)
		{
//			cout<<i+1<<" is LUD -> "<<s[i]<<"\n";
			if(s[i]!='L' && s[i]!='U' && s[i]!='D')
			{
				isPos = 0;
				break;
			}
		}
		else
		{
//			cout<<i+1<<" is RUD -> "<<s[i]<<"\n";
			if(s[i]!='R' && s[i]!='U' && s[i]!='D')
			{
				isPos = 0;
				break;
			}
		}
	}
	if(isPos)
		cout<<"Yes\n";
	else
		cout<<"No\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t = 1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3628
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int X = sc.nextInt();
        int answer =1;
        
        for(int i=2; i*i<=X; i++){
            int max =i*i;
            while(max<=X){
            if(max >= answer){
                answer = max;
            }
                max *= i;
            }
        }
        
        System.out.println(answer);
        
    }
}


Measured memory_bytes: 21844
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

int main()
{
	int32_t N;
	cin >> N;

	int32_t _min = numeric_limits<int32_t>::max(), _max = numeric_limits<int32_t>::min();
	map<int32_t, int32_t> _map;
	for (int32_t i = 0; i < N; i++) {
		int32_t a;
		cin >> a;
		if (_map.find(a) == _map.end()) {
			_map[a] = 1;
		} else {
			_map[a]++;
		}
		_min = min(_min, a);
		_max = max(_max, a);
	}

	int32_t res = 0;
	for (int32_t i = _min; i <= _max; i++) {
		res = max(res, _map[i - 1] + _map[i] + _map[i + 1]);
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 4992
#include<stdio.h>
#include<stdlib.h>

#define NIL NULL
 
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node * Node;
 
Node root;

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
 
  z = malloc(sizeof(struct node));

  z->key = k;
  z->left = NIL;
  z->right = NIL;
 
  while(x != NIL){
    y = x;

    if(z->key < x->key){
      x = x->left;
    }

    else{
      x = x->right;
    }
  }

  z->parent = y;
 
  if(y == NIL){
    root = z;
  }

  else if(z->key < y->key){
    y->left = z;
  }

  else{
    y->right = z;
  }
}
 
void inorder(Node u){
  if(u == NIL) return;
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}
 
void preorder(Node u){
  if (u == NIL) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}
 
 
int main(void){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
 
  for(i = 0; i < n; i++){
    scanf("%s", com);

    if(com[0] == 'i'){
      scanf("%d", &x);
      insert(x);
    }

    else if(com[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }

    else if(com[0] == 'd'){
    }
  }
 
  return 0;
}

Measured memory_bytes: 24040