akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    let size = 100_001;
    input!{
        n:usize,
        k:i64,
        arrays: [(usize, i64); n],
    }
    let mut v = vec![0;size];
    for (a,b) in arrays {
        v[a]+=b;
    }
    let mut cnt=0;
    for i in 0..size {
        cnt+=v[i];
        if cnt>=k {
            println!("{}", i);
            break;
        }
    }
}


Measured memory_bytes: 6396
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <numeric>
#include <map>
#include <set>

using namespace std;
using ll = long long;

vector<int> a;
vector<int> t;
map<int, set<int>> g;

void dfs(int cur, int dist) {
    if (a[cur] <= dist) return;
    a[cur] = dist;
    for (int path : g[cur]) {
        dfs(path, dist + 1);
    }
}

void dfs2(int cur, int dist) {
    if (t[cur] <= dist) return;
    if (a[cur] == dist) {
        t[cur] = a[cur];
        return;
    }
    if (a[cur] < dist) return;
    t[cur] = dist;
    for (int path : g[cur]) {
        dfs2(path, dist + 1);
    }
}

int main() {
    int n, u, v;
    cin >> n >> u >> v;
    for (int i = 1; i < n; ++i) {
        int e1, e2;
        cin >> e1 >> e2;
        g[e1].insert(e2);
        g[e2].insert(e1);
    }
    if (g[u].size() == 1 && g[u].count(v)) {
        cout << "0\n";
        return 0;
    }

    a.resize(n + 1, n + 1);
    t.resize(n + 1, n + 1);
    dfs(v, 0);
    dfs2(u, 0);
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        if (t[i] <= n) {
            res = max(res, a[i] - 1);
        }
    }
    cout << res << "\n";
    return 0;
}


Measured memory_bytes: 26240
from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        l = L[i] + L[j]
        k = bisect_left(L, l)
        ans += max(0, k - j - 1)
print(ans)

Measured memory_bytes: 43372
//
//  main.cpp
//  Hello
//
//  Created by Gasser Mamdouh on 29/10/2019.
//  Copyright © 2019 Gasser Mamdouh. All rights reserved.
//

#include <iostream>
#include <map>
#include <utility>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stdlib.h>
#include <string.h>
#include <list>
#include <set>
#include <stdio.h>
#include <numeric>
#include <queue>
#include <memory>
#include <limits>
#include <iomanip>

using namespace std;


int main(){
    int n, totalWeight;
    cin >> n >> totalWeight;
    vector<int> weight(n), value(n);
    vector<vector<long long> > dp(n, vector<long long> (totalWeight + 1));
    for(int i = 0; i < n; i++){
        cin >> weight[i] >> value[i];
    }
    
    dp[0][totalWeight - weight[0]] = value[0];
    for(int i = 1; i < n; i++){
        dp[i] = dp[i - 1];
        for(int remainingWeight = weight[i]; remainingWeight <= totalWeight; remainingWeight++){
            dp[i][remainingWeight - weight[i]] = max(dp[i][remainingWeight - weight[i]], dp[i - 1][remainingWeight] + value[i]);
        }
    }
    
    cout << *max_element(dp[n - 1].begin(), dp[n - 1].end()) << endl;
    return 0;
}


Measured memory_bytes: 79360
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <cmath>
#include <functional>
#include <fstream>
#include <cstdlib>
typedef long long ll;
const int MOD = 1e9+7;


#define REP(i, N) for (int i = 0; i < (N); i++)
#define REPP(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define VSORT(c) sort((c).begin(),(c).end())
#define SZ(x) ((int)(x).size())
//vvintを作る　マクロで　 #define vvint(N,M) vector<vector<int>>

using namespace std;




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

    int a,b;
    cin >> a;
    vector<int> s;
    int q,t;
    for(int i = 0; i < a;i++){
        cin >> q;
        s.push_back(q);
    }
    cin >> b;
    int count = 0;
    for(int i = 0; i < b;i++){
        cin >> t;
        if(find(ALL(s),t) != s.end()){
            count++;
        }
    }
    cout << count << endl;

    return 0;
}


Measured memory_bytes: 3228
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 2e3+5;
int main()
{
    double h,m,x,y;
    while(cin>>h>>m>>x>>y)
    {
        int have = 0;
        double ans = h*m/2.0;
        if((h/2.0 == x)&&(m/2.0 == y))have = 1;
        printf("%.9lf ",ans);
        printf("%d\n",have);
    }
}




















Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
  int a, b, x;
  cin >> a >> b >> x;

  double ans;

  if (x <= 0.5 * b * a * a) {
    double h = x / (0.5*a*b);
    ans = atan(b / h) * 180 / M_PI;
  } else {
    int remainder = a*a*b - x;
    double h = remainder / (0.5*a*a);
    ans = atan(h / a) * 180 / M_PI;
  }

  cout << fixed << setprecision(15) << ans << endl;
  return 0;
}

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

int main(){
  int N; cin >> N;
  long long asum[200000];
  long long a;
  cin >> asum[0];
  for(int i=1; i<N; i++){
    cin >> a;
    asum[i]=asum[i-1]+a;
  }
  long long minimum=200000000000000;
  for(int i=0; i<N-1; i++){
    minimum=min(minimum,abs(asum[i]-(asum[N-1]-asum[i])));
  }
  cout << minimum << endl;
}

Measured memory_bytes: 1792
import fractions

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

def count(s, f, n):
  return f//n - (s-1)//n

def lcm(x, y):
    return x*y//fractions.gcd(x, y)

print( B-A+1 - ( count(A,B,C) + count(A,B,D) - count(A, B, lcm(C, D)) ) )

Measured memory_bytes: 5052
from collections import defaultdict, deque, Counter
import sys
import bisect
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    # A,B = [int(a) for a in input().split()]
    L = sorted([int(a) for a in input().split()])
    # xy = [
    #     [int(a) for a in input().split()]
    #     for _ in range(N)
    # ]

    r = 0
    for a in range(N):
        for b in range(a + 1, N):
            p = bisect.bisect_left(L, L[a] + L[b])
            r += (p - 1 - b)

            # for c in range(N-1,b,-1):
            #     if L[a] + L[b] > L[c]:
            #         r += (c-b)
            #         break

    print(r)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision; // for use cpp_int
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) {
        cin >> a[i];
        if (a[i] == 0) {
            cout << 0 << endl;
            return 0;
        }
    }
    sort(all(a), greater<ll>());
    cpp_int ans = 1;
    rep(i, n) {
        ans *= a[i];
        if (ans > 1000000000000000000) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4040
# pro level coding
def main():
	ad = input()
	now = int(ad[0])
	q = []
	n = len(ad)
	q.append([0 , now , ad[0]])
	while len(q)!=0:
		#print(23)
		cur = q.pop(0)
		#print(cur[0] , cur[1] , cur[2])
		if cur[0] ==n-1:
			if cur[1]==7:
				print(cur[2]+'='+'7')
				break
				exit(0)
			continue
		#print(cur[1]+((int)(ad[cur[0]+1])) , cur[0])
		if cur[0]+1<n:
			q.append([cur[0]+1, cur[1]+((int)(ad[cur[0]+1])) , cur[2]+'+'+ad[cur[0]+1]])
			q.append([cur[0]+1, cur[1]-((int)(ad[cur[0]+1])) , cur[2]+'-'+ad[cur[0]+1]])
if __name__=="__main__":
	main()

Measured memory_bytes: 62064
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(n);++i)
#define _repe3(i,a,b) for(ll i=(a);i<=(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;

void solve();

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

void solve(){
    string s;cin>>s;
    ll k;cin>>k;
    ll n=s.size();

    rep(i,n-1){
        if(s[i]=='a')continue;
        if('z'+1-s[i]<=k){
            k-='z'-s[i]+1;
            s[i]='a';
        }
    }
    s[n-1]=(char)('a'+(k+s[n-1]-'a')%26);
    cout<<s<<endl;
}

Measured memory_bytes: 592
#include<stdio.h>
#define k 100
int main(){
  int N,A[k],i,j,minj,atai,cou=0;
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);

  }
  for(i=0;i<N;i++){
    minj=i;
    for(j=i;j<N;j++){
      if(A[j]<A[minj]){
	minj=j;
      }
      
    }
    if(A[i]>A[minj]){
      cou++;
    atai=A[i];
    A[i]=A[minj];
    A[minj]=atai;
    }
  }
  for(i=0;i<N;i++){
  printf("%d",A[i]);
  if(i!=N-1)printf(" ");
  }
  printf("\n%d\n",cou);
  return 0;
}

Measured memory_bytes: 604
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N  = sc.nextInt();
		
		int[] h = new int[N];
		
		for(int i = 0; i < N; i++) {
			h[i] =sc.nextInt();
		}
		
		int[] hn = new int[N];
		int sum = 0;
		boolean check = false;
		int count = 0;
		
		while(count < N) {
			count = 0;
			for(int i = 0; i < N; i++) {
				if(h[i] > hn[i]) {
					hn[i]++;
					check = true;
					if(i == N - 1) {
						sum++;
						check = false;
					}
				} else {
					if(check) {
						sum++;
						check = false;
					}
				}
			}
			
			for(int i = 0; i < N; i++) {
				if(h[i] == hn[i]) {
					count++;
				}
			}
		}
		System.out.println(sum);
	}
}


Measured memory_bytes: 23124
h, w = list(map(int, input().split()))

grid = []

for i in range(h):
    row = list(input()) 

    for i in range(len(row)):
        if row[i] == '.':
            row[i] = 0
    
    grid.append(row)

num = 1000000007

for i in range(len(grid)):
    for j in range(len(grid[0])):
        if grid[i][j] == '#':
            continue
        if i == 0 and j == 0:
            grid[i][j] = 1
        elif i == 0:
            if grid[i][j-1] != '#':
                grid[i][j] = grid[i][j-1] % num
        elif j == 0:
            if grid[i-1][j] != '#':
                grid[i][j] = grid[i-1][j] % num
        else:
            if grid[i][j-1] == '#' and grid[i-1][j] == '#':
                grid[i][j] = 0
            elif grid[i][j-1] == '#':
                grid[i][j] = grid[i-1][j] % num
            elif grid[i-1][j] == '#':
                grid[i][j] = grid[i][j-1] % num
            else:
                grid[i][j] = (grid[i-1][j] + grid[i][j-1]) % num

print(grid[-1][-1])

Measured memory_bytes: 113436
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;++i)
#define all(v) v.begin(), v.end()
#define PI 3.141592653589793238462643383279
typedef long long int ll;
typedef unsigned long long ull;
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;}
typedef pair<ll,ll> P;
const long long MOD = 1e9+7;
const ll INF = 1LL << 60;

int main(){
    int n;
    cin >> n;
    map <string,int> mp;

    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        mp[s]++;
    }

    if(!mp.count("AC")){
        cout << "AC x 0" <<endl;
    }else{
        cout << "AC x " << mp["AC"] << endl;
    }

    if(!mp.count("WA")){
        cout << "WA x 0" <<endl;
    }else{
        cout << "WA x " << mp["WA"] << endl;
    }

    if(!mp.count("TLE")){
        cout << "TLE x 0" <<endl;
    }else{
        cout << "TLE x " << mp["TLE"] << endl;
    }

    if(!mp.count("RE")){
        cout << "RE x 0" <<endl;
    }else{
        cout << "RE x " << mp["RE"] << endl;
    }



}

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

void solve(long long N, long long K, std::vector<long long> p)
{

    double val = 0;
    rep (i, K) {
        val += (((double)p[i] + 1.0)) / (2.0);
    }

    double max_val = val;
    for (ll i = 1; i < N - K + 1; i++) {
        val -= (((double)p[i - 1] + 1.0)) / (2.0);
        val += ((double)p[i + K - 1] + 1.0) / 2.0;
        // cout << val << endl;
        if (val > max_val) {
            max_val = val;
        }
    }

    printf("%f\n", max_val);
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long N;
    scanf("%lld", &N);
    long long K;
    scanf("%lld", &K);
    std::vector<long long> p(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &p[i]);
    }
    solve(N, K, std::move(p));
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>

using namespace std;

int n;
int a[200005];

void input(){
  cin >> n;
  for(int i = 0; i < n; ++i){
    cin >> a[i];
  }
}

int solve(){
  int cnt = 0;
  int tmp = 1;
  for(int i = 0; i < n; ++i){
    if(a[i] != tmp){
      cnt++;
    }else{
      tmp++;
    }
  }
  if(cnt == n){
    return -1;
  }else{
    return cnt;
  }
}

int main(){
  input();
  cout << solve() << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
const ll INF=10000000000000000LL;
int main() {
	int n,m;
	int a[2001]={};
	int b[2001]={};
	ll c[2001]={};
	cin>>n>>m;
	for(int i=0;i<m;++i){
		cin>>a[i]>>b[i]>>c[i];
		c[i]*=-1;
	}

	ll k[1001];
	for(int i=0;i<=n;++i)k[i]=INF;
	k[1]=0;
	for(int i=0;i<n-1;++i){
		for(int j=0;j<m;++j){
			if (k[a[j]]==INF)continue;
			k[b[j]]=min(k[a[j]]+c[j],k[b[j]]);
		}
	}
	ll r=k[n];
	bool d[1001]={};
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j){
			if(k[a[j]]==INF)continue;
			if(k[b[j]]>k[a[j]]+c[j]){
				d[b[j]]=true;
				k[b[j]]=k[a[j]]+c[j];
			}
			if(d[a[j]])d[b[j]]=true;
		}
	}
	if(d[n])cout<<"inf"<<endl;
	else cout<<-r<<endl;
	return 0;
}


Measured memory_bytes: 256
array = [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]
k = int(input())
print(str(array[k - 1]))

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

int main(){
  int a,b,k;
  cin>>a>>b>>k;
  int count=0,ans;
  for(int i=min(a,b);i>=1;i--){
    if(a%i==0 && b%i==0) count++;
    if(count==k){
      ans=i;
      break;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void solve() {
	int n;
	cin >> n;
	vector<string> v(n);
	rep(i,n) cin >> v[i];
	ll cab = 0;
	ll ca = 0;
	ll cb = 0;
	ll c = 0;
	rep(i,n) {
		string s = v[i];
		if (s[0] == 'B' && s[s.size() - 1] == 'A') c++;
		else if (s[0] == 'B') cb++;
		else if (s[s.size() - 1] == 'A') ca++;
		for (int j = 0; j < s.size() - 1; j++) {
			string t = s.substr(j, 2);
			if (t == "AB") cab++;
		}
	}
	if (cb == 0 && ca == 0) {
		cout << cab + max((ll)0, c - 1) << endl;
	} else {
		cout << cab + min(ca + c, cb + c) << endl;
	}
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int> a(N);
  rep(i,N){cin>>a.at(i);}
  bool ans=false;
  int k=1;
  rep(i,N){
    if(a.at(i)==k){ans=true;
                   k++;}}
  k--;
  if(ans){cout<<N-k<<endl;}
  else cout<<-1<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n,cnt=0,ans=0,sum=0,xsum=0,l=0;
  cin >> n;
  long long a[n];
  for(int i=0;i<n;i++){
  	cin >> a[i];
  }
  for(int i=0;i<n;i++){
  	sum+=a[i];
  	xsum^=a[i];
    while(sum!=xsum){
  	  sum-=a[l];
  	  xsum^=a[l];
  	  l++;
  	  cnt--;
    }
    cnt++;
  	ans+=cnt;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#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()
template<class T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;

const int D = 365;
const int NTYPE = 26;
array<int, NTYPE> c;
array<array<int, NTYPE>, D> s;

void input(){
    int _d;
    cin >> _d;
    REP(i, NTYPE){
        cin >> c.at(i);
    }
    REP(i, D){
        REP(j, NTYPE){
            cin >> s.at(i).at(j);
        }
    }
}

void output(const array<int, D>& sch){
    for(auto x : sch){
        cout << x + 1 << endl;
    }
}

void solve(){
    array<int, D> ans;
    array<int, NTYPE> last;
    fill(ALL(last), 0);

    ll score = 0;
    REP(i, D){
        const ll cur_d = i + 1;
        int max_type = -1;
        int max_val = numeric_limits<int>::min();
        REP(j, NTYPE){
            int tmp = s.at(i).at(j) + c.at(j) * (cur_d - last.at(j));
            if(max_val < tmp){
                max_type = j;
                max_val = tmp;
            }
        }
        assert(max_type != -1);
        ans.at(i) = max_type;
        score += s.at(i).at(max_type);
        last.at(max_type) = i + 1;
        // REP(j, NTYPE){
        //     score 
        // }
    }
    output(ans);
}

int main(){
    input();
    solve();
    return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
// const int MOD = 1e9 + 7;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> D(K);
    for (int i = 0; i < K; i++) {
        cin >> D.at(i);
    }
    for (int n = N; n < 10 * N; n++) {
        string S = to_string(n);
        bool flag = true;
        for (auto c : S) {
            if (find(ALL(D), (int)(c - '0')) != D.end()) {
                flag = false;
                break;
            }
        }
        if (flag) {
            cout << n << endl;
            return 0;
        }
    }
}


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

int main(){
	int n, m, t;
	long long res;
	priority_queue<int> pq;
	vector<int> a(n);
	cin >> n >> m;

	for(int i=0; i<n; i++){
		cin >> t;
		pq.push(t);
	}

	for(int i=0; i<m; i++){
		t = pq.top();
		pq.pop();
		pq.push(t/2);
	}

	res = 0;
	for(int i=0; i<n; i++){
		res += pq.top();
		pq.pop();
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 25468
n, m = map(int, input().split())
res = ["n" for _ in range(n)]
con = False
for _ in range(m):
    s, c = map(int, input().split())
    idx = s - 1
    if res[idx] == "n" or res[idx] == c:
        res[idx] = c
    if res[idx] != "n" and res[idx] != c:
        con = True
        break
if con or (n > 1 and res[0] == 0): print(-1)
else:
    if res[0] == "n":
        if n == 1:
            res[0] = 0
        else:
            res[0] = 1
    for i in range(1, n):
        if res[i] == "n": res[i] = 0
    print(int("".join([str(r) for r in res])))

Measured memory_bytes: 9188
#include<bits/stdc++.h>
using namespace std;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

vector<int> V[1000];

int main() {
 UL N,Q;scanf("%u%u",&N,&Q);
 rep(q,Q){
  UL c; scanf("%u",&c);
  if(c==0){
   UL t; int x; scanf("%u%d",&t,&x);
   V[t].push_back(x);
  } else if(c==1){
   UL t; scanf("%u",&t);
   rep(i,V[t].size()) {if(i) printf(" "); printf("%d",V[t][i]);}
   printf("\n");
  } else if(c==2){
   UL t; scanf("%u",&t);
   V[t].clear();
  }
 }
 return 0;
}




Measured memory_bytes: 5908
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <math.h>
#include <queue>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)
#define INF 1<<29;

i64 rec(int cur, i64 x, vector<i64>& p, vector<i64>& l)
{
    if(cur == 0)
        return x > 0 ? 1 : 0;

    if(2*x < l[cur])
        return rec(cur-1,x-1,p,l);
    else
        return rec(cur-1,x-l[cur-1]-2,p,l) + p[cur-1] + 1;
}

int main()
{
    i64 n,x;
    cin >> n >> x;

    vector<i64> p(51);
    vector<i64> l(51);
    p[0] = l[0] = 1;
    rep(i,50) p[i+1] = 2*p[i]+1;
    rep(i,50) l[i+1] = 2*l[i]+3;

    cout << rec(n,x,p,l) << endl;

    return 0;
}

Measured memory_bytes: 256
def main():
    N, D, A = (int(i) for i in input().split())
    P = [[int(i) for i in input().split()] for j in range(N)]
    P.sort()
    X = [x[0] for x in P]
    H = [h[1] for h in P]
    diff = [H[0]] + [H[i+1] - H[i] for i in range(N-1)]
    BIT = [0] * (N+1)

    def BIT_query(idx):
        """ A1 ~ Aiまでの和(1-index) """
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx & -idx
        return res_sum

    def BIT_update(idx, x):
        """ Aiにxを加算(1-index) """
        while idx <= N:
            BIT[idx] += x
            idx += idx & -idx
        return

    def BIT_init(A):
        for i, e in enumerate(A):
            BIT_update(i+1, e)

    BIT_init(diff)
    ans = 0
    right = 0
    for left in range(N):
        x = P[left][0]
        h = BIT_query(left+1)
        while right < N and P[right][0] <= x + 2*D:
            right += 1
        if h > 0:
            cur = (h + A - 1) // A
            damage = cur * A
            BIT_update(left+1, -damage)
            BIT_update(right+1, damage)
            ans += cur
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 100772
n = int(input())
s = "abcdefghij"

class Node:
#     __slots__ = ["string", "index"]
    def __init__(self, string, index):
        self.string = string
        self.index = index

    def get_children(self):
        parent = self.string
        out = [None]*(self.index+2)
        for i, c in enumerate(s[:self.index+1], 1):
            out[i] = Node(parent+c, max(i, self.index))
        return out[1:]

root = Node("a", 1)
children = [root]
for _ in range(n-1):
    parents, children = children, []
    for parent in parents:
        children.extend(parent.get_children())
for child in children:
    print(child.string)

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

using namespace std;

set<int> a;

int main() {
    int x, y;
    cin >> x >> y;
    int a = y - 2*x;
    int b = 4*x - y;
    if(!(a&1) && !(b&1)) {
        a /= 2;
        b /= 2;
        if(a >= 0 && b >= 0) {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int n, p[256],count=0;
    cin >> n;
    for(int i=0;i<n;i++) cin >> p[i];
    
    for(int i=1;i<n-1;i++){
        if((p[i-1]<p[i]&&p[i]<p[i+1]) || (p[i-1]>p[i]&&p[i]>p[i+1]) ){
            count++;
        }
    }
    
    cout << count << endl;
    
    return 0;
}


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

int main(){
    ll n; cin >> n;
    vector<ll> ch(n, 0);
    vector<ll> lis(1e6, 0);
    for(int i = 0; i < n; i++){
        ll k; cin >> k;
        lis[k]++;
        ch[i] = k;
    }
    vector<ll> lis1(1e6, 0);
    vector<ll> lis2(1e6, 0);
    ll sum = 0;
    for(int i = 0; i < 2 * 1e5*2; i++){
        ll c = (lis[i] * (lis[i]-1)) / 2;
        lis1[i] = c;
        sum += c;
    }
    for(int i = 0; i < 2 * 1e5*2; i++){
        ll c = lis1[i] - ((lis[i]-1) * (lis[i]-2)) / 2;
        lis2[i] = c;
    }
    for(int i = 0; i < n; i++){
        ll o = ch[i];
        cout << sum - lis2[o] << endl;
    }
}

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

using namespace std;

string a, b;
int dp[3005][3005], where[3005][3005];

int main()
{
    cin >> a >> b;
    a.insert(a.begin(), '$');
    b.insert(b.begin(), '$');

    for(int i = 1; i < a.size(); i++)
        for(int j = 1; j < b.size(); j++)
        {
            if(a[i] == b[j])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                where[i][j] = 1;
            }
            else
            {
                if(dp[i - 1][j] > dp[i][j - 1])
                {
                    dp[i][j] = dp[i - 1][j];
                    where[i][j] = 2;
                }
                else
                {
                    dp[i][j] = dp[i][j - 1];
                    where[i][j] = 3;
                }
            }
        }
    //cout << dp[(int)a.size() - 1][(int)b.size() - 1];

    int N = int(a.size()) - 1;
    int M = int(b.size()) - 1;

    int x = N, y = M;
    string str;
    while(x >= 1 && y >= 1)
    {
        if(where[x][y] == 1)
        {
            str.push_back(a[x]);
            x--, y--;
        }
        else
        {
            if(where[x][y] == 2)    x--;
            else    y--;
        }
    }

    reverse(str.begin(), str.end());
    cout << str;

    exit(0);
}

Measured memory_bytes: 70784
N = gets.chomp.to_i
A = gets.chomp.split(" ").map(&:to_i).sort
B = gets.chomp.split(" ").map(&:to_i).sort
C = gets.chomp.split(" ").map(&:to_i).sort

memo = Array.new(N, 0)
N.times do |ib|
  ic = C.bsearch_index{|x| x > B[ib]}
  next if ic.nil?
  memo[ib] = (N - ic)
end

(N-1).downto(1) do |i|
  memo[i - 1] += memo[i]
end

ans = 0

A.each do |a|
  ib = B.bsearch_index{|x| x > a}
  next if ib.nil?
  ans += memo[ib]
end
puts ans

Measured memory_bytes: 28360
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
template<class T>using vv = vector<vector<T>>; template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T1, class T2>bool chmax(T1& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<class T1, class T2>bool chmin(T1& a, const T2& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

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

    ll sr = (ll)(ceil(sqrt(S)) + 1e-6);
    ll xy = sr * sr;
    ll xdyd = xy - S;

    ll X1 = 0, Y1 = 0, X2, Y2, X3, Y3;

    if (xdyd > 0) {
        ll xd = sqrt(xdyd);
        for (; xd > 0; --xd) {
            if (xdyd % xd == 0) break;
        }

        X2 = sr; Y2 = xdyd / xd;
        X3 = xd; Y3 = sr;
    }
    else {
        X2 = sr; Y2 = 0;
        X3 = 0; Y3 = sr;
    }

    cout << X1 << " " << Y1 << " " << X2 << " " << Y2 << " " << X3 << " " << Y3 << endl;
}

Measured memory_bytes: 256
using System;

namespace ALDS1_1D_Maximum_Profit
{
	class Program
	{
		static int Main ( string[] args )
		{
			//入力
			int inputCount = int.Parse (Console.ReadLine ().Trim ());

			int[] inputNum = new int[inputCount];
			for (int lp = 0; lp < inputCount; lp++)
			{
				inputNum[lp] = int.Parse (Console.ReadLine ().Trim ());
			}

			//処理
			int max = int.MinValue;
			int min = inputNum[0];

			for (int lp = 1; lp < inputNum.Length; lp++)
			{
				max = Math.Max (max, inputNum[lp] - min);
				min = Math.Min (min, inputNum[lp]);
			}
			
			//出力
			Console.WriteLine (max);

			return 0;
		}		
	}
}



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

using namespace std;

int linearSearch(vector<int>& A, int N, int key)
{
  int i = 0;
  A[N] = key;
  while (A[i] != key) {
    i++;
  }
  return i != N;
}

int main() {
  vector<int> A;
  A.reserve(10000 + 1);

  int N;
  cin >> N;
  A.resize(N  + 1);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  int M;
  int key;
  int sum = 0;

  cin >> M;
  for (int i = 0; i < M; i++) {
    cin >> key;
    if(linearSearch(A, N, key)) {
      sum++;
    }
  }
  cout<< sum << endl;

  return 0;
}


Measured memory_bytes: 3108
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
#include <set>
using namespace std;
typedef long long ll;

int a[10];

int main(int argc, char const *argv[]) {
	for (int i = 0; i < 10; i++) cin >> a[i];
	sort(a, a+10);
	for (int i = 9; i > 6; i--) cout << a[i] << endl;
	return 0;
}

Measured memory_bytes: 3124
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def my_round(a,dig=0):
    p = 10 ** dig
    return (a * p * 2 + 1) // 2 / p

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    a,b = map(int,input().split())
    if a % 2 == 0 or b % 2 == 0:
        print('No')
    else:
        print('Yes')
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 38508
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
#include<math.h>

using namespace std;

using p = pair<int, long long>;
using event = pair<long long, p>;

int main(){
  int n, q;
  cin >> n >> q;
  vector<event> v;
  for(int i = 0; i < n ; i++){
    int a,b,c;
    cin >> a >> b >> c;
    v.push_back(event(a-c, p(-1, c)));
    v.push_back(event(b-c, p(0, c)));
  }
  for(int i = 0; i < q; i++){
    int d; cin >> d;
    v.push_back(event(d, p(1, i)));
  }
  sort(v.begin(), v.end());

  multiset<long long> s;
  vector<long long> res(q);
  for(auto t : v){
    int w = t.second.first;
    long long val = t.second.second;
    if(w == -1) s.insert(val);
    else if(w == 0) s.erase(s.lower_bound(val));
    else res[val] = (s.empty() ? -1 : *(s.begin()));
  }
  for(auto v : res) cout << v << endl;
}


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

#ifdef LOCAL_DEBUG
#include "bits/mytest.h"
#endif

using namespace std;


 
class Solution{
#pragma region user
#define CLR(arr,val) fill(arr.begin(),arr.end(),val);
#define CLR0(arr)  CLR(arr,0)

#define d2clear(arr,data) for(int i =0;i<arr.size();i++){for(int j =0;j<arr[i].size();j++){arr[i][j]=data;}}
#define d2print(arr) for(int i =0;i<arr.size();i++){for(int j =0;j<arr[i].size();j++){cout<<arr[i][j];} cout<<endl;}
#define d2array(name,type,rows,cols,data) vector< vector<type>  > name(rows,vector<type>(cols,data))

#define FOR(i,N) for(auto i=0;i<N;i++)
#define RFOR(i,N) for(auto i=(N);i>=0;i--)
#define FORIT(arr,it) for(auto it=arr.begin();it!=arr.end();it++)
#define RFORIT(arr,it) for(auto it=arr.rbegin();it!=arr.rend();it++)

#define in(a,left,right) (a)<=(right)&&(a)>=(left)
#define notin(a,left,right) (a)<(left) && (a)>(right)

#define LL long long
#define A(n) n.begin(),n.end()
#define maxn(a,b) ((a)=((a)>(b)?(a):(b)))
#define minn(a,b) ((a)=((a)<(b)?(a):(b)))

#define min(a,b)  ( (a)<(b)?(a):(b)   )
#define max(a,b)  ( (a)>(b)?(a):(b)  )
#define println(a) cout<<a<<endl;
#define mp(a,b)  make_pair(a,b)
#pragma endregion
public:
	static const bool bMultiCase = false;
	void solve(istream & cin = std::cin, ostream & cout = std::cout){
		int k, t; cin >> k >> t;
		vector<int> arr(t);
		LL max_data = 0;
		FOR(i, t) {
			cin >> arr[i];
			maxn(max_data, arr[i]);
		}
		if (max_data > k - max_data) {
			cout << max_data - (k - max_data) - 1 << endl;
		}
		else {
			cout << 0 << endl;
		}
		
	}

};


int main() {
#ifdef LOCAL_DEBUG 
 
	MyTest::Judge::JudgeNormal judge;
	MyTest::Config config;
	config.judge = &judge;
	MyTest::Test test(config);

	const string ITEM_NAME("1.cpp");
	const string FILE_NAME(__FILE__);
	auto it=FILE_NAME.find_last_of('\\');
	auto inputfile = FILE_NAME.substr(0, it + 1) + ITEM_NAME.substr(0, ITEM_NAME.find_last_of('.')) + "_input.txt";
	auto outputfile = FILE_NAME.substr(0, it + 1) + ITEM_NAME.substr(0, ITEM_NAME.find_last_of('.')) + "_output.txt";
	freopen(inputfile.c_str(), "r", stdin);
	//freopen(outputfile.c_str(), "w", stdout);
	
	while (test.ReadCaseInOneFile()) {
		test.Begin();
		Solution s;
		s.solve(test.Input(),test.Output());
		test.End();
	}
	test.DisplayInfo();
#else   //online judge
	if (Solution::bMultiCase) {
		int t; cin >> t;
		while (t--) {
			Solution s;
			s.solve();
		}
	}
	else {
		Solution s;
		s.solve();
	}
#endif
	

 
	return 0;
}

Measured memory_bytes: 256
ans = []
while 1:
    N, M, T, P = map(int, input().split())
    if N == 0:
        break
    A = [[1]*N for i in range(M)]
    for i in range(T):
        d, c = map(int, input().split())
        if d == 1:
            B = [[0]*max(c, N-c) for i in range(M)]
            for x in range(N-c):
                for y in range(M):
                    B[y][x] = A[y][c+x]
            for x in range(c):
                for y in range(M):
                    B[y][x] += A[y][c-1-x]
            N = max(c, N-c)
        else:
            B = [[0]*N for i in range(max(c, M-c))]
            for x in range(N):
                for y in range(M-c):
                    B[y][x] = A[c+y][x]
            for x in range(N):
                for y in range(c):
                    B[y][x] += A[c-1-y][x]
            M = max(c, M-c)
        A = B
    cnt = 0
    for i in range(P):
        x, y = map(int, input().split())
        ans.append(B[y][x])
print(*ans, sep='\n')



Measured memory_bytes: 5884
while True:
	n=int(input())
	if n==0:
		break
	x=1000-n
	a=x%500
	b=a%100
	c=b%50
	d=c%10
	e=d%5
	f=x//500+a//100+b//50+c//10+d//5+e
	print(f)


Measured memory_bytes: 5584
#define rep(i,a,b) for(int i=a;i<b;++i)
#define repr(i,a,b) for(int i=a,i > b;--i)
#define mm(lamb, tttt) memset(lamb, tttt, sizeof lamb)

#define null NULL
#define eps 0.000000001
#define mod 1000000007
#define PI 3.14159265358979323846
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define ALL(V) V.begin(), V.end()
#define sz(V) (ll)V.size()
#define _ <<" "<<

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <iterator>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <limits.h>
#include <iomanip>
#include <cctype>
#include <numeric>
#include <complex>

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef pair <int, int> ii;
typedef pair<int, pair<int,int> > iii;
typedef vector<int> vii;

vi freq(26,0);

int main(){
	string s;
	cin>>s;
	rep(i,0,s.length()) freq[s[i]-'a']++;
	int first=27;
	//rep(i,0,26) cout<<freq[i]<<" ";cout<<endl;
	rep(i,0,26) {
		//cout<<i<<endl;
		if(freq[i]==0) {first=i;
		break;}
	}
	//cout<<first<<endl;
	if(first==27){
		if(s=="zyxwvutsrqponmlkjihgfedcba") cout<<-1<<endl;
		else{
			int idx=25;
			for(;idx>=1;idx--){
				if(s[idx] > s[idx-1]) break;
			}
			string ans;
			char less=s[idx-1];
			char more=s[idx];
			//char add;
			for(int k=idx-1;k<=25;k++){
				if(s[k] > less && s[k] < more) more=s[k];
			}
			for(int j=0;j<idx;j++){
				if(j!=idx-1) ans+=s[j];
				else ans+=more;
			}//cout<<ans.length()<<endl;
			cout<<ans<<endl;
		}
	}
	else{
		char c= first+'a';
		//cout<<first<<" M"<<endl;
		//cout<<c<<endl;
		cout<<s+c<<endl;
	}
}




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

using namespace std;
using ll = long long;
using ld = long double;

void solve(ll N, ll A, ll B) {
  ll ans = (N/(A+B))*A + min(N%(A+B),A);
  cout << ans << endl;
}

int main() {
  ll N;
  cin >> N;
  ll A;
  cin >> A;
  ll B;
  cin >> B;
  solve(N, A, B);
  return 0;
}


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

        int ans = in[n/2+1] - in[n/2];
        printf("%d\n", ans);
    }
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <utility>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define LL long long
#define INF 1000000001
#define mod 1000000007
using namespace std;
int keta(int n,int k){return (n/int(pow(10,double(k-1)))) % 10;} //nの下からk桁目
ll gcd(ll n,ll m){
	if(n<m){ll a=m;m=n;n=a;}
	ll r=n%m;
	while(r!=0){
		n=m;
		m=r;
		r=n%m;
	}
	return m;
}
ll lcm(ll n,ll m){
	return n*m/gcd(n,m);
}


int main(){
	int n,m;
	cin>>n>>m;
	if(n>m){
		int x=n;
		n=m;
		m=x;
	}
	if(m-n>1){
		cout<<0<<endl;
		return 0;
	}
	ll x=1;
	if(m==n){
		for(int i=n;i>0;i--){
			x*=i;
			x=x%mod;
		}
		x=(x*x)%mod;
		x=(x*2)%mod;
	}
	if(m==n+1){
		for(int i=n;i>0;i--){
			x*=i;
			x=x%mod;
		}
		x=(x*x)%mod;
		x=(x*m)%mod;
	}
	cout<<x<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef map<ll, ll> mpii;
typedef unordered_map<ll, ll> umpii;
 
#define pb(v) push_back(v)
#define all(v) v.begin(), v.end()
#define upb(v, key) (upper_bound(all(v), key) - v.begin())
#define lob(v, key) (lower_bound(all(v), key) - v.begin())
 
ll inf = 1e9;
ll INF = inf * 1ll * inf;
ll mod = 1e9 + 7;
double eps = 1e-9;
const ld pi = ld(3.1415926535897932384626433832795);
ll dr[] = {-1, 0, 0, 1};
ll dc[] = {0, 1, -1, 0};

void mod_add(ll &a, ll b) {
  a += b;
  if(a > mod) a -= mod;
}
void mod_sub(ll &a, ll b) {
  a -= b;
  if(a < 0) a += mod;
}

//only for variables and vectors; 
template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}
template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)

/*...................................................*/

main()
{
  ios_base::sync_with_stdio(false), cin.tie(NULL);
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);

  ll t, n, m, i, j, k, q, u, v;
  // cin >> t;
  // ll tc = t;
  t = 1;
  while (t--)
  {
    cin >> n >> m;
    vi boxes(m), cost(m);
    for(i = 0; i < m; i++) {
      cin >> cost[i] >> k;
      while(k--) {
        ll b;
        cin >> b; b--;
        boxes[i] |= (1 << b);
      }
    }
    
    vvi dp(m + 1, vi(1 << n, inf));
    dp[0][0] = 0;
    for(i = 0; i < m; i++) 
    for(int msk = 0; msk < (1 << n); msk++) {
      dp[i + 1][msk] = min(dp[i + 1][msk], dp[i][msk]);
      dp[i + 1][msk | boxes[i]] = min(dp[i + 1][msk | boxes[i]], dp[i][msk] + cost[i]);
    }
    cout << (dp[m][(1 << n) - 1] == inf ? -1: dp[m][(1 << n) - 1]);
    // cout << "Case #" << tc - t << ": ";

    cout << '\n';
  }
}

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

int main () {
    int N;
    cin >> N;
    vector<int>vec(N);
    int sum = 0;
    
    for (int t = 0; t < N; t++) {
        cin >> vec.at(t);
    }
    
    sort(vec.begin(), vec.end());
    
    for (int t = 0; t < vec.size(); t++) {
        if (t == 0) {
            sum += 1;
        } else {
            if (vec.at(t) == vec.at(t-1)) {
                sum += 0;
            } else {
                sum += 1;
            }
        }
    }
    cout << sum << endl;
    
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

void solve(){
	int N, A, B, C, D; cin >> N >> A >> B >> C >> D;
	for(int i=0;i<=N-1;i++) {
		ll low = (ll)(N-1-i) * C - (ll)i * D;
		ll high = (ll)(N-1-i) * D - (ll)i * C;
		ll t = A - B;
		if(low <= t && t <= high) {
			puts("YES"); return;
		}
	}
	puts("NO");
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		// printf("Case #%d: ", tc);
		solve();
	}
	return 0;
};


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String s = sc.next();
        char[] c = s.toCharArray();
        if(c.length <= k){
            System.out.println(s);
        }else{
            System.out.println(s.substring(0, k) + "...");
        }
    }
}


Measured memory_bytes: 27008
#include "bits/stdc++.h"
#include <set>

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}
template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}

signed main(void) {
	string s, t;
	cin >> s >> t;
	int n = s.size();
	bool same = false;
	if (s == t)same = true;
	rep(i, n) {
		string s1 = s.substr(n - 1, 1);
		string s2 = s.substr(0, n - 1);
		s = s1+s2;
		if (s == t)same = true;
	}
	if (same)print("Yes");
	else print("No");
}

Measured memory_bytes: 256
h,w=map(int,input().split())
b=["n"*(w+2)]
for i in range(h):b.append("n"+input()+"n")
b.append(b[0])
def num(i,j):
  a=0
  def same(i,j):
    global b
    if b[i][j]=="#":return 1
    return 0
  a+=same(i-1,j-1)
  a+=same(i-1,j)
  a+=same(i-1,j+1)
  a+=same(i,j-1)
  a+=same(i,j+1)
  a+=same(i+1,j-1)
  a+=same(i+1,j)
  a+=same(i+1,j+1)
  return a
for i in range(len(b)):
  if 0<i<h+1:
    for j in range(len(b[i])):
      if b[i][j]==".":b[i]=b[i][:j]+str(num(i,j))+b[i][j+1:]
for i in range(1,h+1):print(b[i][1:w+1])


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define pb push_back
#define ff first
#define ss second
#define sz size()
#define mp make_pair
#define p(x) cout<< x << " ";
#define pe(x) cout<< x << endl ;
#define deb(x) cout<<#x<<" : "<<x<<endl;
#define debug(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
#define el endl
#define M 998244353 
#define int long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROR(i,a,b) for(int i=a;i>=b;i--)
const int N = 1e5 + 5;

int32_t main() 
{ 
    int n,k;
    cin>>n>>k;
    if(k==1 || k>=n)
    cout<<"0";
    else
    {
        cout<<n-k;
    }
} 

Measured memory_bytes: 256