akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Wed Jun 17 20:23:33 JST 2020
 **/

template <class T, class S> T make_vec(S x) { return x; }
template <class T, class... Ts> auto make_vec(size_t n, Ts... ts) {
    return std::vector<decltype(make_vec<T>(ts...))>(n, make_vec<T>(ts...));
}

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

const Int W_MAX = 1e5 + 1;
const Int half = 9;
using pii = std::pair<Int, Int>;
signed main() {
    Int n;
    std::cin >> n;
    std::vector<Int> V(n + 1), W(n + 1);
    REP(i, 1, n + 1) std::cin >> V[i] >> W[i];
    auto dp = make_vec<Int>(1LL << half, W_MAX, 0);
    REP(i, 1, std::min(1LL << half, n + 1)) {
        REP(j, W_MAX) {
            dp[i][j] = dp[i / 2][j];
            if (j) chmax(dp[i][j], dp[i][j - 1]);
            if (j - W[i] >= 0) chmax(dp[i][j], dp[i / 2][j - W[i]] + V[i]);
        }
    }
    Int Q;
    std::cin >> Q;
    REP(q, Q) {
        Int v, L;
        std::cin >> v >> L;
        std::vector<pii> cans({{0, 0}});  // {value, weight}
        while (v >= 1LL << half) {
            std::vector<pii> nxt;
            for (auto& p : cans) {
                nxt.push_back(p);
                nxt.push_back({p.first + V[v], p.second + W[v]});
            }
            std::swap(cans, nxt);
            v /= 2;
        }
        Int ma = -1;
        for (auto& p : cans) {
            if (L - p.second >= 0) chmax(ma, p.first + dp[v][L - p.second]);
        }
        std::cout << ma << "\n";
    }
}


Measured memory_bytes: 409420
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

int divs[1000010];

int main() {
    int N; scanf("%d", &N);
    for(int i=1; i<=N; i++) {
        for(int j=1; i*j<=N; j++) {
            divs[i*j]++;
        }
    }

    ll ans = 0;
    for(int C=1; C<N; C++) {
        ans += divs[N-C];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 7544
#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
 
typedef pair<int,int> PI;
typedef pair<int,pair<int,int>> PII;
static const int INF=1010000000000000017LL;
static const double eps=1e-12;
static const double pi=3.14159265358979323846;
static const int dx[4]={1,-1,0,0};
static const int dy[4]={0,0,1,-1};
static const int ddx[8]={1,-1,0,0,1,1,-1,-1};
static const int ddy[8]={0,0,1,-1,1,-1,1,-1};
 
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;}

const int MAX_N=500;
const int MAX_A=100000;

int N,K;
int A[MAX_N+5];

int sum;
int ans;

vector<int> divisor(int n) {
    vector<int> res;
    for (int i=1;i*i<=n;i++) {
        res.push_back(i);
        if(n%i==0)res.push_back(n/i);
    }
    sort(res.begin(),res.end());
    return res;
}

bool check(int m){
    vector<int> d;
    for(int i=0;i<N;++i)d.push_back(A[i]%m);
    sort(d.begin(),d.end());
    int l=0,r=N-1;
    int cnt=0;
    //cout<<"m = "<<m<<endl;
    while(true){
        //cout<<"cnt = "<<cnt<<endl;
        //cout<<"l = "<<d[l]<<", r = "<<d[r]<<endl;
        if(r==l){
            //cout<<d[l]<<endl;
            if(d[l]%m==0)return true;
            else return false;
        }
        if(cnt>K)return false;
        if(d[l]%m==0)l++;
        else if(d[r]%m==0)r--;
        else {
            int cost=min(d[l],m-d[r]);
            //cout<<"cost = "<<cost<<endl;
            cnt+=cost;
            d[l]-=cost;
            d[r]+=cost;
        }
    }
}

signed main(){
    cin>>N>>K;
    for(int i=0;i<N;++i){
        cin>>A[i];
        sum+=A[i];
    }
    for(auto m:divisor(sum)){
        if(check(m))ans=m;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3692
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>

using namespace std;

#define INF 1 << 29
#define LL long long int

LL const MOD = 1000000007;

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

    LL n,m;
    cin >> n >> m;

    vector<LL> x(n),y(n),z(n);

    for(int i = 0; i < n; i++){
        cin >> x[i] >> y[i] >> z[i];
    }

    vector<LL> tmp(n);
    LL result = 0;
    LL tmpresult;
    LL j;

    for(int i = 0; i < n; i++){
        tmp[i] = x[i] + y[i] + z[i];
    }

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

    tmpresult = 0;
    j = 0;
    for(int i = n-1;j < m ; i--){
        tmpresult += tmp[i];
        j++;
    }

    if(tmpresult > result){
        result = tmpresult;
    }

    for(int i = 0; i < n; i++){
        tmp[i] = x[i] + y[i] - z[i];
    }

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

    tmpresult = 0;
    j = 0;
    for(int i = n-1;j < m ; i--){
        tmpresult += tmp[i];
        j++;
    }

    if(tmpresult > result){
        result = tmpresult;
    }

    for(int i = 0; i < n; i++){
        tmp[i] = x[i] - y[i] + z[i];
    }

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

    tmpresult = 0;
    j = 0;
    for(int i = n-1;j < m ; i--){
        tmpresult += tmp[i];
        j++;
    }

    if(tmpresult > result){
        result = tmpresult;
    }

        for(int i = 0; i < n; i++){
        tmp[i] = x[i] - y[i] - z[i];
    }

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

    tmpresult = 0;
    j = 0;
    for(int i = n-1;j < m ; i--){
        tmpresult += tmp[i];
        j++;
    }

    if(tmpresult > result){
        result = tmpresult;
    }

        for(int i = 0; i < n; i++){
        tmp[i] = (-1)*x[i] + y[i] + z[i];
    }

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

    tmpresult = 0;
    j = 0;
    for(int i = n-1;j < m ; i--){
        tmpresult += tmp[i];
        j++;
    }

    if(tmpresult > result){
        result = tmpresult;
    }

    for(int i = 0; i < n; i++){
        tmp[i] = (-1)*x[i] + y[i] - z[i];
    }

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

    tmpresult = 0;
    j = 0;
    for(int i = n-1;j < m ; i--){
        tmpresult += tmp[i];
        j++;
    }

    if(tmpresult > result){
        result = tmpresult;
    }

            for(int i = 0; i < n; i++){
        tmp[i] = (-1)*x[i] - y[i] + z[i];
    }

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

    tmpresult = 0;
    j = 0;
    for(int i = n-1;j < m ; i--){
        tmpresult += tmp[i];
        j++;
    }

    if(tmpresult > result){
        result = tmpresult;
    }

    for(int i = 0; i < n; i++){
        tmp[i] = (-1)*x[i] - y[i] - z[i];
    }

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

    tmpresult = 0;
    j = 0;
    for(int i = n-1;j < m ; i--){
        tmpresult += tmp[i];
        j++;
    }

    if(tmpresult > result){
        result = tmpresult;
    }

    cout << result << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int gcdf(int a, int b) {
  if (b == 0) {
    return a;
  } else {
    return gcdf(b, a%b);
  }
}

int main() {
  int a, b, gcd;

  cin >> a;
  cin >> b;

  gcd = gcdf(a, b);
  cout << gcd << endl;

  return 0;
}

Measured memory_bytes: 3096
package main

import (
	"fmt"
	"strings"
)

func main() {
	for {
		var h, w int

		fmt.Scan(&h, &w)
		if h == 0 && w == 0 {
			break
		}

		ht := strings.Repeat("#", w) + "\n"
		md := "#" + strings.Repeat(".", w-2) + "#\n"
		fmt.Println(ht + strings.Repeat(md, h-2) + ht)
	}
}



Measured memory_bytes: 1376
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let n: i64 = input();
    let k: i64 = input();

    let mut ans: f64 = 0.0;
    if n >= k {
        ans += (n - k + 1) as f64 / n as f64;
        for i in 1..k {
            let mut temp = i;
            let mut cnt = 0;
            while temp < k {
                cnt += 1;
                temp *= 2;
            }
            ans += 1 as f64 / n as f64 / (1 << cnt) as f64;
        }
    } else {
        for i in 1..n + 1 {
            let mut temp = i;
            let mut cnt = 0;
            while temp < k {
                cnt += 1;
                temp *= 2;
            }
            ans += 1 as f64 / n as f64 / (1 << cnt) as f64;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
using namespace std;


int main() {
	//cout << fixed << setprecision(10);
	long long int n, m, a, b, c, d, x, h[30], w, cou = 1,Max=0;
	cin >>n ;
	cin >> h[1];
	Max = h[1];
	for (int i = 2; i <= n; i++) {
		cin >> h[i];
		if (Max <= h[i]) { Max = h[i]; cou++; }
	}
	cout << cou;
	
}



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

#define ll long long
using namespace std;

int main() {
    int n,m;
    cin >> n >> m;
    char a[n+1][n+1];
    char b[m+1][m+1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            cin >> b[i][j];
    if (n == 1 && m == 1)
    {
        if (b[1][1] == a[1][1]) cout << "Yes" << endl;
        else cout << "No" << endl;
        return 0;
    }
    int answ = 0;
    for (int i = 1; i <= n-m; i++)
    {
        for (int j = 1; j <= n-m; j++)
        {
            int local = 1;
            for (int k = 1; k <= m; k++)
                for (int u = 1; u <= m; u++)
                    if (a[i+k][j+u] != b[k][u]) local = 0;
            answ = max(answ,local);
        }
    }
    if (answ == 1) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <set>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <map>
#include <cassert>
#define _USE_MATH_DEFINES
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 1 << 30;
const double EPS = 1e-9;

double dp[200][200];
bool L[101];
bool B[101];

int main(){
	int T, N, l, b;
	while(cin >> N >> T >> l >> b && (T || N || l || b)){
		fill(L, L + 101, false);
		fill(B, B + 101, false);
		int p;
		for(int i = 0; i < l; i++){
			cin >> p;
			L[p] = true;
		}
		for(int i = 0; i < b; i++){
			cin >> p;
			B[p] = true;
		}
		fill(&dp[0][0], &dp[199][199]+1, 0.0);
		dp[0][0] = 1.0;
		for(int t = 0; t < T; t++){
			for(int n = 0; n < N; n++){
				for(int i = 1; i <= 6; i++){
					if(n + i <= N){
						if(B[n+i]){
							dp[t+1][0] += dp[t][n] / 6;
						}else if(L[n+i]){
							dp[t+2][n+i] += dp[t][n] / 6;
						}else{
							dp[t+1][n+i] += dp[t][n] / 6;
						}
					}else{
						if(B[N-(n+i-N)]){
							dp[t+1][0] += dp[t][n] / 6;
						}else if(L[N-(n+i-N)]){
							dp[t+2][N-(n+i-N)] += dp[t][n] / 6;
						}else{
							dp[t+1][N-(n+i-N)] += dp[t][n] / 6;
						}
					}
				}
			}
		}
		double res = 0;
		for(int i = 0; i <= T; i++){
			res += dp[i][N];
		}
		cout << fixed << setprecision(10) << res << endl;
	}
	return 0;
}

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

int main() {
  int a , b, r;
  cin >> a >> b;
  r = a*b%2;
  
  if (r == 1){
    cout << "Odd" << endl;
  }
  else{
    cout << "Even" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(NULL);
int n,m; cin>>n>>m;
int a[n];
for(int i=0;i<n;i++)
a[i]=10;
if(n==1&&m==0)
{
	cout<<0; return 0;
}
if(m==0)
{
cout<<1;
for(int i=1;i<n;i++)
cout<<0;
return 0;
}
while(m--)
{
	int s,c;
	cin>>s>>c;
	if(a[s-1]!=10&&a[s-1]!=c)
	{
		cout<<-1; return 0;
	}
	a[s-1]=c;
}
if(a[0]==10)
cout<<1;
else if(a[0]==0&&n>=2)
{
		cout<<-1; return 0;
}
else
cout<<a[0];
for(int i=1;i<n;i++)
{
	if(a[i]==10)
	{
		a[i]=0;
	}
	cout<<a[i];
}
}


Measured memory_bytes: 256
n, m = map(int, input().split())
s = input()
a = []
for i in range(n):
    if i == 0 or s[i] != s[i - 1]:
        a.append(1)
    else:
        a[len(a) - 1] += 1
for i in range(1, len(a)):
    a[i] += a[i - 1]
cur = int(s[0])
ans = 0
for i in range(len(a)):
    tmp = a[i]
    if cur:
        if i > 2 * m:
            tmp -= a[i - 2 * m - 1]
    else:
        if i > 2 * m - 1:
            tmp -= a[i - 2 * m]
    ans = max(ans, tmp)
    cur = 1 - cur
print(ans)

Measured memory_bytes: 7164
# -*- coding: utf-8 -*-
import numpy as np
import itertools
N = int(input())
town_dic = {}
for i in range(N):
    x, y = map(int, input().split())
    town_dic[i] = [x, y]

l = [i for i in range(N)]
case_list_list = itertools.permutations(l)
mean_distance = 0
temp_distance = 0
counter = 0
for case_list in case_list_list:
    counter += 1
    temp_distance = 0
    for i in range(N - 1):
        temp_distance += np.sqrt((town_dic[case_list[i]][0] - town_dic[case_list[i + 1]][0]) ** 2 + (town_dic[case_list[i]][1] - town_dic[case_list[i + 1]][1]) ** 2)
    mean_distance += temp_distance

print(mean_distance / counter)

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

using namespace std;

const int M = 2e3 + 3;
const int MOD = 1e9 + 7;
int n, k, a[M], cnt[M]; 
long long f[M];
map <pair <int, int>, int> mp;
long long ans;

int main () {
  scanf ("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf ("%d", &a[i]);
    f[a[i]]++;
  }
  for (int i = M-2; i >= 0; i--) f[i] += f[i+1];
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      if (a[i] > a[j]) mp[{i, j}]++, cnt[a[i]]++;
    }
  }
  for (auto i : mp) {
    ans = (ans + 1ll*k*i.second) % MOD;
  }
  //cout << ans << endl;
  for (int i = 0; i < n; i++) {
    long long x = (1ll*(k-1)*k/2ll)%MOD;
    ans = (ans + 1ll*(f[a[i]+1])*x) % MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 63872
def solve():
    s=input()
    num = [0 for i in range(26)]
    for i in range(len(s)):
        num[ord(s[i])-ord('a')]+=1;
    for i in range(26):
        if num[i]>1:
            print("no")
            return
    print("yes")
if __name__ == "__main__":
    solve()

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

from sys import stdin
import math

# 標準入力をスペースで区切って、intに変換 listに収納
int_list  = [int(x) for x in stdin.readline().rstrip().split()]


N = int_list[0]

# 桁数が奇数　＝＞　1桁、3桁、5桁

def is_degits_odd(number):
    digits = len(str(number))
    if digits % 2 == 1:
        return 1
    else:
        return 0
cnt = 0
for i in range(N):
    number = N - i 
    if is_degits_odd(number):
        cnt+=1

print(cnt)


Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

int main()
{
    string str;
    cin >> str;
    int cnt = 0;
    int max_cnt = 0;
    int flag = 1;
    for(int i; i < str.length(); ++i)
    {
        switch(str[i]){
            case 'A':
            case 'C':
            case 'G':
            case 'T':
                if(flag) cnt += 1;
                else cnt = 1;
                flag = 1;
                break;
            default:
                flag = 0;
                cnt = 0;          
        }
       max_cnt = max(max_cnt, cnt); 
    }

    cout << max_cnt << endl;

    return 0;
}

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

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

  int n, k;
  cin >> n >> k;

  int l[n];
  for (int i = 0; i < n; ++i) cin >> l[i];
  
  sort(l, l+n, greater<int>());
  int ans = 0;

  for (int i = 0; i < k; ++i) ans += l[i];
  cout << ans << '\n';

  return (0);
}


Measured memory_bytes: 3532
args = input().split()

a = int(args[0])
b = int(args[1])
c = int(args[2])
d = int(args[3])

while 1:
  c -= b
  if c <= 0:
    print('Yes')
    break
  a -= d
  if a <= 0:
    print('No')
    break

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

#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

int main() {
  ll n;
  cin >> n;
  ll ans = 0;
  for (long long i = 0; i < n; i++) {
    ll l, r;
    cin >> l >> r;
    ans += r - l + 1;
  }

  cout << ans << endl;
}


Measured memory_bytes: 3548
#include <stdio.h>

#define N 100

int main(void){
    int times[N];
    int n, maxtm=0;
    
    for (int i=0; i<N; i++) times[i]=0;
    while (scanf("%d", &n)!=EOF){
        times[n]++;
        if (times[n] > maxtm) maxtm = times[n];
    }
    for (int i=0; i<N; i++){
        if (times[i]==maxtm) printf("%d\n", i);
    }
    return 0;
}

Measured memory_bytes: 1024
n = int(input())
w = list(map(int, input().split()))

min = 1000000
ans = 0

s1 = 0
s2 = sum(w)

for i in range(n):

    s1 += w[i]
    s2 -= w[i]

    if abs(s2-s1) < min:
        ans = abs(s2-s1)
        min = abs(s2-s1)

print(ans)

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

int main(){
    int N;string S;cin>>N>>S;
    vector<int> left(N+1),right(N+1);
    for(int i=1;i<=N;i++){
        left.at(i)=left.at(i-1);
        if(S.at(i-1)=='W')left.at(i)++;
    }
    for(int i=N-1;i>=0;i--){
        right.at(i)=right.at(i+1);
        if(S.at(i)=='E')right.at(i)++;
    }
    int ans=1000000;
    for(int i=1;i<=N;i++){
        int now=left.at(i-1)+right.at(i);
        ans=min(ans,now);
    }
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

vector<int> parent;

void init(int n) {
	parent = vector<int>(n, -1);
}


int find(int x) {
	if (parent[x] < 0) {
		return x;
	}
	else {
		return parent[x] = find(parent[x]);
	}
}

int size(int x) {
	return -parent[find(x)];
}

bool unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return false;

	if (size(x) < size(y)) swap(x, y);

	parent[x] += parent[y];
	parent[y] = x;

	return true;
}


int main() {
	int N, M;
	vector<long long> ans;
	vector<pair<int, int>> bridges;

	cin >> N >> M;
	init(N);

	bridges.resize(M);
	ans.resize(M);
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		bridges[i] = make_pair(x - 1, y - 1);
	}

	ans[M - 1] = ((long long)N*(N - 1)) / 2;

	for (int i = M - 1; i >= 1; i--) {
		ans[i - 1] = ans[i];
		if (find(bridges[i].first) != find(bridges[i].second)) {
			ans[i - 1] -= size(bridges[i].first) * size(bridges[i].second);
			unite(bridges[i].first, bridges[i].second);
		}
	}

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << endl;
	}

	return 0;
}

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

int main(){
	int n,c,a,i,j,count = 0;
	while(cin >> n){
		char b[8][5];
		c = 10000;
		for(i=0;i<5;i++){
			a = n/c;
			if(a<5) {
				b[0][i] = '*';
				b[1][i] = ' ';
			}
			else{
				b[0][i] = ' ';
				b[1][i] = '*';
			}
			b[2][i] = '=';
			if(a==0||a==5){
				b[3][i] = ' ';
				for(j=4;j<8;j++){
					b[j][i] = '*';
				}
			}
			else if(a==1||a==6){
				for(j=3;j<8;j++){
					if(j==4) b[j][i] = ' ';
					else b[j][i] = '*';
				}
			}
			else if(a==2||a==7){
				for(j=3;j<8;j++){
					if(j==5) b[j][i] = ' ';
					else b[j][i] = '*';
				}
			}
			else if(a==3||a==8){
				for(j=3;j<8;j++){
					if(j==6) b[j][i] = ' ';
					else b[j][i] = '*';
				}
			}
			else {
				for(j=3;j<7;j++){
					b[j][i] = '*';
				}
				b[7][i] = ' ';
			}
			n -= c*a;
			c /= 10;
		}
		if(count) printf("\n");
		else count++;
		for(i=0;i<8;i++){
			for(j=0;j<5;j++){
				cout << b[i][j];
			}
			printf("\n");
		}
	}
	return 0;
}

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

using namespace std;

int main()
{
	long long x,y;
	scanf("%lld%lld",&x,&y);
	int ans=0;
	while (x<=y)
	{
		ans++;
		x*=2;
	}
	printf("%d",ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <queue>
#include <deque>

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


#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")


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

    ll const MAX = (N - 1) * (N - 2) / 2;
    // 感想戦
    if(K > MAX){
        cout << -1 << endl;
        return 0;
    }

    vector<pll> edge;
    for(ll i = 2; i <= N; ++i){
        edge.emplace_back(1, i);
    }
    ll diff = MAX - K;
    for(ll i = 1; i < N - 2; ++i){
        if(!diff) break;
        for(ll j = 2; j <= N; ++j){
            if(!diff) break;
            edge.emplace_back(j, (j + i) > N ? j + i - N + 1 : j + i);
            diff--;
        }
    }
    cout << edge.size() << endl;
    for(auto &v : edge){
        cout << v.first << " " << v.second << endl;
    }

    return 0;
}


Measured memory_bytes: 512
import sys
# sys.setrecursionlimit(10**6)
# input = sys.stdin.buffer.readline
# arr = [[int(el) for el in input().split()] for i in range(n)]

s = input()

def sol(s):

    if s == "RRR":
        return 3

    # print (s, s[0], s[1], s[2])

    if (s[0] == s[1] == "R") or (s[1] == s[2] == "R"):
        return 2

    if "R" in s:
        return 1

    return 0

print (sol(s))


Measured memory_bytes: 9096
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, BinaryHeap, VecDeque, BTreeSet, BTreeMap};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::stdin;

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}

#[allow(unused_macros)]
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    get!($t)
                   ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    get!($($t),*)
                   ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    let s: Vec<usize> = util::line()
        .chars()
        .map(|c| c as usize - '0' as usize)
        .collect();

    let mut ans = 0;
    for f in 0..1 << (s.len() - 1) {
        let mut t = 0;

        for i in 0..s.len() {
            t *= 10;
            t += s[i];
            if f & 1 << i != 0 {
                ans += t;
                t = 0;
            }
        }
        ans += t;
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
using System;

namespace DPL_3_A_Largest_Square
{
	class Program
	{
		const string Dirty = "1";

		static void Main ( string[] args )
		{
			int[] size = Array.ConvertAll (Console.ReadLine ().Split (' '), int.Parse);

			string[][] area = new string[size[0]][];

			for (int lp = 0; lp < size[0]; lp++)
			{
				area[lp] = Console.ReadLine ().Split (' ');
			}

			var result = LargestSquare (area);

			Console.WriteLine (result);
		}

		static int LargestSquare ( string[][] area )
		{
			int width = area.Length;
			int height = area[0].Length;
			int[,] dp = new int[width + 1, height + 1];

			int maxLength = 0;

			for (int lp = 1; lp <= width; lp++)
			{
				for (int lp2 = 1; lp2 <= height; lp2++)
				{
					if (area[lp - 1][lp2 - 1] != Dirty)
					{
						int minSize = Math.Min (dp[lp - 1, lp2], Math.Min (dp[lp, lp2 - 1], dp[lp - 1, lp2 - 1]));
						dp[lp, lp2] = minSize + 1;
						maxLength = Math.Max (maxLength, dp[lp, lp2]);
					}
				}
			}

			return maxLength * maxLength;
		}
	}
}



Measured memory_bytes: 99872
import math
A,B = map(int,input().split())
C = math.gcd(A,B)

#N以下の素数れっきょエラトステネス
def prime(N):
    lsprime = [0,0]+[1 for i in range(N-1)]
    lsprime2 = []
    for i in range(N+1):
        if lsprime[i] == 0:
            continue
        lsprime2.append(i)
        k = i
        while i <= N:
            lsprime[i] = 0
            i += k
    return lsprime2

#素因数分解
def prime2(N):
    arr = []
    temp = N
    setprime = set()
    for i in range(2, int(-(-N**0.5//1))+1):
        if temp%i==0:
            cnt=0
            setprime.add(i)
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
        setprime.add(temp)

    if arr==[]:
        arr.append([N, 1])

    return arr,setprime

_,setp = prime2(C)
print(len(setp)+1)

Measured memory_bytes: 9428
// C - Triangular Relationship
// https://atcoder.jp/contests/arc102/tasks/arc102_a?lang=en

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, k;

int main() {
  scanf("%lld %lld", &n, &k);

  vector<ll> num(k, 0);
  for (ll i=1; i<=n; i++) {
    num[i%k]++;
  }

  ll ans = 0;
  for (ll a=0; a<k; a++) {
    ll b = (k-a) % k;
    ll c = (k-a) % k;
    if ((b+c) % k == 0)
      ans += num[a] * num[b] * num[c];
  }
  printf("%lld\n", ans);
}


Measured memory_bytes: 1792
s=list(input())
n=len(s)

def dfs(i,s):
  if i==n-1:
    return eval(''.join(s))
  else:
    s1,s2=s.copy(),s.copy()
    s1.insert(2*i+1,'+')
    s2.insert(2*i+1,'')
    return dfs(i+1,s1)+dfs(i+1,s2)
  
print(dfs(0,s))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int a,i,b,c=0;
    for(i=0; i<s.size()/2; i++){
        if(s[i]!=s[s.size()-1-i])
            c++;
    }
    cout<<c<<endl;
    return 0;
}


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


def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    AB = []
    for a in A:
        for b in B:
            AB.append(a+b)
    AB.sort(reverse=True)
    C.sort(reverse=True)
    AB = AB[:K]
    C = C[:K]
    ABC = []
    for ab in AB:
        for c in C:
            ABC.append(ab+c)
    ABC.sort(reverse=True)
    for i in range(K):
        print(ABC[i])
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(X)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(Y)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(Z)]  # type: "List[int]"
    solve(X, Y, Z, K, A, B, C)

if __name__ == '__main__':
    main()


Measured memory_bytes: 139392
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

class Main {
    int N;
    void input() { cin >> N; }
    void output() {
        for (int k = 1; k * (k - 1) <= 2 * N; ++k) {
            if (k * (k - 1) == 2 * N) {
                vector<vector<int>> res(k);
                int n = 1;
                for (int i = 0; i < k; ++i) {
                    for (int j = 0; j < k - 1 - i; ++j) {
                        res[i].emplace_back(n);
                        res[i + j + 1].emplace_back(n);
                        ++n;
                    }
                }
                cout << "Yes" << endl;
                cout << k << endl;
                REP(i, k) {
                    cout << k - 1;
                    REP(j, k - 1) { cout << " " << res[i][j]; }
                    cout << endl;
                }
                return;
            }
        }
        cout << "No" << endl;
    }

public:
    Main() {
        input();
        output();
    }
};

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

    Main();

    return 0;
}


Measured memory_bytes: 4176
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())
ans3 = 0

food = [A, B, C, D, E]

last_food = []

for i in food:
	sub = i % 10
	sub_last_food = 10 - sub
	
	if sub_last_food == 10:
		x = 0
	else:
		x = sub_last_food
		
	last_food.append(x)
	
	
ans = max(last_food)


ans1 = last_food.index(ans)


for i in range(5):
	ans2 = food[i] + last_food[i]
	ans3 = ans3 + ans2
	

ans4 = ans3  - last_food[ans1]

print(ans4)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,x,y) for(int i=x;i<(y);++i)
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
/* start */

signed main(){
   IOS;
   int a,b,c,d,e;
   cin >> a >> b >> c >> d >> e;
   d += (c-a)*60;
   cout << d-b-e << '\n';  
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int r;
    cin >> r;
    cout << r * r << endl;
    
    return 0;
}



Measured memory_bytes: 256
from sys import stdin
n,w = map(int,stdin.readline().split())
dp = [0]*w
cou = []
for _ in range(n):
    cou.append(tuple(map(int,stdin.readline().split())))
for val in cou:
    for i in range(w-1,-1,-1):
        if dp[i] != 0 and i+val[0] < w:
            dp[i+val[0]] = max(dp[i+val[0]],dp[i]+val[1])
    dp[val[0]-1] = max(dp[val[0]-1],val[1])
print(max(dp))

Measured memory_bytes: 68444
import java.util.*;


class Graph {
	private int totalVertex;
	private LinkedList<LinkedList<Integer>> adjList;
	//adjacency list of edges
	private int[] discover; //discover time stamp, -1 for undiscovered
	private int[] finish; //finish tim
	public Graph() { totalVertex = 0; }
	public void loadAdjList() {
		Scanner in = new Scanner(System.in);
		totalVertex = in.nextInt();
		adjList = new LinkedList<LinkedList<Integer>>();
		for(int i = 0; i < totalVertex; i ++) {
			LinkedList<Integer> tmp = new LinkedList<Integer>();
			int idx1 = in.nextInt() - 1;
			int degree = in.nextInt();
			//System.out.println("mark idx1 = " + idx1 + " degree = " + degree);
			for(int j = 0; j < degree; j ++) {
				int idx2 = in.nextInt() - 1;
				tmp.add(idx2);
			}	
			adjList.add(tmp);
		}
		in.close();
	}
	
	public int DFS(int v, int t0) {
		discover[v] = t0;
		LinkedList<Integer> nb = adjList.get(v);
		Iterator<Integer> it = nb.iterator();
		int t = t0;
		while(it.hasNext()) {
			int w = it.next();
			if(discover[w] == -1) {
				t ++; //one forward step
				t = DFS(w, t);
			}
		}
		finish[v] = t + 1; //+1 for backtrack step
		return t + 1;
	}
	
	public void BFS(int v) {
		Queue<Integer> toVisit = new LinkedList<Integer>();
		ArrayList<Integer> Visited = new ArrayList<Integer>();
		toVisit.add(v);
		int[] distance = new int[totalVertex];
		distance[0] = 0;
		for(int i = 1; i < totalVertex; i++) {
			distance[i] = -1;
		}
		while (! toVisit.isEmpty()) {
			// get first one
			int node = toVisit.poll();
			//set visited
			Visited.add(node);
			//get neighbors
			LinkedList<Integer> nb = adjList.get(node);
			for(Integer v1 : nb) {
	            if((Visited.contains(v1) == false) && (toVisit.contains(v1) == false)) {
	            	toVisit.add(v1);
	            	distance[v1] = distance[node] + 1;
	            }
	            }
		}
		for(int i = 0; i < totalVertex; i++) {
			System.out.println((i+1) + " "+distance[i]);
			}
		}
}
public class Main {
	public static void main(String argv[]) {
		Graph g = new Graph();
		g.loadAdjList();
		g.BFS(0);
	}
	
}



Measured memory_bytes: 28776
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    ll q, h, s, d, n;
    cin >> q >> h >> s >> d >> n;
    ll ans = 0;
    if ( n == 1 ) {
        ans = min({q*4, h*2, s});
    }
    else if ( n >= 2 ) {
        if ( !(n&1) ) {
            ans = min({q*8, h*4, s*2, d}) * n / 2;
        }
        else {
//            cout << min({q*8, h*4, s*2, d}) * ( n / 2 ) << endl;
//            cout << min({q*4, h*2, s}) << endl;
            ans = min({q*8, h*4, s*2, d}) * ( n / 2 ) + min({q*4, h*2, s});
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main()
{
	int n;
	cin >> n;
	vector<int> b(n - 1);
	for (int i = 0; i < n - 1; i++) {
		int b_in;
		cin >> b_in;
		b.at(i) = b_in;
	}

	int ans = 0;
	if (n == 2) {
		ans = b.at(0) * 2;
	} else {
		ans += b.at(0) + b.at(n - 2);
		for (int i = 1; i < n - 1; i++) {
			ans += min(b.at(i - 1), b.at(i));
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define $$ long long int
#define pb push_back
#define db pop_back
#define q2(n) (n%2)==0
#define loop(i,m,p) for ($$ i = m; i < p; ++i)
#define loopn(i,m,p) for ($$ i = p-1; i >=m; --i)

using namespace std;

int main()
{
  $$ a[4],cn=0;
  loop(i,0,4) cin>>a[i];
  sort(a,a+4);
  if (a[0]==1)
  {
    cn++;
  }
  if (a[1]==4)
  {
    cn++;
  }
  if (a[2]==7)
  {
    cn++;
  }
  if (a[3]==9)
  {
    cn++;
  }
  if (cn==4)
  {
    cout<<"YES\n";
  }
  else
    cout<<"NO\n";

    return 0;

}



Measured memory_bytes: 256
#include <stdio.h>

#define MAX 100

int main() {
  int n;
  long a[MAX] = {};
  int i;

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%ld", &a[i]);
  }

  long max = 0;
  long min = 1000000000;

  for(i = 0; i < n; i++){
    if(max < a[i]) max = a[i];
    if(min > a[i]) min = a[i];
  }

  long ans = 0;
  ans = max - min;
  printf("%ld", ans);

  return 0;
}


Measured memory_bytes: 128
n, k = map(int, input().split())
scores = list(map(int, input().split()))

evals = []
cnt = 0

for i in range(k, n, 1):
    edge = scores[cnt]
    new_edge = scores[i]
    if edge < new_edge:
        print('Yes')
    else:
        print('No')
    cnt += 1

Measured memory_bytes: 31692
#include <iostream>

using namespace std;
int h,w,book[105],book2[105];
int main()
{
    int m=0;
    cin >>h>>w;
    char a[105][105];
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin >>a[i][j];
        }
    }

    for(int i=1;i<=h;i++){
            int n=0;
        for(int j=1;j<=w;j++){
            if(a[i][j]=='.')
                n++;
        }
        if(n==w){
            book[i]=1;
        }
    }
     for(int i=1;i<=w;i++){
            int n=0;
        for(int j=1;j<=h;j++){
            if(a[j][i]=='.')
                    n++;
        }
        if(n==h){
            book2[i]=1;
        }
    }
    for(int k=1;k<=h;k++){
            int i=0;
        for(int j = 1;j<=w;j++){
                if(book[k]==1||book2[j]==1)
                    continue;
                    i=1;
                    cout<<a[k][j];

            }
            if(i==1)
        cout<<endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 10000

void setDepth(int,int);
int setHeight(int);
int getSibling(int);

typedef struct{
  int p,l,r;
}Node;
 
Node T[N];
int n,D[N],H[N];
 
void setDepth(int u, int d){
  if(u==-1) return;
  D[u]=d;
  setDepth(T[u].l,d+1);
  setDepth(T[u].r,d+1);
}
 
int setHeight(int u){
  int h1=0, h2=0;
  if(T[u].l!=-1) h1=setHeight(T[u].l)+1;
  if(T[u].r!=-1) h2=setHeight(T[u].r)+1;
  return H[u] = (h1>h2?h1:h2);
}
 
int getSibling(int u){
  if(T[u].p==-1) return -1;
  if(T[T[u].p].l!=u && T[T[u].p].l!=-1) return T[T[u].p].l;
  if(T[T[u].p].r!=u && T[T[u].p].r!=-1) return T[T[u].p].r;
  return -1;
}
 
int main(){
  int i,v,l,r,d,root=0;
 
  scanf("%d",&n);
 
  for(i=0;i<n;i++)T[i].p=-1;
 
  for(i=0;i<n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].l=l;
    T[v].r=r;
    
    if(l!=-1) T[l].p=v;
    if(r!=-1) T[r].p=v;
  }
 
  for(i=0;i<n;i++){
    if(T[i].p==-1) root=i;
  }
 
  setDepth(root,0);
  setHeight(root);
 
  for(i=0;i<n;i++){
    printf("node %d: ",i);
    printf("parent = %d, ",T[i].p);
    printf("sibling = %d, ",getSibling(i));
    d=0;
    
    if(T[i].l != -1) d++;
    if(T[i].r != -1) d++;

    printf("degree = %d, ",d);
    printf("depth = %d, ",D[i]);
    printf("height = %d, ",H[i]);
 
    if(T[i].p == -1) printf("root\n");
    else if(T[i].l == -1 && T[i].r == -1) printf("leaf\n");
    else printf("internal node\n");
  }
   
  return 0;
}

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

int main(void){
	string s;
	cin >> s;
	for(int i = 0; i < s.length(); ++i){
		if(i % 2 == 0){
			cout << s[i];
		}
	}
	cout << endl;
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define repp(i, n) rep(i, n)
#define reppp(i, n) repp(i, n)
#define rrepp(i, n) rrep(i, n)
#define repss(i, n) reps(i, n)
#define repcc(i, n) repc(i, n)
#define repii(i, a, b) repi(i, a, b)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))

using namespace std;

using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
inline u64 xorshift() { static u64 x = 88172645463325252ull; x = x ^ (x << 7); return x = x ^ (x >> 9); }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { os << p.first << ' ' << p.second; return os; }

void solve() {
  int n; cin >> n;
  vi32 d(n); cin >> d;
  sort(all(d));
  int x = n / 2;
  cout << d[x] - d[x - 1] << '\n';
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), a[] = new int[n];
		double sum = 0;
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			sum += a[i];
		}
		sum /= n;
		int p;
		if (Math.ceil(sum) - sum >= sum - Math.floor(sum))
			p = (int) Math.floor(sum);
		else
			p = (int) Math.ceil(sum);
		long ans = 0;
		for (int i = 0; i < n; i++) {
			ans += Math.pow(a[i] - p, 2);
		}
		System.out.println(ans);
		sc.close();
	}
}


Measured memory_bytes: 36100
#[allow(unused_macros)]
macro_rules! invec {
    ( $t:ty ) => {{
        let mut s = String::new();
        match std::io::stdin().read_line(&mut s) {
            Ok(0) => Vec::<$t>::new(),
            Ok(n) => s.trim().split_whitespace().map(|s| s.parse::<$t>().unwrap()).collect::<Vec<$t>>(),
            Err(_) => Vec::<$t>::new(),
        }
    }}
}

#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($(
            {
                 splits.next().unwrap().parse::<$t>().unwrap()
            },
        )*)
    }}
}

struct Work {
    amount: u64,
    deadline: u64,
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (n, ) = input!(usize);
    let mut works = Vec::with_capacity(n);

    for _ in 0..n {
        let (a, d) = input!(u64, u64);
        works.push(Work { amount: a, deadline: d });
    }

    works.sort_by_key(|w| w.deadline);

    let mut time = 0;
    for w in works {
        time += w.amount;
        if time > w.deadline {
            println!("No");
            std::process::exit(0);
        }
    }

    println!("Yes");
}

fn main() {
    solve();
}


Measured memory_bytes: 10492
package main

import (
	"fmt"
	"math"
	"strconv"
)

func main() {
	var a, b string
	fmt.Scanf("%s %s", &a, &b)
	c, _ := strconv.ParseFloat(a+b, 8)
	d := math.Sqrt(c)
	e := fmt.Sprint(d)
	if _, err := strconv.Atoi(e); err != nil {
		fmt.Println("No")
	} else {
		fmt.Println("Yes")
	}
}


Measured memory_bytes: 512
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In,' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
            var X = new int[N];
            var sum = 0;
            for(var i=0; i< N ; i++)
            {
                X[i] = cin.ReadInt;
                sum += X[i];
            }
            var LowerX = sum / N;
            var UpperX = LowerX + 1;

            var SumByLowerX = 0;
            var SumByUpperX = 0;
            foreach(var x in X){
                SumByLowerX += (LowerX - x)*(LowerX - x);
                SumByUpperX += (UpperX - x)*(UpperX - x);
            }

            WriteLine(SumByLowerX > SumByUpperX ? SumByUpperX : SumByLowerX);
        }
    }


    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream,char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }

        public string Read
        {
            get
            {
                if(inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for(int i = 0;i < tmp.Length;i++)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }

        
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }

}

Measured memory_bytes: 11220