akhauriyash/Code-Regression huggingface dataset:
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

#define FOR(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;

int main() {
	string s;
	cin >> s;
	int n = s.size();
	// 最小値は0点
	int g = 0, p = 0;
	FOR(i, 0, n) {
		if (s[i] == 'g')
			g++;
		else
			p++;
	}
	int res = -p;
	res += n / 2;
	cout << res << endl;

	return 0;
}

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

using namespace std;

int main(void){
    int n, a, b, buf;
    vector<int> p;
    p.push_back(-1);
    cin>>n>>a>>b;

    for(int i=1; i<n+1; i++){
        cin>>buf;
        p.push_back(buf);
    }

    sort(p.begin()+1, p.end());

    int cnt1 = 0;
    int cnt2 = 0;
    int cnt3 = 0;

    for(int i=1; i<n+1; i++) {
        if (p[i] <= a) {
            cnt1++;
        } else if(p[i] <= b){
            cnt2++;
        }else{
            cnt3++;
        }
    }

    int ans = min({cnt1, cnt2, cnt3});

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n ;
    cin >> n ;
    vector<int> d(n) ;
    for (int i = 0; i < n; i++)
    {
        cin >> d.at(i) ;
    }
    sort(d.begin(), d.end()) ;
    int h = n/2 ;
    int ans = d.at(h) - d.at(h-1) ;

    cout << ans << endl ;
}

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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a, 0xff, sizeof(a))

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
typedef complex<ld> Point;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 1e5 + 5;
const int MAX_N = 1e5 + 5;
const double PI = acos(-1);

long long fac[MAX_N], finv[MAX_N], inv[MAX_N];
// テーブルを作る前処理 from: https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX_N; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    int n, k;
    cin >> n >> k;
    COMinit();
    int ma = COM(n - 1, 2);
    if (k > ma) {
        out(-1);
        return 0;
    } else {
        int cnt = 0;
        vector<pair<int, int>> ans;
        repeat(i, 2, n + 1) {
            ans.push_back(make_pair(1, i));
            cnt++;
        }
        int res = COM(n - 1, 2) - k;
        int add = 0;
        int u = 1, v = 2;
        while (res > add) {
            if (add < n - 1) {
                u++;
                v++;
                if (v > n) {
                    v = 2;
                }
            } else {
                v++;
                if (v > n) {
                    u++;
                    v = u + 2;
                }
                if (u == 2 && v == n) {
                    u = 3;
                    v = u + 2;
                }
            }
            // debug(u);
            // debug(v);
            // debug(add);
            ans.emplace_back(u, v);
            if (u == n) {
                u = 2;
                v = u + 1;
            }
            add++;
        }
        cnt += add;

        out(cnt);
        for (auto p : ans) {
            cout << p.first << " " << p.second << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 2688
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll m, ll n){
      while(m!=n){
  		if (m>n) m = m - n;
  		else n = n - m;
  	}
  	return m;
}
ll lcm(ll m,ll n){
      return ((m/gcd(m, n))*n);
}
int main(){
      ll a,b;
      while(cin>>a>>b){
            cout<<gcd(a,b)<<' '<<lcm(a,b)<<endl;
      }
}

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

int main(){
	int a, b, c, n;
	cin >> n;
	for( int i=0; i<n; i++ ){
		cin >> a >> b >> c;
		a *= a;
		b *= b;
		c *= c;
		if( (a+b==c) || (a+c==b) || (b+c==a) ){
			cout << "YES" << endl;
		}else{
			cout << "NO" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 0
s = int(input())
num = []
num.append(s)
i = 1
while True:
    i += 1
    if s % 2 == 0:
        s = s/2
        if s in num:
            break
        else:
            num.append(s)
    else:
        s = 3 * s + 1
        if s in num:
            break
        else:
            num.append(s)
    
print(i,end="")

Measured memory_bytes: 3060
#include <stdio.h>

int main(){

  int a, b;

  scanf("%d %d", &a, &b);

  if(a < b){
    printf("a < b\n");
  }
  else if(a > b){
    printf("a > b\n");
  }
  else if(a == b){
    printf("a == b\n");
  }

  return 0;

}

Measured memory_bytes: 580
N = int(input())
alist = [int(i) for i in input().split(" ")]
blist = [int(i) for i in input().split(" ")]
counts = 0
if alist[0] < blist[0]:
  counts += alist[0]
  blist[0] -= alist[0]
else:
  counts += blist[0]
  blist[0] = 0
for i in range(1,N):
  if alist[i] < blist[i-1]:
    counts += alist[i]
  elif alist[i] < blist[i-1] + blist[i]:
    counts += alist[i]
    blist[i] -= alist[i] - blist[i-1]
  else:
    counts += blist[i-1] + blist[i]
    blist[i] = 0
counts += min(alist[-1], blist[-1])
print(counts)
    

Measured memory_bytes: 19004
//Date of submission: 13-06-2020

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1e5 + 5;

//------------------------------------------------------------------------------

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a,b,v,w,t;
    cin>>a>>v>>b>>w>>t;
    if(abs(a-b)<=((v-w)*t))
    cout<<"YES";
    else
    cout<<"NO";
    return 0;
}

//------------------------------------------------------------------------------


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

i_m = m
import math
root_m = int(math.sqrt(m))

m_s = []
for i in range(2,root_m+1):
    while m%i == 0:
        m_s.append(i)
        m = int(m/i)
        if m == 1:
            break
    if m ==1:
        break

if m_s == []:
    if n == 1:
        print(i_m)
    else:
        print(1)

else:
    for i in range(0,i_m-n+1):
        if i_m%(n+i) == 0:
            print(int(i_m/(n+i)))
            break

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

#define int long long int 

int32_t main()
{
    int n;
    cin>>n;
    int x,y;
    cin>>x>>y;
    int a[n];
    int ans=n+y;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        ans+=(x-1)/a[i];
       // cout<<ans<<endl;
    }
    cout<<ans<<endl;
    
}

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

typedef long long ll;

int main() {
    ll N, K, k, ans = 0, s;
    cin >> N >> K;
    vector<ll> A(N), B(N);
    rep(i, N) cin >> A[i] >>B[i];
    rep(i, 31) {
        if (i == 0) k = K;
        else k = ((K >> i) << i) - 1;
        if (k < 0) break;
        //cout << i << " " << k << endl;
        s = 0;
        rep(j, N) {
            if ((A[j] | k) == k) s += B[j];
        }
        ans = max(ans, s);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#define ENABLE_DEBUG 1
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    usize n;
    std::cin >> n;
    vec<i64> a(n);
    for (i64& x: a) std::cin >> x;

    usize ans = 0;
    for (usize i=0, j=0; i<n; i=j) {
        i64 nonzero = 0;
        for (j=i+1; j<n && 0 <= nonzero * (a.at(j)-a.at(j-1)); j++) {
            if (!nonzero) nonzero = a.at(j) - a.at(j-1);
        }
        ans++;
    }
    std::cout << ans << '\n';
}


Measured memory_bytes: 1024
<?php
//$queueからarray_shift()でひとつ頭を取り出す。
//$ary[]に体節の並びを保持。体節の長さ分だけfor(foreach)でまわして $ary[$i] と $ary[$i+1] とを比較
//もし、色が違えば$queueに次階層の状態を追加($array_push)
//体節の色がすべて同じなら終了する。

$file_handle = fopen('php://stdin', "r");	//fopen()は同位フォルダにファイルがあればその名前のみでOK


//wfs
function wfs() {
	global $cnt;	//終了条件に使用
	global $sec;
	global $ary_start;
	global $goal_flag;

	$queue[0] = $ary_start;			//スタートを$queueに入れて開始
	$queue_size = count($queue[0]);	//キューの長さを取得
	$queue[0]['sec'] = 0;			//スタート時の秒数(階層の深さ)を入れる
	while (!empty($queue)) {		//$queueが1つ以上あればループ
	   $cur = array_shift($queue);	//配列$queueの頭から１つ取り出す。
	   
	   //終了条件。全ての配列が同じ色なら終了
	   $cnt = 0;	//カウントの初期化
	   for($i=0; $i<$queue_size; $i++){
	       if ($cur[$i] !== $cur[0]){ break; }
	       $cnt++;
	   }
	   if ($cnt === $queue_size) {
	       $goal_flag = 1;
	       $sec = $cur['sec'];	//ゴールした時の秒数
	       break;	//色がすべて同じならwhileを抜ける
	   }
	   
	   //探索
	    for($i=0; $i<$queue_size-1; $i++){
	    	if ($cur[$i] !== $cur[$i+1]){	//隣接する体節の色が違う場合
    			$new = $cur;
    			$new['sec'] = $cur['sec'] + 1;		//（バグ３に関して）キュー自身に階層情報を持たせるのが一番早い
	    		//変化する色ごとに場合分け
	    		if ($cur[$i] !== 'r' && $cur[$i+1] !== 'r'){	//次の階層で赤になる場合
	    			$new[$i] = 'r';  $new[$i+1] = 'r';
	    		} else if ($cur[$i] !== 'g' && $cur[$i+1] !== 'g'){
	    			$new[$i] = 'g';  $new[$i+1] = 'g';
	    		} else {
	    			$new[$i] = 'b';  $new[$i+1] = 'b';
	    		}
	    		$str = toString($new);
	    		if (empty($visited[$str])){	//未探索の場合。バグの原因２。この再訪防止処置が無いと同じパターンを何度も辿ることになり効率が非常に悪くなる
		    		array_push($queue, $new);
				    $visited[$str] = 1;		//pushしたキューを探索済みに追加
				}
	    	}
	    }
	    //$sec++;
	    //バグの原因３。一番嵌った場所。位置がNG。階層が進んだところでインクリメントする必要あり。
	    //これだとnodeをひとつ調べるたびに秒数が増えていってしまう。
	}
}

//再訪防止用。配列のキーに文字列を設定するために使用
function toString($ary){
	$str = '';
	foreach ($ary as $key => $val){
		if (is_numeric($key)) {		//配列のキーが数値ならば（secがあるので）
			$str = $str.$val;
		}
	}
	return $str;
}


while (1){
	//変数の初期化
	$sec = 0;
	$goal_flag = 0;

	//ファイル読み込み
	$stdin = trim(fgets($file_handle));
	//終了条件
	if ($stdin == '0'){		//バグの原因１。 === とか == 0 だとバグ
		break;
	}
	$ary_start = str_split($stdin);
	

	//探索
	wfs();

	//出力
	if ($goal_flag === 1){
		echo $sec;
	} else {
		echo 'NA';
	}
	echo PHP_EOL;
}

fclose($file_handle);

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

int main() {
    string S; cin >> S;
    if (S == "SUN") {
        cout << 7 << endl;
    }
    if (S == "MON") {
        cout << 6 << endl;
    }
    if (S == "TUE") {
        cout << 5 << endl;
    }
    if (S == "WED") {
        cout << 4 << endl;
    }
    if (S == "THU") {
        cout << 3 << endl;
    }
    if (S == "FRI") {
        cout << 2 << endl;
    }
    if (S == "SAT") {
        cout << 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import qualified Data.Vector.Unboxed as VU

main :: IO ()
main = do
  s <- T.getLine :: IO T.Text
  let
    tailRems :: [Int]
    tailRems = uncurry (:) . snd . T.foldr step (10, (0, [])) $ s
      where
        step :: Char -> (Int, (Int, [Int])) -> (Int, (Int, [Int]))
        step c (l, (r, rs)) = (10 * l `mod` 2019, ((unsafeCharToInt c * l + r) `mod` 2019, r : rs))
    cs :: VU.Vector Int
    cs = count tailRems
  print . VU.sum . VU.map (\k -> k * pred k `div` 2) $ cs

count :: [Int] -> VU.Vector Int
count = VU.accum (+) (VU.replicate 2019 0) . map (flip (,) 1)

unsafeCharToInt :: Char -> Int
unsafeCharToInt c = fromEnum c - 48


Measured memory_bytes: 47048
#include<bits/stdc++.h>
using namespace std;
#define arep(i,x,n) for(int i=int(x);i<(int)(n);i++)
#define rep(i,n) for(long long i = 0;i < n;++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9+7  
using ll = long long; 
using P=pair<int,int>;
using lP=pair<ll,ll>;
using fP=pair<double,double>;


int main(){
   string s;
   cin>>s;
   rep(i,s.size()-1){
       if(s[i]=='A'&&s[i+1]=='C'){
           cout<<"Yes"<<endl;
           return 0;
       }
   }
   cout<<"No"<<endl;


    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int N;
    scanf("%d", &N);
    int a[N+1];
    a[0]=0;
    for (int i=1; i<=N; i++){
        scanf("%d", &a[i]);
    }
    int count = 0;
    for (int i=N; i>0; i--){
        int ans = 0;
        for(int j = 1; j*i <= N; j++){
            ans += a[i*j];
        }
        a[i] = ans%2;
        count += a[i];
    }
    printf("%d\n", count);
    for(int i=1; i<=N; i++){
        if(a[i] == 1){
            printf("%d\n", i);
        }
    }
    return 0; 
}

Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a%b);
}

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

struct edge {
	ll ind;
	ll to;
	ll d;
};


///////////////////////////



int main() {
	string s[3];
	cin >> s[0]>>s[1]>>s[2];
	ll t[3] = {};

	ll x = 0;

	while (1 == 1) {
		if (s[x][t[x]] == 'a') { t[x]++; x = 0; }
		if (s[x][t[x]] == 'b') { t[x]++; x = 1; }
		if (s[x][t[x]] == 'c') { t[x]++; x = 2; }
		if (t[x] == s[x].size()) { break; }
	}

	if (x == 0) { cout << 'A'; }
	if (x == 1) { cout << 'B'; }
	if (x == 2) { cout << 'C'; }



	system("PAUSE");
}

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

using namespace std;
using ll = long long;

int main() {
    ll k;
    cin >> k;

    if (k % 2 == 0 || k % 5 == 0) {
        cout << -1 << endl;
        return 0;
    }

    bool flag = true;
    ll rem = 7;
    ll ans = 1;
    while (flag) {
        rem = rem % k;
        if (rem == 0) {
            flag = false;
        }
        else {
            rem = rem * 10 + 7;
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
//
// Created by nuwaisir on ৬/১১/১৯.
//

#include<bits/stdc++.h>

using namespace std;
#define ll long long

#define MOD 1000000007

long long bigmod ( long long a, long long p, long long m )
{
    long long res = 1;
    long long x = a;

    while ( p )
    {
        if ( p & 1 ) //p is odd
        {
            res = ( res * x ) % m;
        }
        x = ( x * x ) % m;
        p = p >> 1;
    }

    return res;
}
int main(){
    ios_base :: sync_with_stdio(false); //cin.tie(nullptr); cout.tie(nullptr);
    ll n, i, j, cost, l, x, y;
    string s;
    cin >> s;
    if(s == "SAT"){
        cout << 1 << "\n";
    }
    if(s == "SUN"){
        cout << 7 << "\n";
    }
    if(s == "FRI"){
        cout << 2 << "\n";
    }
    if(s == "THU"){
        cout << 3 << "\n";
    }
    if(s == "WED"){
        cout << 4 << "\n";
    }
    if(s == "TUE"){
        cout << 5 << "\n";
    }
    if(s == "MON"){
        cout << 6 << "\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAXN 10000005
#define INF 1000000000
#define MOD 998244353
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,fact[MAXN],invf[MAXN],p2[MAXN];
int res[MAXN],sum[MAXN];
void add(int &a,int b) {a+=b; if(a>=MOD) a-=MOD;}
void dec(int &a,int b) {a-=b; if(a<0) a+=MOD;}
int pow_mod(int a,int i)
{
    int s=1;
    while(i)
    {
        if(i&1) s=1LL*s*a%MOD;
        a=1LL*a*a%MOD;
        i>>=1;
    }
    return s;
}
int comb(int n,int k)
{
    if(n<k) return 0;
    return 1LL*fact[n]*invf[k]%MOD*invf[n-k]%MOD;
}
int main()
{
    fact[0]=invf[0]=p2[0]=1;
    for(int i=1;i<=10000000;i++) fact[i]=1LL*fact[i-1]*i%MOD;
    invf[10000000]=pow_mod(fact[10000000],MOD-2);
    for(int i=9999999;i>=1;i--) invf[i]=1LL*invf[i+1]*(i+1)%MOD;
    for(int i=1;i<=10000000;i++) p2[i]=2LL*p2[i-1]%MOD;
    scanf("%d",&n);
    int ans=pow_mod(3,n);
    for(int i=0;i<=n/2;i++) res[i]=1LL*comb(n/2,i)*p2[n/2-i]%MOD;
    sum[n/2]=res[n/2];
    for(int i=n/2-1;i>=0;i--)
    {
        sum[i]=sum[i+1];
        add(sum[i],res[i]);
    }
    for(int i=1;i<=n/2;i++)
    {
        int j=n/2+1-i;
        dec(ans,2LL*res[i]*sum[j]%MOD);
    }
    printf("%d\n",ans);
}


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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

ll gcd(ll a, ll b){
  ll r = a%b;
  if(r==0) return b;
  else return gcd(b, a%b);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

struct UnionFind{
  ll N;
  llvec p;
  llvec cnt;
  UnionFind(ll n){
    N = n;
    p=llvec(N);
    cnt=llvec(N, 0);
    rep(i, N){
      p[i] = i;
      cnt[i] = 1;
    }
  }

  void con(ll a, ll b){
    P at = root(a);
    P bt = root(b);
    if(at.second!=bt.second){
      if(at.first>bt.first){
        swap(at, bt);
        swap(a, b);
      }
      p[at.second] = bt.second;
      cnt[bt.second]+=cnt[at.second];
      p[a]=bt.second;
    }
  }

  P root(ll a){
    ll atmp = a;
    ll c=0;
    while(atmp!=p[atmp]){
      atmp = p[atmp];
      c++;
    }
    p[a] = atmp;
    return {c, atmp};
  }

  bool is_con(ll a, ll b){
    P at=root(a);
    P bt=root(b);
    return at.second == bt.second;
  }
  
};

struct dijkstra{
  ll N;
  llvec d;
  vector<vector<edge>> e;
  dijkstra(ll n){
    N = n;
    //d = llvec(N, 1e18);
    e = vector<vector<edge>>(N);
  }

  void add_edge(ll from, ll to, ll cost){
    e[from].push_back({to, cost});
  }

  void run(ll start){
    priority_queue<P, vector<P>, greater<P>> que;
    que.push({0, start});
    d = llvec(N, 1e18);
    d[start]=0;
    while(!que.empty()){
      P q = que.top();que.pop();
      ll dc = q.first;
      ll x = q.second;
      if(dc>d[x]){
        continue;
      }else{
        for(auto ip: e[x]){
          if(d[ip.x]<=d[x]+ip.c){
            continue;
          }else{
            d[ip.x]= d[x]+ip.c;
            que.push({d[ip.x], ip.x});
          }
        }
      }
    }
  }  
};


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  ll k;
  cin >> k;
  cout << a[k-1];
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int a[5],b[4],t;
	while(1){
	b[3]=0;b[1]=0;b[2]=0;
	for(t=0;t<5;t++){
		scanf("%d",&a[t]);
		b[a[t]]=1;
		if(a[t]==0){
			return 0;
		}
	}
		if((b[3]+b[1]+b[2]==3)||(b[3]+b[1]+b[2]==1)){
			printf("3\n3\n3\n3\n3\n");
		}
	else if(b[3]==0){
		for(t=0;t<5;t++){
			if(a[t]==1){
				printf("1\n");
			}
			if(a[t]==2){
				printf("2\n");
			}
		}
	}
	else if(b[2]==0){
		for(t=0;t<5;t++){
			if(a[t]==3){
				printf("1\n");
			}
			if(a[t]==1){
				printf("2\n");
			}
		}
	}
	else if(b[1]==0){
		for(t=0;t<5;t++){
			if(a[t]==2){
				printf("1\n");
			}
			if(a[t]==3){
				printf("2\n");
			}
		}
	}
	}
	return 0;
	}
	

Measured memory_bytes: 580
#include <bits/stdc++.h>
#define x first
#define y second
#define y1 secondy1
#define rank tipa_rank
#define pb push_back
#define mp make_pair
#define pow10 tipa_pow10
#define ll long long
#define INF 1000000000
#define EPS 1e-9
#define EPS2 1e-8
#define PI acos(-1.0)
using namespace std;
int n;
int a[300000];
int main() {
	scanf("%d" , &n);
	for(int i = 0; i < 3 * n; i++)
		scanf("%d" , &a[i]);
	sort(a , a + 3 * n);
	ll ans = 0;
	for(int i = n; i < 3 * n; i += 2)
		ans += a[i];
	cout << ans;
}



Measured memory_bytes: 1408
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.complex, std.container, std.math, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


int N, M;
int[] A, B;

int[][] G;

int[][] ans;
int[] cnt;

int[] dep, pi;
int[] us;

void dfs(int u, int p) {
  dep[u] = (p == -1) ? 0 : (dep[p] + 1);
  us ~= u;
  foreach (i; G[u]) {
    const v = A[i] ^ B[i] ^ u;
    if (v != p) {
      if (dep[v] == -1) {
        pi[v] = i;
        dfs(v, u);
      } else {
        if (dep[u] > dep[v]) {
          ans[i] = [u, v];
          ++cnt[u];
        }
      }
    }
  }
}

void main() {
  try {
    for (; ; ) {
      N = readInt();
      M = readInt();
      A = new int[M];
      B = new int[M];
      foreach (i; 0 .. M) {
        A[i] = readInt() - 1;
        B[i] = readInt() - 1;
      }
      
      G = new int[][N];
      foreach (i; 0 .. M) {
        G[A[i]] ~= i;
        G[B[i]] ~= i;
      }
      
      if (M % 2 == 0) {
        ans = new int[][M];
        cnt = new int[N];
        dep = new int[N];
        dep[] = -1;
        pi = new int[N];
        pi[] = -1;
        us = [];
        foreach (u; 0 .. N) {
          if (dep[u] == -1) {
            dfs(u, -1);
          }
        }
        foreach_reverse (u; us) {
          if (pi[u] != -1) {
            const i = pi[u];
            const v = A[i] ^ B[i] ^ u;
            if (cnt[u] % 2 != 0) {
              ans[i] = [u, v];
              ++cnt[u];
            } else {
              ans[i] = [v, u];
              ++cnt[v];
            }
          }
        }
        foreach (i; 0 .. M) {
          writeln(ans[i][0] + 1, " ", ans[i][1] + 1);
        }
      } else {
        writeln(-1);
      }
    }
  } catch (EOFException e) {
  }
}


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

ll n,a[100005],p[100005],br1,br2;

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

    cin>>n;
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
        p[a[i]]++;
    }
    for(ll i=1;i<=1e5;i++)
        if(p[i]>2)
            p[i]=2;
    for(ll i=1;i<=1e5;i++)
        if(p[i]==1)
            br1++;
        else if(p[i]==2)
            br2++;
    if((br1+br2)%2==0)
        cout<<br1+br2-1<<endl;
    else
        cout<<br1+br2<<endl;

    return 0;
}


Measured memory_bytes: 5076
import java.util.*;
public class Main {
    public static void main(String[] args){
      // 入力
      Scanner sc = new Scanner(System.in);
      int A = sc.nextInt();
      int B = sc.nextInt();
      int C = sc.nextInt();
      
      // 判定
      String result = "NO";
      if((A == 7 && B == 5 && C == 5) || 
         (A == 5 && B == 7 && C == 5) || 
         (A == 5 && B == 5 && C == 7)){
           result = "YES";
      }
      
      // 出力
      System.out.println(result);
    }
    
}

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

int main(){
    string s;
    cin >> s;
    while(s != ""){
        s.pop_back();
        if(s.size() % 2 != 0)continue;
        string s1 = s.substr(0, s.size()/2), s2 = s.substr(s.size()/2);
        if(s1 == s2){
            cout << s.size() << endl;
            break;
        }
    }

    return 0;
}


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

mt19937 mt(time(nullptr));
// uniform_int_distribution< int > rand_int(0, 10) // rand[0, 10] inclusive

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  int x, n;
  cin >> x >> n;
  vector< int > p(n);
  for (int i=0; i<n; ++i) cin >> p[i];
  if (n==0) {
    cout << x << endl;
    return 0;
  }
  sort(p.begin(), p.end());
  int ans = p[0]-1;
  int ci = 0;
  for (int i=p[0]-1; i<=p[n-1]+1; ++i) {
    if (ci<n && i==p[ci]) {
      ci++;
      continue;
    }
    if (abs(x-ans) > abs(x-i)) ans = i;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3648
#include<iostream>
#include<vector>
using namespace std;
int main() {
  int n,m,c;
  cin >> n >> m >> c;
  vector<vector<int>> A(n,vector<int>(m));
  vector<int> B(m);
  vector<int> S(n,0);
  for(int i=0;i<m;i++) cin >> B[i];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++) cin >> A[i][j];
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++) S[i] += A[i][j]*B[j];
  }
  int ans = 0;
  for(int i=0;i<n;i++){
    if(S[i] + c > 0) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define N 1e7+10

lli n;

int main(void){
	cin >> n;
	lli sum = 0;
	lli k = 1;
	while(sum < n) sum+=k, k++;
	for(int i = 1; i <= k-1; i++){
		if(sum-i == n)continue;
		else cout << i << endl;
	}
	return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstring>
 
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> P;

const int INF = 1<<29;

int check(int J, int O, int I){
	if(J < O) return 0;
	if(I < O) return 0;
	return O;
}

int main(){
	string s;
	cin >> s;
	int J = 0, O = 0, I = 0;
	char prev = ' ';
	int ans = 0;
	for(int i = 0; i < s.size(); i++){
		if(s[i] == 'J'){
			if(prev != 'J'){
				ans = max(ans, check(J, O, I));
				J = 0, O = 0, I = 0;
			}
			J++;
			prev = 'J';
		}else if(s[i] == 'O'){
			if(prev != 'J' && prev != 'O'){
				ans = max(ans, check(J, O, I));
				prev = ' ';
			}else{
				if(prev == 'J') O = 1;
				if(prev == 'O') O++;
				prev = 'O';
			}
		}else if(s[i] == 'I'){
			if(prev != 'O' && prev != 'I'){
				ans = max(ans, check(J, O, I));
				prev = ' ';
			}else{
				if(prev == 'O') I = 1;
				if(prev == 'I') I++;
				prev = 'I';
			}
		}
	}
	ans = max(ans, check(J, O, I));
	cout << ans << endl;

    return 0;
}

Measured memory_bytes: 2052
R,G,B,N = map(int, input().split())
cnt = 0
for r in range((N+R)//R):
	for g in range((N+G)//G):
		b = (N-(R*r+G*g))/B
		if b >= 0 and b%1==0:
			cnt += 1
print(cnt)

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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define rrepa(i,a,n) for(int i=n;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;

int main(){

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

    rep(i,k){
        cout<<s<<" ";
    }

    repa(i,k,n){
        if(s<=2)cout<<3<<" ";
        else cout<<s-1<<" ";
    }

    return 0;
}

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

#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define fi first
#define se second
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef long double ld;
typedef string st;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
const ll MOD = 1e9 + 7 ;
const ll INF=1e14;
ll mpow(ll a,ll b,ll p=MOD){a=a%p;ll res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b=b>>1;}return res%p;}
const ll N=100005;
vi a[N];
ll in[N];
ll cnt[N];
bool vis[N];
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  st s;
  cin>>s;
  ll ans=0;
  ll n=s.length();
  ll k=0;
  forn(i,n)
  {
    if(s[i]=='W')
    {
      ans+=(i-k);
      k++;
    }
  }
  cout<<ans;
} 
//nothing is impossible

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

int main(){
    long long K;
    cin >> K;

    long long r = (abs(7 % K) <= abs(7 % K - K))? 7%K : 7 % K - K;
    long long num = 1;
    long long min_r = r;
    while(true){
        if(r == 0){
            break;
        }


        r = (10*r + 7) % K;
        r = (abs(r) <= abs(r - K))? r : r - K;
        num++;

        
        if(min_r == r){
            cout << -1 << endl;
            return 0;
        }
        if(min_r > r){min_r = r;}
    }
    cout << num << endl;
    return 0;
}


Measured memory_bytes: 3612
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#include <set>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <stack>
#include <queue>
#include <cstring>
#include <iterator>
#include <string>

#define REP(i,n) for(int i=0;i<(n);++i)
#define FORR(it,cont) for(auto it=rbegin(cont);it!=rend(cont);++it)
#define FOR(it,cont) for(auto it=begin(cont);it!=end(cont);++it)
#define ALL(cont) begin(cont), end(cont)
#define LB(b,e,v) lower_bound(b,e,v)
#define UB(b,e,v) upper_bound(b,e,v)
#define AS_MOD(a,b) ((((a) % (b) ) + (b)) % (b))
#define MODDING(a,b) (a) = AS_MOD(a,b)
#define MAXIMIZE(a, b) (a) = max((a),(b))
#define MINIMIZE(a, b) (a) = min((a),(b))

using namespace std;
typedef pair<int,int> P;
typedef pair<P, P> PP;
typedef long long ll;
int N;
int K;
int A[100010];
ll B[100010];
int main() {
  cin >> N >>K;
  REP(i, N) {
    int a;ll b;
    scanf("%d%lld", &a, &b);
    A[i]=a;B[i]=b;
  }
  ll answer = 0;
  for(int i=0;K>>i;++i) {
    int mask=0;
    if (K>>i & 1) {
      mask = (K - (1<<i)) | (1<<i)-1;
    }
    ll subanswer = 0;
    for(int j=0;j<N;++j) {
      if ((mask | A[j]) == mask) {
        subanswer += B[j];
      }
    }
    MAXIMIZE(answer, subanswer);
  }
  int mask=K;
  ll subanswer = 0;
  for(int j=0;j<N;++j) {
    if ((mask | A[j]) == mask) {
      subanswer += B[j];
    }
  }
  MAXIMIZE(answer, subanswer);
  printf("%lld\n", answer);
  return 0;

}


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

typedef int64_t Int;
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << endl; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << std::endl;
}

// 素因数分解
vector<pair<Int, Int>> factorization(Int n) {
    vector<pair<Int, Int>> ret;
    for (Int i = 2; i * i <= n; i++) {
        Int cnt = 0;
        while (n % i == 0) {
            n /= i;
            cnt++;
        }
        if (cnt > 0) {
            ret.emplace_back(i, cnt);
        }
    }
    if (n > 1) {
        ret.emplace_back(n, 1);
    }
    return ret;
}


int main() {
    Int n;
    cin >> n;
    vector<pair<Int, Int>> fc = factorization(n);
    Int sum = 0;
    for (Int i = 0; i < (Int)fc.size(); i++) {
        sum += fc[i].second;
    }
    Int res = 0;
    Int cnt = 1;
    bool update = true;
    while (update) {
        update = false;
        for (Int i = 0; i < (Int)fc.size(); i++) {
            if (fc[i].second >= cnt) {
                update = true;
                fc[i].second -= cnt;
                res++;
            }
        }
        cnt++;
    }
    print(res);
    return 0;
}

Measured memory_bytes: 3636
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <utility>

using namespace std;

int ans[1000];

int main() {
  int n, w, d;
  while (cin >> n >> w >> d, n | w | d) {
    vector<pair<int, int> > rects;
    rects.push_back(make_pair(w, d));
    for (int i = 0; i < n; i++) {
      int index, s;
      cin >> index >> s;
      index--;
      int w = rects[index].first;
      int h = rects[index].second;
      int c = w + h;
      s %= c;
      rects.erase(rects.begin() + index);
      if (s < w) {
        if (w - s < s) {
          rects.push_back(make_pair(w - s, h));
          rects.push_back(make_pair(s, h));
        } else {
          rects.push_back(make_pair(s, h));
          rects.push_back(make_pair(w - s, h));
        }
      } else {
        s -= w;
        if (h - s < s) {
          rects.push_back(make_pair(w, h - s));
          rects.push_back(make_pair(w, s));
        } else {
          rects.push_back(make_pair(w, s));
          rects.push_back(make_pair(w, h - s));
        }
      }
    }
    for (int i = 0; i < n + 1; i++) {
      ans[i] = rects[i].first * rects[i].second;
    }
    sort(ans, ans + n + 1);
    for (int i = 0; i < n + 1; i++) {
      if (i != 0) { cout << " "; }
      cout << ans[i];
    }
    cout << endl;
  }
}

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

int main() {
    string s;
    int c = 0;
    cin >> s;
    for (int i = 0; i < (int)s.length(); i++) {
        if ((i % 2 == 0 && s[i] == '0') || (i % 2 == 1 && s[i] == '1')) c++;
    }
    cout << min({c, (int)s.length()-c}) << endl;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
//priority_queue<int, vector<int>, greater<int> > pq;
#define _CRT_SECURE_NO_DEPRECATE
const int N = 300030;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =  1e9+7;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n,x;
    cin>>n>>x;
	ll ans=0;
	ll a[n];
	rep(i,0,n)
	cin>>a[i];
	rep(i,1,n)
	{
		if(a[i]+a[i-1]>x)
		{
			ll y=min(a[i],a[i]+a[i-1]-x);
			a[i]-=y;
			ans+=y;

			if(a[i]+a[i-1]>x)
			{
				ans+=(a[i-1]-x);
				a[i-1]-=(a[i-1]-x);
			}
		}
	}
	cout<<ans;
}








Measured memory_bytes: 1024
package main
 
import (
    "fmt"
)
 
func main() {
 
    var a, b, c int
 
    fmt.Scan(&a, &b, &c)
 
  if (a < c && b > c) || (a > c && b < c) {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (int i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using II = pair<int, int>; using VII = vector<II>;
using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>;
template <class T = int> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <class T = int> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <class T> ostream& operator<<(ostream &s, const vector<T>& d) { int n = d.size(); REP (i, n) s << d[i] << " "; return s; }
template <class T> ostream& operator<<(ostream &s, const vector<vector<T>>& dd) { for (vector<T> d: dd) s << d << endl; return s; }
template <class T, class S> ostream& operator<<(ostream &s, const pair<T, S>& p) { s << "{" << p.first << ", " << p.second << "}"; return s; }
#ifdef _MY_DEBUG
  #define dump(...) cerr << "\t" << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << endl << "\t", dump_func(__VA_ARGS__);
#else
  #define dump(...)
#endif
void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) { cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...); }
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
const int MOD = 1e9 + 7;

signed main() {
  int N, K; cin >> N >> K;
  VI h(N);
  REP (i, N) cin >> h[i];
  sort(ALL(h));
  int ans = 1e18;
  REP (i, N) {
    if (i + K - 1 >= N) break;
    ans = min(ans, h[i + K - 1] - h[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
//Author: Lixiang
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxk=2001;
struct D{
	int cnt[2][maxk][maxk],N,K,k;
	void init(){
		int x,y,id;
		char s[2];
		scanf("%d%d",&N,&K);
		k=K*2;
		while(N--){
			scanf("%d%d%s",&x,&y,s);
			id=(s[0]=='W');
			cnt[id][x%k][y%k]++;
		}
		for(int i=0;i<2;i++)
			for(int x=0;x<k;x++)
				for(int y=1;y<k;y++)
					cnt[i][x][y]+=cnt[i][x][y-1];
		for(int i=0;i<2;i++)
			for(int y=0;y<k;y++)
				for(int x=1;x<k;x++)
					cnt[i][x][y]+=cnt[i][x-1][y];
	}
	int c(int id,int x,int y){
		if(x<0||y<0)return 0;
		else return cnt[id][x][y];
	}
	int cal(int id,int x1,int x2,int y1,int y2){
		return c(id,x2,y2)-c(id,x2,y1-1)-c(id,x1-1,y2)+c(id,x1-1,y1-1);
	}
	int cal2(int id,int x1,int x2,int y){
		return cal(id,x1,x2,0,y-1)+cal(1-id,x1,x2,y,y+K-1)+cal(id,x1,x2,y+K,k-1);
	}
	int cal3(int id,int x,int y){
		return cal2(id,0,x-1,y)+cal2(1-id,x,x+K-1,y)+cal2(id,x+K,k-1,y);
	}
	void work(){
		int ans=0;
		for(int i=0;i<K;i++)
			for(int j=0;j<K;j++)
				ans=max(ans,max(cal3(0,i,j),cal3(1,i,j)));
		printf("%d\n",ans);
	}
}sol;
int main(){
	sol.init();
	sol.work();
	return 0;
}


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

int main(void){
    int n;
    cin >> n;
    int ans=0;
    char l,u,m;
    int lower=0;
    int upper=n;
    cout << ans << endl;
    string s;
    cin >> s;
    if(s=="Vacant"){
        return 0;
    }else if(s=="Male"){
        l='m';
        u='m';
    }else{
        l='f';
        u='f';
    }
    for(int i=1; i<20; i++){
        ans = (lower+upper)/2;
        cout << ans%n << endl;
        string s;
        cin >> s;
        if(s=="Vacant"){
            return 0;
        }else if(s=="Male"){
            m='m';
        }else{
            m='f';
        }
        if(((upper-ans%n)%2==0) ^ (u==m)){
            lower=ans;
            l=m;
        }else{
            upper=ans;
            u=m;
        }
    }
    return 0;
}


Measured memory_bytes: 852
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int n;
vector<long int> sum;
long int dp[1000][1000];

long int solve(vector<int>& a,int i, int j) {
  if (i==j) return 0;
  if (dp[i][j]!=-1) return dp[i][j];
  long int soln = LONG_MAX;
  for (int k=i;k<j;k++) {
    long int temp = (0ll + solve(a,i,k) + solve(a,k+1,j) + sum[j+1] - sum[i+1] +a[i]);
    
    soln = min(soln, temp);
  }
  return dp[i][j] = soln;
}


int main() {
  cin>>n;
  vector<int> a(n);
  sum = vector<long int>(n+1,0);
  for (int i=0;i<n;i++) {
    cin>>a[i];
    sum[i+1] = sum[i]+a[i];
  }
  
  memset(dp,-1,sizeof(dp));
  cout<<solve(a,0,n-1);
  
  return 0;
}


Measured memory_bytes: 11464
#include <stdio.h>
#include <string.h>

int main(void)
{
    char s[201], s2[201], s3[201];
    int m, h;
    int i;
    
    while (1){
        scanf("%s", s);
        if (strcmp(s, "-") == 0){
            break;
        }
        
        scanf("%d", &m);
        for (i = 0; i < m; i++){
            scanf("%d", &h);
            
            strncpy(s2, s, h);
            s2[h] = '\0';
            strcpy(s3, &s[h]);
            strcpy(s, s3);
            strcat(s, s2);
        }
    
        printf("%s\n", s);
    }

    return (0);
}



Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define ld long double
#define pii pair <int,int>
#define pll pair <ll,ll>
#define pil pair <int,ll>
#define pli pair <ll,int>
#define ull unsigned long long
#define pdd pair <double,double>
#define pb push_back
#define mp make_pair
#define puu pair<ull,ull>
#define pvv pair<vector<int>, vector<int> >
#define _bp __builtin_popcount
#define ptt pair <Tree*,Tree*>
#define all(v) v.begin(),v.end();
const long double pi = acos(-1);
void boos()
{
     ios_base :: sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
}
void file()
{
   freopen(".in","r",stdin);
   freopen(".out","w",stdout);
}
const ll INF = 1e9 + 7;
const ll INF1 = 998244353;
const ll LLINF = (ll)1e18;
const int  INTmx = (int)1e9;
const int N = 2e5 + 100;
ll dp[N];
ll a[N];
int main()
{
    //file();
    boos();
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    dp[1] = 0;
    a[0] = a[1];
    for(int i = 2;i <= n;i++)
    {
        dp[i] = min(dp[i - 2] + abs(a[i - 2] - a[i]),dp[i - 1] + abs(a[i - 1] - a[i]));
    }
    cout << dp[n];
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

int main(){
  int n;
  cin >> n;
  REP(i,n){
    int x,y,b,p;
    cin>>x>>y>>b>>p;
    if(b>=5 && p>=2){
      cout << ((x*b+y*p)*4/5) << endl;
    }else{
      int val = (x*b+y*p);
      if(b<5 && p<2){
        val = min(val,(x*5+y*2)*4/5);
      }else if(b<5){
        val = min(val,(x*5+y*p)*4/5);
      }else if(p<2){
        val = min(val,(x*b+y*2)*4/5);
      }
      cout << val << endl;
    }
  }
  return 0;
}

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

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

    return 0;
}

Measured memory_bytes: 3624
import fractions
n = int(input())
a = [0] + list(map(int,input().split())) + [0]


#はじめと最初の値を代入
L = [0] * (n+2)
R = [0] * (n+2)

for i in range(n):
    L[i+1] = fractions.gcd(L[i], a[i+1])

for j in range(n,0,-1):
    R[j] = fractions.gcd(R[j+1],a[j])

#print(a)
#print(L)
#print(R)

print(max(fractions.gcd(L[k-1],R[k+1]) for k in range(1,len(L)-1)))

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

int n, ans=0;
vector<int> h;

int main() {
	cin >> n;
	h.resize(n);
	for (int i = 0; i < n; ++i) cin >> h.at(i);

	int l=0, r=0;
	
	while(l!=n-1 || h.at(l))
	{
		while(l < n-1 && !h.at(l)){
			l++;
		}

		r = l;
		for (; r < n-1; ++r)
		{
			if (h.at(r+1)==0) break;
		}

		int minh = 10000;
		for (int i = l; i <= r; ++i) minh = min(minh, h.at(i));
		for (int i = l; i <= r; ++i)
		{
			h.at(i) -= minh;
		}
		ans += minh;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256