akhauriyash/Code-Regression huggingface dataset:
#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;
typedef long long ll;
typedef double db;
typedef vector <ll> vll;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define MAX 1000000
#define mod 1000000007
#define all(_) _.begin(), _.end()
#define F first
#define S second
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    ll l, r;
    vll a;
    cin >> l >> r;
    for(ll i = l; i <= r && i - l <= 2019; i++)
    {
        a.pb(i % 2019);
    }
    sort(all(a));
    ll ans = LLONG_MAX;
    for(ll i = 0; i < a.size(); i++)
    {
        for(ll j = i + 1; j < a.size(); j++)
            ans = min(ans, (a[i] * a[j]) % 2019);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }

int main(){
    ll A,B,C,D;
    string S;
    cin >> A >> B >> C >> D;
    bool flag = true;
    while(true){
        if(C <= 0){
            break;
        }else if(A <= 0){
            flag = false;
            break;
        }
        C -= B;
        A -= D;
    }
    if(flag){
        cout << "Yes" <<endl;
    }else{
        cout << "No" <<endl;
    }
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N, fault = 0;
    cin >> N;
    vector<int> order(N);
    for(int i = 0; i < N; i++){
        cin >> order.at(i);
    }
    for(int j = 0; j < N ; j++){
        if(order.at(j) != j + 1)
    fault++;
    }
  if(fault <= 2)
  cout << "YES" << endl;
  else
  {
      cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
N,H=map(int,input().split())
L=[list(map(int,input().split())) for _ in range(N)]
A=max(a for a,_ in L)
B=sorted(b for _,b in L if b>A)
c=0
while B and H>0:
    H-=B.pop()
    c+=1
print(c-(-max(0,H)//A))

Measured memory_bytes: 28584
class BinarySearchTree:
    def __init__(self):
        self.root = None
    def insert(self, z):
        p = None
        x = self.root
        while x != None:
            p = x
            if z.key < x.key : x = x.left
            else             : x = x.right
        z.p = p
        if p == None      : self.root = z
        elif z.key < p.key: p.left  = z
        else              : p.right = z
    def get_inorder_list(self):
        def _get_inorder_list(root):
            l = root.left
            r = root.right
            if l: yield from _get_inorder_list(l)
            yield root.key
            if r: yield from _get_inorder_list(r)
        yield from _get_inorder_list(self.root)
    def get_preorder_list(self):
        def _get_preorder_list(root):
            l = root.left
            r = root.right
            yield root.key
            if l: yield from _get_preorder_list(l)
            if r: yield from _get_preorder_list(r)
        yield from _get_preorder_list(self.root)
    def find(self, k):
        def _find(k, x):
            if x == None : return False
            if k == x.key: return True
            if k <  x.key: return _find(k, x.left)
            return _find(k, x.right)
        return _find(k, self.root)

class Node:
    def __init__(self, k):
        self.key = k
        self.p = None
        self.left = None
        self.right = None

if __name__=='__main__':
    m = int(input())

    T = BinarySearchTree()
    for _ in range(m):        
        op = input().split()
        if   op[0] == 'insert': T.insert( Node(int(op[1])) )
        elif op[0] == 'find':
            print("yes" if T.find(int(op[1])) else "no")
        else:
            print("",*T.get_inorder_list())
            print("",*T.get_preorder_list())

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

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for(int i=0; i<N; ++i) cin >> A[i];

    vector<long long> sum(N + 1, 0), sumeven(N + 1, 0);
    for(int i=0; i<N; ++i) {
        sum[i + 1] = sum[i] + A[i];
        sumeven[i + 1] = sumeven[i];
        if(i % 2 == 0) sumeven[i + 1] += A[i];
    }

    for(int q=0; q<Q; ++q) {
        int x;
        cin >> x;

        auto itx = upper_bound(begin(A), end(A), x);
        if(itx == end(A)) {
            if(N % 2) cout << sumeven[N] << endl;
            else cout << sum[N] - sumeven[N] << endl;
            continue;
        }

        --itx;
        int left = itx - begin(A);
        int right = N;
        while(right - left > 1) {
            int mid = (left + right) / 2;
            auto itr = lower_bound(begin(A), end(A), 2 * x - A[mid]);
            int cnt = mid + 1 - (itr - begin(A));
            if(N - cnt > mid) left = mid;
            else right = mid;
        }

        long long res = sum[N] - sum[left + 1];
        if(N % 2 == 0) res += sum[max(0, 2 * left - N + 2)] - sumeven[max(0, 2 * left - N + 2)];
        else res += sumeven[max(0, 2 * left - N + 2)];
        cout << res << endl;
    }
}

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

int main(){
    string s;
    cin>>s;
    int a=(s[0]-'0')*10+(s[1]-'0');
    int b=(s[2]-'0')*10+(s[3]-'0');
    bool YYMM;
    bool MMYY;
    YYMM=(1<=b&&b<=12);
    MMYY=(1<=a&&a<=12);

    if(YYMM && MMYY) cout<<"AMBIGUOUS"<<endl;
    else if(YYMM && not MMYY)cout<<"YYMM"<<endl;
    else if(MMYY && not YYMM)cout<<"MMYY"<<endl;
    else cout<<"NA"<<endl;
}

Measured memory_bytes: 256
n=int(input())
a,b=map(int,input().split())
l=list(map(int,input().split()))

ans=[0]*3

for i in range(n):
    if l[i]<=a:
        ans[0]+=1
    elif l[i]>b:
        ans[2]+=1
    else:
        ans[1]+=1
print(min(ans))

Measured memory_bytes: 3064
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int limitC = sc.nextInt();
		int limitT = sc.nextInt();
		int[][] routeOption = new int[2][1000];
		int ans = 1010;
		while(sc.hasNext() == true){
			int optionC = sc.nextInt();
			int optionT = sc.nextInt();
			if(optionT <= limitT){
				ans = Math.min(ans, optionC);
			}
		}
		if(ans == 1010){
			System.out.println("TLE");
		}else{
			System.out.println(ans);
		}
	}

}


Measured memory_bytes: 21588
#include <bits/stdc++.h>
using namespace std;
#define e1 first
#define e2 second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PLL, PLL> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int mod = 1e9+7;
const int inf = 1e9+9;
const ll MOD = 1e9+696969;
const long long INF = 1e18+3;
const ll most = 1e9;

bool query(ll val){
	std::cout << "? " << val << std::endl;
	
	char c;
	std::cin >> c;
	
	return (c == 'Y');
}
 
int main(){
	ll length = 1;
	
	if(!query(9)){
		for(ll i = 10; i <= most; i *= 10){
			if(query(i * 10 - 1)){
				length = i;
				break;
			}
		}
	}
	
	if(!query(most)){
		for(ll i = most; i >= 1; i /= 10){
			if(query(i)){
				length = i;
				break;
			}
		}
	}
	
	ll l = length;
	ll r = length * 10 - 1;
	
	ll best = r;
	
	while(l <= r){
		ll mid = (l + r) / 2;
		
		if(query(mid * 10)){
			r = mid - 1;
			best = mid;
		} else {
			l = mid + 1;
		}
	}
	
	std::cout << "! " << best << std::endl;
}


Measured memory_bytes: 684
#include<bits/stdc++.h>
using namespace std;
int n,arr[1000005],p[1000005],d;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>arr[i];
	d=arr[1];
	for(int i=2;i<=n;i++) d=__gcd(d,arr[i]);
	if(d!=1) 
	{
		cout<<"not coprime"<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		int k=arr[i];
		for(int j=1;j<=sqrt(k);j++)
		{
			if(k%j==0) 
			{
				if(j!=1&&p[j]==1||p[k/j]==1) 
				{
					cout<<"setwise coprime"<<endl;
					return 0;
				}
				p[j]++,p[k/j]++;
			}
		}
	}
	cout<<"pairwise coprime"<<endl;
}

Measured memory_bytes: 7800
N = int(input())
S = list(input())
 
we = []
west = 0
east = 0
for i in range(N):
    if S[i] == "W":
        west += 1
    elif S[i] == "E":
        east += 1
    we.append([west,east])
 
ans = 1e9
for i in range(N):
    if i == 0:
        left = 0
    else:
        left = we[i][0]
    right = we[N-1][1] - we[i][1]
    ans = min(ans,left+right)
 
print(ans)

Measured memory_bytes: 45816
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInteger = readLn :: IO Integer
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

modifyArray a i f = writeArray a i =<< f <$> readArray a i

main = do
	s <- getLine
	putStrLn $ which "Yes" "No" $ ( s !! 2 ) == ( s !! 3 ) && ( s !! 4 ) == ( s !! 5 )

Measured memory_bytes: 380
using System;
using System.Linq;
class c
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var count = new int[101];
        addPrime(n, ref count);
        int a, b, c, d, e, g, h;
        a = count.Where(f => f >= 4).Count();
        b = count.Where(f => f < 4 && f >= 2).Count();
        c = count.Where(f => f >= 14).Count();
        d = count.Where(f => f < 14 && f >= 4).Count();
        e = count.Where(f => f >= 24).Count();
        g = count.Where(f => f < 24 && f >= 2).Count();
        h = count.Where(f => f >= 74).Count();
        long ans = 0;
        ans += a * (a - 1) * (a - 2) / 2 + a * (a - 1) * b / 2;
        ans += c * (c - 1) + c * d;
        ans += e * (e - 1) + e * g;
        ans += h;
        Console.WriteLine(ans);
    }
    static void addPrime(int n, ref int[] count)
    {
        for (int i = 2; i <= n; i++)
        {
            int x = i;
            for (int j = 2; j <= n; j++)
            {
                while (x % j == 0)
                {
                    x /= j;
                    count[j]++;
                }
            }
        }
    }
}

Measured memory_bytes: 13268
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   main.cpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: monoue <marvin@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/22 12:30:15 by monoue            #+#    #+#             */
/*   Updated: 2020/04/25 15:37:28 by monoue           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <bits/stdc++.h>

/* #include <boost/multi_array.hpp> */
/* #include <boost/optional.hpp> */
/* #include <boost/range/irange.hpp> */
/* #include <boost/range/algorithm.hpp> */
/* #include <boost/range/adaptors.hpp> */
/* #include <boost/multiprecision/cpp_int.hpp> */
/* #include <boost/algorithm/string/classification.hpp> // is_any_of */
/* #include <boost/algorithm/string/split.hpp> */
/* #include <boost/algorithm/string/join.hpp> */
/* #include <boost/algorithm/string/replace.hpp> */
/* #include <boost/math/tools/minima.hpp> */
/* namespace adaptor = boost::adaptors; */
/* using boost::math::tools::brent_find_minima; */
/* using boost::irange; */
/* using boost::algorithm::join; */
/* using boost::algorithm::split; */
/* using boost::algorithm::replace_all; */
/* using boost::multiprecision::cpp_int; */

#define MOD 1e9+7;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

// TOP
void	Main()
{
	ll	n;
	cin >> n;
	vector<ll>	V(n);
	rep(i, n)
		cin >> V.at(i);
	auto	itr = unique(V.begin(), V.end());
	V.erase(itr, V.end());
	ll	lcmv;
	lcmv = V.at(0);
	for (ll i = 1; i < V.size(); i++)
		lcmv = lcmv / __gcd(lcmv, V.at(i)) * V.at(i);
	cout << lcmv << endl;
}
// END

int		main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<long long, int> ii;
int main() {
	int X, Y, A, B, C, off = 0;
	priority_queue<ii> pq;
	scanf("%d %d %d %d %d", &X, &Y, &A, &B, &C);
	long long v, ans = 0;
	for (int i = 0; i < A; ++i) scanf("%lld", &v), pq.push(ii(v, 0));
	for (int i = 0; i < B; ++i) scanf("%lld", &v), pq.push(ii(v, 1));
	for (int i = 0; i < C; ++i) scanf("%lld", &v), pq.push(ii(v, 2));
	while (off < X + Y) {
		ii i = pq.top();
		pq.pop();
		if (i.second == 0 && X != 0) ans += i.first, --X;
		if (i.second == 1 && Y != 0) ans += i.first, --Y;
		if (i.second == 2) ans += i.first, ++off;
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 10348
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  string S;
  cin >> S;
  unordered_map<char,int> ma;
  ma['0'] = 0;
  ma['1'] = 0;
  F0R(i, S.size()) {
    ma[S[i]]++;
  }
  int r = 1e9;
  for (auto& p : ma) {
    chmin(r, p.second);
  }
  cout << (r*2);
}
#endif


Measured memory_bytes: 3784
use std::io;

fn read_line()-> String {
    let mut s = String::new();
    let _ = io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn sortString(mut vec: Vec<&str>) -> Vec<&str> {

	for i in 0..vec.len() {
		for j in 0..vec.len()-1 {
			if vec[j].to_string() > vec[j+1].to_string() {
				vec.swap(j+1,j);
			}
		}
	}
	vec
}

fn main() {
	let mut nl = read_line().split_whitespace().map(|e|e.parse().unwrap()).collect::<Vec<i32>>();
	let mut vec = vec!();
	for _ in 0..nl[0] {
		let s = read_line();
		vec.push(s);
	}
	let vec = vec.iter().map(|e|e.as_str()).collect();
	println!("{}",sortString(vec).join(""));
}


Measured memory_bytes: 4352
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		final int N = sc.nextInt();
		boolean s[] = {false, false, false, false}; //P, W, G, Y
		String c;
		
		for(int i=0; i<N; i++) {
			c = sc.next();
			if("P".equals(c)) s[0] = true;
			else if("W".equals(c)) s[1] = true;
			else if("G".equals(c)) s[2] = true;
			else if("Y".equals(c)) s[3] = true;
			
			if(s[0] && s[1] && s[2] && s[3]) {
				sc.close();
				System.out.println("Four");
				return;
			}
		}
		sc.close();
		System.out.println("Three");
	}

}

Measured memory_bytes: 22868
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <bits/stdc++.h>
using namespace std;

int main(){
  ll m;
  cin>>m;
  
  vector<ll> D(m),C(m);
  rep(i,m) cin>>D[i]>>C[i];
  
  ll sum1=0,sum2=0;
  rep(i,m) sum1+=C[i];
  rep(i,m) sum2+=C[i]*D[i];
  
  cout<<sum1-1+(sum2-1)/9<<endl;

  return 0;
}

Measured memory_bytes: 6432
s = input()
t = input()
ls, lt = len(s), len(t)

# DP
dp = [[0 for _ in range(lt + 1)] for j in range(ls + 1)]
for i in range(ls + 1):
    dp[i][0] = i
for j in range(lt + 1):
    dp[0][j] = j

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            cost = 0
        else:
            cost = 1
        dp[i + 1][j + 1] = min(dp[i][j+1] + 1, dp[i+1][j] + 1, dp[i][j] + cost)
print(dp[ls][lt])


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

int main() {
  int H, W;
  cin >> H >> W;
  cout << '#';
  for (int i = 0; i < W; i++) {
    cout << '#';
  }
  cout << '#' << endl;
  for (int i = 0; i < H; i++) {
    string A;
    cin >> A;
    cout << '#' << A << '#' << endl;
  }
  cout << '#';
  for (int i = 0; i < W; i++) {
    cout << '#';
  }
  cout << '#' << endl;
}

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

using namespace std;

int g[105][105];

int main(){
    int h,w;
    cin >> h >> w;
    int n;
    cin >> n;
    vector <int> a(n);
    int x=0,y=0,dir=1;
    for(int i=0;i<n;i++){
        cin >> a[i];
        for(int j=0;j<a[i];j++){
            g[y][x]=i+1;
            if(((x==w-1) && !(y&1)) || ((x==0) && (y&1))){
                y++;
                dir*=-1;
            }
            else{
                x+=dir;
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

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

const int _ = 1e5 + 7;
struct seg{int L , R;}L[_] , R[_]; int N; long long ans;
bool cmp1(seg p , seg q){return p.L > q.L;}
bool cmp2(seg p , seg q){return p.R < q.R;}

int main(){
	ios::sync_with_stdio(0); cin >> N;
	for(int i = 1 , l , r ; i <= N ; ++i){cin >> l >> r; L[i] = R[i] = (seg){l , r};}
	sort(L + 1 , L + N + 1 , cmp1); sort(R + 1 , R + N + 1 , cmp2);
	long long sum = 0; 
	for(int i = 1 ; i <= N ; ++i){ans = max(ans , sum += 2 * L[i].L); ans = max(ans , sum -= 2 * R[i].R);}
	sum = 0; for(int i = 1 ; i <= N ; ++i){ans = max(ans , sum -= 2 * R[i].R); ans = max(ans , sum += 2 * L[i].L);}
	cout << ans; return 0;
}

Measured memory_bytes: 1792
#!/usr/bin/env python3
import sys


def solve(N: int):
    print(N ** 3)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include<math.h>
#include<numeric>
#include<iomanip>
#define rep(i, n) rep2(i,0,n)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define PI acos(-1);
typedef long long ll;
using namespace std;
const int MOD=1000000007;
//scanf("%d", &a); '\n';


int main() {
	int n, y;
	cin >> n >> y;
	for (int i = int(y/10000); i >=0; i--) {
		for (int j = min(n-i,int((y-10000*i)/5000)); j >=0; j--) {
			if (9000 * i + 4000 * j == y - 1000 * n) {
				cout << i << " " << j << " " << n - i - j;
				return 0;
			}
		}
	}
	cout << -1 << " " << -1 << " " << -1;
	}

	

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9 + 7);
constexpr ll INF = 1LL << 60;

int main(void) {
	int n;
	cin >> n;
	
	vector< vector<ll> > x(n, vector<ll>(3));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < 3; ++j) {
			cin >> x[i][j];
		}
	}
	
	vector< vector<ll> > dp(n + 10, vector<ll>(3, 0));

	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < 3; ++j) {
			for(int k = 0; k < 3; ++k) {
				if( j != k ) dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + x[i][k]);
			}
		}
	}
	
	cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
	
	return 0;
}


Measured memory_bytes: 14280
//#include "oj/atcoder.h"
//#include "std.h"
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <float.h>

#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define SWAP(T,a,b) do { T _tmp=a; a=b; b=_tmp; } while (0)

//#include "oj/io.h"

void print_ai(int *a, int n) {
	for (int i=0; i<n; i++) {
		if (i) printf(" ");
		printf("%d", a[i]);
	}
	printf("\n");
}

void scan_ai(int *a, int n) {
	for (int i=0; i<n; i++)
		scanf("%d", &a[i]);
}

//#include "oj/debug.h"

void print_hr() {
	printf("---------------------------\n");
}




int main() {
	long q, h, s, d, n;
	while (scanf("%ld %ld %ld %ld %ld", &q, &h, &s, &d, &n)==5) {
		q *= 4;
		h *= 2;
		if (q < s) s = q;
		if (h < s) s = h;
		long s1 = s*n, s2 = n/2*d + (n%2)*s;
		if (s2 < s1) s1 = s2;
		printf("%ld\n", s1);
	}
}



Measured memory_bytes: 128
#include <cstdio>

using namespace std;

int main()
{
  int K;
  scanf("%d", &K);
  int S;
  scanf("%d", &S);
  int counter = 0;
  //(x, y) -> S-x-y=z -> 0<=z<=K
  for (int i = 0; i < K+1; i++) {
    for (int j = 0; j < K+1; j++) {
      if (S-i-j>=0 && S-i-j<=K) counter++;
    }
  }
  printf("%d\n", counter);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef long double lld;
#define mod 1000000007
#define mod2 998244353
#define fori(n) for (int i = 0; i < n; i++)
#define forj(n) for (int j = 0; j < n; j++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define sortvec(a) sort(a.begin(), a.end())
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl
#define cerr if(true)cerr
void print(){cout<<endl;}
template<typename T,typename... Args>
void print(T a, Args... args) {cout<<a<<" ";print(args...);}
lli llipowerp(lli x, lli y, lli p=LLONG_MAX)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1) res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
lli binarySearch(vector<int> arr, int l, int r, int x)
{
    if (r >= l)
    {
        lli mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
template <typename T>
inline void printvec(vector<T> inp){
    for(auto it:inp) cout<<it<<" ";
    cout << endl;
}
//---------------------------------------------------------------------------------

int main()
{
    int k,a,b;
    cin>>k>>a>>b;
    fori(1050){
        if(i*k>=a && i*k<=b){
            cout<<"OK"<<endl;
            return 0;
        }
    }
    cout<<"NG"<<endl;
}


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

int main(){
    int a, b, x, y;
    while(1){
        cin >> a >> b;
        if(a == 0 && b == 0)break;
        for(int i = 1;i <= a;i++){
            for(int j = 1;j <= b;j++){
                x = i - (i / 2) * 2;
                y = j - (j / 2) * 2;
                if(x == 1 && y == 1 || x == 0 && y == 0)cout << "#";
                if(x == 1 && y == 0 || x == 0 && y == 1)cout << ".";
            }
         cout << endl;
         }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <numeric>
#include <set>
#include <list>
#include <bitset>
#include <cstdlib>
using namespace std;

int main()
{
    string S;
    cin >> S;
    set<char> ans(S.begin(), S.end());
    pair<int, int> output;
    output.first = 0;
    output.second = 0;
    for (char c : ans)
    {
        if (c == 'N')
        {
            output.second++;
        }
        else if (c == 'S')
        {
            output.second--;
        }
        else if (c == 'E')
        {
            output.first++;
        }
        else
        {
            output.first--;
        }
    }
    if (!((output.first) || (output.second)))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        k: i128,
        a: i128,
        b: i128,
    };
    let res = (a..b+1).find(|x| {
        x%k == 0
    });
    let ans = if res != None {
        "OK"
    } else {
        "NG"
    };
    println!("{}", ans);
}


Measured memory_bytes: 2144
h, w = gets.split.map(&:to_i)
while (h != 0 || w != 0)
puts "#" * w
 (h-2).times{
     puts "#" + "." * (w - 2) + "#"
}
puts "#" * w
puts
 
 h, w = gets.split.map(&:to_i)
end




Measured memory_bytes: 6956
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iomanip>
#include<limits>
#include<queue>
#include<set>
#include<cstdio>
#include<climits>
#include<cstring>

using namespace std;

bool is_prime(int n){
	for(int i = 2;i*i <=n ;i++){
		if(n%i == 0)return false;
	}
	return n!=1;
}

int main(){

	int q;
	cin >> q;

	vector<int> left(q) ,right(q);
	vector<int>cnt(100010);
    cnt[0] = 0;

    for(int i = 0;i < q;i++){
    	cin >> left[i] >> right[i];
    }

    for(int i = 1;i <= 100000;i+=2){
    	if(is_prime(i) && is_prime((i+1)/2)){
    		cnt[i] = cnt[i-1] + 1;
    	}else{
    		cnt[i] = cnt[i-1];
    	}
    	cnt[i+1] = cnt[i];
    }

    for(int i = 0;i <q;i++){
    	cout << cnt[right[i]] - cnt[left[i] -  1] << endl;
    }

    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,i,l,r,mid,ans,sum[N],c[N],x;
int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&x),++sum[++c[x]];
	for (i=1;i<=n + 5;i++) sum[i]+=sum[i-1];
	for (i=1;i<=n;i++){
		l=1,r=n + 5,ans=0;
		while (l<=r){
			mid=l+r>>1;
			if (1ll*mid*i<=sum[mid]) ans=mid,l=mid+1;
			else r=mid-1;
		}
		printf("%d\n",ans);
	}
}

Measured memory_bytes: 6144
#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
input:
1 2 1
4 2 2

output:
3
"""

import sys
from collections import namedtuple


class CircleIntersections(object):
    def __init__(self, in_data):
        x1, y1, r1 = map(int, in_data[0].split())
        x2, y2, r2 = map(int, in_data[1].split())

        Circle = namedtuple('Circle', ('centre', 'radius'))
        self.c1 = Circle(centre=x1 + y1 * 1j, radius=r1)
        self.c2 = Circle(centre=x2 + y2 * 1j, radius=r2)

    def calc_intersection(self):
        c_distance = abs(self.c2.centre - self.c1.centre)
        r1, r2 = self.c1.radius, self.c2.radius

        if c_distance > r1 + r2:
            return 4
        elif c_distance == r1 + r2:
            return 3
        elif abs(r1 - r2) < c_distance < r1 + r2:
            return 2
        elif c_distance == abs(r1 - r2):
            return 1
        else:
            return 0


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    case = CircleIntersections(in_data=_input)
    print(case.calc_intersection())

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

#pragma warning(disable:4996)

#define MAX_N 120
#define MAX_M 1440

int x[MAX_N][MAX_M];
int y[MAX_N][MAX_M];
int z[MAX_N][2];
int a, n, m, b, a1, a2, a3, a4, a5, a6;

int main() {
	cin >> a;
	for (int i = 0; i < a; i++) { scanf("%02d:%02d-%02d:%02d", &a1, &a2, &a3, &a4); z[i][0] = a1 * 60 + a2; z[i][1] = a3 * 60 + a4; }
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> b;
		for (int j = 0; j < b; j++) {
			scanf("%02d:%02d-%02d:%02d", &a1, &a2, &a3, &a4);
			a5 = a1 * 60 + a2; a6 = a3 * 60 + a4;
			for (int j = a5; j < a6; j++) { x[i][j] = 1; }
		}
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> b;
		for (int j = 0; j < b; j++) {
			scanf("%02d:%02d-%02d:%02d", &a1, &a2, &a3, &a4);
			a5 = a1 * 60 + a2; a6 = a3 * 60 + a4;
			for (int j = a5; j < a6; j++) { y[i][j] = 1; }
		}
	}
	int sum = 0, sum1 = 0, sum2 = 0;
	for (int i = 0; i < a; i++) {
		sum1 = 0; sum2 = 0;
		for (int j = 0; j < n; j++) {
			for (int k = z[i][0]; k < z[i][1]; k++) {
				if (x[j][k] == 0) { goto E; }
			}
			sum1++;
		E:;
		}
		for (int j = 0; j < m; j++) {
			for (int k = z[i][0]; k < z[i][1]; k++) {
				if (y[j][k] == 0) { goto F; }
			}
			sum2++;
		F:;
		}
		sum += min(sum1, sum2);
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 2372
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

int main(){
  int c = 0, t = 0, n; string s; cin >> n >> s;
  rep(i, n) if(s[i] == 'R') ++t;
  rep(i, t) if(s[i] == 'W') ++c;
  cout << c << endl;
  return 0;
}

Measured memory_bytes: 3768
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }


const int mod = 1000000007;
struct mint{
	ll x;
	mint(ll x = 0):x((x%mod+mod)%mod){}
	mint operator-() const{return mint(-x);}
	mint& operator+=(const mint a){
		if((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a){
		if((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a){
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const{
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const{
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const{
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const{
		if(!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if(t&1) a *= *this;
		return a;
	}
	mint inv() const{
		return pow(mod-2);
	}
	mint& operator/=(const mint a){
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const{
		mint res(*this);
		return res/=a;
	}
};

//istream& operator>>(istream& is, const mint& a){return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a){return os << a.x;}

// nCa
mint choose(int n, int a){
	mint x = 1, y = 1;
	rep(i,a){
		x *= n-i;
		y *= i+1;
	}
	return x / y;
}

struct Combination{
	vector<mint> fact, ifact;
	Combination(int n):fact(n+1),ifact(n+1){
		assert(n < mod);
		fact[0] = 1;
		for(int i = 1; i <= n; i++) fact[i] = fact[i-1]*i;
		ifact[n] = fact[n].inv();
		for(int i = n; i >= 1; i--) ifact[i-1] = ifact[i]*i;
	}
	mint operator()(int n, int k){
		if(k < 0 || k > n) return 0;
		return fact[n]*ifact[k]*ifact[n-k];
	}
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	Combination comb(h+w+1);
	mint ans = 0;
	for(int i = b; i < w; i++){
		ans += comb(i+h-a-1, i) * comb(a-1+w-i-1, a-1);
	}
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3328
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scanln(&n)

	if n == 0 {
		fmt.Println(0)
		return
	}

	ds := []int{0, 0} // padding
	mbs := 0

	var v int
	for i := uint(0); ; i++ {
		if i%2 == 0 {
			v = 1 << i
		} else {
			v = -1 << i
		}
		ds = append(ds, ds[i]+v)

		if n < 0 && n >= ds[i+2] || n > 0 && n <= ds[i+2] {
			mbs = int(i + 2)
			break
		}
	}

	m := ds[mbs] - ds[mbs-2]
	bits := make([]rune, mbs-1)
	bits[0] = '1'

	for i := mbs - 1; i >= 2; i-- {
		bi := mbs - i
		diff := n - m
		if (diff < 0) == (ds[i] < 0) && abs(diff) >= abs(ds[i-2])+1 {
			bits[bi] = '1'
			m += ds[i] - ds[i-2]
		} else {
			bits[bi] = '0'
		}
	}

	fmt.Println(string(bits))
}

func abs(a int) int {
	if a < 0 {
		return -1 * a
	}
	return a
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i=x;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define UNIQ(a) unique(all(a))
#define UNIQNUM(a) UNIQ(a)-a.begin()
#define UNIQIT(a) a.erase(UNIQ(a), a.end());
#define VOUT(v,i) rep(i,v.size())cout<<v[i]<<(i==v.size()-1?"\n":" ");
#define vout(v) VOUT(v,z);
#define vdbg(v,i) cout<<#v<<": ";for(int i=0;i<(int)v.size();i++){cout<<v[i]<<" ";}cout<<"\n";
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define vsum(v) accumulate(all(v), 0LL)
#define MOUT(m,r,c) rep(i,r){rep(j,c){cout<<m[i][j]<<" ";}cout<<endl;}
#define mout(m) MOUT(m,m.size(),m[0].size())
#define debg(a) cout<<#a<<": "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define digit(a) to_string(a).length();
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
// template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
// template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
bool is_palindrome(string s){return s == string(s.rbegin(),s.rend());}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef vector<ll> V;
typedef vector<vector<ll>> VV;
// const long long MOD=1000000007;
const long long INF = 1e18;
#define EPS (1e-7)
#define PI (acos(-1))
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) { a = b; return true; }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) { a = b; return true; }
    return false;
}



int main(){
    long long a;
    scanf("%lld",&a);
    cout << a+a*a+a*a*a << endl;
    return 0;
}


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

int main() {
  string a;
  cin >> a;
  if(a.at(0)==a.at(1) && a.at(1)==a.at(2)){
    cout << "No" << endl;  
  }
  else{
  cout << "Yes" << endl;
  }  
}

Measured memory_bytes: 256
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

const int S = 1000000;
int fact[S+10], inv[S+10];

int mod_pow(int n, int k) {
    int ret = 1, dbl = n % MOD;
    for(; k; k>>=1) {
        if(k & 1) (ret *= dbl) %= MOD;
        (dbl *= dbl) %= MOD;
    }
    return ret;
}

int comb(int n, int r) {
    if(n < r) return 0;
    int p = fact[n];
    int q = (inv[n-r] * inv[r]) % MOD;
    return (p * q) % MOD;
}
 
signed main() {
    fact[0] = 1;
    for(int i=1; i<=S; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }

    inv[S] = mod_pow(fact[S], MOD-2);
    for(int i=S-1; i>=0; i--) {
        inv[i] = (inv[i+1] * (i+1)) % MOD;
    }

    int N; scanf("%lld", &N);
    int ans = 0, prev = 0;
    for(int k=1; k<N; k++) {
        int Perm = (fact[k] * fact[N-1-k]) % MOD;
        int Comb = comb(k-1, N-1-k);
        int Value = Perm * Comb % MOD;
        int KValue = (Value - prev + MOD);

        (ans += (KValue * k % MOD)) %= MOD;
        prev = Value;
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 15872
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < n; i++)

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (b / a > c) cout << c << endl;
	else cout << b / a << endl;
	return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int, input().split()))
for i in range(n):
    a[i]-=1
b=list(map(int, input().split()))
c=list(map(int, input().split()))
ans=b[a[0]]
for i in range(1,n):
    ans+=b[a[i]]
    if a[i-1]+1==a[i]:
        ans+=c[a[i-1]]
print(ans)

Measured memory_bytes: 3064
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, M = inm()

prices = []
for i in range(N):
    a, b = inm()
    prices.append((a, b))
prices.sort()


def solve():
    cnt = 0
    amount = 0
    for a, b in prices:
        x = min(b, M - cnt)
        amount += x * a
        cnt += x
        if cnt >= M:
            break

    return amount


print(solve())


Measured memory_bytes: 22788
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N;
vector<pair<i64, i64> > ch[202020];

vector<pair<i64, i64> > canonize(vector<pair<i64, i64> > &seq)
{
	sort(seq.begin(), seq.end());
	vector<pair<i64, i64> > ret;

	i64 upp = 1LL << 50LL;
	for (auto e : seq) {
		if (e.second < upp) {
			ret.push_back(e);
			upp = e.second;
		}
	}

	return ret;
}

vector<pair<i64, i64> > solve(int p, i64 thr)
{
	if (ch[p].size() == 0) {
		return{ {0LL, 0LL} };
	}

	vector<pair<i64, i64> > left = solve(ch[p][0].first, thr);
	int augl = ch[p][0].second;
	vector<pair<i64, i64> > right = solve(ch[p][1].first, thr);
	int augr = ch[p][1].second;

	if (left.size() > right.size()) {
		swap(left, right);
		swap(augl, augr);
	}

	vector<pair<i64, i64> > ret;
	for (int i = 0; i < left.size(); ++i) {
		i64 inl = left[i].first + augl, outl = left[i].second + augl;
		int idx = lower_bound(right.begin(), right.end(), make_pair(thr - augr - outl, 1LL << 50LL)) - right.begin() - 1;
		if (idx < 0) continue;
		i64 outr = right[idx].second + augr;

		ret.push_back({ inl, outr });
		ret.push_back({ outr, inl });
	}

	return canonize(ret);
}

bool isok(i64 thr)
{
	return solve(0, thr).size() > 0;
}

int main()
{
	scanf("%d", &N);
	for (int i = 1; i < N; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a;
		ch[a].push_back({ i, b });
	}

	i64 left = 0, right = 1LL << 40LL;
	while (left < right) {
		i64 mid = (left + right) / 2;
		if (isok(mid)) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	printf("%lld\n", left);
	return 0;
}


Measured memory_bytes: 23424
/*
  AOJ 0523
  Title:Time Card
  @kankichi573
*/
#include <stdio.h>
// #include <stdlib.h>
// #include <string.h>
// #include <math.h>
// #include <float.h>
// #include <stdlib.h>

int h1,m1,s1,h2,m2,s2;
main()
{
        int i,t;

        for(i=0;i<3;i++)
        {
                scanf("%d %d %d %d %d %d",&h1,&m1,&s1,&h2,&m2,&s2);
                t=(h2-h1)*3600+(m2-m1)*60+(s2-s1);
                printf("%d %d %d\n",t/3600,(t/60)%60,t%60);

        }
        return(0); 
}

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

#define ed cout << "\n";
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ffor(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(i, n) ffor(i, 0, n)
#define All(obj) (obj).begin(), (obj).end()
#define INF ((ll)1e9 + 7)
#define c(a) cout << a << "\n";
using namespace std;
const int N = 100005;
ll gcd(ll a, ll b)
{
    return (b ? gcd(b, a % b) : a);
}
int main()
{
    speed;
    cout << fixed << setprecision(10);
    /*start*/
    int n, X;
    cin >> n >> X;
    vector<ll> x(n);
    rep(i, n)
    {
        cin >> x[i];
        x[i] = abs(X - x[i]);
    }
    ll mem = gcd(x[0], x[1]);
    rep(i, n)
    {
        mem = gcd(mem, x[i]);
    }
    if (x.size() == 1)
        mem = x[0];
    c(mem);

    return 0;
}


Measured memory_bytes: 1024
fun main(args: Array<String>) {
  val input1 = readLine()!!.toInt()
  val input2 = readLine()!!
  var result = ""
  result = if (input2.length <= input1) {
    input2
  } else {
    input2.substring(0, input1).plus("...")
  }
  println(result)
}


Measured memory_bytes: 34492
from functools import lru_cache

N = int(input())
X = input()


@lru_cache(maxsize=None)
def popcount(x):
    return x % bin(x).count('1')


def f(x):
    cnt = 1
    while x > 0:
        x = popcount(x)
        cnt += 1

    return cnt


count = X.count('1')
mod_one = count - 1
if mod_one == 0:
    mod_one = 1
mod_zero = count + 1
ones = [1 % mod_one]
zeros = [1 % mod_zero]
x_mod_one = 0 if X[-1] == '0' else 1 % mod_one
x_mod_zero = 0 if X[-1] == '0' else 1 % mod_zero

for xi in reversed(X[:-1]):
    ones.append(ones[-1] * 2 % mod_one)
    zeros.append(zeros[-1] * 2 % mod_zero)
    if xi == '1':
        x_mod_one += ones[-1]
        x_mod_one %= mod_one
        x_mod_zero += zeros[-1]
        x_mod_zero %= mod_zero

ones = list(reversed(ones))
zeros = list(reversed(zeros))

for i in range(N):
    if count == 1 and X[i] == '1':
        print(0)
    elif X[i] == '1':
        x = (x_mod_one - ones[i]) % mod_one
        print(f(x))
    else:
        x = (x_mod_zero + zeros[i]) % mod_zero
        print(f(x))


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

int N;

void dfs(char a = 'a', string b = "") {
	if (b.size() == N) cout << b << endl;
	else {
		for (char i = 'a'; i < a; i++) dfs(a, b + i);
		dfs(a + 1, b + a);
	}
}

int main() {
	cin >> N;
	dfs();
}

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

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> h(n);
    for(int i = 0; i < n; i++){
        cin >> h.at(i);
    }
    sort(h.begin(), h.end());
    reverse(h.begin(), h.end());
    if(k < n){
        for(int i = 0; i < k; i++){
            h.at(i) = 0;
        }
    } else {
        for(int i = 0; i < n; i++){
            h.at(i) = 0;
        }
    }
    long sum = 0;
    for(int i = 0; i < n; i++){
        sum = sum + h.at(i);
    }
    cout << sum << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
int main(){
	int k, x; std::cin >> k >> x;
	for (auto i = x - k + 1; i < x + k; ++i) {
		if (i != x - k + 1) std::cout << ' ';
		std::cout << i;
	}
}



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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define vc vector<char>
#define ii pair<int,int>
#define fi first
#define sc second
#define all(x) (x).begin(),(x).end()
#define get_bit(x, k) ((x >> k) & 1)
// ---------------------------------

void MAIN() {
  int n; cin >> n;
  vector<int> a(n), l(n), r(n);
  for (auto &i : a) cin >> i;
  for (int i = 0; i < n; i++) {
    l[i] = a[i];
    if (i) l[i] = __gcd(l[i], l[i - 1]);
  }
  for (int i = n - 1; i >= 0; i--) {
    r[i] = a[i];
    if (i != n - 1) r[i] = __gcd(r[i], r[i + 1]);
  }
  int ans = max(r[1], l[n - 2]);
  for (int i = 1; i < n - 1; i++) {
    ans = max(ans, __gcd(l[i - 1], r[i + 1]));
  }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 5556
#include<bits/stdc++.h>
#define Int int64_t
#define ll long long
#define pb push_back
using namespace std;
const Int MAXN=200005;
const int ALPHA=26;

Int N,K,M;
Int X,Y,Z;Int C;
vector<Int> ID;
vector<Int> SZ;
string S;
int find(int x){
    if(ID[x]==x) return x;
    return find(ID[x]);
}
void Union(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(SZ[x]>SZ[y]){
        ID[y]=x;
        SZ[x]+=SZ[y];
    }
    else{
        ID[x]=y;
        SZ[y]+=SZ[x];
    }
    return;
}
string common_prefix(string s,string t){
    string ans="";
    for(int i=0;i<min(s.length(),t.length());++i){
        if(s[i]==t[i]) ans.pb(s[i]);
        else break;
    }
    return ans;
}
string LCP(vector<string> A,int l,int r){
    if(l>r) return "";
    if(l==r) return A[l];
    int mid=(l+r)/2;
    string left=LCP(A,l,mid);
    string right=LCP(A,mid+1,r);
    return common_prefix(left,right);
}

long long ModExpo(long long x,unsigned long long y,long long M){
    Int ans=1;
    ans=(long long)ans;
    
    while(y>0){
        if(y&1) ans=((ans%M)*(x%M))%M;
        y>>=1LL;
        x=((x%M)*(x%M))%M;
    }
    return ans%M;
}
Int LCM(Int x,Int y){
    return (x*y)/__gcd(x,y);
}

using D=long double;
vector<Int> A,B;
Int ceils(Int x,Int k){
    return (x+k-1)/k-1;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
    int t;
    t=1;
    while(t--){
        cin>>N>>K;
        vector<Int> A(N);
        Int maxs=-1;
        for(auto &x:A) cin>>x,maxs=max(maxs,x);
        if(!K) {
            cout<<maxs<<"\n";
            continue;
        }
        Int lb=1,rb=1e9+200;
        auto possible=[&](vector<Int> &arr,Int k,Int tt){
         
          for(auto x:arr){
              tt-=ceils(x,k);
          }
          return tt>=0;
        };
        while(lb<rb){
            Int mid=(lb+rb)/2;
            if(possible(A,mid,K)) rb=mid;
            else lb=mid+1;
        }
        cout<<lb<<"\n";
        
    }
}

Measured memory_bytes: 4672