akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll MOD = 1e9 + 7;

ll dp[100001][13];

int main(){
    string s;
    cin >> s;
    //文字列を再構築するイメージで進めていく(なのでdp[i+1][]が一番最初に更新されている)
    dp[0][0] = 1;
    reverse(all(s));
    int mul = 1;
    rep(i, s.size()){
        int c = -1;
        if(s[i] != '?') c = (s[i] - '0');
        rep(j, 10){
            if(c != -1 && c != j) continue;
            rep(k, 13){
                dp[i+1][(j*mul + k)%13] += dp[i][k];
            }
        }
        rep(j, 13) dp[i+1][j] %= MOD;
        mul *= 10;
        mul %= 13;
    }
    cout << dp[s.size()][5] << endl;
}

Measured memory_bytes: 10624
#include <stdio.h>

int main(void)
{
	int i;
	int j;
	int a;
	int b;
	int c;
	
	scanf("%d", &j);
	for (i = 0; i < j; i++){
		scanf("%d %d %d", &a, &b, &c);
		if ((a * a + b * b == c * c) || (b * b + c * c == a * a) || (c * c + a * a == b * b)){
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
	
	return 0;
}

Measured memory_bytes: 580
Q = int(input())

MASK = (1 << 64) - 1

x = 0
def c_test(i):
    return+(x & (1 << i) > 0)
def c_set(i):
    global x
    x |= 1 << i
def c_clear(i):
    global x
    if x & (1 << i):
        x ^= 1 << i
def c_flip(i):
    global x
    x ^= 1 << i
def c_all():
    return+(x & MASK == MASK)
def c_any():
    return+(x & MASK > 0)
def c_none():
    return+(x & MASK == 0)
def c_count():
    return bin(x).count('1')
def c_val():
    return x


fmap = [
    c_test,
    c_set,
    c_clear,
    c_flip,
    c_all,
    c_any,
    c_none,
    c_count,
    c_val,
]
def query(Q):
    for q in range(Q):
        t, *cmd = map(int, input().split())
        res = fmap[t](*cmd)
        if res is not None:
            yield res
print(*query(Q), sep='\n')



Measured memory_bytes: 7884
#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    int x,y,z,a,b;
    scanf("%d",&x);
    y=x/3600;
    z=x%3600;
    a=z/60;
    b=z%60;
    printf("%d:%d:%d\n",y,a,b);
    return 0;
}


Measured memory_bytes: 2144
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
using namespace std;
#define sz(x) ((int)(x).size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))
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; }
#define pb push_back
#define mp make_pair
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const ll INF = 1LL<<60;
 
int main() {
	string X;
  	cin >> X;
  	int ans = X.size();
  	stack<char> st;
  	for (int i = 0; i < X.size(); ++i) {
        if (st.empty() || st.top() == X[i] || st.top() == 'T') st.push(X[i]);
        else if(st.top() == 'S' && X[i] == 'T') {
            ans -= 2;
            st.pop();
        }
    }
  	cout << ans << endl;
}

Measured memory_bytes: 644
/// awoooooo

# include <bits/stdc++.h>
# define sz(x) (int)((x).size())

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;

const int N = (int)2e5 + 5;
const int inf = (int)1e9 + 7;

int n;
int a[N];
map < ll, int > cnt;

int main(){
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i){
    scanf("%d", a + i);
  }
  cnt[0] = 1;
  ll sum = 0, ans = 0;
  for(int i = 1; i <= n; ++i){
    sum += a[i];
    ans += cnt[sum];
    cnt[sum]++;
  }
  printf("%lld", ans);
  return 0;
}


Measured memory_bytes: 13568
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5100, mod = 1e9 + 7;
int n, w, b, B[maxn][maxn][2], W[maxn][maxn][2], dep[maxn][2];
void add(int &a, int b) {
	a += b;
	if(a >= mod) a -= mod;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> w >> b;
	if(b < w) swap(w, b);
	B[0][0][0] = 1;
	int ans = 0;
	for(int l = 0; l <= n; l++) {
		if(l) {
			add(dep[l][0], dep[l-1][0]);
			add(dep[l][1], dep[l-1][1]);
		}
		for(int h = 0; h <= l; h++) {
			for(int f = 0; f < 2; f++) {
				if(h == 0) add(W[l][h][f], dep[l][f]);
				
				//cout << "B " << l << " " << h << " " << f << " " << B[l][h][f] << '\n';
				//cout << "W " << l << " " << h << " " << f << " " << W[l][h][f] << '\n';
				
				add(B[l + 1][h + 1][f | (h + 1 >= b)], B[l][h][f]);
				add(B[l + 1][h + 1][f | (h + 1 >= b)], W[l][h][f]);
				
				if(h) add(W[l + 1][h + 1][f | (h + 1 >= b)], W[l][h][f]);
				//B->W
				if(l + w < maxn)
					add(W[l + w][h + w][f | (h + w >= b)], B[l][h][f]);
				if(B[l][h][f]) {
					add(dep[l + 1][f], B[l][h][f]);
					if(l + w < maxn)
						add(dep[l + w][f], mod - B[l][h][f]);
				}
				
				if(l == n && f) add(ans, B[l][h][f]), add(ans, W[l][h][f]);
			}
		}
	}
	cout << ans;
}


Measured memory_bytes: 241560
N, K = map(int,input().split())
# N以下の正の整数
# Kの倍数
# a+b, b+c, c+a a < b < c
# a, b, c すべてのmodが 0 or K/2 (n=1,2,3,...) となる必要がある

# Kで割った余りが0 or K/2(偶数の時)以外ムリでは？
# Kで割った余りが0の時
ans = 0
cnt = N//K
ans += cnt ** 3
# Kで割った余りがK/2の時(偶数のみ)
if K % 2 == 0:
    n = 0
    cnt = 0
    while (n + 1/2) * K <= N:
        cnt += 1
        n += 1
    ans += cnt ** 3
print(ans)

Measured memory_bytes: 3060
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

bonus=0
for i in range(len(a)-1):
  if a[i+1]-a[i]==1:
    bonus=bonus+c[a[i]-1]

print(bonus+sum(b))

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define pb         push_back
const int N = 100005;
const int inf = ( 1 << 21);


class Edge{
public:
  int next,c;
};

class state{
public:
  int now,c;
  bool operator<(const state & a)const{
    return c > a.c;
  }
};

void dijkstra(vector<int>&ini,int n,vector<Edge> *edge,int *cost){
  rep(i,n)cost[i]=inf;
  
  priority_queue<state>  Q;
  rep(i,ini.size()){
    Q.push((state){ini[i],0});
  }
  
  while(!Q.empty()){
    state now = Q.top();Q.pop();
    if (cost[now.now] != inf)continue;
    cost[now.now]=now.c;
    rep(i,edge[now.now].size()){
      int next=edge[now.now][i].next,nec=now.c+edge[now.now][i].c;
      Q.push((state){next,nec});
    }
  }
}

vector<Edge> Ledge[N],Nedge[N];
int Lcost[N],Scost[N],Ncost[N];
int LBFS[N],SBFS[N];

template<class T> void op(T &in,int n){rep(i,n)cout<<in[i]<<' ';cout << endl;}

int solve(int n,int L,int S,int N){
  vector<int> ini;
  ini.push_back(L);
  dijkstra(ini,n,Ledge,LBFS);
  //  op(LBFS,n);
  if (LBFS[S] != inf)return 0;//natune is not needed
  ini.clear();

  

  ini.push_back(S);
  dijkstra(ini,n,Ledge,SBFS);
  ini.clear();

  //  op(SBFS,n);


  vector<int> Lini,Nini,Sini;
  Nini.push_back(N);
  rep(i,n){
    if (LBFS[i] != inf)Lini.push_back(i);
    if (SBFS[i] != inf)Sini.push_back(i);
  }

  dijkstra(Lini,n,Nedge,Lcost);
  dijkstra(Sini,n,Nedge,Scost);
  dijkstra(Nini,n,Nedge,Ncost);

  
  int ans = inf;
  rep(i,n){
    //if (LBFS[i] == inf && SBFS[i] == inf)
      ans=min(ans,Ncost[i]+Scost[i]+Lcost[i]);
  }
  return ans;
}


main(){
  int te;
  cin>>te;
  while(te--){
    int n,m;
    cin>>n >>m;
    n++;
    rep(i,n)Nedge[i].clear(),Ledge[i].clear();
    int S = 0,L,N;
    cin>>N>>L;

    rep(i,m){
      int f,t;
      char k;
      cin>>f>>t>>k;
      if (k == 'L'){
	Ledge[f].pb((Edge){t,1});
	Ledge[t].pb((Edge){f,1});
      }else if (k == 'N'){
	Nedge[f].pb((Edge){t,1});
	Nedge[t].pb((Edge){f,1});
      }
    }
    cout << solve(n,L,S,N) << endl;
  }
}

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

int main() {
    int n, k; cin >> n >> k;
    vector<int> h(n);
    rep(i, n)
        cin >> h.at(i);
    
    sort(h.begin(), h.end());

    int ans = h.at(k-1) - h.at(0);
    rep(i, n - k + 1) {
        ans = min(ans, h.at(i + k-1) - h.at(i));
    }

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

Measured memory_bytes: 640
// 2011/01/27 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		// üÍ
		int w;						// ¡ÌgpÊ
		cin >> w;
		if(w==-1)
			break;

		// Z
		int bil;					// ¡Ì¹¿à
		if(w<=10)
			bil = 1150;
		else if(w<=20)
			bil = 1150+(w-10)*125;
		else if(w<=30)
			bil = 1150+10*125+(w-20)*140;
		else
			bil = 1150+10*125+10*140+(w-30)*160;

		// oÍ
		cout << 4280-bil << endl;	// ÇÌ­ç¢ßñÅ«½©
	}

	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define mod 1000000007;
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long int li;
using namespace std;
int main()
{
    fast_io;
    li c=0,i;
string s,s1;
cin>>s>>s1;
for(i=0;s[i]!='\0';i++)
{
	if(s[i]==s1[i])
	c++;
}
cout<<c;
return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define N 10000
typedef long long ll;
using namespace std;
int a[105];
int b[N][3];
int c[100];
int main()
{
    int n,k=0;
    int ans=1;
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=1;i<=n;i++)
    {
        b[i][0]=a[i]-1;
        b[i][1]=a[i];
        b[i][2]=a[i]+1;
    }

    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<3;j++)
        if ((b[i][j])%2==1)
            c[i]++;
    }

    for (int i=1;i<=n;i++)
      {
           if (c[i]==0)
            {
                ans=0;
                break;
            }
         else
            ans*=c[i];
      }

    cout << pow(3,n)-ans << endl;
    return 0;
}


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

const int vmax=5010;
const int inf=1<<30;
struct edge{int to,cap,rev;};
vector<edge> graph[vmax];
int level[vmax],iter[vmax];

void reset(){
	rep(i,vmax) graph[i].clear();
}

void add_edge(int from,int to,int cap){
	// cout << from << " " << to << " "  << cap << endl;
	graph[from].push_back({to,cap,(int)graph[to].size()});
	graph[to].push_back({from,0,(int)graph[from].size()-1});
}

int max_flow(int s,int t){
	auto bfs=[&](int s,int t){
		rep(i,vmax) level[i]=-1;
		queue<int> q;
		level[s]=0,q.push(s);
		while(!q.empty()){
			int v=q.front();q.pop();
			for(auto &e:graph[v]){
				if(e.cap>0 && level[e.to]<0){
					level[e.to]=level[v]+1;
					q.push(e.to);
				}
			}
		}
		return level[t]>=0;
	};
	function<int(int,int,int)> dfs=[&dfs](int v,int t,int f){
		if(v==t) return f;
		for(int &i=iter[v];i<graph[v].size();i++){
			edge &e=graph[v][i];
			if(e.cap>0 && level[v]<level[e.to]){
				int d=dfs(e.to,t,min(f,e.cap));
				if(d==0) continue;
				e.cap-=d;graph[e.to][e.rev].cap+=d;
				return d;
			}
		}
		return 0;
	};
	int flow=0;
	while(bfs(s,t)){
		rep(i,vmax) iter[i]=0;
		while(1){
			int f=dfs(s,t,inf);
			if(f==0) break;
			flow+=f;
		}
	}
	return flow;
}

int n,w,a[1010],b[1010];
void set_edge(int s,int t){
	reset();
	// init select 0
	rep(i,w+1){
		if(i%2==0)
			add_edge(i,t,inf);
		else
			add_edge(s,i,inf);
	}
	// select 0~n-1
	/*
	rep(i,n){
		int idx=i+w+1;
		add_edge(s,idx,0);
		add_edge(idx,t,0);
	}
	*/
	// a[i] cost loss
	rep(i,n){
		int idx=i+w+1;
		add_edge(idx,idx-1,a[i]);
		add_edge(idx-1,idx,a[i]);
	}
	// b[i] cost loss
	rep(i,n){
		add_edge(i,i+2*w+1,b[i]);
		add_edge(i+2*w+1,i,b[i]);
	}
}

string get(){
	string ret="";
	int cur=0;
	rep(i,n){
		int idx=i+w+1;
		int nxt=(level[idx]>=0);
		nxt^=(idx%2);
		ret+=(nxt^cur)+'0';
		cur=nxt;
	}
	return ret;
}

int main(void){
	cin >> n >> w;
	rep(i,n) cin >> a[i];
	rep(i,n) cin >> b[i];
	int vertex=n+2*w+1;
	const int s=vertex,t=vertex+1;

	set_edge(s,t);
	// last select type 0
	rep(i,w+1){
		int idx=i+n+w;
		if(idx%2==0)
			add_edge(idx,t,inf);
		else
			add_edge(s,idx,inf);
	}

	int zero_score=max_flow(s,t);
	string zero_str=get();

	set_edge(s,t);
	// last select type 2
	rep(i,w+1){
		int idx=i+n+w;
		if(idx%2==0)
			add_edge(s,idx,inf);
		else
			add_edge(idx,t,inf);
	}

	int one_score=max_flow(s,t);
	string one_str=get();

	if(zero_score<one_score)
		cout << zero_str << endl;
	else
		cout << one_str << endl;
	return 0;
}

Measured memory_bytes: 1716
#include <iostream>
#include <string.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <vector>
#include <map>
using namespace std;

#define cio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ll long long
#define ii pair < int, int >
#define iii pair < int, ii >
#define INF 987654321
#define LINF 987654321987654321

int main()
{
	cio;
	int a;
	cin >> a;

	cout << a + a * a + a * a * a;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

int main() {
    ll X;
    cin >> X;
    ll ans = 0;
    ll cnt = X / 500LL;
    ans += cnt * 1000LL;
    X -= cnt * 500LL;
    ans += (X / 5LL) * 5LL;
    cout << ans << endl;
}


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

using namespace std;

struct Edge {
  int from;
  int to;
};

int main() {
  int n, k, m;
  cin >> n;
  cin >> k;
  
  vector<Edge> result;

  // 方針として、
  // 1をハブとして、各頂点との間に辺を張る
  // その後、kを満たすまで、1以外の頂点対に辺を張っていく。
  // その頂点対の距離が1になるため、1個辺を張るたびに最短距離2の組は1減る。

  for (int i = 2; i <= n; i++) {
    result.push_back({1,i});
  }
  int pair_count = (n-1)*(n-2)/2;
  /* この時点で条件を満たす頂点対が最大。1以外の全頂点対が条件を満たす。
     理由は、連結しているため、最低n-1の辺(最低距離1の組)が存在する。
     よって、最短距離2の組は、最大n*(n-1)/2 - (n-1) = (n-1)(n-2)/2 */
  
  // 1以外の頂点対に辺を張っていく。
  if (pair_count > k) {
    for (int i = 2; i < n; i++) {
      for (int j = i + 1; j <= n; j++) {
        result.push_back({i,j});
        pair_count--; // 1個辺を張るたびに最短距離2の組は1減る。
        
        if (pair_count == k) {
          goto finish;
        }
      }
    }
  }
  finish:
  
  if (pair_count != k) {
    cout << -1 << endl;
  } else {
    cout << result.size() << endl;
    for(Edge &e : result) {
      cout << e.from << " " << e.to << endl;
    }
  }
   
  return 0;
}

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

int main()
{
	int K,sum=0;
	cin>>K;
	for(int i=1; i<=K; i++)
	{
		for(int j=1; j<=K; j++)
		{
			int gcd;
			gcd = __gcd(i, j);
			for(int k=1; k<=K; k++)
			{
				sum += __gcd(gcd, k);
			}
		}
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 3636
from itertools import combinations
from itertools import permutations


def f(x, lst, rem):
    d = abs(x - min(lst))
    min_lst = min(lst)
    tpl = None
    for v in range(len(lst) - rem + 1):
        for t in combinations(lst, v + 1):
            if abs(x - sum(t)) + 10 * v < d:
                d = abs(x - sum(t)) + 10 * v
                tpl = t
    if tpl is None:
        lst.remove(min_lst)
    else:
        for v in tpl:
            lst.remove(v)
    return d, lst


def main():
    N, A, B, C = map(int, input().split())
    L = [int(input()) for i in range(N)]

    ans = int(1e9+7)
    for ABC in permutations((A, B, C), 3):
        lst = L[:]
        accum = 0
        for i, v in enumerate(ABC):
            d, lst = f(v, lst, 3 - i)
            accum += d
        ans = min(ans, accum)
    print(ans)


main()


Measured memory_bytes: 3064
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;
string S;
int dp(int place, long long count);
int memoCountOdd[100000] = {};
int memoCountEven[100000] = {};

int main()
{
    cin >> S;
    int lastPlace[100000] = {};

    for(int i = 0; i < S.length(); i++)
    {
        memoCountOdd[i] = -1;
        memoCountEven[i] = -1;
    }

    for(int i = 0; i < S.length(); i++)
    {
        int ret = dp(i, 100000);
        lastPlace[ret]++;
    }

    for(int i = 0; i < S.length(); i++)
    {
        cout << lastPlace[i]<< " ";
    }
    cout << endl;
    return 0;
}


int dp(int place, long long count)
{
    if(S[place] == 'L' && S[place - 1] == 'R')
    {
        if(count % 2 == 1)
        {
            memoCountOdd[place] = place - 1;
            return place - 1;
        }
        else
        {
            memoCountEven[place] = place;
            return place;
        }
    }
    
    if(S[place] == 'R' && S[place + 1] == 'L')
    {
        if(count % 2 == 1)
        {
            memoCountOdd[place] = place + 1;
            return place + 1;
        }
        else
        {
            memoCountEven[place] = place;
            return place;
        }
    }

    if(count % 2 == 1 && memoCountOdd[place] != -1)
    {
        return memoCountOdd[place];
    }
    if(count % 2 == 0 && memoCountEven[place] != -1)
    {
        return memoCountEven[place];
    }
    if(S[place] == 'L')
    {
        int ret = dp(place - 1, count - 1);
        if(count % 2 == 1)
        {
            memoCountOdd[place] = ret;
            return ret;
        }
        if(count % 2 == 0)
        {
            memoCountEven[place] = ret;
            return ret;
        }
    }
    if(S[place] == 'R')
    {
        int ret = dp(place + 1, count - 1);
        if(count % 2 == 1)
        {
            memoCountOdd[place] = ret;
            return ret;
        }
        if(count % 2 == 0)
        {
            memoCountEven[place] = ret;
            return ret;
        }
    }
}

Measured memory_bytes: 8064
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
int p[3] = { 1,2,4 }; int x[8], y[8]; int z[8] = { 2,0,2,0,1,0,1,0 };
int main() {
	while (cin >> x[0]) {
		int maxn = 100000000, maxid = 0;
		for (int i = 1; i < 8; i++) { cin >> x[i]; }
		for (int i = 0; i < 8; i++) {
			int sum = 0, sum2 = 0;
			for (int j = 0; j < 8; j++) { y[j] = z[(i + j) % 8]; }
			for (int j = 0; j < 8; j++) { if (p[y[j]] < x[j]) { sum += x[j] - p[y[j]]; } }
			for (int j = 0; j < 8; j++) { sum2 += p[y[j]] * (int)pow(10, 7 - j); }
			if (maxn > sum) { maxn = sum; maxid = sum2; }
			else if (maxn == sum && maxid > sum2) { maxid = sum2; }
		}
		for (int j = 0; j < 8; j++) { if (j) { cout << ' '; }cout << (maxid / (int)pow(10, 7 - j)) % 10; }cout << endl;
	}
	return 0;
}

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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int k,n; cin >> k >> n;
	int a[n],d[n];
	for(int i=0; i<n; i++){
		cin >> a[i];
		d[i]=0;
	}
	d[0] = k-a[n-1]+a[0];
	int mx = d[0];
	for(int i=1; i<n; i++){
		d[i] = a[i]-a[i-1];
		mx = max(mx,d[i]);
	}
	cout << k-mx << endl;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
vector<int>v[100001];
bool visit[100001];
queue<int >q;
int ctr=0,flag=0;
void bfs(int x){
    q.push(x);
    while(!q.empty()){ ctr++;
        x=q.front(); q.pop(); visit[x]=1;
        for(int y=0;y<v[x].size();y++){
            if(v[x][y]==2){
                flag=1; return;
            }
            if(!visit[v[x][y]]) q.push(v[x][y]);
        }
    }
}
int main() { memset(visit,0,sizeof(visit));
    int n,i;
    cin>>n;
    for(int x=1;x<=n;x++){
        cin>>i;
        v[x].push_back(i);
    }
    bfs(1);
    if(!flag) cout<<-1<<endl;
    else cout<<ctr<<endl;
	return 0;
}


Measured memory_bytes: 5760
package main
import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
)

func Solve() {
  var N, u, v int
  NextInt(&N)
  ans := 0
  for i := 1; i <= N; i++ {
    ans += i * (N + 1 - i)
  }
  for i := 1; i < N; i++ {
    NextInt(&u, &v)
    if u > v { u, v = v, u }
    ans -= u * (N + 1 - v)
  }
  Write(ans)
}

func main() {
  Solve()
  Output()
}

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntSlice(A *[]int) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatSlice(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(S ...interface{}) {
  fmt.Fprintln(writer, S...)
}
func WriteIntSlice(A []int) {
  B := make([]interface{}, len(A))
  for i, a := range A { B[i] = a }
  Write(B...)
}
func Output() {
  _ = writer.Flush()
}
func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}
func AbsInt(x int) int {
  if x < 0 { x = -x }
  return x
}

Measured memory_bytes: 6316
[N, A, B] = list(map(int, input().split(" ")))

def numOfSumDigit(n):
  sum = 0
  while n > 0:
    sum += n%10
    n = int(n / 10)
  return sum

total = 0
for i in range(1, N+1):
  SUM = numOfSumDigit(i)

  if A <= SUM and SUM <= B:
    total += i
    
print(total)

Measured memory_bytes: 3064
package main
 
import "fmt"
 
func main() {
	var s string
	fmt.Scan(&s)
 
	ans := "No"
	if s[0] != s[1] && s[0] != s[2] && s[1] != s[2] {
		ans = "Yes"
	}
 
	fmt.Println(ans)
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INTINF = 1<<29;
const ll LLINF = 1LL<<61;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const int DX[8]={ 0, 1, 0,-1, 1, 1,-1,-1};
const int DY[8]={ 1, 0,-1, 0, 1,-1, 1,-1};


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  REP(j,2){
    bool flag = true;
    REP(i,3){
        if(S[j] != S[j+i])flag = false;
    }
    if (flag){
        cout << "Yes" << endl;
        return 0;
    }
  }
  cout << "No" << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1), EPS = 1e-10;
const ll MOD = 1e9+7;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  V<pii> z(n);
  REP(i,n) cin >> z[i].fi >> z[i].se;
  map<pii,int> mp;
  REP(i,n)FOR(j,i+1,n){
    mp[make_pair(z[j].fi-z[i].fi,z[j].se-z[i].se)]++;
    mp[make_pair(-z[j].fi+z[i].fi,-z[j].se+z[i].se)]++;
  }
  int mx = 0;
  for(auto i = mp.begin();i!=mp.end();++i){
    maxs(mx,i->se);
    //cout << i->se << " " << mx << endl;
  }
  cout << n-mx << endl;

}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define int long long
using namespace std;

main(){
     ios_base::sync_with_stdio(false);
     cin.tie(nullptr);
     int x, N; cin >> x >> N;
     set<int> s;
     for(int i = 0; i < N; i++){
          int n; cin >> n; s.insert(n);
     }
     int d = abs(-101-x), ans = -101;
     for(int i = -100; i <= 101; i++){
          if(s.count(i)) continue;
          if(abs(i-x) < d){
               d = abs(i-x);
               ans = i;
          }
     }
     cout << ans;
}

Measured memory_bytes: 3656
#include<iostream>
#include<cstring>

using namespace std;
char s[1005];

int main(){
	cin>>s;
	int len=strlen(s);
	if(s[len-1]=='s') s[len]='e',s[len+1]='s';
	else s[len]='s';
	cout<<s<<endl;
	return 0;	
}

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


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

#ifndef ONLINE_JUDGE
    freopen("input.txt" , "r" , stdin);
    freopen("output.txt" , "w" , stdout);
#endif


    int n, ele;
    cin >> n;
    vector<int> H;

    for (int i = 0; i < n; i++)
    {
        cin >> ele;
        H.push_back(ele);
    }

    int dp[n];


    dp[0] = 0;
    dp[1] = abs(H[1] - H[0]);

    for (int i = 2; i < n; i++)
    {
        dp[i] = min(dp[i - 1] + abs(H[i - 1] - H[i]), dp[i - 2] + abs(H[i] - H[i - 2]));
    }
    cout << dp[n - 1] << endl;
    return 0;

}

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

vector<string> A;
unordered_map<string, int> M;

int main()
{
    ios_base::sync_with_stdio(false);
    string s;
    int k;
    cin >> s >> k;
    int n = (int) s.size();
    for(int i = 0; i < n; i++) {
        string t = "";
        for(int j = i; j < min(i + 5, n); j++) {
            t += s[j];
            //cout << t.size() << endl;
            if(M[t] == 0) A.push_back(t);
            M[t]++;
        }
    }
    //for(string s : A) cout << s << endl;
    //cout << endl;
    nth_element(A.begin(), A.begin() + (k - 1), A.end());
    //for(string s : A) cout << s << endl;
    cout << A[k - 1] << "\n";
}



Measured memory_bytes: 1920
#include<iostream>
 #include<stdio.h>
 #include<string>
 #include<math.h>
 #include<iomanip>
 #include<algorithm>
 #include<string.h>
 #include<cctype>
 #include<map>
 #include<set>
 #include<vector>
 #include<sstream>
 
 using namespace std;
 
 int v[35];
 
 int main()
 {
   int w,n;
   cin>>w>>n;
   for(int i=1;i<=w;i++) v[i]=i;
   while(n--)
   {
     int l,r;
     char temp;
     cin>>l>>temp>>r;
     swap(v[l],v[r]);          
   } 
   for(int i=1;i<=w;i++)
   {
     cout<<v[i]<<endl;        
   }
   //while(1);      
   return 0;    
 }
 
 
 

Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
	cin>>s;
	if(s=="SUN")cout<<"7";
	else if(s=="MON")cout<<"6";
	else if(s=="TUE")cout<<"5";
	else if(s=="WED")cout<<"4";
	else if(s=="THU")cout<<"3";
	else if(s=="FRI")cout<<"2";
	else cout<<"1";
	return 0;
}


Measured memory_bytes: 3604
f=[True]*(10**5+1)
like=[False]*(10**5+1)
f[0]=False
f[1]=False
import math
for i in range(2,len(f)):
  fact=True
  for j in range(2,int(math.sqrt(i))+1):
    if i%j==0:
      fact=False
      break
  
  if fact:
    f[i]=True
    if i*2-1<len(like):
      like[i*2-1]=True
    for p in range(i*2,len(f),i):
      f[p]=False

sums=[0]*(10**5+1)
cur=0
for i in range(len(sums)):
  if f[i] and like[i]:
    sums[i]=cur+1
    cur+=1
  else:
    sums[i]=cur

Q=int(input())
for i in range(Q):
  l,r=map(int,input().split())
  if l>0:
    print(sums[r]-sums[l-1])
  else:
    print(sums[r])


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

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
#define SZ(x) ((int)(x).size())

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

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

string s, t;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "r", stdin);
#endif

    cin >> s >> t;
    bool flag = true;
    forn(i, SZ(s)) {
        flag &= (s[i] == t[i]);
    }
    cout <<(flag ? "Yes" : "No") << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 3652
from collections import deque


def gen753number(max_value):
    numbers = '357'
    que = deque([l for l in numbers])

    while True:
        while len(que):
            pre = que.popleft()
            if int(pre) > max_value:
                break
            if all([i in pre for i in numbers]):
                yield pre
            for n in numbers:
                que.append(pre + n)
        break


n = int(input())
print(len(list(gen753number(n))))



Measured memory_bytes: 9452
#include <functional>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <climits>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <deque>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long LL;
typedef unsigned int ui;
typedef unsigned long long ULL;

typedef pair < int , int > ii;
typedef pair < LL  , LL  > ll;

typedef vector <int>  vint;
typedef vector <bool> vbool;
typedef vector <long> vlong;

#define sz(x)			((int)x.size())
#define tin(x)			scanf("%d",&x)
#define all(x)			x.begin(),x.end()
#define Set(b,a)		memset(b,a,sizeof b)
#define print1(x)		printf("Case %d:",x++)
#define tin2(x,y)		scanf("%d%d",&x,&y)
#define tin3(x,y,z)		scanf("%d%d%d",&x,&y,&z)
#define loop(i,i0,in)	for(int i=i0 ; i<in ; i++)
#define rep(i,n)		for(int i=0 ; i<(n) ; i++)
#define _rep(i,n)		for(int i=n-1 ; i>=0 ; i--)
#define _loop(i,in,i0)	for(int i=in-1 ; i>=i0 ; i--)
#define Fore(it, x)		for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)

const int maxn = 5;

int seq[maxn];
     
int main()  
{  
#ifdef Online_Judge
	freopen("a.in","r",stdin);
#endif
	int t;
	tin(t);
	while(t--)
	{
		rep(i,3)
			tin(seq[i]);
		sort(seq,seq+3);
		if((seq[0]*seq[0])+(seq[1]*seq[1])==(seq[2]*seq[2]))
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}  

Measured memory_bytes: 1184
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <tuple>
#include <random>
#include <map>
#include <queue>
#include <set>
#include <complex>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>

using namespace std;

typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

const ll INF = 1e15;
const double eps = 1e-6;
const ll MOD = 1000000007;

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

void solve(ll l, ll r, string ls, string lr) {
	ll m = (l + r) / 2;
	cout << m << endl;
	string ret;
	cin >> ret;
	if (ret == "Vacant")
		return;
	if (ret == ls && (m - l) % 2 || ret != ls && (m - l) % 2 == 0)
		solve(l, m, ls, ret);
	else
		solve(m, r, ret, lr);
}

int main() {
	ll N;
	cin >> N;
	cout << 0 << endl;
	string start;
	cin >> start;
	//Vacant, Male, Female
	if (start == "Vacant")
		return 0;
	string end;
	cout << N - 1 << endl;
	cin >> end;
	if (end == "Vacant")
		return 0;
	solve(0, N-1, start, end);
	return 0;
}


Measured memory_bytes: 852
#include <bits/stdc++.h>
using namespace std;
const int INF = 2100100100;
using ll = long long;

int main() {
    int n;
    cin >> n ;
    vector<double> x(n);
    for (int i=0;i<n;i++){
        cin >> x.at(i);
    }
    float nin=INF;
    for (int p=1;p<100;p++){
        float sum =0;
        for (int i=0;i<n;i++){
            sum += pow((x.at(i)-p),2);
        }
        nin = min(nin,sum);
    }
    cout << nin << endl;
    return 0;
}



Measured memory_bytes: 256
n = int(input())
from collections import defaultdict
G = defaultdict(list)
for i in range(n):
    i = [int(i) for i in input().split()]
    k = i[1]
    G[i[0]] = list(zip(i[2::2],i[3::2]))

def mind(Q, d):
    c = float('inf')
    ret = 0
    for i, j in enumerate(d):
        if c > j and i in Q:
            c = j
            ret = i
    return ret

def dijkstra(G):
    d = [0] + [float('inf')] * (n - 1)
    Q = set(range(n))
    while len(Q) != 0:
        u = mind(Q, d)
        Q = Q - set([u])
        for v, c in G[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
    return d

for i,j in enumerate(dijkstra(G)):
    print(i, j)

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

int main()
{
    string str;
    cin >> str;
    int first = str.find('C');
    int last = str.rfind('F');
    if ((first < last) && (0 <= first))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

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

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

  if (N % 1110 < 10 || (N - N / 1000 * 1000) % 111 == 0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define sd(x)   scanf("%g",&x)
#define ss(s)	scanf("%s",s)
#define pd(x)   printf("%g\n",x)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define nline   printf("\n")
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define fitr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
void update(multiset<int> &best, int c[],int pos,int val);
int main()
{
    int r,c,n,i;
    si(r);si(c);si(n);
    int cols[c];
    multiset<int> best;
    vector<int> row[r];
    fo(i,c)
    {
        cols[i] = 0;
        best.insert(0);
    }
    fo(i,n)
    {
        int x,y;
        si(x);si(y);
        x--;y--;
        row[x].pb(y);
        update(best,cols,y,1);
    }
    int res = 0;
    fo(i,r)
    {
        int bmbs = row[i].size();
        for(int x:row[i])
        {
            update(best,cols,x,-1);
        }
        if(best.size())
        bmbs+=*best.rbegin();
        res = max(res,bmbs);
        for(int x:row[i])
        {
            update(best,cols,x,1);
        }
    }
    pi(res);
}
void update(multiset<int> &best, int c[],int pos,int val)
{
    best.erase(best.find(c[pos]));
    c[pos]+=val;
    best.insert(c[pos]);
}

Measured memory_bytes: 35392
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = [0]*(n-1)
    for i in range(n):
        for j in range(i+1, n):
            if i < x and y < j:
                dist = j-i-(y-x)+1
            elif j < x or y < i:
                dist = j-i
            elif i <= x and j <= y:
                dist = min(j-i, x-i+1+y-j)
            elif x <= i and y <= j:
                dist = min(j-i, j-y+1+i-x)
            else:
                dist = min(j-i, y-x-(j-i)+1)
            ans[dist-1] += 1
    for i in ans:
        print(i)


main()

Measured memory_bytes: 45916
<?php
  while (true) {
    list($h, $w) = explode(" ", trim(fgets(STDIN)));
    if (($h == 0) && ($w == 0)) {
      return;
    }
    $i = 1;
    while ($i <= $h) {
      if (($i % 2) == 1) {
        $n = 1;
        while ($n <= $w) {
          if (($n % 2) == 1) {
            print "#";
          } else {
            print ".";
          }
          $n++;
        }
        print "\n";
      } else {
        $n = 1;
        while ($n <= $w) {
          if (($n % 2) == 1) {
            print ".";
          } else {
            print "#";
          }
          $n++;
        }
        print "\n";
      }
      $i++;
    }
    print ("\n");
  }
?>

Measured memory_bytes: 6588
#include <bits/stdc++.h>
using namespace std;
int n;
string s, c;
int main () {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
		cin >> s;
		cin >> c;
	for(int i = 0; i < n; i++) {
		cout << s[i] << c[i];
	}
	return 0;
}

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

int main(){
	int a,b,c,x,y;
  	cin >> a >> b >> c >> x >> y;
  	int ans = a*x+b*y;
  	for (int i=0;i<=max(x,y);i++){
    	ans = min (ans,a*max(0,(x-i))+b*max(0,(y-i))+c*2*i);
    }
  	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,const pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,const vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}
template<typename T>vector<T> & cset(vector<T> &A,T e=T()){for(auto &I:A){I=e;} return A;}





int main(){
    ll n;
    cin>>n;
    vector<ll> A(n);
    cin>>A;
    sort(A.begin(),A.end());
    if(n&1){cout<<0<<endl;}
    else{
        cout<<A[n/2]-A[n/2-1]<<endl;
    }
    
    
    return 0;
}


Measured memory_bytes: 1152
#include<iostream>
#include<vector>
#include<utility>
#include<map>
#include<deque>
#include<numeric>
#include<algorithm>
#include<unordered_map>
#include<cmath>

using namespace std;
using ll = long long int;
constexpr int INF = 1 << 29;
constexpr ll MOD = ll(1e9 + 7);


int main(void) {
	int a[32] = {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 };
	int k;
	cin >> k;
	cout << a[k - 1] << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
ma, mi = max(a), min(a)
if ma - mi > 1:
    print("No")
elif ma - mi == 1:
    z, o = 0, 0
    for i in range(n):
        if a[i] == ma - 1:
            z += 1
        else:
            o += 1
    if z < ma and ma - z <= o / 2:
        print("Yes")
    else:
        print("No")
else:
    if ma == n - 1 or ma <= n / 2:
        print("Yes")
    else:
        print("No")

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

int main() {
  int n, m, c; cin >> n >> m >> c;
  int b[21];
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int sum = c;
    for (int j = 0; j < m; j++) {
      int a; cin >> a;
      sum += a * b[j];
    }
    if (sum > 0) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
using System;

class Program
{
    static void Main(string[] args)
    {
        var ab = Console.ReadLine().Split();
        var a = int.Parse(ab[0]);
        var b = int.Parse(ab[1]);
        if (a < 10 && b < 10) Console.WriteLine(a * b);
        else Console.WriteLine(-1);
    }
}


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

#define LL 					long long
#define ULL 				unsigned long long
#define pii 				pair<int,int>
#define fi 					first
#define se 					second
#define vi 					vector<int>
#define psb 				push_back
#define ppb 				pop_back
#define all(x)			 	(x).begin(),(x).end()
#define sz(x)				(int)(x).size()
#define endln 				printf("\n")
#define gc					getchar_unlocked
#define setmin(x)			memset((x), -1, sizeof((x)))
#define setnul(x)			memset((x), 0, sizeof((x)))
#ifndef getchar_unlocked
#define getchar_unlocked 	getchar
#endif
const int inf = 1e9 + 5;
const int mod = 1e9 + 7;

template <typename T>
void gi(T &ret) {
	ret = 0; char inp=gc(); int kl=1;
	while (inp<'0' || inp>'9') {if (inp=='-') kl=-1; inp=gc();}
	while ('0'<=inp && inp<='9') ret=(ret<<3)+(ret<<1)+(inp-'0'), inp=gc();
	if (kl<1) ret=-ret;
}

int tg, lb, val[30];
char inp[105];

bool cek() {
	int a = 0, b = 0;
	if (tg%2 && lb%2) {
		a = (tg/2)+(lb/2);
		b = 1;
	} else if (tg%2) {
		a = lb/2;;
	} else if (lb%2) {
		a = tg/2;
	}
	int ha = 0, hb = 0;
	for (int i=0; i<26; i++) {
		if (val[i]%4==3) return 0;
		if (val[i]%4==1) hb++;
		if (val[i]%4==2) ha++;
	}
	if (hb != b) return 0;
	if (ha>a) return 0;
	return 1;
}

int main() {
	gi(tg); gi(lb);
	setnul(val);
	for (int i=0; i<tg; i++) {
		scanf("%s", inp);
		for (int j=0; j<lb; j++) 
			val[inp[j]-'a']++;
	}
	if (cek()) puts("Yes");
	else puts("No");
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//exist x map o set
int D;
int c[26];
int s[365][26];
void input(){
    scanf("%d",&D);
    for(int i=0;i<26;i++) scanf("%d",&c[i]);
    for(int i=0;i<D;i++) for(int j=0;j<26;j++) scanf("%d",&s[i][j]);
}

vector<int> calc(vector<int> d){
    vector<int> last(26,0);
    vector<int> ret;
    int res=0;
    for(int i=0;i<D;i++){
        res+=s[i][d[i]];
        last[d[i]]=i+1;
        for(int j=0;j<26;j++){
            res-=c[j]*(i+1-last[j]);
        }
        ret.pb(res);
    }
    return ret;
}
constexpr ll INF=1e18;
signed main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    input();
    ll res=0;
    vector<int> last(26,0);
    rep(i,D){
        ll plus=-INF;
        int ans=0;
        rep(j,26){
            //open j contest
            ll ret=s[i][j];
            rep(k,26){
                if(j!=k) ret-=c[k]*(i+1-last[k]);
            }
            if(ret>plus){
                plus=ret;
                ans=j;
            }
        }
        cout << ans+1 << endl;
    }
}


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

using namespace std;

#define debug(x,y) cout<<(#x)<<" " <<(#y)<<" is " << (x) <<" "<< (y) << endl
#define watch(x) cout<<(#x)<<" is " << (x) << endl
#define fast ios_base::sync_with_stdio(false)
#define fie(i,a,b) for(i=a;i<b;i++)
#define MOD 1000000007
#define mod 998244353
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define ll long long
#define lld long long int
#define ALL(x) (x).begin(),(x).end()

typedef vector<lld> vi;
typedef vector<vector<lld>> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<pair<lld, lld>> vpi;
typedef long long LL;

const int N = 200009;
bool visited[N];

int main() {
  fast;
  cin.tie(0);
/*#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w" , stdout);
#endif*/
  lld n, k;
  cin >> n >> k;

  lld a[n];
  for (lld& x : a) {
    cin >> x;
    --x;
  }

  lld s = 0;
  lld p = a[s];
  visited[s] = true;
  vi path = {s};
  while (!visited[p]) {
    visited[p] = true;
    path.PB(p);
    p = a[p];
  }
  if (k < (lld)path.size()) {
    cout << path[k] + 1 << endl;
  } else {
    lld e = 0;
    while (e < (lld)path.size() && path[e] != p) e++;
    vi np;
    for (lld i = e; i < (lld)path.size(); i++) np.PB(path[i]);
    k -= e;
    cout << np[k % (lld)np.size()] + 1 << endl;
  }
}


Measured memory_bytes: 9280
#include <bits/stdc++.h>
using namespace std;
int main ()
{
    int n,x,t,ans=0;
    cin>>n>>x>>t;
    if (n%x == 0)
    {
        ans = (n/x) * t;
        cout<<ans<<endl;
    }
    else
    {
        ans = ((n/x) + 1)*t;
        cout<<ans<<endl;
    }
    
    
    
    return 0;
    
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int dp[MAXN];
int rdp[MAXN];
int ra[MAXN];
int rb[MAXN];

char S[MAXN];

bool solve(int st,int en)
{
    for(int i=st;i<=en;i++)
        dp[i] = 0;

    dp[st] = 1;

    for(int i=st+1;i<=en;i++){
        if(S[i-1]=='#')continue;
        else if(dp[i-1]||dp[i-2]){dp[i] = 1;}
    }

    return dp[en];
}

bool rsolve(int st,int en)
{
    for(int i=st;i<=en;i++)
        rdp[i] = 0;

    rdp[en] = 1;


    for(int i=en-1;i>=st;i--){
        if(S[i-1]=='#')continue;
        else if(rdp[i+1]||rdp[i+2]){rdp[i] = 1;}
    }

    return rdp[st];
}

int main()
{
    int n,m,k,a,b,c,d,x,y;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;

    cin>>n>>a>>b>>c>>d;

    scanf("%s",&S);

    if(c<d){
        bool juda = solve(a,c);
        bool judb = solve(b,d);
        if(juda&&judb)cout<<"Yes";
        else cout<<"No";
        return 0;
    }

    solve(a,c);
    rsolve(a,c);

    for(int i=a;i<=c;i++)
        if(dp[i]&&rdp[i])ra[i] = 1;

    solve(b,d);
    rsolve(b,d);

    for(int i=b;i<=d;i++)
        if(dp[i]&&rdp[i])rb[i] = 1;

    bool res = false;

    for(int i=b;i<=d;i++)
    {
        if(!rb[i])continue;
        if(ra[i-1]&&ra[i+1])res = true;
    }

    if(res)cout<<"Yes";
    else cout<<"No";

    return 0;
}


Measured memory_bytes: 2944