akhauriyash/Code-Regression huggingface dataset:
local mma = math.max
local msq = math.sqrt
local n = io.read("*n")
local x, y = {}, {}
for i = 1, n do
  x[i], y[i] = io.read("*n", "*n")
end
local rep = 1000

local function getlength(tx, ty)
  local sq = 0
  for i = 1, n do
    local tmp = (tx - x[i]) * (tx - x[i]) + (ty - y[i]) * (ty - y[i])
    sq = mma(sq, tmp)
  end
  return sq
end


local function solvex(ty)
  local xmin, xmax = 0, 1000
  local v1, v2 = getlength(xmin, ty), getlength(xmax, ty)
  for i = 1, rep do
    local xmid1, xmid2 = (xmin * 2 + xmax) / 3, (xmin + xmax * 2) / 3
    local m1, m2 = getlength(xmid1, ty), getlength(xmid2, ty)
    if v1 > m1 then
      if m2 > v2 then
        xmin = xmid2
        v1 = m2
      elseif m1 > m2 then
        xmin = xmid1
        v1 = m1
      else
        xmax = xmid2
        v2 = m2
      end
    else
      if m2 < v2 then
        xmax = xmid1
        v2 = m1
      elseif m1 < m2 then
        xmin = xmid1
        v1 = m1
      else
        xmax = xmid2
        v2 = m2
      end
    end
  end
  -- print(xmin)
  return (v1 + v2) / 2
end
-- print(solvex(0.439))
-- print(solvex(0.466))
-- print(solvex(0.492))
-- print(solvex(0.519))
-- for i = 1, 1000 do
--   local yy = 0.45 + 0.10 * i / 1000
--   print(yy, solvex(yy))
-- end
-- os.exit()
local ymin, ymax = 0, 1000
local v1, v2 = solvex(ymin), solvex(ymax)
for i = 1, rep do
  local ymid1, ymid2 = (ymin * 2 + ymax) / 3, (ymin + ymax * 2) / 3
  local m1, m2 = solvex(ymid1), solvex(ymid2)
  if v1 > m1 then
    if m2 > v2 then
      ymin = ymid2
      v1 = m2
    elseif m1 > m2 then
      ymin = ymid1
      v1 = m1
    else
      ymax = ymid2
      v2 = m2
    end
  else
    if m2 < v2 then
      ymax = ymid1
      v2 = m1
    elseif m1 < m2 then
      ymin = ymid1
      v1 = m1
    else
      ymax = ymid2
      v2 = m2
    end
  end
  -- if i < 20 then print(ymin, ymax) end
  -- if i % 20 == 0 then print(ymin, ymax) end
end

local ret = msq(solvex((ymin + ymax) / 2))
print(string.format("%.10f", ret))


Measured memory_bytes: 256
#include "iostream"
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <string>
#include <cctype>
#include <stack>
#include <vector>
#include <list>
#include <queue>
using namespace std;
using ll=long long;
#define mod  1000000007

int main(int argc, char const *argv[]) {
  int a,b,c,d;
  std::cin >> a >> b >>c >>d;

  int low=max(a,c);
  int high=min(b,d);
  std::cout << max(0,high-low) << '\n';
  
  return 0;
}


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

int main() {
  int n;
  string c="APPROVED";
  cin >> n;
  vector<int>b(n);
  for(int i=0;i<n;i++){
  cin >> b.at(i);
  }  
  for(int i=0;i<n;i++){  
  if(b.at(i)%2==0){
    if(b.at(i)%3!=0 && b.at(i)%5!=0){
    c="DENIED";
    break;
    }
  }
  }
  cout << c << endl;
}  

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  int n;
  cin>>n;
  if(n<1000){
    cout<<"ABC"<<endl;
  }else{
    cout<<"ABD"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <sstream>
#include <fstream>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <map>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

#define MAX(x,y) ( (x) > (y) ? (x) : (y) )
#define MIN(x, y) ( (x) < (y) ? (x) : (y) )
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define IVFOR(p,a) for(vector<int>::iterator p = (a).begin(); p!=(a).end(); p++)
#define ILFOR(p,a) for(list<int>::iterator p = (a).begin(); p!=(a).end(); p++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define CHECK(x)  cout << #x << " = " << (x) << endl
#define FINA(y) cout << (y) << endl

int main(){

  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if(a*b > c*d)
    cout << a*b << endl;
  else
    cout << c*d << endl;
 return 0;
}

Measured memory_bytes: 256
import sys
import math

ALPHABET = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
result = []
N = int(input())
def alphabet_decimal(v):
    quotient = math.floor(v / len(ALPHABET))
    surplus = v % len(ALPHABET)
    quotient -= 1 if surplus == 0 else 0
    surplus = len(ALPHABET) if surplus == 0 else surplus
    result.append(surplus)
    if len(ALPHABET) < quotient:
        alphabet_decimal(quotient)
    elif len(ALPHABET) < v:
        result.append(quotient)
    return "".join([ALPHABET[i - 1] for i in reversed(result)])

print(alphabet_decimal(N).lower())

Measured memory_bytes: 9132
//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define fi first
#define se second
#define pii pair<int, int>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
  int n, x;
  cin >> n >> x;
  if (n == 1 && x != 1) {
    cout << "No\n";
    return 0;
  }
  if (n == 1 && x == 1) {
    cout << "Yes\n1\n";
    return 0;
  }
  if (x == 1 || x == 2 * n - 1) {
    cout << "No\n";
    return 0;
  }
  if (n == 2 && x == 2) {
    cout << "Yes\n1 2 3\n";
    return  0;
  }

  cout << "Yes\n";
  int a, b, c, d;
  if (x == 2) {
    a = x + 1, b = x, c = x - 1, d = x + 2;
  } else {
    a = x - 1, b = x, c = x + 1, d = x - 2;
  }
  set<int> st = {a, b, c, d};
  vector<int> v;
  for (int i = 1; i <= 2 * n - 1; i++) {
    if (st.find(i) == st.end()) {
      v.push_back(i);
    }
  }
  for (int i = 0; i < min(n - 2, sz(v)); i++) {
    cout << v[i] << " ";
  }
  cout << a << " " << b << " " << c << " " << d << " ";
  for (int i = n - 2; i < sz(v); i++) {
    cout << v[i] << " ";
  }
  cout << "\n";
}



Measured memory_bytes: 5344
fun main(args : Array<String>) {
    var testCaseNum = 1
    var inputNum: Int
    while (true) {
        inputNum = readLine()!!.toInt()
        if (inputNum == 0) {
            break
        } else {
            println("Case $testCaseNum: $inputNum")
        }
        testCaseNum++
    }
}



Measured memory_bytes: 33464
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define PR pair
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define REP(i, x, y)   for(int i = (int)(x); i <= (int)(y); i++)
#define FOR(i, x, y)   for(int i = (int)(x); i <  (int)(y); i++)
#define PER(i ,x, y)  for(int i = (int)(x); i >= (int)(y); i--)
#define CH	         ch = getchar()
#define Exit(...)    printf(__VA_ARGS__), exit(0)
#define dln()        fprintf(stderr,"\n")
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef double	  db;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI > VII;
typedef PR<int,int> PII;
typedef vector<PII> VPI;
const	int inf=2e9;
const	LL Inf=1e10;
const	int P=1e9+7;
const	int N=2005;

inline LL IN(){
	LL x = 0;
	int ch = 0, f = 0;
	for (CH; ch != -1 && (ch < 48 || ch > 57); CH) f = (ch == '-');
	for (; ch >= 48 && ch <= 57; CH) x = (x << 1) + (x << 3) + ch - '0';
	return f ? (-x) : x;
}
template<typename T> inline int chkmin(T &a, const T &b){if(b < a) return a = b, 1; return 0;}
template<typename T> inline int chkmax(T &a, const T &b){if(b > a) return a = b, 1; return 0;}

void renew(int &x, const int &y){
	x += y;
	if(x >= P) x -= P;
	if(x <  0) x += P;
}

int Pow(int x, int y, int p){
	int a = 1;
	for (; y; y >>= 1, x = (LL)x * x %p) if(y & 1) a=(LL)a * x%p;
	return a;
}

int n, k, S;
int fac[4000005], inv[4000005], f[4000005];
int DP[N << 1][N];

int main(){
	scanf("%d%d", &n, &k);
	if(k == 1){
		puts("1");
		return 0;
	}
	S = n * k;
	fac[0] = inv[0] = fac[1] = inv[1] = 1;
	REP(i, 1, 4000000) fac[i] = (LL)fac[i - 1] * i % P;
	REP(i, 2, 4000000) inv[i] = (LL)inv[P % i] * (P - P / i) % P;
	REP(i, 2, 4000000) inv[i] = (LL)inv[i - 1] * inv[i] % P;
	REP(i, k - 2, 4000000) f[i] = (LL)fac[i] * inv[k - 2] % P * inv[i - k + 2] % P;
	DP[0][0] = 1;
	//DP[i][j] 考虑[1..i],填了j个数字。
	FOR(i, 0, n + n){
		for(int j = 0; 2 * j < i; j ++) DP[i][j] = 0;
		REP(j, 0, n){
			int val = DP[i][j];
			if(!val) continue;
			renew(DP[i + 1][j], val);
			int cf = f[i + (j + 1) * (k - 2)];
			renew(DP[i + 1][j + 1], (LL)val * cf % P);
		}
	}
	int ans = DP[n + n][n];
	REP(i, 1, n) ans = (LL)ans * i % P;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 76544
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  cin >> N;
  vector<int> A(200009);
  vector<long long> B(N+1);
  for(int i=0;i<N;i++)cin >> A[i];
  B[0]=0;
  for(int i=1;i<=N;i++)B[i]+=B[i-1]+A[i-1];
  sort(B.begin(),B.end());
  long long ans=0; long long count=0;
  for(int i=0;i<N;i++){
    if(B[i]==B[i+1]){count++;}
    else{ans+=count*(count+1)/2; count=0;}
  }
  ans+=count*(count+1)/2;
  cout << ans << endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include<math.h>
using namespace std;
int main(void){
       double a,b,c,s,PI=3.1415926535,d,h;
       cin>>a>>b>>c;
       s=a*b*sin(c*PI/180)*0.5;
       printf("%.5lf",s);
       d=sqrt(a*a+b*b-2*a*b*cos(c*PI/180));
       cout<<endl;
       printf("%.5lf",d+a+b);
       cout<<endl;
       h=2*s/a;
       printf("%.5lf",h);
       cout<<endl;
}



Measured memory_bytes: 3476
import java.util.*;
public class Main {
    static final long MODVAL = 998244353L;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int N = sc.nextInt();
        int A[] = new int[N+2];
        for(int i=0; i<N; i++) {
            A[i+1] = sc.nextInt();
        }
        A[0] = A[N] - K;
        A[N+1] = A[1] + K;
        int result = K;
        for(int i=0; i<N+1; i++) {
            if(K-(A[i+1]-A[i]) < result) {
               result = K-(A[i+1]-A[i]);
            }
        }
        System.out.println(result);
    }
}


Measured memory_bytes: 78160
a, b, c, x, y =map(int, input().split())
ab = 2*c
i = 0
cost = 0
minCost = 10**10
while i < 10**6:
    cost = i*ab
    cost += a *(max(0, (x-i)))
    cost += b *(max(0, (y-i)))
    if minCost >= cost:
        minCost = cost
    i += 1
print(minCost)

Measured memory_bytes: 9216
import java.util.Scanner;

public class Main {

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

		String S = sc.next();
		int length = S.length();
		char c =' ';
		char d =' ';
		int cnt = 0;

		for(int i=0;i<=length/2-1;i++) {
			c = S.charAt(i);
			d = S.charAt(length-1-i);
			if(c!=d) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}

}


Measured memory_bytes: 23636
#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define MSET(x,y) memset(x,y,sizeof(x))
#define M 100005
using namespace std;
int n;
char in[M];
int main()
{ 
    while (~scanf("%s",in+1)) {
        n = strlen(in+1);

        int ans = 1000000000;
        REP(x,0,1) {
            int cnt = 0;
            REP(i,1,n) {
                cnt += (in[i]-48) ^ (i%2) ^ x;
            }
            ans = min(ans, cnt);
        }
        printf("%d\n", ans);
    }
    
    return 0;
}



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

int n;

int dfs(string s) {
    if (stoll(s) > n) return 0;
    int ret = 0;
    if (count(s.cbegin(), s.cend(), '7') > 0 &&
        count(s.cbegin(), s.cend(), '5') > 0 &&
        count(s.cbegin(), s.cend(), '3') > 0) ret++;

    ret += dfs(s+'7');
    ret += dfs(s+'5');
    ret += dfs(s+'3');
    return ret;
}

int main() {
    cin >> n;

    int ans = dfs("0");

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


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

int main(){
  int h, w;
  while(1){
    cin >> h >> w;
    if(h == 0 && w == 0) break;
    else{
      for(int i = 0;i < h;i++){
        for(int j = 0;j < w;j++){
          if(i % 2 == 0 && j % 2 == 0) cout << "#";
          else if(i % 2 == 0 && j % 2 == 1) cout << ".";
          else if(i % 2 == 1 && j % 2 == 0) cout << ".";
          else if(i % 2 == 1 && j % 2 == 1) cout << "#";
        }
        cout << "\n";
      }
      cout << "\n";
    }
  }
  return 0;
}



Measured memory_bytes: 3036
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,A,B;
string S;
string alpha = "abcdefghijklmnopqrstuvwxyz";
string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main(){
    cin>>N>>K;
    if(K%2 == 1){
        cout<<(N/K)*(N/K)*(N/K)<<endl;
    }else{
        A = (N+K/2)/K;
        B = N/K;
        cout<<A*A*A+B*B*B<<endl;
    }
}

Measured memory_bytes: 256
N,A,B = map(int,input().split())
H = []
for _ in range(N):
    h = int(input())
    H.append(h)

ok = 1000000000
ng = 0

while ok != ng+1:
    mid = (ok+ng)//2
    range_damage = mid*B
    attack_count = 0
    for value in H:
        if range_damage < value:
            if (value - range_damage)%(A-B)==0:
                attack_count += (value - range_damage)//(A-B)
            else:
                attack_count += 1+(value - range_damage)//(A-B)

    if attack_count <= mid:
        ok = mid
    else:
        ng = mid
print(ok)

Measured memory_bytes: 81596
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <functional>
#include <array>

using namespace std;

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

    for(int i = 0; i < N; ++i){
        int A; cin >> A;
    }

    cout << ((N % K == 0) ? (N / K) : (N / K + 1)) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int a,b,c,d;
 cin>>a>>b>>c>>d;
 if(a+b>c+d)
cout<<"Left";
else if(a+b<c+d)
 cout<<"Right";
else
cout<<"Balanced";
return 0;
}

Measured memory_bytes: 256
#include <cstdio>

const long long mod=1000000007ll;

int main()
{
  int n,x,y,z;
  scanf("%d%d%d%d",&n,&x,&y,&z);
  int m=x+y+z;
  static long long dp[41][1<<17]={0};
  dp[0][0]=1ll;
  for(int i=0;i<n;i++){
    for(int I=0;I<1<<m;I++){
      if(((I>>(z-1))&1)&&((I>>(y+z-1))&1)&&((I>>(x+y+z-1))&1)){
	dp[i+1][I]+=dp[i][I]*10%mod;
	dp[i+1][I]%=mod;
	continue;
      }
      for(int a=1;a<=10;a++){
	int J=((I<<a)|(1<<(a-1)))&((1<<m)-1);
	dp[i+1][J]+=dp[i][I];
	dp[i+1][J]%=mod;
      }
    }
  }
  long long A=0ll;
  for(int I=0;I<1<<m;I++){
    if(((I>>(z-1))&1)&&((I>>(y+z-1))&1)&&((I>>(x+y+z-1))&1)){
      A+=dp[n][I];
      A%=mod;
    }
  }
  printf("%lld\n",A);
  return 0;
}


Measured memory_bytes: 41088
import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer

object Main {
  val MaxNumber = 999999

  def main(args: Array[String]): Unit = {
    @tailrec
    def _eratos(_primes: ListBuffer[Int], _numbers: Array[Byte], prime: Int): Unit = {

      prime +=: _primes
      _numbers.update(prime, 1)

      var i = 0
      _numbers.foreach { delFlg =>
        if (delFlg == 0 && (i % prime == 0)) _numbers.update(i, 1)
        i += 1
      }

      if (prime < Math.sqrt(MaxNumber)) {
        val nextPrime = _numbers.indexOf(0, prime + 1)
        _eratos(_primes, _numbers, nextPrime)
      } else {
        i = 0
        _numbers.foreach { delFlg =>
          if (delFlg == 0) i +=: _primes
          i += 1
        }
      }
    }

    val numbers = Array.fill[Byte](MaxNumber + 1)(0)
    numbers.update(0, 1)
    numbers.update(1, 1)

    val primes = ListBuffer[Int]()
    _eratos(primes, numbers, 2)

    val sc = new java.util.Scanner(System.in)
    while(sc.hasNextInt) {
      val input = sc.nextInt
      println(primes.count(_ <= input))
    }
  }
}

Measured memory_bytes: 49872
import sys
sys.setrecursionlimit(10**7)

def dfs(s,idx):
    if idx==len(s):
        print("YES")
        exit()
    if idx>len(s):
        return
    if idx+5<=len(s) and s[idx:idx+5]=="dream":
        dfs(s,idx+5)
    if idx+7<=len(s) and s[idx:idx+7]=="dreamer":
        dfs(s,idx+7)
    if idx+5<=len(s) and s[idx:idx+5]=="erase":
        dfs(s,idx+5)
    if idx+6<=len(s) and s[idx:idx+6]=="eraser":
        dfs(s,idx+6)
    return
s=raw_input()
dfs(s,0)
print("NO")


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

void check()
{

}

int main()
{
    string s;
    cin >> s;
    reverse(s.begin(),s.end());

    for(int i = 0; i < s.size(); i++)
    {
        if(s.at(i) == 'm' && s.at(i+1) == 'a' && s.at(i+2) == 'e' && s.at(i+3) == 'r' && s.at(i+4) == 'd')
        {
            i += 4;
        }
        else if(s.at(i) == 'e' && s.at(i+1) == 's' && s.at(i+2) == 'a' && s.at(i+3) == 'r' && s.at(i+4) == 'e')
        {
            i += 4;
        }
        else if(s.at(i) == 'r' && s.at(i+1) == 'e' && s.at(i+2) == 's' && s.at(i+3) == 'a' && s.at(i+4) == 'r' && s.at(i+5) == 'e')
        {
            i += 5;
        }
        else if(s.at(i) == 'r' && s.at(i+1) == 'e' && s.at(i+2) == 'm' && s.at(i+3) == 'a' && s.at(i+4) == 'e' && s.at(i+5) == 'r' && s.at(i+6) == 'd')
        {
            i += 6;
        }
        else
        {
            cout << "NO" << endl;
            return 0;
        }
        
        
    }
    cout << "YES" << endl;
}

Measured memory_bytes: 512
n=int(input())
s=list(input())
q=int(input())
def segfunc(x,y):
    return x|y
def init(init_val,var):
    #set_val
    for i in range(n):
        seg[var][i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[var][i]=segfunc(seg[var][2*i+1],seg[var][2*i+2]) 
    
def update(k,x,var):
    k += num-1
    seg[var][k] = x
    while k:
        k = (k-1)//2
        seg[var][k] = segfunc(seg[var][k*2+1],seg[var][k*2+2])
    
def query(p,q,var):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[var][p])
        if q&1 == 1:
            res = segfunc(res,seg[var][q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[var][p])
    else:
        res = segfunc(segfunc(res,seg[var][p]),seg[var][q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[[ide_ele]*2*num for i in range(26)]
for i in range(n):
    update(i,1,ord(s[i])-97)
for i in range(q):
    a,b,c=input().split()
    if a=="1":
        update(int(b)-1,0,ord(s[int(b)-1])-97)
        s[int(b)-1]=c
        update(int(b)-1,1,ord(c)-97)
    else:
        ans=0
        for j in range(26):
            ans+=query(int(b)-1,int(c),j)
        print(ans)

Measured memory_bytes: 281768
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int a, b, c;
    cin >> a >> b >> c;
    int k;
    cin >> k;

    while(a >= b) {
        b *= 2;
        --k;
    }
    while(b >= c) {
        c *= 2;
        --k;
    }

    cout << ((k>=0) ? "Yes" : "No") << endl;
}


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

typedef long long ll;
#define pb push_back
#define mp make_pair
#define pii pair <int,int>
#define in insert
#define X first
#define Y second
#define frn front
#define bc back
#define rep(i,a,b)for (ll (i) = (a); (i) < b(); ++(i))
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()

using namespace std;

const int N = 1e5 + 2;
const double PI = 3.14;
const int MOD = 1e7 + 7;

ll x,t;

int main ()	{
	cin >>x>>t;
	if (x-t > 0)cout<<x-t;
	else cout <<0;
	cout <<endl;
	return 0;
}


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

vector< vector< pair<int, long long > > > g;
vector<long long> dist;

void dfs(int u, int par) {
  for (auto& v : g[u]) {
    if (v.first != par) {
      dist[v.first] = dist[u] + v.second;
      dfs(v.first, u);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  g.resize(n + 1);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    long long w;
    cin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  dist.assign(n + 1, 0);
  dfs(1, -1);
  for (int i = 1; i <= n; i++) {
    cout << dist[i] % 2 << '\n';
  }
  return 0;
}

Measured memory_bytes: 9984
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=1e9+7;
//const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
std::vector<int> Factorial(1234567);
void Cinit(){
  Factorial[0]=1;
  for(int i=1;i<1234567;i++)Factorial[i]=Factorial[i-1]*i%MOD;
}
//main
signed main(){
  Cinit();
  int N,H,D;cin>>N>>H>>D;
  std::vector<int> wa(1234567);//階乗の累積和
  wa[0]=0;for(int i=1;i<1234567;i++)wa[i]=(wa[i-1]+Factorial[i])%MOD;
  int sum=0;
  queue<int> que;
  for(int i=0;i<=H;i++){
    if(i==0){
      sum+=Factorial[N];
      que.push(sum);
      continue;
    }
    if(que.size()>D){
      int p=que.front();que.pop();
      sum-=p;
      if(sum<0)sum+=MOD;
    }
    if(i==H)cout<<sum<<endl;
    que.push(sum*wa[N]%MOD);
    sum+=sum*wa[N]%MOD;sum%=MOD;
  }
}


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

using namespace std;
using ll = long long;
using ull = unsigned long long;

typedef pair< long long, long long > P;
typedef pair< long long, P > PP;
typedef pair< P, P > PPP;

const long long MOD = 1e9 + 7;
const long long  INF = 5e18;
const double DINF = 5e14;
const double eps = 1e-10;
const int di[4] = { 1,0,-1,0 }, dj[4] = { 0,1,0,-1 };

#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define ALL(x) (x).begin(),(x).end()

struct Union_Find_Tree {
private:
	vector< int >par;
	vector< int >Rank;
	int N;
public:
	void init(int n) {
		N = n;
		par.resize(N + 1);
		Rank.resize(N + 1);
		for (int i = 0;i <= N;i++)par[i] = i, Rank[i] = 0;
	}
	int find(int x) {
		if (par[x] == x)return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)return;
		if (Rank[x] < Rank[y])par[x] = y;
		else {
			par[y] = x;
			if (Rank[x] == Rank[y])Rank[x]++;
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};



int n, m, a[200010], b[200010], acnt[200010], bcnt[200010];
string s;
vector<P>ab;
vector<int>v[200010];
bool fl[200010];
map<int, int>mp;

void dfs(int x) {
	if (fl[x])return;
	if (acnt[x]==0&&bcnt[x]==0) {
		fl[x] = 1;
		return;
	}
	else if (acnt[x] == 0) {
		fl[x] = 1;
		for (auto u : v[x]) {
			if (s[x] == 'A')acnt[u]--;
			else bcnt[u]--;
			dfs(u);
		}
	}
	else if (bcnt[x] == 0) {
		fl[x] = 1;
		for (auto u : v[x]) {
			if (s[x] == 'A')acnt[u]--;
			else bcnt[u]--;
			dfs(u);
		}
	}
	return;
}

int main() {
	cin >> n >> m >> s;
	for (int i = 0;i < m;i++) {
		cin >> a[i] >> b[i];
		a[i]--, b[i]--;
		v[a[i]].eb(b[i]);
		v[b[i]].eb(a[i]);
		ab.eb(P(a[i], b[i]));
		if (s[a[i]] == 'A')acnt[b[i]]++;
		else bcnt[b[i]]++;
		if (a[i] == b[i])continue;
		if (s[b[i]] == 'A')acnt[a[i]]++;
		else bcnt[a[i]]++;
	}
	for (int i = 0;i < n;i++) {
		dfs(i);
	}
	Union_Find_Tree uf;
	uf.init(n);
	for (int i = 0;i < m;i++) {
		if (fl[a[i]] || fl[b[i]]) {
			continue;
		}
		uf.unite(a[i], b[i]);
	}
	for (int i = 0;i < n;i++) {
		mp[uf.find(i)]++;
	}
	for (auto u : mp) {
		if (u.sc > 1) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}



Measured memory_bytes: 28912
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace C_gacha
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string[] Thg = new string[N];



            for (int i = 0; i < N; i++)
            {
                Thg[i] = Console.ReadLine();
            }

            string[] A = Thg.Distinct().ToArray();
            Console.WriteLine(A.Length);
            Console.Read();
        }
    }
}


Measured memory_bytes: 49708
#include <iostream>
using namespace std;
int main(void){
    // Here your code !
    int a[100] = {0}, ccc = 0;
    string b;
    cin >> b;
    for(int i = 0; i < b.size(); i++)
        a[b[i]-'a'] += 1;
    for(int i = 0; i < 30; i++)
        if(a[i] >= 2) ccc = 1;
        
    if (ccc == 1)
        cout << "no\n";
    else
        cout << "yes\n";
    
    return 0;
}


Measured memory_bytes: 256
divisors m = [ x | x <- [1..m], m `mod` x == 0 ] 
g x y = y - x

ans l =
  let m = maximum l
      y = divisors m
      d = map (\x -> g x $ head $ dropWhile (< x) y ) l
  in
    sum d

main = do
  _ <- getLine
  c <- getContents
  let i = map read $ lines c :: [Int]
      o = ans i
  print o
  

Measured memory_bytes: 51200
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define SORT(c) sort((c).begin(),(c).end())
#define ANS(ans) cout<<(ans)<<endl;
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
typedef vector<int> VI;


//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  for (int i = 0; i < (n); ++i)



int main() {
	int x, y;
	cin >> x >> y;
	ANS(x + y / 2);

	return 0;
}



Measured memory_bytes: 256
import java.util.*;
/**
 * Main
 */
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		Long N = sc.nextLong();
		Long min = N+1;
		for(int i=1; i<=Math.sqrt(N); i++){
				if(N%i==0){
					if((i+N/i)<=min){
						min = i+(N/i);
					}
				}
		}
		System.out.println(min-2);
		sc.close();
	}
};

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

t = 0
f = False

while True :
    for i in range(n):
        if a[i] % 2 == 0 :
            a[i] //= 2
        else :
            f = True
            break

    if f == True :
        print(t)
        break
    else :
        t += 1

Measured memory_bytes: 3060
/*****************************************************

*****************************************************/

#include<bits/stdc++.h>
#define MAX 9223372036854775807
#define endl "\n"
#define ll long long
#define int long long
#define pb push_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define ip pair<int, int>

#define loop(i,n) for(int i=0;i<n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;

const ll MOD = 1e9+7;
const ll SZ = 107;
const ll N = 2e5+7;
const ll inf = 1e17;

int pwr(int x, int y)
{
    ll r = 1LL;
    while(y)
    {
        if(y&1)
            r = (r * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return r % MOD;
}

int inv(int x)
{
    return pow(x, MOD-2);
}
vector<int> adj[N];
bool vis[N];
int c[N], d[N], score, idx;

void dfs(int v)
{
    vis[v] = 1;
    for(auto i: adj[v])
    {
        if(!vis[i])
        {
            score += min(d[i], d[v]);
            dfs(i);
        }
    }
}


void solve()
{
    int n; cin>>n;
    map<int, int> cnt;
    for(int i=0;i<n-1;i++)
    {
        int x, y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
        cnt[x]++;
        cnt[y]++;
    }
    vector<ip> v;
    for(int i=1;i<=n;i++){
        cin>>c[i];
        // v.pb({adj[i].size(), c[i]});
    }

    sort(c+1, c+1+n);
    reverse(c+1, c+1+n);
    
    memset(d, -1, sizeof(d));
    memset(vis, 0, sizeof(vis));
    idx = 1;
    
    queue<int> q;
    q.push(1);
    d[1] = c[idx++];
    vis[1] = 1;
    while(!q.empty())
    {
        int v = q.front();
        q.pop();
        for(auto i: adj[v])
        {
            if(!vis[i])
            {
                vis[i] = 1;
                q.push(i);
                d[i] = c[idx++];
            }
        }
    }
    
    score = 0;
    memset(vis, 0, sizeof(vis));
    dfs(1);
    cout<<score<<endl;
    for(int i=1;i<=n;i++)
        cout<<d[i]<<" ";

}

signed main()
{
    fast;

    int t=1;
    // cin >>t;
    while(t--){
        solve();
    }
    return 0;
}

/*****************************


****************************/

Measured memory_bytes: 9216
#include <stdio.h>
#include <string>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int main(void){
    string s,ans="";cin >> s;
    for(int i=0; i<s.size(); i++){
        if(ans!=""){
            if(s[i]=='B')ans.pop_back();
        }
        if(s[i]!='B')ans.push_back(s[i]);
    }
    cout << ans << endl;
}

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

int main() {
  int n,m,l;
  cin >> n >> m >> l;
  
  vector<vector<long long> > data(n, vector<long long>(l,0));
  vector<vector<int> > data1(n, vector<int>(m,0));
  vector<vector<int> > data2(m, vector<int>(l,0));
  

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> data1.at(i).at(j);
    }
  }
  
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < l; j++) {
      cin >> data2.at(i).at(j);
    }
  }
  
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < l; j++) {
      for (int k = 0; k < m; k++) {
        data.at(i).at(j) += data1.at(i).at(k) * data2.at(k).at(j);
      }
    }
  }
  
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < l; j++) {
      cout << data.at(i).at(j);
      if (j < l - 1) {
        cout << ' ';
      }
      else if (j == l - 1) {
        cout << endl;
      }
    }
  }
}
  
  
  


Measured memory_bytes: 3268
import java.util.*;
import java.io.*;

public class Main {	

	private static void solve(){
		//Implement solution here.
		int N = ni();
		int mod = N % 1000;
		if(mod == 0) {
			System.out.println(0);
		} else {
			System.out.println(1000 - mod);
		}
		
	}

	//Switch input source (stdin/file)
	private static BufferedReader br;
	public static void main(String[] args){
		br = new BufferedReader(new InputStreamReader(System.in));
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		}
		boolean hasNext = true;
		while(hasNext){
			solve();	
			try{
				br.mark(1);
				if(br.read() > 0){
					br.reset();			
					System.out.println("---");
				} else {
					hasNext = false;
				}
			}catch(Exception e){
				throw new RuntimeException(e);
			} 
		}
	}

	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}


Measured memory_bytes: 25388
#include<bits/stdc++.h>
#define N 200010
using namespace std;
int n;
int a[N]={};
struct node{
  int l,r,u,v;
  friend bool operator <(const node x,const node y){return a[x.u]>a[y.u];}
};
struct rode{
  int l,r;
  int x;
}t[N<<2][2]={};
priority_queue<node>q;
inline int read()
{
	int s = 0, w = 1;
	char c = getchar();
	while ((c<'0' || c>'9') && c != '0')c = getchar();
	if (c == '-')w = -1, c = getchar();
	while (c <= '9'&&c >= '0')s = (s << 3) + (s << 1) + c - '0', c = getchar();
	return s * w;
}
inline void push(int p)
{
  for(int i=0;i<=1;++i)
    if(a[t[p<<1][i].x]<a[t[p<<1|1][i].x])
      t[p][i].x=t[p<<1][i].x;
    else t[p][i].x=t[p<<1|1][i].x;
}
void build(int p,int l,int r)
{
  if(l==r){t[p][l%2].x=l;return ;}
  int mid=(l+r)>>1;
  build(p<<1,l,mid);build(p<<1|1,mid+1,r);
  push(p);
}
inline int ask(int p,int l,int r,int tl,int tr,int c)
{
  if(tl==l&&r==tr)return t[p][c].x;
  int mid=(l+r)>>1;
  if(tr<=mid)return ask(p<<1,l,mid,tl,tr,c);
  else if(tl>mid)return ask(p<<1|1,mid+1,r,tl,tr,c);
  else{
    int k=ask(p<<1,l,mid,tl,mid,c),kk=ask(p<<1|1,mid+1,r,mid+1,tr,c);
    if(a[k]<a[kk])return k;else return kk;
  }
}
inline void ins(int l,int r)
{
  int c=ask(1,1,n,l,r,l%2);
  int d=ask(1,1,n,c+1,r,r%2);
  node t;
  t.l=l;t.r=r;t.u=c;t.v=d;
  q.push(t);
}
int ans[N]={},cnt=0;
int main()
{
  n=read();a[0]=0x3f3f3f3f;
  for(int i=1;i<=n;++i)a[i]=read();
  build(1,1,n);
  ins(1,n);
  while(!q.empty())
  {
    node t=q.top();q.pop();
    ans[++cnt]=a[t.u];ans[++cnt]=a[t.v];
    if(t.u!=t.l)ins(t.l,t.u-1);
    if(t.u+1!=t.v)ins(t.u+1,t.v-1);
    if(t.v!=t.r)ins(t.v+1,t.r);
  }
  // printf("%d\n",cnt);
  for(int i=1;i<=cnt;++i)printf("%d ",ans[i]);
  return 0;
}


Measured memory_bytes: 17396
#最大公約数を求めるアルゴリズム

A, B = map(int, input().split())

if A >= B:
    while True:
        if A % B == 0:
            print(B)
            break
        A, B = B, A % B
else:
    while True:
        if B % A == 0:
            print(A)
            break
        B, A = A, B % A


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

int main() {
  int N=0;
  int Y=0;
  string S;
  cin >> N;
  for(int i=0;i<N;i++){
  	cin >>S;
    if(S=="Y"){
      Y=1;
      break;
    }
  }
  if(Y==1){
  	cout<<"Four"<<endl;
  }
  else{
  	cout<<"Three"<<endl;
  }
}

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

int n, m;
bool G[51][51], used[50];

void DFS(int now){
    if(used[now]) return;   //無限ループ防止（そのためのused）
    used[now] = true;    //今来た！
    REP(i, n){   //今いるところ以外をいけるかどうかチェック！
        if(i == now) continue;
        if(G[now][i]) DFS(i);    //いけるならいっちゃえ！
    }
}

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

    cin >> n >> m;
    vector<pair<int, int>> A(m);
    REP(i, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a][b] = true;
        G[b][a] = true;
        A[i] = make_pair(a, b);
    }

    int ans = 0;
    for(auto x : A){
        int a, b;
        a = x.first;
        b = x.second;
        G[a][b] = false;
        G[b][a] = false;

        REP(i, n) used[i] = false;
        DFS(0);
        int cnt = count(used, used + n, true);
        ans += cnt != n;
        
        G[a][b] = true;
        G[b][a] = true;
    }
    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<long> A;
  vector<long> B;
  for (int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;
    A.push_back(a);
    B.push_back(b);
  }

  long result = 0;
  for (int i = N - 1; i >= 0; i--) {
    int amari = (A[i] + result) % B[i];
    int plusnum = amari == 0 ? 0 : B[i] - amari;
    result += plusnum;
  }
  cout << result;
  return 0;
}


Measured memory_bytes: 2036
import sys
input = sys.stdin.readline
INF = 10**20
MOD = 10**9 + 7
sys.setrecursionlimit(100000000)
from bisect import bisect_right

def main():
    n,w = map(int,input().split())
    minw,u = map(int,input().split())
    item = {minw:[u],minw + 1:[],minw + 2:[], minw + 3:[]}
    for _ in range(n - 1):
        wei,u = map(int,input().split())
        item[wei].append(u)
    
    l = [0] * 4
    keys = sorted(item.keys())
    i = 0
    for k in keys:
        item[k].sort(reverse = True)
        l[i] = len(item[k])
        i += 1
    
    X = set()
    for i in range(l[0] + 1):
        if i == 0:
            cumsum = 0
        else:
            cumsum += item[minw][i - 1]
        cumsumx = cumsum
        for j in range(l[1] + 1):
            weight = minw * i + (minw + 1) * j 
            if j != 0:
                cumsumx += item[minw + 1][j - 1]
            if weight <= w:
                X.add((weight, cumsumx))

    Y = []
    for i in range(l[2] + 1):
        if i == 0:
            cumsum = 0
        else:
            cumsum += item[minw + 2][i - 1]
        cumsumy = cumsum
        for j in range(l[3] + 1):
            weight = (minw + 2) * i + (minw + 3) * j
            if j != 0:
                cumsumy += item[minw  + 3][j - 1]
            if weight <= w:
                Y.append((weight, cumsumy))
    
    Y.sort(key = lambda x:x[0])
    Yw = [0] * len(Y)
    cummax = [0] * len(Y)
    for i in range(len(Y)):
        if i == 0:
            cummax[i] = Y[i][1]
            Yw[i] = Y[i][0]
        else:
            cummax[i] = max(cummax[i - 1],Y[i][1])
            Yw[i] = Y[i][0]
    
    ans = 0
    for x in X:
        wei,va = x
        idx = bisect_right(Yw,w - wei)
        if idx == 0:
            continue
        else:
            ans = max(ans,cummax[idx - 1] + va)
    
    print(ans)
    
    
if __name__=='__main__':
    main() 

Measured memory_bytes: 3192
#include <algorithm>
#include <array>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

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

constexpr double EPS = 1e-7;
constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
#define PI (acos(-1))

constexpr int MOD = 1e9 + 7;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}

	// union
	bool unionSet(int x, int y) {
		x = root(x);
		y = root(y);
		if (x != y) {
			if (data[y] < data[x]) {
				swap(x, y);
			}
			data[x] += data[y];
			data[y] = x;
		}
		return x != y;
	}

	// find
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}

	// root
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}

	// size
	int size(int x) {
		return -data[root(x)];
	}
};

int main(int argc, char const *argv[]) {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);

	int N;
	cin >> N;

	vector<pint> x(N), y(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i].first >> y[i].first;
		x[i].second = y[i].second = i;
	}

	sort(x.begin(), x.end());
	sort(y.begin(), y.end());

	auto c = [](auto &lhs, auto &rhs) {
		return get<2>(lhs) > get<2>(rhs);
	};
	priority_queue<tuple<int, int, int>,
				   vector<tuple<int, int, int>>,
				   decltype(c)>
		q(c);

	for (int i = 0; i < N - 1; i++) {
		q.push(make_tuple(x[i].second, x[i + 1].second, abs(x[i].first - x[i + 1].first)));
		q.push(make_tuple(y[i].second, y[i + 1].second, abs(y[i].first - y[i + 1].first)));
	}

	UnionFind uf(N);
	ll ans = 0;
	while (uf.size(0) < N) {
		auto e = q.top();
		q.pop();

		if (!uf.findSet(get<0>(e), get<1>(e))) {
			uf.unionSet(get<0>(e), get<1>(e));
			ans += get<2>(e);
		}
	}

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


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

int main(){
    int n,m;cin>>n>>m;
    vector<set<int>> popu(n);
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        popu[a].insert(b);
        popu[b].insert(a);
    }

    vector<int> dist(n);
    int Max=0;
    for(int i=0;i<n;i++){
        if(dist[i]!=0) continue;

        queue<int> que;
        dist[i]=1;
        que.push(i);
        int sum = 1;

        while(!que.empty()){
            int p=que.front();
            que.pop();

            for(auto np:popu[p]){
                if(dist[np]!=0)continue;
                dist[np]=1;
                sum+=1;
                que.push(np);
            }
        }
        Max=max(sum,Max);
    }
    cout << Max;   
}

Measured memory_bytes: 32464
#include<bits/stdc++.h>
 
using namespace std;
using S = set<long long>;
using D = deque<long long>;
using L = vector<long long>;
using M = map<int,long long>;
using A = vector<vector<long long>>;
using Q = priority_queue<long long>;

#define sorted(vector) sort(vector.begin(),vector.end())
#define vmin(vector) *min_element(vector.begin(),vector.end())
#define vmax(vector) *max_element(vector.begin(),vector.end())
#define vsum(vector) accumulate(vector.begin(),vector.end(),0)
#define vfind(vector,a) find(vector.begin(), vector.end(), a) != vector.end() //遅いからあんまり使うな
#define bisect_left(vector,a) (lower_bound(vector.begin(),vector.end(),a)-vector.begin())
#define bisect_right(vector,a) (upper_bound(vector.begin(),vector.end(),a)-vector.begin())

//__gcd(a,b)はコンパイラがGCC時のみ

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    long long n;
    cin>>n;
    vector<double> l(n,0);
    for(int i=0  ;i<n  ;i++){
        cin>>l[i];
    }
    sorted(l);
    for(int i=0  ;i<n-1  ;i++){
        l[i+1]=(l[i]+l[i+1])/2.0;
    }
    cout<<l[n-1]<<endl;
}

Measured memory_bytes: 256
#include <cstdio>

long int fun2(long int n){
    long int b=4;
    for(;;){
        if(2*b>n)break;
        b*=2;
    }
    return b;
}

long int fun(long int n){
    if(n==0)return 0;
    if(n==1)return 1;
    if(n==2)return 3;
    if(n==3)return 0;
    long int b = fun2(n);
    return b*((n-b+1)%2)+fun(n-b);
}

int main(){
    long int a,b;
    scanf("%ld %ld",&a,&b);
    if(a>b){printf("error\n");return 1;}
    if(a==0){a=1;}
    printf("%ld\n",fun(a-1)^fun(b));
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<cmath>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60; 
#define MOD 1000000007

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

/**
* @fn
* 最大値を取ります.Vector<int>を渡すこと.
*/
long long int imax(vector<int> a) {
	int MAX = -10000000;
	for (int i = 0; i < a.size(); i++) {
		if (MAX < a.at(i)) MAX = a.at(i);
	}
	return MAX;
}

/**
* @fn
* 最小値を取ります.Vector<int>を渡すこと.
*/
long long int imin(vector<int> a) {
	int MIN = 1000000000;
	for (int i = 0; i < a.size(); i++) {
		if (MIN > a.at(i)) MIN = a.at(i);
	}
	return MIN;
}


long long int absmin(vector<int> a, long long int b) {
	int mini = 100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (mini > abs(a.at(i) - b)) {
			mini = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}

//ここまでライブラリ
//ここから本文

long long int tpimin(vector<int> a) {
	int MIN = 1000000000;
	int number = 0;
	for (int i = 0; i < a.size(); i++) {
		if (MIN > a.at(i)) MIN = a.at(i);
		number = i;
	}
	return number;
}


int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a.at(i);
	}
	sort(a.begin(), a.end());
	cout << a.at(a.size() - 1) - a.at(0) << endl;
}



Measured memory_bytes: 256
// Vicfred
// https://atcoder.jp/contests/abc163/tasks/abc163_d
// math
import std.stdio;

long ways(long k, long n) {
    long minima = k*(k-1)/2;
    long maxima = minima + k*(n-k+1);
    return maxima - minima + 1;
}

void main() {
    long n, k;
    readf("%s %s\n", &n, &k);

    long mod = 10^^9+7;

    long answer = 0;
    for(long i = k; i <= n+1; i++)
        answer = (answer+ways(i, n))%mod;

    answer %= mod;

    answer.writeln;
}



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

const int MOD = 1000000007;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main()
{
    int n;
    cin>>n;
    int x = n%10;
    if(x==2||x==4 ||x==5|| x==7|| x==9)
    {
        cout<<"hon"<<endl;
    }
    else if(x==0||x==1||x==6||x==8)
    {
        cout<<"pon"<<endl;
    }
    else
    {
        cout<<"bon"<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 3636
from collections import deque

s = input()
a = deque()
for i in s:
  a.append(i)
q = int(input())
rev = 0     # 反転をフラグで持って、実際には反転させない
for i in range(q):
  s = input()
  if s[0] == '1':
    rev ^= 1
  else:
    b = (int(s[2]) - 1) ^ rev
    if b:
      a.append(s[4])
    else:
      a.appendleft(s[4])
if rev:
  a.reverse()
for i in a:
  print(i, end="")

Measured memory_bytes: 7536
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <ctime>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
#include <set>
#include <list>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <bitset>
#include <array>
#include <stdlib.h>
#include <thread>
#include <chrono>
#include <map>
#include <set>
#include <stdio.h>
#include <math.h>
#include <fenv.h>
using namespace std;

int n;


int main()
{
    string s;
    cin>>s;
    for(auto c:s)
    {
        if(c=='g')
            ++n;
        else
            --n;
    }
    if(n<=0)
        cout << "0" << endl;
    else
        cout << n/2 << endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

ll a,b,c,k;

int main()
{
    scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
    ll ans;
    if (k%2==0) ans=a-b;
    else ans=b-a;
    printf("%lld\n",ans);
}

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

using namespace std;


int main() {
    int N; cin >> N;
    vector<int> A(N), B(N), C(N-1);

    for(auto& a : A){
        cin >> a;
        a--;
    }
    for(auto& b : B) cin >> b;
    for(auto& c : C) cin >> c;

    int ans = B[A[0]];
    for(int i=1;i<N;i++) {
        ans += B[A[i]];
        if(A[i] == A[i-1]+1) ans += C[A[i-1]];
    }

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


Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int n, p[31] = {}, i, res;
  p[0] = 1;
  p[1] = 1;
  p[2] = 2;


  while(scanf("%d", &n) && n){
    for(i = 3; i <= n; i++) p[i] = p[i - 1] + p[i - 2] + p[i - 3];
    res = p[n] / 10 / 365 + 1;
    printf("%d\n", res);
  }
  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define INF 1000000000
#define MOD 1000000007

void solve() {
    int n, k;
    cin >> n >> k;
    vi a(n);
    rep(i,0,n) {
        cin >> a[i];
    }
    sort(all(a));
    int ans = 0;
    rep(i,0,k) {
        ans += a[i];
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}


Measured memory_bytes: 3648