akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;

long long MOD = 1000000007;

int main(){
    int N;
    cin >> N;
    vector<int> A(N,0);

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

    int cnt=0;
    for(int i=0; i<=N; i++){
        if(A[i]==cnt+1){
            cnt++;
        }
    }
    if(cnt==0){
        cnt=-1;
    }else{
        cnt=N-cnt;
    }
    cout << cnt << endl;
}

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

signed main(){
    int N,M; cin>>N>>M;
    int ans=1;
    int mod=1000000007;
    if(abs(N-M)>1){
        cout<<0<<endl;
        return 0;
    }
    rep(i,N) ans=ans*(i+1)%mod;
    rep(i,M) ans=ans*(i+1)%mod;
    if(N==M) cout<<(2*ans)%mod<<endl;
    else cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void)
{
	char a[3][100];
	int x,y,i,w[3],j,p[3];
	for(i=0;i<3;i++) w[i]=0;
	for(i=0;i<3;i++){
		scanf("%s",a[i]); w[i]=strlen(a[i]); p[i]=0;
	}	
	x=0;
	while(1){
		y=a[x][p[x]]-'a';
		p[x]++;
		x=y;
		if(p[x]==w[x]) break;
	}
	printf("%c\n",x+'A');
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

#define P 10007
#define modp(x) ((((x)%P)+P)%P)

int fac[40];

int calc2(int n,int a,int b,int c,int d){
	vector<int> hoge(n+1);
	hoge[0]=1;
	for(int t=0;t<a;t++){
		for(int i=n;i>=0;i--){
			if(i>=1)hoge[i]=modp(hoge[i]+4*hoge[i-1]);
			if(i>=2)hoge[i]=modp(hoge[i]+2*hoge[i-2]);
		}
	}
	for(int t=0;t<b;t++){
		for(int i=n;i>=0;i--){
			if(i>=1)hoge[i]=modp(hoge[i]+2*hoge[i-1]);
		}
	}
	for(int t=0;t<c;t++){
		for(int i=n;i>=0;i--){
			if(i>=1)hoge[i]=modp(hoge[i]+2*hoge[i-1]);
		}
	}
	for(int t=0;t<d;t++){
		for(int i=n;i>=0;i--){
			if(i>=1)hoge[i]=modp(hoge[i]+hoge[i-1]);
		}
	}
	int ret=0;
	for(int i=0;i<=n;i++){
		ret=modp(ret+fac[n-i]*hoge[i]*(i%2==0?1:-1));
	}
	return ret;
}

int calc(int n,vector<pair<int,int> > ng){
	int k=ng.size();
	int ret=0;
	for(int b=0;b<(1<<k);b++){
		bool collide=false;
		for(int i=0;i<k;i++)for(int j=0;j<k;j++)if(i!=j && (b&(1<<i))!=0 && (b&(1<<j))!=0 && (ng[i].first==ng[j].first || ng[i].second==ng[j].second))collide=true;
		if(collide)continue;
		for(int d=0;d<4;d++){
			int sn=((__builtin_popcount(b)+__builtin_popcount(d))%2==0)?1:-1;
			bool ok=true;
			if(d&1){
				for(int i=0;i<k;i++)if((b&(1<<i))!=0 && ng[i].first==ng[i].second)ok=false;
			}
			if(d&2){
				for(int i=0;i<k;i++)if((b&(1<<i))!=0 && ng[i].first==n-1-ng[i].second)ok=false;
			}
			if(ok){
				vector<int> row(n),col(n);
				for(int i=0;i<k;i++)if((b&(1<<i))!=0)row[ng[i].first]=col[ng[i].second]=1;
				//calculate parameters
				int m=n-__builtin_popcount(b),p=0,q=0,r=0,s=0;
				if(d==1){
					for(int i=0;i<n;i++)if(row[i]==0&&col[i]==0)s++;
				}
				if(d==2){
					for(int i=0;i<n;i++)if(row[i]==0&&col[n-1-i]==0)s++;
				}
				if(d==3){
					for(int i=0;i<n-1-i;i++){
						if(row[i]+row[n-1-i]==0 && col[i]+col[n-1-i]==0)p++;
						if(row[i]+row[n-1-i]==0 && col[i]+col[n-1-i]==1)q++;
						if(row[i]+row[n-1-i]==1 && col[i]+col[n-1-i]==0)r++;
						if(row[i]+row[n-1-i]==1 && col[i]+col[n-1-i]==1)s++;
						
					}
					if((n-1)%2==0 && row[(n-1)/2]==0 && col[(n-1)/2]==0)s++;
				}
				ret=modp(ret+sn*calc2(m,p,q,r,s));
			}
		}
	}
	return ret;
}

main(){
	fac[0]=1;for(int i=1;i<40;i++)fac[i]=modp(fac[i-1]*i);
	int n,k;
	scanf("%d%d",&n,&k);
	vector<pair<int,int> > ng(k);
	for(int i=0;i<k;i++)scanf("%d%d",&ng[i].first,&ng[i].second);
	printf("%d\n",calc(n,ng));
}

Measured memory_bytes: 1040
#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <cstring>
#include <climits>
#include <iomanip>

#define EPS 1e-7
#define LLMAX 9223372036854775807
#define INTMAX 2147483647
#define ULLMAX 18446744073709551615
#define precision(n) cout << setprecision(n) << fixed
#define forn(i, n) for (int i = 0; i<(int)n; ++i)
#define forr(i, t, n) for (int i = t; i<n; ++i)
#define rforr(i, t, n) (int i = n-1; i>=t; --i)
#define rfor(i, n) for (int i = n-1; i>=0; --i)
#define rmod(x, y) (((x%y)+y)%y)
#define pb push_back
#define emp emplace_back
using namespace std;
typedef vector<int>::iterator vit;
typedef unsigned int uint;
typedef unsigned short ushort;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int MAXN = 1024;

//STRUCTS


//OPERATORS


//GLOBALS


//FUNCTIONS


//PROBLEM: 
//LINK: 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
		int n, k;
		cin >> n >> k;
		int q;
		int ans = 0;
		forn(i, n) 
		{
			cin >> q;
			if (q>=k) ans++;
		}
		cout << ans;



	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
template <class T>
inline bool chmax(T &a, T b)
{
	if (a < b)
	{
		a = b;
		return 1;
	}
	return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
	if (a > b)
	{
		a = b;
		return 1;
	}
	return 0;
}
const long long INFLL = 1LL << 60;
const int INF = 1 << 28;
const long long MOD = 1000000000 + 7;



int main()
{
	string s;
	cin >> s;
	int legth=s.size();
	vector<int>ans(legth,0);
	int len=0;
	for(int i=0;i<legth;i++){
		if(s[i]=='R'){
			len++;
		}else{
			if(len >=1){
				ans[i]+=len/2;
				ans[i-1]+=(len+1)/2;
				len=0;
			}

		}
	}
	if(len >0){
		ans[legth-1]+=len;
	}
	len=0;
	for(int i=legth-1;i>=0;i--){
		if(s[i]=='L'){
			len++;
		}else{
			if (len >= 1)
			{
				ans[i] += len / 2;
				ans[i + 1] += (len + 1) / 2;
				len = 0;
			}
		}
	}
	if (len > 0)
	{
		ans[0] += len;
	}
	for(int i=0;i<legth;i++){
		if(i!=0){
			cout <<" ";
		}
		cout<<ans[i];
	}
	cout << endl;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, x[100005], m, mk[100005], mini=0, maxi=0;
long long sum = 0;

struct dif{
    int diferencia, idx, num;
};
dif d[100005];

bool compare(dif a, dif b){
    if(a.diferencia == b.diferencia)
        return a.idx < b.idx;

    return a.diferencia > b.diferencia;
}
bool compare2(dif a, dif b){
    return a.idx < b.idx;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++)
        scanf("%d", &x[i]);

    sort(x, x+m);
    for(int i=0; i<m-1; i++){
        d[i].diferencia = x[i+1]-x[i];
        d[i].idx = i;
        d[i].num = x[i];
        sum += d[i].diferencia;
    }
    sort(d, d+m-1, compare);
    sum =0;
    for(int i=0; i<m-1; i++){
        if(n > 1){
            n--;
            mk[d[i].idx]=1;

        } else {
            sum += d[i].diferencia;
            //printf("%d  ", d[i].diferencia);
            //break;
        }
    }
    printf("%lld\n", sum);
    //sort(d, d+m-1, compare2);

    /*for(int i=0; i<m-1; i++){
        printf("%d  ", mk[i]);
    }
    printf("\n");
    for(int i=0; i<m; i++){
        printf("%d  ", x[i]);
    }*/
    //printf("\n");
   /* bool num=false, pt=false;
    mini = 100000, maxi=-1000000;

    for(int i=0; i<m; i++){
       // printf("%d %d\n", x[i], mk[i]);
        if(mk[i] == 0){
           // printf("no punto\n");
            mini = min(mini, x[i]);
            maxi = max(maxi, x[i]);
            num = true;
        } else {
            //printf("punto  -> ");
            if(num){
               // printf("num verd\n");
                mini = min(mini, x[i]);
                maxi = max(maxi, x[i]);
                sum +=(maxi-mini);
                //printf("%d %d\n", mini, maxi);
                mini = 100000;
                maxi = -100000;
                num=false;
                pt = false;
            } else if (!num && !pt){
               // printf("num falso\n");
                pt=true;
                mini = min(mini, x[i]);
                maxi = max(maxi, x[i]);
            } else if(pt){
                //printf("pt verdader0\n");
                sum +=(maxi-mini);
               // printf("%d\n", maxi-mini);
                mini = 100000;
                maxi = -100000;
                mini = min(mini, x[i]);
                maxi = max(maxi, x[i]);
                num=true;
                pt = false;
            }
        }
    }
    if(maxi !=0)
        sum += (maxi-mini);
    */
    //printf("%lld\n", sum);
}


Measured memory_bytes: 2048
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

typedef pair<int, int> BC;
#define mp(a, b) make_pair(a, b)

int main(int argc, char const *argv[]) {
  int a, p;

  cin >> a;
  cin >> p;

  cout << (3 * a + p) / 2;

  return 0;
}


Measured memory_bytes: 256
def tr(a,b,c):
	l = a*a
	m = b*b
	n = c*c
	if(l+m==n or m+n==l or l+n==m):
		print "YES"
	else:
		print "NO"
for i in range(int(raw_input())):
	(l,m,n) = map(int,raw_input().split())
	tr(l,m,n)

Measured memory_bytes: 4224
/// kAAzuki Hoshino
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
#define inf 1000000000
#define mod 1000000007
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define rep1(i, a, b) for(int i =a; i >=b; i--)
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple

int n,m,ans;
vpi v;

signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

cin >> n >> m;
for(int i=1;i<=n;i++){
 int x,y;
 cin >> x >> y;
 v.pb({x,y});
}
sort(all(v));
for(auto t:v){
 if(m){
  ans+= min(m,t.sc)*t.fs;
  m-= min(m,t.sc);
 }
}
cout << ans << endl;

return 0;
}
///....


Measured memory_bytes: 2420
import heapq

N, M = map(int, input().split())
A = [-1 * int(a) for a in input().split()]
heapq.heapify(A)

for _ in range(M):
    tmp_min = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmp_min//2))
print(-sum(A))

Measured memory_bytes: 14180
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
const char newl = '\n';
typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;
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; }
const long long INF = 1LL<<60;

int main(){
    Int n;cin >> n;
    Int m,a,r,c,h;
    int p[10]={0,0,0,0,0,0,1,1,1,2};
    int q[10]={1,1,1,2,2,3,2,2,3,3};
    int k[10]={2,3,4,3,4,4,3,4,4,4};
    m = 0,a=0,r=0,c=0,h=0;
    rep(i,n){
        string s;
        cin >> s;
        if(s[0]=='M') m++;
        if(s[0]=='A') a++;
        if(s[0]=='R') r++;
        if(s[0]=='C') c++;
        if(s[0]=='H') h++;
    }
    Int d[5];
    d[0] = m,d[1] = a,d[2] = r,d[3] = c,d[4] = h;
    Int ans = 0;
    rep(i,10){
        ans+=d[p[i]]*d[q[i]]*d[k[i]];
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
        int n,m,sum=0,a;
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
                cin >> a;
                sum += a;
        }   
        if (n - sum >= 0)
                cout << (n - sum) << endl;
        else
                cout << "-1" << endl;
        return 0;
}

Measured memory_bytes: 3624
program modularness
  implicit none
  integer :: k, q, n, p, r, s, i, j
  integer(8) :: d(0:5000) = 0, x, m, dj, dn, a
  read(*,*) k, q
  read(*,*) d(0:k - 1)
  do i = 1, q
    read(*,*) n, x, m
    p = (n - 1) / k
    r = mod(n - 1, k)
    dn = x
    a = n - 1
    do j = 0, k - 1
      s = p + merge(1, 0, j < r)
      dj = mod(d(j), m)
      if (dj == 0) a = a - s
      dn = dn + dj * s
    end do
    a = a - dn / m + x / m
    write(*,'(i0)') a
  end do
end program modularness

Measured memory_bytes: 2928
import math
N=int(input())
L=math.log10(N)

if L<1.:
    print(N)
elif 1.<= L < 2.:
    print(9)
elif 2.<= L < 3.:
    print(N-100+1+9)
elif 3.<= L < 4.:
    print(909)
elif 4.<= L < 5.:
    print(N-10000+1+909)
elif L==5.:
    print(90909)

Measured memory_bytes: 3060
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;


int main(){
string a,b;
cin >> a >> b;
int N = stoi(a + b);
bool ok = false;
for(int i = 0; i <= N; i++){
    if(i*i == N)ok = true;
}

if(ok)cout << "Yes" << endl;
else cout << "No" << endl;
}

Measured memory_bytes: 256
N = int(input())
l = list(map(int, input().split()))

result = 0
i = 0

while(i < N - 1):
  if(l[i] == l[i + 1]):
    i += 1
    continue
  elif(l[i] < l[i + 1]):
    while(i < N - 1 and l[i] <= l[i + 1]):
      i += 1
  else:
    while(i < N - 1 and l[i] >= l[i + 1]):
      i += 1
  result += 1
  i += 1

if(i == N - 1):
  result += 1
  
print(result)

Measured memory_bytes: 14252
S = input()
front = int(S[0:2])
back = int(S[2:4])
if 1 <= front <= 12:
    if 1 <= back <= 12:
        print("AMBIGUOUS")
    else:
        print("MMYY")
elif 1 <= back <= 12:
    print("YYMM")
else:
    print("NA")


Measured memory_bytes: 3064
P = 10 ** 9 + 7
N = int(input())
k = (N-1) ** 2 % P + 2
a, b, c = 1, 0, 0
ans = 0
for i in range(N-1):
    ans += a * (k + min(i, N-3))
    ans %= P
    a, b, c = a + b, b + c, a
    if a >= P: a -= P
    if b >= P: b -= P

ans += N * a
ans %= P
print(ans)

Measured memory_bytes: 40940
#include<bits/stdc++.h>
#define int long long int
#define hell (int)(1e9+7)
#define inf 1000000000000

using namespace std;

void solve(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(x%2==0&&x%3!=0&&x%5!=0){
            cout<<"DENIED";
            return;
        }
    }
    cout<<"APPROVED";
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t,c;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 256
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Nの制約が1000,円の中心を飛び石→dijkstra
sx, sy, gx, gy = lr()
N = ir()
XYR = [[sx, sy, 0]] + [lr() for _ in range(N)] + [[gx, gy, 0]]
graph = [[] for _ in range(N+2)]  # 0がstart,N+1がgoal
for i in range(N+2):
    for j in range(i+1, N+2):
        sp = XYR[i]; ep = XYR[j]
        length = max(0, ((sp[0]-ep[0]) ** 2 + (sp[1]-ep[1]) ** 2) ** .5 - sp[2] - ep[2])
        graph[i].append((j, length))
        graph[j].append((i, length))

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * (N+2)
    dist[start] = 0
    que = [(0, start)]
    visited = set()
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next, l in graph[prev]:
            if next == prev or next in visited:
                continue
            d1 = d + l
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
        visited.add(prev)
    return dist

dist = dijkstra(0)
answer = dist[N+1]
print(answer)
# 46


Measured memory_bytes: 126808
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define segment_size 65536
#define ROOP() while (true)

int main(){
    
    int a,b;
    cin >> a >> b;
    cout << abs(a-b) << endl;
    
    return 0;
}


Measured memory_bytes: 3096
import re

def calc(op, a, b):
    if op == '+' :
        return a + b
    elif op == '-':
        return a - b
    elif op == '*':
        return a * b
    elif op == '/':
        return a // b
    
    return None


EOL = re.compile(r'^\w+\s\?\s\w+$')
MAX = 20000

for _ in range(MAX):
  line = input()
  if EOL.match(line):
    break
  
  # ここに処理 a, b は int に変換せよ
  a, op, b = line.split()
  print(calc(op, int(a), int(b)))
  


Measured memory_bytes: 6536
H, W = map(int, input().split())

res = 0

#odd : (W+1) // 2
#even : W // 2

r = (W+1) // 2 + W // 2
if W == 1 or H == 1:
  print(1)
elif H % 2 == 0:
  print( r * (H // 2))
else:
  print( r * (H // 2) + (W+1)//2)


Measured memory_bytes: 2940
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,x,t;
    string str;
    cin>>n>>x>>t;
    if(n%x!=0){
    cout<<(n/x+1)*t;
    }else cout<<n/x*t;
    }


Measured memory_bytes: 3580
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);    
        int N=0;
        N = sc.nextInt();
        int[] A;
        A = new int[N];
        int i=0;
        for(i=0;i<N;i++){
            A[i] = sc.nextInt();
        }
        int j;
        int k;
        int z;
        int swap = 0;
        for(j=0;j<N-1;j++){
            for(k=0;k<N-1;k++){
                if(A[k]>A[k+1]){
                    z = A[k];
                    A[k] = A[k+1];
                    A[k+1] = z;
                    swap++;
                }
            }
        }

        for(i=0;i<N-1;i++){
            System.out.print(A[i]+" ");
        }
        System.out.println(A[N-1]);
        System.out.println(swap);   
        sc.close();
    }
}


Measured memory_bytes: 26324
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define rrep(i,n) for(int i=(n);i>=0;--i)
#define ssort(n) sort((n).begin(),(n).end())
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define INF 10101010

int main()
{
    int N,K;

    cin >> N >> K;
    vector<int> p(N);
    rep(i,N)cin >> p[i];
    ssort(p);
    ll ans=0;
    rep(i,K)ans+=p[i];
    cout << ans << endl;

}

Measured memory_bytes: 3596
import math

K = int(input())
count = 0
for i in range(1 ,K + 1 ,1):
    for j in range(1, K + 1, 1):
        for l in range(1 ,K + 1 ,1):
            count += math.gcd(math.gcd(i, j), l)
print(count)

Measured memory_bytes: 67820
/*
    Author: isaf27 (Ivan Safonov)
*/

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

//defines
typedef long long ll;
typedef long double ld;
#define TIME clock() * 1.0 / CLOCKS_PER_SEC

//permanent constants
const ld pi = acos(-1.0);
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int dxt[6] = {0, 0, -1, -1, 1, 1};
const int dyt[6] = {-2, 2, 1, -1, -1, 1};
const int alf = 26;
const int dig = 10;
const int two = 2;
const int th = 3;
const ll prost = 239;
const ll bt = 30;
const ld eps = 1e-8;
const ll INF = 1e18 + 239;
const int BIG = 1e9 + 239;
const int MOD = 1e9 + 7; //998244353;
const ll MOD2 = (ll)MOD * (ll)MOD;

//random
mt19937 rnd(239); //rnd(chrono::high_resolution_clock::now().time_since_epoch().count())

//constants
const int M = 2e5 + 239;
const int N = 2e3 + 239;
const int L = 20;
const int T = (1 << 20);
const int B = trunc(sqrt(M)) + 1;
const int X = 1e4 + 239;

int kol[4];

int32_t main()
{
    #ifdef ONPC
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    memset(kol, 0, sizeof(kol));
    for (int i = 0; i < 3; i++)
    {
        int s, f;
        cin >> s >> f;
        s--, f--;
        kol[s]++;
        kol[f]++;
    }
    for (int i = 0; i < 4; i++)
        if (kol[i] == 3)
    {
        cout << "NO";
        return 0;
    }
    cout << "YES";
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
    //static List<string> str = new List<string>();
    static void Main(string[] args)
    {
        // 入力
        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]);
        int A = int.Parse(input[1]);
        int B = int.Parse(input[2]);
        int C = int.Parse(input[3]);

        int ret = -1;
        List<int> bumboo = new List<int>();
        for (int i = 0; i < N; i++ )
        {
            int a = int.Parse(Console.ReadLine());
            bumboo.Add(a);
        }
    
        // 最大８本の竹をA/B/C/使わない 場合を全探索する
        int pow = (int)Math.Pow(4, N);
        //Console.WriteLine(pow);
        for (int i = 0; i < pow; i++ )
        {
            //bool isDone = false; // ABC全て作れたか？
            List<int> abc = new List<int>() { A, B, C };
            int bumboo_choice = i;
            int mp = 0; // 消費MP
            string str = "";
            //if (bumboo_choice == 937) Console.WriteLine(bumboo_choice);
            for(int j = 0; j<N; j++)
            {
                // j番目の竹を振り分ける
                str += bumboo_choice % 4 + " ";
                switch(bumboo_choice%4)
                {
                    case 0:
                        // 使わない
                        break;
                    case 1:
                        // A
                        if (abc[0] != A) mp += 10;
                        abc[0] -= bumboo[j];
                        break;
                    case 2:
                        // B
                        if (abc[1] != B) mp += 10;
                        abc[1] -= bumboo[j];
                        break;
                    case 3:
                        // C
                        if (abc[2] != C) mp += 10;
                        abc[2] -= bumboo[j];
                        break;
                }
                bumboo_choice /= 4;
            }

            if (abc[0] == A || abc[1] == B || abc[2] == C)
            {
                //Console.WriteLine(" false");
                continue;
            }

            mp += Math.Abs(abc[0]) + Math.Abs(abc[1]) + Math.Abs(abc[2]);

            

            if (ret == -1 || mp < ret)
            {
                //Console.WriteLine(str + mp + " abc:" + abc[0] + " " + abc[1] + " " + abc[2]);
                ret = mp;
            }
        }
        Console.WriteLine(ret);
    }

}

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

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

int main(){
    int A, B ,C;

    cin >> A >> B >> C;

    cout << max(0,(C-(A-B))) << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
using namespace std;

int main(){
	int n;
	int a = 100000;

	cin >> n;
	for (int i = 0; i < n; i++){
		a *= 1.05;
		if (a % 1000 != 0){
			a = (a / 1000 + 1) * 1000;
		}
	}
	cout << a << endl;
}


Measured memory_bytes: 2988
#include <iostream>
#include <vector>
using namespace std;
const long long mod = (1e9) + 7;

int main(){
  int N;
  cin >> N;
  vector<string> S(2);
  for(int i = 0; i < 2; ++i) cin >> S[i];
  long long ans = 3;
  for(int i = 0; i < N; ++i){
    
    if(S[0][i] != S[1][i]){
      if(i > 0 && S[0][i-1] != S[1][i-1])
        ans *= 3;
      else ans *= 2;
      ans %= mod;
      ++i;
    }else if(i > 0 && S[0][i-1] == S[1][i-1]){
      ans *= 2;
      ans %= mod;
    }
  }
  cout << ans << endl;
  return 0;
}


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


int main(void){
  int N;
  cin >> N;
  bool ans = false;

  for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      int sum = i*4 + j*7;
      if(sum == N) ans = true;
    }
  }

  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        h: usize,
        _w: usize,
        cs: [String; h],
    }
    for c in cs {
        println!("{}", c);
        println!("{}", c);
    }
}


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

res = 1 << 30

for t in range(n-1):
    less = sum([w[i] for i in range(t+1)])
    over = sum([w[i] for i in range(t+1, n)])
    res = min(res, abs(less - over))

print(res)

Measured memory_bytes: 3060
import java.util.Scanner;

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

        int n = Integer.parseInt(sc.next());

        int r0 = Integer.parseInt(sc.next());
        int r1 = Integer.parseInt(sc.next());

        int max = r1-r0;
        int min = Math.min(r0,r1);

        for(int i = 2; i < n; i++){
            int r = Integer.parseInt(sc.next());
            max = Math.max(max, r - min);
            min = Math.min(min,r);
        }
        
        System.out.println(max);
    }
}


Measured memory_bytes: 70836
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=1000000007;
const ll INF=1000000000000LL;
const int MAX=100001;
const double EPS=1e-10;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> G[100010];
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int l=0;int r=G[0][0];
    bool p[100010]={false};
    p[l]=true;p[r]=true;
    deque<int> q;
    q.push_front(l);q.push_back(r);
    int s=2;
    while(1){
        bool f=true;
        vector<int> v;
        int L=l;int R=r;
        for(auto e:G[L]){
            if(!p[e]){
                f=false;
                l=e;
                q.push_front(l);
                p[l]=true;
                s++;
                break;
            }
        }
        for(auto e:G[R]){
            if(!p[e]){
                f=false;
                r=e;
                q.push_back(r);
                s++;
                p[r]=true;
                break;
            }
        }
        if(f){
            break;
        }
    }
    cout<<s<<endl;
    for(int i=0;i<(int)q.size();i++){
        cout<<q[i]+1;
        if(i==(int)q.size()-1){
            cout<<endl;
        }else{
            cout<<" ";
        }
    }
}


Measured memory_bytes: 7552
[N,A,B] = list(map(int,input().split()))
out=0

for dam in range(1,N+1):
    L = list(str(dam))
    wa=0
    for i in range(len(L)):
        wa+=int(L[i])
    if wa>=A and wa<=B:
        out+=int(''.join(L))
    # print('L,wa,out:',L,wa,out)

print(out)

Measured memory_bytes: 73200
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
//using System.Numerics;
using static System.Math;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;


    void solve()
    {
        int N = cin.nextint;
        var T = cin.scanint;
        var V = cin.scanint;
        V = V.Concat(new int[] { 0 }).ToArray();
        var time = T.Sum();

        var B = new int[N + 1];
        B[N] = 0;
        int nowtime = 0;
        for (int i = N - 1; i >= 1; i--)
        {
            nowtime += T[i];
            int limit = Min(V[i], V[i - 1]);
            B[i] = Min(B[i + 1] + T[i], limit);
        }

        int speed = 0;
        double ans = 0;
        for (int i = 0; i < N; i++)
        {

            int nextspeed = Min(Min(V[i], V[i + 1]), Min(B[i + 1], speed + T[i]));
            var a = (T[i] + nextspeed - speed) / (double)2;
            var b = T[i] - a;
            var maxspeed = speed + a;
            if (maxspeed > V[i])
            {
                ans -= (maxspeed - V[i]) * (maxspeed - V[i]);
            }
            ans += (speed + maxspeed) * a / 2 + (maxspeed + nextspeed) * b / 2;

            speed = nextspeed;
        }
        WriteLine(ans.ToString("F4"));
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 13396
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;




int main(){
	string s, t;
	bool flg = true;
	vector<pair<char, char> > vec;
	cin >> s >> t;
	for (int i = 0; i < s.length(); i++){
		bool exist = false;
		for (int j = 0; j < vec.size(); j++){
			if (s[i] == vec[j].first){
				exist = true;
				if (t[i] != vec[j].second){
					flg = false;
				}
			}
		}
		if (!exist){
			for (int j = 0; j < vec.size(); j++){
				if (t[i] == vec[j].second) flg = false;
			}
			vec.push_back(make_pair(s[i], t[i]));
		}
	}
	if (flg) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 776
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef vector<int> vec;
//配列の添字ズレに注意
//=に注意
int main(){
  long ans=0,n;cin>>n;
  long a[n];
  rep(i,n)cin>>a[i];
  
  for(int i=1;i<n;i++){
    if(a[i-1]>a[i]){
      ans+=a[i-1]-a[i];
      a[i]=a[i-1];
    
    }
  
  
  }

  
  cout<<ans<<endl;
}


Measured memory_bytes: 5184
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cctype>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<int(b); i++)
#define rep(i,b) loop(i,0,b)
#define all(c) (c).begin(), (c).end()

char const op='[';
char const cl=']';
typedef vector<int> vi;
#define isd isdigit

namespace std {
  ostream& operator<<(ostream& os, const vi& v){
    rep(i,v.size()){
      os << v[i] << " ";
    }
    return os;
  }
}


int get(int & i, string s){
  int res = 0;
  while(isd(s[i])){
    res*=10;
    res+=s[i]-'0';
    i++;
  }
  return res;
}

string tos(int i){
  stringstream ss;
  ss << i;
  return ss.str();
}

vi parse(string s){
  vi res;
  int n = s.size();
  for(int i=0; i<s.size();i++){
    if(isdigit(s[i])){
      int t=get(i,s);
      res.push_back(t);
    }	
  }
  // rep(i,res.size()){
  //   cout << res[i] << " ";
  // }  cout << endl;
  return res;
}

int solve(string s){
  int n =s.size();
    bool begin = true;
  while(1){
    for(int i=0; i+2<s.size(); i++){
      string sss = "[";
      if(s[i]==op && s[i+1]==op && isdigit(s[i+2])){
	int j=0;
	while(!(isd(s[i+2+j]) && s[i+2+j+1]==cl && s[i+2+j+2]==cl)){
	  j++;
	}

	vi c = parse(s.substr(i+1,j+3));
	sort(all(c));
	int k=0;
	if(begin){
	  rep(x,(c.size()+1)/2){
	    if(c[x]%2 == 0) k+=c[x]/2+1;
	    else k+=(c[x]+1)/2;
	  }
	} else {
	  rep(x,(c.size()+1)/2){
	    k+=c[x];
	  }
	}
	sss+= tos(k);
	s.replace(i, j+4, sss);
      }
    }
    begin = false;
    // cout << s << endl;
    if(s[2]!=op){
      int ans = 0;
      vi v = parse(s);
      sort(all(v));
      rep(i,v.size()/2+1){
	ans += v[i];
      }
      return ans;
    }
  }
  int i=1;
  return get(i,s);

}

int main(){
  int n;
  cin>>n;
  rep(i,n){
    string s; cin>>s;
    cout << solve(s) << endl;
  }
}

Measured memory_bytes: 1324
/*
author : seryu
title : ABC176E_"Bomber"
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define mreps(i,j,n) for(int i = j; i <= n; i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(all(x), val), x.end())
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }

//vector<pair<int,int>>の比較関数
bool compare_by_second(pair<int, int> a, pair<int, int> b)
{
    if (a.first != b.first)return a.first < b.first;
    else return a.second < b.second;
}

void solve()
{
    int h, w, m;
    cin >> h >> w >> m;
    vector<P> r_sum, c_sum;
    rep(i, h)r_sum.push_back({0, i});
    rep(i, w)c_sum.push_back({0, i});
    vector<P> obj;
    rep(i, m)
    {
        int a, b;
        cin >> a >> b;
        a--;b--;
        obj.push_back({a, b});
        r_sum[a].first++;
        c_sum[b].first++;
    }
    sort(all(obj));
    sort(all(r_sum));
    reverse(all(r_sum));
    sort(all(c_sum));
    reverse(all(c_sum));
    int ans = 0;
    int i_r = 0, i_c = 0;
    int last_r = r_sum[i_r].first, last_c = c_sum[i_c].first;
    while (true)
    {
        int tmp = last_r + last_c;
        int r = r_sum[i_r].second;
        int c = c_sum[i_c].second;
        
        bool cross = [&]{
            int left = 0, right = m;
            while (left <= right)
            {
                int mid = (left+right)/2;
                if (obj[mid].first == r && obj[mid].second == c)return true;
                else if(obj[mid].first < r) left = mid+1;
                else if(obj[mid].first > r) right = mid-1;
                else if(obj[mid].second < c)left = mid+1;
                else right = mid-1;
            }
            return false;
        }();

        if(cross)tmp--;
        chmax(ans, tmp);
        if (i_r+1 < h && r_sum[i_r+1].first == last_r)
        {
            i_r++;
        }
        else if (i_c+1 < w && c_sum[i_c+1].first == last_c)
        {
            i_c++;
        }
        else
        {
            break;
        }        
    }
    cout << ans << endl;
    return;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 13876
n=int(input())
h=list(map(int,input().split()))
c=1
for i in range(1,n):
    if h[-i-1]>h[-i]:
        if h[-i-1]-1==h[-i]:
            h[-i-1]-=1
            c+=1
        else:
            print('No')
            break
    else:
        c+=1
if c==n:print('Yes')

Measured memory_bytes: 14396
# print('input >>')
N, K = map(int, (input().split()))
x = list(map(int, (input().split())))

neg = 0
pos = 0

left = 0
right = 0

ans = 10**10

for l in range(N - K + 1):
    left = x[l]
    right = x[l + K - 1]
    neg = min(left, 0)
    pos = max(right, 0)
    if neg < 0 and pos > 0:
        ans = min(ans, abs(neg) * 2 + pos, abs(neg) + pos * 2)
    else:
        ans = min(ans, abs(neg) + pos)

# print('----------output----------')
print(ans)

Measured memory_bytes: 14384
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;
// using namespace __gnu_pbds;

#define all(c) (c).begin(),(c).end()
#define endl "\n"
#define ff first
#define ss second
#define allr(c) (c).rbegin(),(c).rend()
#define fr(x,in,n,r) for(x=in;x<n;x+=r)
#define ifr(x,n) for(ll x=0;x<n;x++)
#define dfr(x,n) for(ll x=n-1;x>=0;x--)
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define pof(a) pop_front(a)
#define pob(a) pop_back(a)
#define eb(a) emplace_back(a)
#define ef(a) emplace_front(a)
typedef long long ll;
typedef map<ll,ll> mll;
typedef map<string,ll> msll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mod 1000000007


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt","r",stdin);
    ll n,k;
	string s;
	cin>>n>>k>>s;
	s[k-1]+=32;
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 384
def gcd(A, B):
    if A%B == 0:
        return B
    else:
        return gcd(B, A%B)
N, X = map(int, input().split())
x = [abs(int(i) - X) for i in input().split()] 
if N == 1:
    print(x[0])
    exit()
gcd_x = []
for i in range(N-1):
    gcd_x.append(gcd(x[i], x[i+1]))
print(min(gcd_x))

Measured memory_bytes: 14252
void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  int a, b; rd(a, b);
  auto s=readln.chomp.to!(char[]);

  if(count(s, '-')!=1){writeln("No"); return;}
  if(s[a]=='-') writeln("Yes");
  else writeln("No");
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}
void wr(T...)(T x){
  import std.stdio;
  foreach(e; x) write(e, " ");
  writeln();
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		long n = S.length();
		long[][] cnt = new long[S.length()][26];
		for (int i = 0; i < S.length(); ++i) {
			cnt[i][S.charAt(i) - 'a']++;
			for (int j = 0; j < 26 && i > 0; ++j) {
				cnt[i][j] += cnt[i - 1][j];
			}
		}
		long ans = n * (n - 1) / 2 + 1;
		for (long i = n - 1; i >= 0; --i) {
			ans -= cnt[(int)n - 1][S.charAt((int)i) - 'a'] - cnt[(int)i][S.charAt((int)i) - 'a'];
		}
		// for (int i = 0; i + 1 < n; ++i) {
		// for (int j = 0; j < 2; ++j) {
		// int l, r;
		// if (j == 0) {
		// l = i - 1;
		// r = i + 1;
		// } else {
		// l = i;
		// r = i + 1;
		// }
		// while (l >= 0 && r < n) {
		// if (S.charAt(l) != S.charAt(r)) {
		// ++ans;
		// }
		// --l;
		// ++r;
		// }
		// }
		// }
		System.out.println(ans);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int D[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>D[i];
	sort(D,D+N);
	x=D[N/2-1];
	y=D[N/2];
	
	cout<<y-x<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

#define MAX 100000

int main() {
	long long N;
	cin >> N;
	long long ans[MAX];
	long long A[MAX];
	long long sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		sum += A[i];
	}
	for (int i = 1; i < N; i += 2) {
		sum -= 2 * A[i];
	}
	ans[0] = sum;
	for (int i = 1; i < N; i++) {
		ans[i] = 2 * A[i - 1] - ans[i - 1];
	}
	for (int i = 0; i < N; i++) {
		cout << ans[i] << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 2816
n = int(input())

xs = sorted(map(int, input().split()))
ys = sorted(map(int, input().split()))
zs = sorted(map(int, input().split()))

bs = [0] * n
j = 0
for i in range(n):
    while j < n and xs[j] < ys[i]:
        j += 1
    bs[i] = j

cs = [0] * n
j = 0
k = 0
for i in range(n):
    while j < n and ys[j] < zs[i]:
        k += bs[j]
        j += 1
    cs[i] = k

print(sum(cs))


Measured memory_bytes: 23348
// luogu-judger-enable-o2
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define R register
using namespace std;
char s[351];int len,k;
int f[351][351][351],ans;
inline void read(R int &x)
{
    x=0;R int f=1;
	R char c=getchar();
	while(c<'0'||c>'9')
	{
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>=48&&c<=57)
	{
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
	x=x*f;
}
inline void input_data()
{
	char ch=getchar();
	while(ch>='a'&&ch<='z')
		s[++len]=ch,ch=getchar();
	read(k);return;
}
int dfs(R int k,R int l,R int r)
{
	if(l>r) return false;
	if(l==r) return s[l]==s[r];
	if(f[k][l][r]) return f[k][l][r];
	f[k][l][r]=max(dfs(k,l+1,r),dfs(k,l,r-1));
	if(s[l]==s[r]) f[k][l][r]=max(f[k][l][r],dfs(k,l+1,r-1)+2);
	if(k>=1) f[k][l][r]=max(f[k][l][r],dfs(k-1,l+1,r-1)+2);
	return f[k][l][r];
}
int main()
{
	input_data();
	for(R int i=0;i<=k;++i)
		ans=max(ans,dfs(i,1,len));
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 145408
n,k = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
if A[0]>k:
    ans += A[0]-k
    A[0] = k
for i in range(1, n):
    if A[i]+A[i-1]<=k:
        continue
    ans += (A[i]+A[i-1])-k
    A[i] = k-A[i-1]
print(ans)

Measured memory_bytes: 14068
s=input()+'T'
x,y=map(int,input().split())
if 'T' in s:
  pos=s.index('T')
  x-=pos
  s=s[pos+1:]
arr=s.split('T')
xarr=[]
yarr=[]
for i in range(len(arr)):
  l=len(arr[i])
  if l==0:
    continue
  if i%2==0:
    yarr.append(l)
  else:
    xarr.append(l)
xarr=sorted(xarr)
yarr=sorted(yarr)
xsums=[0]
for val in xarr:
  xsums.append(xsums[-1]+val)
ysums=[0]
for val in yarr:
  ysums.append(ysums[-1]+val)
if len(xarr)!=0:
  xmax=xarr[-1]
  xsum=xsums[-1]
else:
  xmax=0
  xsum=0
if len(yarr)!=0:
  ymax=yarr[-1]
  ysum=ysums[-1]
else:
  ymax=0
  ysum=0
x+=xsum
y+=ysum
if x%2==1 or y%2==1:
  print('No')
else:
  xdp=[0]*10000
  xdp[0]=1
  for j in range(len(xarr)):
    val=xarr[j]
    for i in range(xsums[j]+val+1,-1,-1):
      if i-val<0:
        break
      if xdp[i-val]==1:
        xdp[i]=1
  ydp=[0]*10000
  ydp[0]=1
  for j in range(len(yarr)):
    val=yarr[j]
    for i in range(ysums[j]+val+1,-1,-1):
      if i-val<0:
        break
      if ydp[i-val]==1:
        ydp[i]=1
  if xdp[x//2]==0:
    print('No')
  else:
    if ydp[y//2]==0:
      print('No')
    else:
      print('Yes')

Measured memory_bytes: 3572
#include <iostream>
#include <map>
#include <vector>

#define rep(i,s,n) for(int i=(s);i<(n);i++)

typedef unsigned long long ull;

using namespace std;

//考え方：1+2+3=6 -> 1+2 = 6-3 -> 1+2 = 3 -> 1=3-2 -> 1= 1
//計算済みデータのメモ領域,左辺の項列，項目列，右辺の解の引数
//戻り値には0~n番目までの項のみの解がansになる符号の打ち方の個数
ull solve(map<int,ull> *mem,int *seq,int n,int ans){
	//0~n番目までの項の解が0未満20より大きくなれば条件に従わないので
	//再帰を打ち切って0を出力
	if(ans<0 || ans>20) return 0;
	//すでに計算済みのデータであれば出力
	if(mem[n-1].find(ans)!=mem[n-1].end())
		return mem[n-1][ans];
	//項の長さが１つならば
	if(n==1){
		//項と結果がおなじなら１を出力
		if(ans==seq[n-1])
			return 1;
		//違う場合は2を出力
		return 0;
	}
	//n項目までのansの計算結果の変数
	ull result=0;
	//足し算と引き算を行った時のn項目以前の計算値の変数
	int ansP,ansM;
	//n項目までの計算値を求める
	ansP=ans-seq[n-1];
	ansM=ans+seq[n-1];

	//足し算の場合と引き算の場合をそれぞれを再帰的解を求める
	result+=solve(mem,seq,n-1,ansM);
	result+=solve(mem,seq,n-1,ansP);
	//メモに計算結果を代入
	mem[n-1][ans]=result;
	
	//計算結果を出力
	return result;
}


int main(void){

	int n;
	int seq[100];
	int ans;

	//入力
	while(cin >> n){
		//わかりやすいようにn-1
		n--;
		//左辺を入力
		rep(i,0,n)	cin >> seq[i];
		//右辺を入力
		cin >> ans;

		//計算結果をメモする変数
		map<int,ull> mem[n];
		//計算と出力
		cout << solve(mem,seq,n,ans) << endl;
	}

	return 0;
}

Measured memory_bytes: 1260
#include <set>
#include <map>
#include <list>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;

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

	int ans = 1;
	for(int A = 1; A * A <= M; A++){
		if( M % A != 0) continue;
		int B = M / A;
		if((long)A * N <= M) ans = max(ans, A);
		if((long)B * N <= M) ans = max(ans, B);
	}
	cout<< ans <<endl;

	return 0;
}

Measured memory_bytes: 256