akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--)
#define REP(i, n) for(int i=0; i<(n); i++)
#define RREP(i, n) for(int i=(n-1); i>=0; i--)
#define REP1(i, n) for(int i=1; i<=(n); i++)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(a) (a).begin(),(a).end()
#define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end());
#define CONTAIN(a, b) find(ALL(a), (b)) != (a).end()
#define out(...) printf(__VA_ARGS__)
#if DEBUG
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...) /* ... */
#endif
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
void _OUT() {}; template<class H, class... T> void _OUT(H &h, T &... t) { cout<<' '<<h; _OUT(t...); };
template<class H, class... T> void _P(H &h, T &... t) { cout<<h; _OUT(t...); };
#define _PN(...) _P(__VA_ARGS__); cout << endl;
#define EXEC(...) void exec() { (__VA_ARGS__ - 1) ? multi() : solve(0); }

void exec();
void solve(int t);
void multi() { int TT; cin>>TT; REP1(t,TT) solve(t); }
signed main()
{
#if DEBUG
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    exec();
    return 0;
}

/*================================*/
#if DEBUG
#define SIZE 100
#else
#define SIZE 223450
#endif

int N,M;
vector<int> A(SIZE);

void solve(int _t) {
    cin>>N;
    pair<int,int> V[N];
    int l,r;
    REP(i,N) {
        cin>>V[i].first>>V[i].second;
        V[i].first--;
        V[i].second--;
    }
    sort(V,V+N);
    int DPL[N],DPR[N];
    l=0;r=1e9;
    REP(i,N) {
        chmax(l,V[i].first);
        chmin(r,V[i].second);
        DPL[i]=max(0LL,r-l+1);
    }
    l=0;r=1e9;
    RREP(i,N) {
        chmax(l,V[i].first);
        chmin(r,V[i].second);
        DPR[i]=max(0LL,r-l+1);
    }
    int maxi = 0;
    auto f = [](pair<int,int> &a) -> int {
        return a.second - a.first;
    };
    REP(i,N-1) {
        if (f(V[maxi]) < f(V[i])) maxi = i;
    }
    l=0;r=1e9;
    REP(i,N)if(i!=maxi) {
        chmax(l,V[i].first);
        chmin(r,V[i].second);
    }
    int ans = f(V[maxi])+1+max(0LL,r-l+1);
    REP(i,N-1) {
        if (chmax(ans, DPL[i]+DPR[i+1])) {
            debug("i:%lld\n");
        }
    }
    _PN(ans);
}
EXEC(1)



Measured memory_bytes: 8236
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef pair<int, int> pint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;
#define Pi 3.1415926535897932384626

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

bool check(int a, int b) {
	return a > b;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//aCbを1000000007で割った余りを求める
llint convination(llint a, llint b) {
	llint ans = 1;
	for (llint i = 0; i < b; i++) {
		ans *= a - i;
		ans %= 1000000007;
	}
	for (llint i = 1; i <= b; i++) {
		ans *= modinv(i, 1000000007);
		ans %= 1000000007;
	}
	return ans;
}

int main() {
	int n;
	cin >> n;
	vint a(n);
	rep(i, n)cin >> a[i];
	drep(i, n) {
		cout << a[i];
		if (i == 0)cout << endl;
		else {
			cout << " ";
		}
	}
	return 0;
}


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

int main(void) {
  double weight, height;
  int number, bmi;

  while (scanf("%d,%lf,%lf", &number, &weight, &height) != EOF) {
    if (weight / (height * height) >= 25) {
      printf("%d\n", number);
    }
  }

  return EXIT_SUCCESS;
}

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

using namespace std;

int main()
{
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        vector<int> v;
        for (int i = 0; i < n; ++i) {
            int a;
            cin >> a;
            v.push_back(a);
        }

        int r = 10000000;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j) {
                    continue;
                }
                r = min(abs(v[i] - v[j]), r);
            }
        }
        cout << r << endl;
    }
}

Measured memory_bytes: 3140
#include <stdio.h>

int main(void){
  char S[3];
  int ans = 0;

  scanf("%s",S);

  if(S[0] == '1') ans++;
  if(S[1] == '1') ans++;
  if(S[2] == '1') ans++;

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

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

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int n, k;
int a[100000];
vector<int> e[100000];
int ans = 0;
P dist[100000];
bool done[100000];

void dfs(int v, int d) {
    rep(i,e[v].size()) {
        dist[e[v][i]] = P(d+1, e[v][i]);
        dfs(e[v][i], d+1);
    }
}

void paint(int v) {
    if (done[v]) return;
    done[v] = true;
    rep(i,e[v].size()) {
        paint(e[v][i]);
    }
}

int main() {
    cin >> n >> k;
    rep(i,n) {
        cin >> a[i];
        a[i]--;
        if (i == 0) {
            if (a[0] != 0)  {
                a[0] = 0;
                ans++;
            }
        } else {
            e[a[i]].push_back(i);
        }
    }
    done[0] = true;
    dist[0] = P(0, 0);
    dfs(0, 0);
    sort(dist, dist+n, greater<P>());
    rep(i,n) {
        if (done[dist[i].second]) continue;
        if (dist[i].first <= k) continue;
        ans++;
        int now = dist[i].second;
        rep(j,k-1) {
            now = a[now];
        }
        paint(now);
    }
    cout << ans << endl;
}
































Measured memory_bytes: 11648
import scala.io.StdIn.{readInt,readLine}

object Main {
  val alist = List(1,3,5,7,9,11,15,17,19,21,23,25)
  val blist = 0 to 25
  val invs = (for{
    i<-alist
    j<-1 to 25 by 2
    if (i*j) % 26 == 1
  } yield (i,j)).toMap
  def encode(c:Int,a:Int,b:Int) = (((a*(c-97)+b) % 26)+97).toChar
  def decode(c:Int,a:Int,b:Int) = ((a*(c-97-b+26) % 26)+97).toChar

  def main(args:Array[String]) = {
    val n = readInt
    (0 until n).foreach { _ =>
      val l = readLine
      val (a,b) = {for(i<-alist;j<-blist) yield (i,j)}.find{ case (i,j) =>
            l.contains("that".map{encode(_,i,j)}) || l.contains("this".map{encode(_,i,j)})
      }.get
      println( l.map { c=> if(c>=97 && c<=122) decode(c,invs(a),b) else c })
    }
  }
}

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

int main()
{
	int N, K, Q;
	cin >> N >> K >> Q;
	vector<int> cnt(N);
	for (int i = 0; i < Q; i++) {
		int A;
		cin >> A; --A;
		++cnt[A];
	}
	for (int i = 0; i < N; i++) {
		puts(K - (Q - cnt[i]) > 0 ? "Yes" : "No");
	}
	return 0;
}


Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
"""
C - Grand Garden
https://atcoder.jp/contests/abc116/tasks/abc116_c

"""
import sys



def solve(heights):
    def w(arr):
        stack = []
        buff = []
        while arr:
            h = arr.pop(0)
            if h == 0:
                if buff:
                    stack.append(buff)
                    buff = []
            else:
                buff.append(h)
        if buff:
            stack.append(buff)
        return stack

    ans = 0
    stack = w(heights)
    while stack:
        arr = stack.pop()
        m = min(arr)
        ans += m
        s = w([a-m for a in arr])
        stack.extend(s)
    return ans


def main(args):
    N = int(input())
    heights = [int(h) for h in input().split()]
    ans = solve(heights)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


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

int main(void) {
    int cnt=0,ans=0,max=0;
    long long int N;
    cin>>N;

    for (int i=0;i<4;i++){
    }

    if(N%2!=0){
      N = N*2;
    }

    cout<<N<<endl;

    return 0;
}

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

using namespace std;

typedef long long int ll;

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

  int n;
  cin >> n;
  vector < int > a (n + 1);
  int mx = 0, mi = n + 1;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    mx = max (mx, a[i]);
    mi = min (mi, a[i]);
  }

  if (mx - mi > 1) {
    cout << "No\n";
    return 0;
  }

  if(mx == mi) {
    bool ok = true;
    for (int i = 1; i <= n; i++) {
      if (a[i] != n - 1) ok = false;
    }
    if (ok) {
      cout << "Yes\n";
      return 0;
    }

    ok = true;
    for (int i = 1; i <= n; i++) {
      if (a[i] > (n / 2)) ok = false;
    }

    if (ok) {
      cout << "Yes\n";
    } else {
      cout << "No\n";
    }
  } else {
    int alone = 0;
    for (int i = 1; i <= n; i++) {
      if (a[i] == mi) alone++;
    }
    int not_alone = n - alone;

    if(mx >= alone + 1 && mx <= alone + (not_alone / 2)) cout << "Yes\n";
    else cout << "No\n";
  }
}


Measured memory_bytes: 640
// B - Toll Gates
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	int N,M,X; cin>>N>>M>>X;
	vector<int> A(M); rp(i, 0, M) cin>>A[i];

	int l = 0, r = 0;
	rp(i, 0, M){
		if(A[i] < X) l++;
		else r++;
	}
	cout<< min(l, r) <<endl;
}

Measured memory_bytes: 256
import java.util.*;

class Edge implements Comparable<Edge> {
	
	public int u, v, w;
	Edge(int u, int v, int w) {
		this.u = u;
		this.v = v;
		this.w = w;
	}
	
	@Override
	public int compareTo(Edge e) {
		return this.w - e.w;
	}
	
	public String toString() {
		return this.u + " " + this.v + " " + this.w;
	}
}

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int n, m;
	static int[] parent, rank;
	static Edge[] es;
	
	public static void main(String[] args) {
		while(read()){
			solve();
		}
	}

	static boolean read(){
		n = sc.nextInt();
		if(n == 0)return false;
		m = sc.nextInt();
		es = new Edge[m];
		for (int i = 0; i < m; i++) {
			String[] ps = sc.next().split(",");
			es[i] = new Edge(Integer.parseInt(ps[0]), Integer.parseInt(ps[1]), Integer.parseInt(ps[2]));
		}
		parent = new int[n];
		rank = new int[n];
		return true;
	}
	
	static void solve(){
		Arrays.sort(es);
		int res = 0;
		init(n);
		for (int i = 0; i < m; i++) {
			Edge e = es[i];
			if (!same(e.u, e.v)) {
				unite(e.u, e.v);
				res += (e.w / 100) - 1;
			}
		}
		System.out.println(res);
	}

	static void init(int n){
		for(int i = 0; i < n; i++){
			parent[i] = i;
			rank[i] = 0;
		}
	}
	
	static int find(int x){
		if(parent[x] == x){
			return x;
		}else{
			return parent[x] = find(parent[x]);
		}
	}
	
	static void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y)return;
		
		if(rank[x] < rank[y]){
			parent[x] = y;
		}else{
			parent[y] = x;
			if(rank[x] == rank[y])rank[x]++;
		}
	}
	
	static boolean same(int x, int y){
		return find(x) == find(y);
	}
}

Measured memory_bytes: 13000
use std::cmp;
use std::collections::HashMap;
use std::collections::VecDeque;
use std::io::Read;
use std::usize::MAX;

macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}
macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}
macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, [ $t:tt ]) => {{let len = read_value!($next, usize);(0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()}};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}

fn solve() {
    input! {
        n: usize,
        task: [(usize,usize);n]
    }

    let mut task: Vec<(usize, usize)> = task;
    task.sort_by(|a, b| {
        if a.1 == b.1 {
            a.0.cmp(&b.0)
        } else {
            a.1.cmp(&b.1)
        }
    });

    let mut ans = true;
    let mut time = 0;
    for i in 0..n {
        time += task[i].0;
        if task[i].1 < time {
            ans = false;
            break;
        }
    }

    println!("{}", if ans { "Yes" } else { "No" });
}

fn main() {
    let thd = std::thread::Builder::new().stack_size(104_857_600);
    thd.spawn(|| solve()).unwrap().join().unwrap();

    /*
    // 入力を一括で読み込む場合
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut input = buf.split_whitespace();

    // inputに対しnext()で読み込んでいく
    let q: usize = input.next().unwrap().parse().unwrap();
    */
}

const LARGE_PRIME: u64 = 1_000_000_007;

// @〜でsnippet


Measured memory_bytes: 14716
n, m = list(map(int, input().split()))
ab = [[] for _ in range(n)]

for i in range(n):
    ai, bi = list(map(int, input().split()))
    ab[i] = [ai, bi]
    
ab.sort(key = lambda x: x[0])
cnt = 0
yen = 0
i = 0
while True:
    if cnt + ab[i][1] >= m:
        yen += ab[i][0]*(m-cnt)
        #print(cnt, yen)
        break
    else:
        cnt += ab[i][1]
        yen += ab[i][1]*ab[i][0]
        #print(cnt, yen)
    i += 1

print(yen)


Measured memory_bytes: 21600
using System;
using System.Collections.Generic;
using System.Linq;


class Program
    {
        static void Main(string[] args) {
            const short N = 51;
            short i=0;
            int[][] K = new int[4][];
            List<int> n = new List<int>();
            string s;
            for (i = 0; i < 4; i++)
                K[i] = new int[N];
            for (i = 0; i < N; i++)
                K[0][i] = (i<10)?1:0;
            for (i = 0; i < 3; i++)
                K[i+1] = S(K[i]);

            while (true)
            {
                s = Console.ReadLine();
                if (string.IsNullOrEmpty(s)) break;
                n.Add(int.Parse(s));
            }
            foreach(int n1 in n)
            Console.WriteLine(K[3][n1]);
        }

        public static int[] S(int[] I) {
            int[] A = new int[51];
            for (int i = 0; i < 51; i++) {
                for (int j = 0; j < 10; j++) {
                    A[i] += (i - j < 0 || i - j >= 51) ? 0 : I[i - j];
                }
            }
            return A;
        }

    }

Measured memory_bytes: 9160
N,A,B,C,D=map(int,input().split())
S=input()
 

if "##" in S[A-1:C] or "##" in S[B-1:D]:
  print("No")
  exit()


# A B C D
# A C B D
if C < D:
  print("Yes")
  exit()

# A B D C  
else:
  if "..." in S[B-2:D+1]:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 3572
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.Maybe
import qualified Data.Vector.Unboxed   as V


readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine



main = do
  let xs = V.fromList ([1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51] :: [Int])
  n <- getInt

  print $ xs V.! (n-1)

Measured memory_bytes: 380
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		if ((b - a) == (c - b)){
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}

	}

}


Measured memory_bytes: 21844
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;

public class Program
{

    public void Proc()
    {
        System.Text.StringBuilder ans = new System.Text.StringBuilder();
        while(true) {
            string wd = Reader.ReadLine();
            if(wd.Equals("-")) {
                break;
            }
            int shuffleCount = int.Parse(Reader.ReadLine());
            for (int i = 0; i < shuffleCount; i++) {
                int tmp = int.Parse(Reader.ReadLine());
                wd = wd.Substring(tmp) + wd.Substring(0, tmp);
            }
            ans.AppendLine(wd);
        }
        Console.Write(ans.ToString());
    }


    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"






aabc
3
1
2
1
vwxyz
2
3
4
-







";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}

Measured memory_bytes: 8936
import heapq
import math

q = []
N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in A:
    heapq.heappush(q, -i)
for j in range(M):
    x = heapq.heappop(q)
    heapq.heappush(q, math.ceil(x/2))
print(-sum(q))



Measured memory_bytes: 14532
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int K = scan.nextInt(),X = scan.nextInt();
        X = X - K;
        for(int i=0;i< -1 + K*2;i++){
            System.out.print(X+1 + " ");
            X = X+1;
        }
    }
}

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

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

  // ここにプログラムを追記
  int Num = 1;
  for(int i=0; i<N; i++) {
  	if(Num*2 > Num+K) {
      Num += K;
    }
    else {
      Num *= 2;
    }
  }
  cout << Num << endl;
}

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

using namespace std;
int gcd(int a, int b)
{
    int c=min(a,b),d=max(a,b);
    if  (a==0 || b==0) return d;
    else return gcd(c, d%c);
}

int main()
{

    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b)<<endl;
}

Measured memory_bytes: 3076
s = input()
a = int(s[:2])
b = int(s[2:])
p = 0
q = 0
if a >= 1 and a <= 12:
  p = 1
if b >= 1 and b <= 12:
  q = 1
if p==1 and q == 1:
  print("AMBIGUOUS")
elif p == 1 and q == 0:
  print("MMYY")
elif p == 0 and q == 1:
  print("YYMM")
else:
  print("NA")

Measured memory_bytes: 3064
#include <cstdio>

using namespace std;

int main() {
	int h = 0;
	int a = 0;

	scanf("%d%d", &h, &a);
	if (h%a != 0) {
		printf("%d", (h/a) + 1);
	} else {
	printf("%d", h/a);
    }
  
	return 0;
}

Measured memory_bytes: 128
import std.stdio, std.string, std.conv, std.algorithm, std.math;

void main()
{
    while(true)
    {
        int n = readln.chomp.to!int;
        if(!n)break;

        int y = readln.chomp.to!int;
        real max = 0;
        int maxBank;
        foreach(_; 0 .. n)
        {
            auto inp = readln.split.map!(to!int);
            int b = inp[0],
                r = inp[1],
                t = inp[2];
            real sum;
            final switch(t)
            {
                case 1:
                    sum = (1 + y * r / 100.0);
                    break;
                case 2:
                    sum = (1 + r / 100.0) ^^ y;
                    break;
            } 
            if(sum > max)
            {
                max = sum;
                maxBank = b;
            }
        }
        maxBank.writeln;
    }
}

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

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

ll maxx(ll x,ll y,ll z,ll w){
  return max(x,max(y,max(z,w)));
}
ll minn(ll x,ll y,ll z,ll w){
  return min(x,min(y,min(z,w)));
}
int main() {
  ll N; cin>>N;
  ll ans=10000000000000;
  vector<ll> s(N+1,0);
  rep(i,N){
    ll a; cin>>a;
    s[i+1]=s[i]+a;
  }
  ll i=2;//真ん中の分割
  ll l=1;//l:1~i-1
  ll r=3;//r:i+1~N-1
  ll P,Q,R,S;
  while(i<=N-2){
    while(1){//lを決定する
      if(l<i-1 && abs(s[l]-(s[i]-s[l]))>abs((s[l+1])-(s[i]-s[l+1]))){
        l++;
        continue;
      }
      break;
    }
    while(1){//rを決定する
      if(r<N-1 && abs((s[r]-s[i])-(s[N]-s[r]))>abs((s[r+1]-s[i])-(s[N]-s[r+1]))){
        r++;
        continue;
      }
      break;
    }
    
    P=s[l];
    Q=s[i]-s[l];
    R=s[r]-s[i];
    S=s[N]-s[r];
    ans=min(ans,maxx(P,Q,R,S)-minn(P,Q,R,S));

    i++;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1920
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
constexpr int inf = 1e5 + 1;
vector<int> dp(inf);
vector<bool> vis(inf);
vector<int>v;
int f(int x) {
	int& ans = dp[x];
	if (x >= n - 1) {
		return 0;
	}
	if (vis[x]) {
		return ans;
	}
	else {
		vis[x] = 1;
		ans = min(abs(v[x] - v[x + 1]) + f(x + 1), f(x + 2) + abs(v[x] - v[x + 2]));
		return ans;
	}
}
int main() {
	int t;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> t;
		v.push_back(t);
	}
	for (int i = 0; i < 3; i++) {
		v.push_back(t);
	}
	cout << f(0);
}

Measured memory_bytes: 3452
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (int64_t)(n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

#define chmax(a, b) (a) = max(a, b)
#define chmin(a, b) (a) = min(a, b)

int D;
vector<int> c(26);
vector<vector<int>> s;

int64_t calc_score(const vector<int>& t) {
  int64_t result = 0;
  vector<int> last(26, -1);
  rep(i, D) {
    const int j = t[i];
    result += s[i][j];
    last[j] = i;
    rep(k, 26) { result -= c[k] * (i - last[k]); }
  }
  return result;
}

int main() {
  cin >> D;

  rep(i, 26) { cin >> c[i]; }

  s.resize(D, vector<int>(26));
  rep(i, D) rep(j, 26) { cin >> s[i][j]; }

  int64_t score = numeric_limits<int64_t>::min();
  vector<int> sln(D);
  vector<int> last(26, -1);
  rep(i, D) {
    int next;
    int64_t point = numeric_limits<int64_t>::min();
    int64_t penalty = 0;
    rep(j, 26) { penalty += c[j] * (i - last[j]); }
    rep(j, 26) {
      int z = s[i][j] - penalty + c[j] * (i - last[j]);
      if (point < z) {
        point = z;
        next = j;
      }
    }

    last[next] = i;
    sln[i] = next;
    score += point;
  }

  mt19937 rng(111);
  uniform_int_distribution<int> select_day(0, D - 1);
  uniform_int_distribution<int> select_kind(0, 25);
  rep(iter, 10'000) {
    int j = select_day(rng);
    int old = sln[j];
    sln[j] = select_kind(rng);

    int64_t z = calc_score(sln);
    if (score > z) {
      sln[j] = old;
    } else {
      score = z;
    }
  }

  rep(i, D) { cout << sln[i] + 1 << "\n"; }
  cerr << "score = " << score << "\n";

  return 0;
}

Measured memory_bytes: 3260
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
typedef long long int lint;
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;
    int left_w = 0, right_e = 0;
    for (int i = 1; i < n; i++) {
        if (s[i] == 'E') right_e++;
    }
    s = s + 'Z';
    int ans = INT_MAX;
    // i:リーダーの場所
    for (int i = 0; i < n; i++) {
        ans = min(ans, left_w + right_e);
        if (s[i] == 'W') left_w++;
        if (s[i + 1] == 'E') right_e--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1284
N,M = map(int, input().split())

A = [[] for j in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)
    

D = [0]*N
C = 0
D[0] = 1

def dfs(x):
    global C
    
    if not 0 in D:
        C += 1
        return
    
    for i in A[x]:
        if D[i] == 1:
            continue
        D[i] = 1
        dfs(i)
        D[i] = 0

dfs(0)
print(C)

Measured memory_bytes: 3064
from heapq import heappop, heappush, heapify

class Graph():  #non-directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def prim(self):
        used = [False for _ in range(self.n)]
        used[0] = True
        heap = [(cost, adj) for adj, cost in self.graph[0]]
        heapify(heap)
        res = 0
        while heap:
            cost, node = heappop(heap)
            if used[node]:
                continue
            used[node] = True
            res += cost
            for adj, adjcost in self.graph[node]:
                if used[adj]:
                    continue
                heappush(heap, (adjcost, adj))
        return res

import sys
input = sys.stdin.readline

N = int(input())
T = []

for i in range(N):
    x, y = map(int, input().split())
    T.append((x, y, i))

sort_by_x = sorted(T, key=lambda x: x[0])
sort_by_y = sorted(T, key=lambda x: x[1])

E = []

for i in range(N - 1):
    x1, y1, id1 = sort_by_x[i]
    x2, y2 ,id2 = sort_by_x[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))
    x1, y1, id1 = sort_by_y[i]
    x2, y2 ,id2 = sort_by_y[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))

g = Graph(N, E, 0)

print(g.prim())

Measured memory_bytes: 123360
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;
using vi = vector<int>;

#define in(v) v; cin >> v;
void ins() {}
template<class T,class... Rest>void ins(T& v,Rest&... rest){cin>>v;ins(rest...);}

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rrep(i,n) for(long long i=(n);i>=0;--i)
#define all(f,c,...) (([&](decltype((c)) cccc) { return (f)(begin(cccc), end(cccc), ## __VA_ARGS__); })(c))

// ========== debug ==========
template<class T>ostream& operator<<(ostream& os,const vector<T>& vec){os<<"{";for(size_t i=0;i<vec.size();++i)os<<(i?", ":"")<<vec[i];os<<"}";return os;}
ostream& operator<<(ostream& os,const vector<char>&v){for(size_t i=0;i<v.size();++i)os<<v[i];return os;}
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>& rhs){os<<"("<<rhs.first<<", "<<rhs.second<<")";return os;}

#ifdef LOCAL
void debug() {cerr << "\n";}
template<class First> void debug(const First& first) {cerr<<first<<"\n";}
template<class First, class... Rest> void debug(const First& first, const Rest&... rest) {cerr<<first<<",";debug(rest...);}
void debug2() {cerr << "\n";}
template<class First> void debug2(const First& first) {cerr<<first<<" ";}
template<class First, class... Rest> void debug2(const First& first, const Rest&... rest) {cerr<<first<<" ";debug2(rest...);}
#else
#define debug(...) 42
#define debug2(...) 42
#endif
// ===========================

int main() {
  int N, K;
  ins(N, K);

  vi A(N);
  rep(i, N) {
    cin >> A[i];
  }
  all(sort, A);
  int ans = 0;
  rep(i, K) {
    ans += A[i];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3628
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define iter(it,c) for(auto it=c.begin(); it!=c.end(); ++it)
#define rep(i,b) for(int i=0; i<int(b); i++)
typedef int Weight;
int const inf = 1e8;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight) :
        src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void dijk(Graph const&g, int s, vector<Weight> &dist, vi &prev) {
    int n = g.size();
    dist.assign(n, inf); dist[s] = 0;
    prev.assign(n, -1);
    priority_queue<Edge> q; // "e < f" <=> "e.weight > f.weight"
    q.push(Edge(-2, s, 0));
    while(q.size()) {
        Edge e = q.top();
        q.pop();
        if (prev[e.dst] != -1) continue;
        prev[e.dst] = e.src;
        iter(f,g[e.dst]) {
            if (dist[f->dst] > e.weight+f->weight) {
                dist[f->dst] = e.weight+f->weight;
                q.push(Edge(f->src, f->dst, e.weight+f->weight));
            }
        }
    }
}

int main(){
    int n,k;
    while(cin>>n>>k, n|k){
        Graph g(n);
        rep(i,k){
            int op; cin>>op;
            if(op==1){
                int a,b,c; cin>>a>>b>>c;
                a--; b--;
                g[a].push_back(Edge(a,b,c));
                g[b].push_back(Edge(b,a,c));
            } else {
                int a,b; cin>>a>>b;
                a--; b--;
                vi d,p;
                dijk(g,a,d,p);
                if(d[b]==inf){
                    cout << -1 << endl;
                } else {
                    cout << d[b] << endl;
                }
            }
        }
    }
}

Measured memory_bytes: 1248
import sys
S = input()
S = S[:-1]
for _ in range(len(S)):
    len_s = len(S)
    if len_s%2 == 0:
        s1 = S[:int(len_s/2)]
        s2 = S[int(len_s/2):len_s]
        if s1 == s2:
            print(len_s)
            sys.exit()
        else:
            S = S[:-1]
    else:
        S = S[:-1]


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

import sys
import os
from queue import Queue


N, Q = list(map(int, input().split()))

q = Queue()
for i in range(N):
    lst = input().split()
    name = lst[0]
    t = int(lst[1])
    data = [name, t]
    q.put(data)

time = 0
while not q.empty():
    data = q.get()
    if data[1] > Q:
        data[1] -= Q
        q.put(data)
        time += Q
    else:
        time += data[1]
        print(data[0], time)

Measured memory_bytes: 16820
n,m=map(int,input().split())
s=eval('list(map(int,input().split()[1:])),'*m)
*p,=map(int,input().split())
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n):
  for k in r(m):c[k]+=i>>j&1and j+1in s[k]
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Measured memory_bytes: 44780
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <cassert>

using namespace std;

#define    watch(x); cout << "\n" <<  #x << " is: " << x << "\n";
#define    all(a) (a).begin(), (a).end()
#define    fi first
#define    se second

template<class A, class B>
ostream& operator << (ostream& output, const pair<A, B>& p) {
    output << "(" << p.first << ", " << p.second << ")";
    return output;
}

template<class A>
ostream& operator << (ostream& output, const vector<A>& a) {
    output << "[";
    for(auto it = a.begin(); it != a.end(); ++it) {
        if(it != a.begin()) {
            output << ", ";
        }
        output << *it;
    }
    output << "]";
    return output;
}

using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

//const int inf = 1e9;
//const int mod = 1e9 + 7;
//const double PI = acos(-1.0);
const int mx = 1e5 + 5;
int arr[mx];


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif

    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; ++ i) {
        cin >> arr[i];
    }
    k--;
    int ans = 1e9;
    for(int i = 0; i < n - k; ++i) {
        if(arr[i] >= 0 && arr[i + k] >= 0) {
            ans = min(ans, arr[i + k]);
        }
        else if(arr[i] <= 0 && arr[i + k] <= 0) {
            ans =min(ans, abs(arr[i]));
        }
        else {
            ans = min(ans, arr[i + k] * 2 - arr[i]);
            ans = min(ans, arr[i + k] - arr[i] * 2);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4000
#include <cstdio>
#include <vector>

#define MAXN 100000

std::vector <int> v[MAXN+1], q[MAXN+1];

int m, aib[MAXN+1], ans[MAXN+1], sum;

inline void update(int p, int x){
    sum+=x;
    while(p<=m){
        aib[p]+=x;
        p+=p&(-p);
    }
}

inline int query(int p){
    int u=sum;
    while(p>0){
        u-=aib[p];
        p-=p&(-p);
    }
    return u;
}

int main(){
    int n;
    scanf("%d%d", &n, &m);

    for(int i=1; i<=n; i++){
        int x, y;
        scanf("%d%d", &x, &y);

        v[x].push_back(-1);
        v[y+1].push_back(x);
    }

    for(int i=2; i<=m; i++)
        for(int j=i; j<=m; j+=i)
            q[j].push_back(i);

    for(int i=1; i<=m; i++){
        for(auto x:v[i]){
            if(x==-1) update(i, 1);
            else
                update(x, -1);
        }
        for(auto x:q[i])
            ans[x]+=query(i-x);
    }
    ans[1]=n;

    for(int i=1; i<=m; i++)
        printf("%d\n", ans[i]);

    return 0;
}


Measured memory_bytes: 18816
import java.util.*;
class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int A = Integer.parseInt(sc.next());
	int B = Integer.parseInt(sc.next());
	int K = Integer.parseInt(sc.next());
	int[] arr = new int[100];
	int cnt = 0;
	for(int i = 1; i<=Math.min(A,B); i++) {
	    if(A%i==0 && B%i == 0) {
		arr[cnt] = i;
		cnt++;
	    }
	}
	Arrays.sort(arr);
	System.out.println(arr[arr.length-K]);
    }
}

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

#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using ld = long double;
template <typename T>
vector<T> Vec(int n, T v)
{
    return vector<T>(n, v);
}
template <class... Args>
auto Vec(int n, Args... args)
{
    auto val = Vec(args...);
    return vector<decltype(val)>(n, move(val));
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = (ll)1e9 + 7LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;

class WeightedDisjointSets
{
    using T = int;

public:
    WeightedDisjointSets(const int v) : parent(v), rank(v, 0), size(v, 1), weight(v, 0)
    {
        parent.resize(v);
        for (int i = 0; i < v; i++) {
            parent[i] = i;
        }
    }

    bool same(const int a, const int b)
    {
        return find(a) == find(b);
    }


    int find(const int a)
    {
        if (parent[a] == a) {
            return a;
        } else {
            const int t = find(parent[a]);
            weight[a] += weight[parent[a]];
            return parent[a] = t;
        }
    }

    T getWeight(const int a)
    {
        find(a);
        return weight[a];
    }

    void unite(int a, int b, T d)
    {
        d += getWeight(a);
        d -= getWeight(b);
        a = find(a);
        b = find(b);
        if (a == b) {
            return;
        }
        if (rank[a] < rank[b]) {
            swap(a, b);
            d = -d;
        }
        rank[a] += rank[b];
        parent[b] = a;
        weight[b] = d;
    }

    T diff(const int a, const int b)
    {
        assert(same(a, b));
        return getWeight(b) - getWeight(a);
    }

    int getSize(const int a) const
    {
        return size[parent[a]];
    }

private:
    vector<int> parent;
    vector<int> rank;
    vector<int> size;
    vector<T> weight;
};


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    WeightedDisjointSets uf(N);
    bool ans = true;
    for (int i = 0; i < M; i++) {
        int l, r, d;
        cin >> l >> r >> d;
        l--;
        r--;
        if (uf.same(l, r)) {
            if (uf.diff(l, r) != d) {
                ans = false;
            }
        } else {
            uf.unite(l, r, d);
        }
    }
    cout << (ans ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 1920
#include <atcoder/math>
#include <iostream>

int main()
{
  int T;
  std::cin >> T;
  
  for (int i = 0; i < T; i++) {
    int64_t N, M, A, B;
    std::cin >> N >> M >> A >> B;
    std::cout << atcoder::floor_sum(N, M, A, B) << '\n';
  }
}

Measured memory_bytes: 3612
n, m = map(int, input().split())

if n % 2 == 1:
    for i in range(m):
        print(n - i, i + 1)
else:
    used = [False] * (n + 1)
    offset = 0
    for i in range(m):
        a = n - (i + offset)
        b = i + offset + 1
        d = min(a - b, n - (a - b))
        if used[d] or a - b == n - (a - b):
            offset = 1
        used[d] = True
        print(n - i, i + offset + 1)


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

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)
#define INF 1000000000

typedef long long ll;
typedef pair<ll,ll> P;

int main()
{
	int n;cin >> n;
	vector<P> v;
	
	REP(i,n)
	{
		int a;cin >> a;
		v.PB(P(a,i%2));
	}
	
	sort(ALL(v));
	
	int ans = 0;
	REP(i,n)
	{
		if(i % 2 != v[i].SE)ans++;
	}
	
	cout << ans / 2 << endl;
	
	return 0;
}

Measured memory_bytes: 3444
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

// UnionFind高速
type UnionFind struct {
	d []int
}

func newUnionFind(N int) *UnionFind {
	u := new(UnionFind)
	u.d = make([]int, N)
	for i := 0; i < N; i++ {
		u.d[i] = -1
	}
	return u
}

func (p *UnionFind) root(x int) int {
	if p.d[x] < 0 {
		return x
	}
	p.d[x] = p.root(p.d[x])
	return p.d[x]
}

func (p *UnionFind) unite(x, y int) bool {
	x = p.root(x)
	y = p.root(y)
	if x == y {
		return false
	}
	if p.d[x] > p.d[y] {
		x, y = y, x
	}
	p.d[x] += p.d[y]
	p.d[y] = x
	return true
}

func (p *UnionFind) same(x, y int) bool {
	return p.root(x) == p.root(y)
}

func (p *UnionFind) size(x int) int {
	return -p.d[p.root(x)]
}

// Data :
type Data struct {
	x, y, id int
}

var sw bool

// Datas :
type Datas []Data

func (p Datas) Len() int {
	return len(p)
}

func (p Datas) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Datas) Less(i, j int) bool {
	if sw {
		return p[i].y < p[j].y
	}
	return p[i].x < p[j].x
}

func main() {
	sc.Split(bufio.ScanWords)

	N := getInt()
	x := make(Datas, N)
	y := make(Datas, N)
	for i := 0; i < N; i++ {
		a, b := getInt(), getInt()
		x[i] = Data{a, b, i}
		y[i] = Data{a, b, i}
	}
	sort.Sort(x)
	sw = true
	sort.Sort(y)

	d := make(Datas, 0)
	for i := 1; i < N; i++ {
		di := x[i].x - x[i-1].x
		d = append(d, Data{di, x[i].id, x[i-1].id})
	}
	for i := 1; i < N; i++ {
		di := y[i].y - y[i-1].y
		d = append(d, Data{di, y[i].id, y[i-1].id})
	}
	sw = false
	sort.Sort(d)
	// out(d)
	u := newUnionFind(N)
	ans := 0
	for _, v := range d {
		if u.same(v.y, v.id) {
			continue
		}
		u.unite(v.y, v.id)
		ans += v.x
	}
	out(ans)
}


Measured memory_bytes: 27776
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
struct Pos
{
  int64_t x,y;
};
int main()
{
  	std::string Input;
    int Len;
	std::cin >> Len;
  	auto MakeTown = []()
    {
      Pos p;
      std::cin >> p.x >> p.y;
      return p;
    };
  	
  std::vector<Pos> Towns(Len);
  std::vector<int> Index(Len);
  	for(int i =0;i<Len;i++)
    {
      Towns[i] = MakeTown();
      Index[i] = i;
    }
  	double SumLen=0.0;
  	int Count=1;
    do {
      for(int i =0;i<Len-1;i++)
      {
        auto&&  A = Towns[Index[i]];
        auto&&  B = Towns[Index[i+1]];
        long double dx = (A.x -B.x);
        long double dy = (A.y -B.y);
        SumLen += std::sqrt(dx*dx+dy*dy);
        
      }
	} while (std::next_permutation(Index.begin(), Index.end()));
  	for(int i =0;i<Len;i++)
    {
      SumLen /= (i+1);
    }
  	std::cout<<std::fixed << std::setprecision(10)  << SumLen <<std::endl;
}

Measured memory_bytes: 256
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
N = int(input())
trains = [ [int(j) for j in input().split()] for _ in range(N-1)] 


for i in range(0,N):
    ans_i = 0
    for j in range(i, N-1):
        c,s,f = trains[j]
        ans_i = max(ans_i, s)
        if not ans_i % f == 0:
            ans_i += f - ans_i%f
        ans_i += c

        # ans_i += c + (f - ans_i%f)%f 
    print(ans_i)

exit(0)



Measured memory_bytes: 42220
//start of jonathanirvings' template v3.0.3 (BETA)

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

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  #ifndef TESTING
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
  #endif
}

//end of jonathanirvings' template v3.0.3 (BETA)

int ada[200005];
int n,k;
int x;

int main()
{
  scanf("%d %d",&n,&k);
  REP(i,n)
  {
    scanf("%d",&x);
    --x;
    ++ada[x];
  }
  int risan = 0;
  SORTA(ada,n);
  REVERSEA(ada,n);
  REP(i,k) risan += ada[i];
  printf("%d\n",n - risan);
  return 0;
}











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

using namespace std;

int main()
{
    long long n,a,b,ans,mod;
    cin>>n>>a>>b;
    ans=n/(a+b);
    ans*=a;
    mod=n%(a+b);
    ans+=min(mod,a);
    cout<<ans;

    return 0;
}


Measured memory_bytes: 256
def par(a):
    L = []
    while P[a] != a:
        L.append(a)
        a = P[a]
    for l in L:
        P[l] = a
    return a
def unite(a, b):
    pa = par(a)
    pb = par(b)
    if pa == pb: return
    if LEN[pa] < LEN[pb]:
        a, b, pa, pb = b, a, pb, pa
    P[pb] = pa
    if LEN[pa] == LEN[pb]: LEN[pa] += 1
    CNT[pa] += CNT[pb]
def cnt(a):
    return CNT[par(a)]

N = int(input())
P = [i for i in range(N)]
LEN = [1] * N
CNT = [1] * N
FULL = [0] * N
A = [int(a) - 1 for a in input().split()]
for i, a in enumerate(A):
    if a < 0: continue
    if par(i) != par(a):
        unite(i, a)
    else:
        FULL[i] = 1
for i in range(N):
    if FULL[i]:
        FULL[par(i)] = 1
X = []
Y = []
for i in range(N):
    if par(i) == i:
        if FULL[i] == 0:
            X.append(CNT[i])
        else:
            Y.append(CNT[i])
M = len(X)
mod = 10 ** 9 + 7
K = 96
m = int(("1" * 32 + "0" * 64) * 5050, 2)
pa = (1 << 64) - ((1 << 64) % mod)
modP = lambda x: x - ((x & m) >> 64) * pa
ans = (sum(X) + sum(Y) - len(Y)) * pow(N - 1, M, mod) % mod
x = 1
for i, a in enumerate(X):
    x *= (a << K) + 1
    x = modP(x)

sx = bin(x)[2:] + "_"
L = [int(sx[-(i+1) * K - 1:-i * K - 1], 2) % mod for i in range((len(sx)+K-2) // K)]
if M:
    fa = 1
    ans = (ans + M * pow(N - 1, M - 1, mod)) % mod
    for i, l in enumerate(L):
        if i == 0: continue
        ans = (ans - l * fa * pow(N - 1, M - i, mod)) % mod
        fa = fa * i % mod
print(ans)

Measured memory_bytes: 78752