akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define F(i,n) for (int i = 0; i < n; ++i)
#define F1(i,n) for (int i = 1; i <= n; ++i)
#define dbg(x) cerr << #x << " = " << x << endl
#define dbgg(x) cerr << #x << " = " << x << ' '
#define T(x) x[pool]
#define mineq(x,y) { if ((x) > (y)) (x) = (y); }
#define maxeq(x,y) { if ((x) < (y)) (x) = (y); }
#define MEOW cout << "meowwwww" << '\n'; system("pause");
#define int long long
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;

template<typename T>
ostream& operator <<(ostream &s, const vector<T> &c)
{
	s << "[ "; for (auto it : c) s << it << " "; s << "\b]\n";
	return s;
}

template<typename T>
ostream& operator <<(ostream &s, const pair<int, T> &c)
{
	s << "[ "; cout << c.fi << " , " << c.se << " ] ";
	return s;
}

const int maxn = 267890, mod = 1000000007, LL = 262144;
int H;
int L;
int a[maxn];
int val[maxn], vval[maxn];
int fac[maxn], inv[maxn];
int ans;

void input()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> H;
	L = 1 << (H - 1);
	F1 (i, L) cin >> a[i];
}

void gao2(int l, int r, vector<pii> p, vector<pii> q, int lca)
{
	if (p.size() == 0) return;
	if (q.size() == 0) return;
	//dbgg(l); dbgg(r);
	//dbgg(p);
	//dbg(q);
	int m = (l + r) >> 1;
	if (l == r) return;
	vector<pii> s, t, u, v;
	for (auto x : p)
		if (x.fi <= m) s.pb(x);
		else t.pb(x);
	for (auto x : q)
		if (x.fi <= m) u.pb(x);
		else v.pb(x);
	//dbgg(s);dbgg(t);dbgg(u);dbg(v);
	int S = 0, T = 0, U = 0, V = 0;
	for (auto x : s) S = (S + x.se) % mod;
	for (auto x : t) T = (T + x.se) % mod;
	for (auto x : u) U = (U + x.se) % mod;
	for (auto x : v) V = (V + x.se) % mod;
	ans = (ans + (S * V % mod + T * U % mod) * inv[lca] % mod) % mod;
	//dbg(ans);
	for (auto &x : s) x.se = x.se * inv[lca] % mod;
	for (auto &x : t) x.se = x.se * inv[lca] % mod;
	for (auto &x : u) x.se = x.se * inv[lca] % mod;
	for (auto &x : v) x.se = x.se * inv[lca] % mod;
	gao2(l, m, s, u, lca * 2);
	gao2(m + 1, r, t, v, lca * 2 + 1);
}

void gao(int l, int r, int lca)
{
	int m = (l + r) >> 1;
	if (l == r) return;
	vector<pii> p, q;
	for (int i = l; i <= m; ++i)
		p.pb(mp(a[i], val[i] * vval[a[i]] % mod));
	for (int i = m + 1; i <= r; ++i)
		q.pb(mp(a[i], (val[i] * vval[a[i]] % mod) * inv[lca] % mod));
	gao2(1, L, p, q, 1);
	for (int i = l; i <= r; ++i)
		val[i] = val[i] * inv[lca] % mod;
	gao(l, m, lca * 2);
	gao(m + 1, r, lca * 2 + 1);
}

int power(int x, int y)
{
	if (y == 1) return x;
	int ret = power(x, y / 2);
	ret = ret * ret % mod;
	if (y & 1) ret = ret * x % mod;
	return ret;
}

void solve()
{
	F1 (i, L)
	{
		int cur = i + L - 1;
		val[i] = 1;
		while (cur >= 1)
		{
			val[i] = val[i] * cur % mod; 
			cur >>= 1;
		}
		vval[i] = val[i];
	}
	fac[0] = 1;
	F1 (i, LL) fac[i] = fac[i - 1] * i % mod;
	inv[LL] = power(fac[LL], mod - 2);
	for (int i = LL - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
	F1 (i, LL) inv[i] = inv[i] * fac[i - 1] % mod;
	gao(1, L, 1);
	cout << ans << '\n';
}

main()
{
	input();
	solve();
}


Measured memory_bytes: 21704
c['   '],n=1e6;main(i,j){for(i=2;i*i<n;i++)for(j=i;!c[i]&&j<n;c[j+=i]=1);for(i=1;i++<n;c[i]=c[i-1]+!c[i]);for(;~scanf("%d",&n);printf("%d\n",c[n]));}

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

#define mod 1000000007

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

using namespace std;
typedef long long ll;
const long long INF = 1LL << 60;
 
int main(void){
	
	int X, Y, Z;
    cin >> X >> Y >> Z;

    cout << Z << " " << X << " " << Y << endl;
	
	return 0;
}

Measured memory_bytes: 256
S=input()
ans=True
for i in range(len(S)):
    if((i+1)%2==1):
        if(not(S[i]=="R" or S[i]=="U" or S[i]=="D")):
            ans=False
            continue
    else:
        if (not (S[i] == "L" or S[i] == "U" or S[i] == "D")):
            ans = False
            continue

if(ans):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<queue>
#include <algorithm>
#include<functional>
#include<cstdlib>
#include<cmath>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define CI cin >>
#define CO cout <<
#define E << endl;

using namespace std;

typedef pair<int, int> P;
typedef pair<long, long> LP;
typedef pair<int, P> PP;
typedef pair<long, LP> LPP;



int dy[] = { 0, 0, 1, -1, 0 };
int dx[] = { 1, -1, 0, 0, 0 };

int A = 0, B = 0, K = 0, T = 0, W = 0, N = 0, H = 0;
int n = 0;
double L = 0;
double S = 0;
double ar = 0, br = 0, cr = 0;
int answer = 0;

string C;
string sA, strB;
vector<vector<char>> map;
vector<double> num;
vector<string> str;

int sum = 0;

vector<int> value;
vector<int> weight;

int dp[110][10010];

int data_[210][2] = {-2};

void input() {
	int i = 0;

	

	return;
}


int main(void) {
	input();
	int i = 0;
	int sum = 0;
	int numb = 0;
	int a = 0;
	int b = 0;

	while ((scanf("%d%d",&a,&b)) != EOF) {
		sum = a + b;
		while (sum != 0) {
			numb++;
			sum /= 10;
		}
		CO numb E
		numb = 0;
	}



	return 0;
}

Measured memory_bytes: 3044
#include<bits/stdc++.h> 
using namespace std; 
  
#define PI 3.1415 
  
double circumference(double r) 
{ 
    double cir = 2*PI*r; 
    return cir; 
} 
  
// driver function 
int main() 
{ 
  double r;
  cin>>r;
  cout<<circumference(r); 
  return 0; 
}  

Measured memory_bytes: 3788
INF = 10**18

N,M = map(int,input().split())
edge = [list(map(int,input().split())) for i in range(M)]

graph = [[] for _ in range(N)]

for e in edge:
    graph[e[0]-1].append([e[1]-1,-e[2]])
    
dist = [INF for _ in range(N)]
dist[0] = 0

for _ in range(N):
    flag = False
    for node,g in enumerate(graph):
        for adj,cost in g:
            if dist[node] != INF and dist[node]+cost < dist[adj]:
                dist[adj] = dist[node]+cost
                if _==N-1:
                    update = adj
                flag = True
    if not flag:
        print(-dist[N-1])
        break
else:
    visited = [0 for _ in range(N)]
    visited[update] = 1
    stack = [update]
    while stack:
        node = stack.pop()
        for adj,c in graph[node]:
            if not visited[adj]:
                visited[adj] = 1
                stack.append(adj)
    if visited[N-1]:
        print('inf')
    else:
        print(-dist[N-1])
        

Measured memory_bytes: 48216
n,m=map(int,input().split())
a=[list(map(int,input().split()[1:]))for i in range(n)]
x=0
for i in range(1,m+1):
    c=0
    for j in range(n):
        if i in a[j]:
            c+=1
        else:continue
    if c==n:
        x+=1
    else:continue
print(x)

Measured memory_bytes: 3060
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
using namespace std;

int main(void)
{
    string S;
    cin >> S;

    for (int i = 0; i < (int)S.size(); i++) {
        bool bad = false;
        if (i % 2 == 0 && S[i] == 'L')
            bad = true;
        else if (i % 2 == 1 && S[i] == 'R')
            bad = true;

        if (bad == true) {
            cout << "No" << endl;

            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
r1, c1, r2, c2 = map(int, input().split())
N = 10 ** 7
MOD = 10 ** 9 + 7
def createFacArr(n, mod):
    '''
    二項係数計算用の配列の作成

    Parameters
    n : int
        配列のサイズ
    mod : int
        あまり

    Returns
    fac : list
        階乗のリスト
    finv : list
        modの逆元のリスト
    ivn : list
    '''
    fac = [0] * n
    finv = [0] * n
    inv = [0] * n
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod
    return fac, finv
fac, finv = createFacArr(N+100, MOD)

def comb(n ,k, mod):
    '''
    二項係数の計算

    Parameters
    n : int
        元集合
    k : int
        元集合から選択する数
    mod : int
        あまり
    Returns
    c : int
        nCkの組み合わせの数
    '''
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 0

for c in range(c1,c2+1):
    ans += comb(r2+c+1, c+1, MOD) - comb(r1-1+c+1, c+1, MOD)
    ans %= MOD

print(ans)



Measured memory_bytes: 269720
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main(){
    int k,t;
    cin>>k>>t;
    vector<int> a(t);
    rep(i,t) cin>>a[i];
    sort(all(a));
    if(k-a[t-1]>=a[t-1]-1) cout<<0<<endl;
    else{
        cout<<a[t-1]-1-(k-a[t-1])<<endl;
    }
}



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

using namespace std;

int main() {
    int n, m, M;
    cin >> n >> m;
    M = m;
    for(int i=1; i<n; i++) {
        int x;
        cin >> x;
        m = min(m, x);
        M = max(M, x);
    }
    cout << M - m << endl;

}

Measured memory_bytes: 256
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define repr4(i,s,n) for(ll i = (n);i>=(s);i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
using Graphw = vector<vector<pair<ll,ll>>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/
const int mod = 1000000007;




int main() {
string S;
cin>>S;
int ans,min_=10000;

rep(i,S.size()-2){
int num=0;
num=(S[i]-'0')*100+(S[i+1]-'0')*10+(S[i+2]-'0');
min_=min(min_,abs(num-753));
}
cout<<min_<<endl;
return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
string cts(char x) {string t(1,x); return t;}
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> void chmax(T& a, T b) { a = max(a, b); }
template <typename T> void chmin(T& a, T b) { a = min(a, b); }
const int MAXN = -1;
#ifndef LOCAL
#define cerr if(0)cout
#endif
 
int32_t main() 
{
	IAMSPEED
	int a[10];
	cin >> a[1] >> a[2] >> a[3] >> a[4] >> a[5];
	FOR(i,1,5) {
		if(a[i]==0)return cout << i, 0;
	}
}


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

int main(){
    int N,Q;
    cin >> N >> Q;
    
    long long a[N];
    long long x[Q];
    for(int i=0; i<N; i++){
        cin >> a[i];
    }
    for(int i=0; i<Q; i++){
        cin >> x[i];
        
        int right=0;
        long long count=0;
        long long sum=0;
        for(int left=0; left<N; left++){
            
            while(right < N){
                if(sum + a[right] > x[i]){
                    break;
                }
                sum += a[right];
                right++;
            }
            
            count += right - left;
            
            if(left == right){
                right++;
            }else{
                sum -= a[left];
            }
            
        }
        cout << count << endl;
    }
    
    
    return 0;
}



Measured memory_bytes: 3900
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001;
#define LLINF 1001001001001001001001;
#define LL long long

int main(){
    int A,B,X;
    scanf("%d %d %d",&A,&B,&X);long long int ans=0;
    if(X<A)printf("NO\n");
    else if(X<=A+B)printf("YES\n");
    else printf("NO\n");
}

Measured memory_bytes: 128
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int i=1;
while(true){
int x=scan.nextInt();
if(x==0){break;}
else{
System.out.println("Case" + " " + i + ":" + " " + x );
i=i+1;
}}}}

Measured memory_bytes: 41212
#include<iostream>
using namespace std;
int p[100000];

int main(){
	int n;
	int cnt=0;
	int buf;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>p[i];

	for(int i=0;i<n;i++){
		if(p[i]==i+1){
			cnt++;
			buf=p[i];p[i]=p[i+1];p[i+1]=buf;
		}
	}
	cout<<cnt<<endl;

	return 0;
}



Measured memory_bytes: 640
#include<stdio.h>

int t1[25];
float t2[25];
int i;
int run[6];
int z=0;

void pick(int s, int g, int f1){
  int st_n=0, nd_n=0;
  float st_t=50, nd_t=50;
  int f2,j;
  
  for(i=s;i<=g;i++){
    f2=1;
    if(st_t>t2[i]){
      if(f1){
	for(j=0;j<6;j++){
	  if(run[j]==t1[i])
	    f2=0;
	}
      }
      if(f2){
	nd_n=st_n;
	nd_t=st_t;
	st_n=t1[i];
	st_t=t2[i];
      }
    }
    else if(nd_t>t2[i]){
      if(f1){
	for(j=0;j<6;j++){
	  if(run[j]==t1[i])
	    f2=0;
	}
      }
      if(f2){
	nd_n=t1[i];
	nd_t=t2[i];
      }
    }
  }
  printf("%d %.2f\n%d %.2f\n",st_n,st_t,nd_n,nd_t);
  run[z++]=st_n;
  run[z++]=nd_n;
}

int main(){

  for(i=1;i<=24;i++)
    scanf("%d%f",&t1[i],&t2[i]);

  pick( 1, 8,0);
  pick( 9,16,0);
  pick(17,24,0);
  pick( 1,24,1);
  
  return 0;
}

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

int n;
int a[4000];
long long int joi[2000][2000];
long long int ans;

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

	for(int i=0; i<n; i++){
		joi[i][0] = a[i];
	}
	for(int i=0; i<n; i++){
		joi[i][1] = max(a[i], a[i+1]);
	}
	for(int j=2; j<n; j++){
		for(int i=0; i<n; i++){
			if(a[i+1] < a[i+j]) joi[i][j] = max(joi[i][j], a[i] + joi[(i+1)%n][j-2]);
			else joi[i][j] = max(joi[i][j], a[i] + joi[(i+2)%n][j-2]);
			if(a[i] < a[i+j-1]) joi[i][j] = max(joi[i][j], a[i+j] + joi[i][j-2]);
			else joi[i][j] = max(joi[i][j], a[i+j] + joi[(i+1)%n][j-2]);
		}
	}
	for(int i=0; i<n; i++){
		ans = max(ans, joi[i][n-1]);
//		printf("%lld\n", joi[i][n-1]);
	}
	printf("%lld\n", ans);
}

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

using namespace std;

using ll = long long;

struct ALB{
  ll a; // 日数
  ll b; // 報酬

  // 演算子オーバーロード priority_queueの優先度
  bool operator<(const ALB& another) const {
    return (b == another.b) ? (a < another.a) : (b < another.b);
  }
};

// ソート用
bool cmp_alb(const ALB &x, const ALB &y){
  return (x.a == y.a) ? (x.b > y.b) : (x.a < y.a);
}

int main(){
  ll n, m;

  cin >> n >> m;

  vector <ALB> alb;
  ALB tmp_alb;
  for(ll i = 0; i < n; i++){
    cin >> tmp_alb.a >> tmp_alb.b;
    --tmp_alb.a;
    cin.ignore();
    if(tmp_alb.a <= m - 1){
      alb.push_back(tmp_alb);
    }
  }

  n = alb.size(); // 実際のサイズに書き換える
  if(n == 0){
    cout << 0 << endl;
    return 0;
  }
  sort(alb.begin(), alb.end(), cmp_alb); // この時点でaがm以下しか入っていない

  // 末尾からスタックのごとく引っこ抜く

  tmp_alb = alb[n - 1];

  ll income = 0;

  ALB max_alb;

  //for(ll i = 0; i < n; i++){
  //  cout << alb[i].a << " " << alb[i].b << endl;
  //}

  // A[i] ポインタとも
  int ptrs_begin[m], ptrs_end[m];
  for(int i = 0; i < m; i++){
    ptrs_begin[i] = -1; // NULLの代用
    ptrs_end[i] = -1; // NULLの代用
  }

  // 登録
  ptrs_begin[alb[0].a] = 0;
  ptrs_end[alb[n-1].a] = n-1;
  for(int i = 1; i < n; i++){
    if(alb[i-1].a != alb[i].a){
      ptrs_end[alb[i-1].a] = i - 1;
      ptrs_begin[alb[i].a] = i;
    }
  }

  // 優先度キューに突っ込みながら候補出しする

  priority_queue<ALB> que;

  // 1日前からループ
  for (int i = 0; i < m; i++){
    if(ptrs_begin[i] != -1){
      for(int j = ptrs_begin[i]; j <= ptrs_end[i]; j++){
        que.push(alb[j]);
        //cout << "alb[j] = " << alb[j].a << " " << alb[j].b << endl;
      }
    }
    if(que.empty() == true) continue;
    tmp_alb = que.top();
    //cout << "que.top() = " << tmp_alb.a << " " << tmp_alb.b << endl;
    income += tmp_alb.b;
    que.pop();
  }
  cout << income << endl;
}
    
  


Measured memory_bytes: 5616
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
    int n,k;cin>>n>>k;
    int a[n+2];
    a[0] = 0;
    for(int i=1;i<=n;i++)
        {cin>>a[i];}
    int dp[n+2][k+2];

   for(int j=0;j<=k;j++){
       dp[1][j] = a[1]>=j ? 1 : 0;
   }

   for(int i = 2; i<=n; i++){
       for(int j = 0; j<=k; j++){
           if(j==0){dp[i][j] = dp[i-1][j];}
           else
           {
               dp[i][j] = (1000000007 + dp[i][j-1] + dp[i-1][j] - ((j-1-a[i])>=0 ? dp[i-1][j-1-a[i]] : 0))%1000000007;
           }
       }
   }
   cout<<dp[n][k];

}

Measured memory_bytes: 81744
import math
import itertools
n = int(input())
lis = [list(map(int, input().split())) for i in range(n)]
dislis = []
for i in range(n):
    dislis.append([])
    for j in range(n):
        dislis[i].append(math.sqrt((lis[i][0]-lis[j][0])**2 + (lis[i][1]-lis[j][1])**2))

lenlis = []
cnt = 0
for v in itertools.permutations(range(n+1)[1:], n):
    cnt += 1
    lenlis.append([])
    for i in range(len(v)):
        if i != len(v)-2:
            lenlis[cnt-1].append(dislis[v[i-1]-1][v[i]-1])
anslis = []
cntcnt = 0
for i in lenlis:
    anslis.append(sum(lenlis[cntcnt]))
    cntcnt += 1
print(sum(anslis)/len(anslis))

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

const int nil = -1;

class Node{
  int parent, left, right;
public:
  int key;
  Node(){
  }
  
  int ParentId(int id){
    return (id != 1) ? (parent = id / 2) : nil;
  }
  int LeftId(int id){
    return left = 2 * id;
  }
  int RightId(int id){
    return right = 2 * id + 1;
  }
  
};

void maxHeapify(vector<Node> &heap, int id){
//  auto left = heap[id].LeftId(id);
//  auto right = heap[id].RightId(id);
  auto left = id * 2;
  auto right = left + 1;
  auto largest = (left <= heap.size() && heap[left].key > heap[id].key) ? left : id;
  // 子と自分のの中で最大のノードを

  if(right <= heap.size() && heap[right].key > heap[largest].key)
    largest = right;

  if(largest != id){
//    auto tmp = heap[id].key;
//    heap[id].key = heap[largest].key;
//    heap[largest].key = tmp;
    swap(heap[id], heap[largest]);
    maxHeapify(heap, largest);
  }

}


void buildMaxHeap(vector<Node> &heap){
  for(int i = heap.size() / 2; i >= 1; i--){
    maxHeapify(heap, i);
  }
}

int main(){
  int n;
  cin >> n;
  vector<Node> heap(n + 1);

  for(auto i = 1; i <= heap.size() - 1; i++){
    cin >> heap[i].key;
  }

  buildMaxHeap(heap);

  for(auto i = 1; i <= heap.size() - 1; i++){
    cout << " " << heap[i].key;
  }

  cout << endl;

  return 0;
}



Measured memory_bytes: 10720
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = 998244353
INF = int(1e15)


def calc(N):
    return sum(int(x) for x in str(N))


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    D = Scanner.map_int()
    if D[0] != 0:
        print(0)
        return
    if D.count(0) != 1:
        print(0)
        return
    C = Counter(D)
    ans = 1
    for i in range(1, len(C) + 1):
        ans *= C[i-1] ** C[i]
        ans %= MOD
    print(ans)
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 65272
#include<stdio.h>

main(){
int s=0;
scanf("%d",&s);

int m=0;
int h=0;

//s???????????????????????????s?????????????????????
while(s>3599){
s=s-3600;
h++;

}

while(s>59){
s=s-60;
m++;
}

printf("%d:%d:%d\n",h,m,s);
return(0);
}

Measured memory_bytes: 1844
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x, k, d;
int main()
{
    std::ios::sync_with_stdio(false);
    cin >> x >> k >> d;
    if(x < 0) x = -x;
    if(x / d >= k)
    {
    	cout << x - k * d << endl;
    	return 0;
	}
	if(x / d % 2 == k % 2) cout << x % d << endl;
    else cout << d - x % d << endl;
	return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
  int a;
  string b;
  cin>>b;
  a=stoi(b);
  ll c=b.size();
  ll d=0;
  for(ll i=0;i<c;i++){
    int e=b.at(i)-'0';
    d+=e;
  }
  if(a%d==0){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
  
  return 0;
}


Measured memory_bytes: 3560
import collections

N,K = map(int,input().split())
A = list(map(int,input().split()))

count = collections.Counter(A)
c = []
for i in count:
    c.append([count[i],i])

c.sort()

l = len(c)
ans = 0
for i in range(0,max(0,l-K),1):
    ans += c[i][0]

print(ans)


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

int main(){
  int k;
  int ans=1;
  int flag = false;
  cin >> k;
  int amari = 7;
  rep(i, 1000005){
    if(amari%k==0){
      flag=true;
      break;
    }
    amari = (amari%k)*10+7;
    ans++;
  }

  if(flag)cout << ans;
  else cout << "-1";
  return 0;
}


Measured memory_bytes: 3668
N = gets.to_i
A = gets.chomp.split(" ").map(&:to_i)

def search_half(a, n)
  a_s = a[n]
  a_i = a.bsearch_index{|x| x >= a_s / 2}
  if a_i == 0 then
    [[a[a_i], a_s - a[a_i]]]
  else
    [[a[a_i], a_s - a[a_i]], [a[a_i-1], a_s - a[a_i-1]]]
  end
end

wk = 0
al = A.map{|a| wk += a; wk}
wk = 0
ar = A.reverse.map{|a| wk += a; wk}
ans = 10 ** 9
1.upto(N-3){|n|
  al_a = search_half(al, n)
  ar_a = search_half(ar, N-n-2)
  al_a.product(ar_a){|(a, b), (c, d)|
    l = [a, b, c, d]
    wk = l.max - l.min
    ans = wk if ans > wk
  }
}

puts ans


Measured memory_bytes: 26244
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
#include<algorithm>
#include<map>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
int r;
int a[100005],b[100005],c[100005],d[100005],e[100005];
int main()
{
	int n,i,j,t,k,l,o,m,q,w;
	cin>>m>>t>>k;
	for(i=1;i<=m;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=1;i<=t;i++)
	{
		scanf("%d",&b[i]);
	}
	for(i=1;i<=k;i++)
	{
		scanf("%d%d%d",&c[i],&d[i],&e[i]);
		if(i==1) r=a[c[1]]+b[d[1]]-e[1];
	r=min(r,a[c[i]]+b[d[i]]-e[i]);
	}
	sort(a+1,a+1+m);
	sort(b+1,b+1+t);
	r=min(a[1]+b[1],r);
	cout<<r;
	
 } 

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

int main(){
	int n, i, total = 100000;

	cin >> n;
	for(i = 0; i < n; i++){
		total = total * 1.05;
		if(total % 1000 != 0){
			total += 1000 - (total % 1000);
		}
	}
	cout << total << endl;

	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1)/ (y))
#define MOD 1000000007ULL

char S[5];

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

    cin >> S;

    int *ans = new int[100]();

    ++ans[S[0] - 'A'];
    ++ans[S[1] - 'A'];
    ++ans[S[2] - 'A'];
    ++ans[S[3] - 'A'];

    if (ans[S[0] - 'A'] == 2 && ans[S[1] - 'A'] == 2 && ans[S[2] - 'A'] == 2 && ans[S[3] - 'A'] == 2)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }

    return 0;
}



Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main(String args[]) {
    int rep = 1;
    if( args.length > 0 ) { rep = Integer.parseInt(args[0]); }
    (new Main()).__solve(rep);
  }

  void __solve(int rep) {

    try (
      Scanner cin = new Scanner(System.in);
    ) {

      for( int i = 0; i < rep; ++i ) {
        __solve(cin);
      }

    }

  }

  void __solve(Scanner cin) {

	  int N = cin.nextInt();
	  int K = cin.nextInt();
	  int Q = cin.nextInt();
	  
	  int array[] = new int[N];
	  
	  Pair pairs[] = new Pair[N];
	  
	  for( int i = 0; i < N; ++i ) {
		  array[i] = cin.nextInt();
	  }
	  
	  for( int i = 0; i < N; ++i ) {
		  int value = array[i];
		  int rest = K - 1;
		  int min = value;
		  int L = i - 1;
		  int R = i + 1;
		  while( rest > 0 ) {
			  if( L >= 0 && R < N ) {
				  if( array[L] < array[R] ) {
					  if( array[R] >= value ) {
						  --rest;
					  }
					  min = Math.min(min, array[R]);
					  ++R;
				  }
				  else {
					  if( array[L] > value ) {
						  --rest;
					  }
					  min = Math.min(min, array[L]);
					  --L;
				  }
			  }
			  else if( L >= 0 ) {
				  if( array[L] > value ) {
					  --rest;
				  }
				  min = Math.min(min, array[L]);
				  --L;
			  }
			  else if( R < N ) {
				  if( array[R] >= value ) {
					  --rest;
				  }
				  min = Math.min(min, array[R]);
				  ++R;
			  }
			  else {
				  // cannot remove this;
				  min = -1;
				  break;
			  }
		  }
		  pairs[i] = new Pair(value, min);
	  }
	  
	  Arrays.sort(pairs);
	  int ret = pairs[N - 1].value - pairs[0].value;

	  MAIN:
	  for(int i = 0; i + Q < N; ++i ) {
		  int start = pairs[i].value;
		  int index = i;
		  for(int j = 0; j < Q; ++j ) {
			  while( index < N && pairs[index].min < start ) { ++index; }
			  if( index == N ) { continue MAIN; }
			  if( j == Q - 1 ) {
				   ret = Math.min(ret, pairs[index].value - start);
			  }
			  ++index;
		  }
	  }
	  
	  System.out.println(ret);
	  
  }
  
  class Pair implements Comparable<Pair> {
	  int value;
	  // removed minimum value;
	  int min;
	  
	  Pair(int value, int min) {
		  this.value = value;
		  this.min = min;
	  }
	  
	  @Override
	  public int compareTo(Pair p) {
		  if( p.value > value ) { return -1; }
		  if( p.value < value ) { return 1; }
		  if( p.min > min ) { return 1; }
		  if( p.min < min ) { return -1; }
		  return 0;
	  }
  }

}


Measured memory_bytes: 28432
#include <stdio.h>

int main(){
  int i,H,A[100000];

  scanf("%d",&H);
  for(i=1;i<=H;i++) scanf("%d",&A[i]);

  for(i=1;i<=H;i++){
    printf("node %d: key = %d, ",i,A[i]);      
    if(1<=i/2) printf("parent key = %d, ",A[i/2]);
    if(i*2<=H) printf("left key = %d, ",A[i*2]);
    if(i*2+1<=H) printf("right key = %d, ",A[i*2+1]);

    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 608
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef vector<int>vi;
typedef pair<int,int>pi;
typedef vector<pi>vpi;
typedef vector<vi>vvi;
#define double long double
#define pow powl
#define sqrt sqrtl
#define cbrt cbrtl
#define floor floorl
#define ceil ceill
#define pb push_back
#define ep emplace_back
#define PB pop_back
#define pf push_front
#define ef emplace_front
#define PF pop_front
#define mp make_pair
#define ub(a,b) upper_bound(all(a),b)-a.begin()
#define lb(a,b) lower_bound(all(a),b)-a.begin()
#define bs(a,b) binary_search(all(a),b)
#define mem(a,b) memset(a,b,sizeof(a))
#define in(a,n) FOR(i,0,n-1) cin>>a[i]
#define in1(a,n) FOR(i,1,n) cin>>a[i]
#define ff first
#define ss second
#define out(a,n) FOR(i,0,n-1) cout<<a[i]<<" ";cout<<endl;
#define out1(a,n) FOR(i,1,n) cout<<a[i]<<" ";cout<<endl;
#define clr(a) a.clear()
#define pow2(a) (1LL<<a)
#define all(a) a.begin(),a.end()
#define all1(a) a.begin()+1,a.end()
#define rall(a) a.rbegin(),a.rend()
#define rall1(a) a.rbegin(),a.rend()
#define sz(a) ((int)a.size())
#define FOR(i,a,b) for(auto i=a;i<=b;i++)
#define NFOR(i,a,b) for(auto i=a;i>=b;i--)
const int mod=1e9+7;

inline int add(int a,int b){return (a%mod + b%mod)%mod;}
inline int sub(int a ,int b){return (a%mod - b%mod + mod)%mod;}
inline int mul(int a,int b){a%=mod;b%=mod;return a*b%mod;}
inline int power(int a,int b,int MOD){a%=mod;int res=1;while(b){if(b&1){res*=a;res%=MOD;}a=a*a;a%=MOD;b>>=1;}return res;}

#define trace(x) cout<<#x<<" :: "<<x<<endl;
#define trace2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define trace3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define trace4(x,y,z,w) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
clock_t time_p = clock();
void time()
{
  time_p = clock() - time_p;
  cerr << "Time elapsed : " << (double)(time_p)/CLOCKS_PER_SEC <<endl;
}
signed main()
{
     SPEED;
     int n;
     cin>>n;
     cout<<(n==7||n==5||n==3 ? "YES" : "NO")<<endl;
     time();
     return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define Max 100005
#define mem(a,b) memset(a,b,sizeof(a));
#define pb push_back
#define mp make_pair
const LL mod=1e9+7;
const ULL base=131;
const LL LL_MAX=9223372036854775807;
using namespace std;
int main()
{
    int r;
    scanf("%d",&r);
    printf("%d\n",3*r*r);
    return 0;
}


Measured memory_bytes: 256
import java.util.*
import java.math.*
import java.lang.Math.*

val readString: ()->String = {readLine()!!}
val readInt: ()->Int = {readLine()!!.toInt()}
val readLong: ()->Long = {readLine()!!.toLong()}
val readIntArray: ()->IntArray = {readLine()!!.split(' ').map{it.toInt()}.toIntArray()}
val readLongArray: ()->LongArray = {readLine()!!.split(' ').map{it.toLong()}.toLongArray()}
val errPrintln: (String)->Unit = {msg -> System.err.println(msg)}
val MOD = 1e9.toLong()+7
val INF = Int.MAX_VALUE/2
val LINF = Long.MAX_VALUE/2
data class IntPair(val first: Int, val second: Int)
data class To(val idx: Int, val cost: Long)


fun solve(): Int {
    var res = 0
    return res
}


fun main(args: Array<String>) {
    val (A,B) = readIntArray()

    //val ans = solve()
    val ans = A*B

    println(ans)
}


Measured memory_bytes: 36524
def gcd(a, b):
    if a == 0:
        return b

    return gcd(b % a, a)


n = int(input())
xs = list(map(int, input().split()))

g = gcd(xs[0], xs[1])
for x in xs[2:]:
    g = gcd(g, x)

print(g)

Measured memory_bytes: 15020
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define all(x) x.begin(),x.end()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
 
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

//
int main(void) {
    int A,B,C;
    cin >> A >> B >> C;
    if(A<C&&C<B) cout << "Yes" << endl;
    else if(B<C&&C<A) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
int g[110];
int h[110];
int p[110];
int q[110];
int dp2[11000];
int dp3[110][110];
int dp[110][110];
int main(){
	int a,b,c,d,e,f;
	scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
	for(int i=0;i<b;i++){
		scanf("%d%d",g+i,h+i);
	}
	for(int i=0;i<d;i++)scanf("%d%d",p+i,q+i);
	for(int i=0;i<d;i++){
		for(int j=0;j<10100;j++){
			dp2[j+q[i]]=max(dp2[j+q[i]],dp2[j]+p[i]);
		}
	}
	for(int i=0;i<110;i++)for(int j=0;j<110;j++)dp3[i][j]=-999999999;
	dp3[0][0]=0;
	for(int i=0;i<b;i++){
		for(int j=b-1;j>=0;j--){
			for(int k=0;k<110;k++){
				if(dp3[j][k]<0)continue;
				if(k+g[i]<110){
					dp3[j+1][k+g[i]]=max(dp3[j+1][k+g[i]],dp3[j][k]+h[i]);
				}
			}
		}
	}
	bool ok=false;
	for(int i=1;i<=a;i++)dp3[c][i]=max(dp3[c][i],dp3[c][i-1]);
	for(int i=0;i<=a;i++)if(dp3[c][i]>=0)ok=true;
	if(!ok){printf("-1\n");return 0;}
	for(int i=0;i<110;i++)for(int j=0;j<110;j++)dp[i][j]=-999999999;
	dp[0][a]=0;
	for(int i=0;i<f;i++){
		for(int j=0;j<=a;j++){
			if(dp[i][j]<0)continue;
			for(int k=0;k<=min(j+e,a);k++){
				if(dp3[c][k]>=0){
					dp[i+1][min(j+e,a)-k]=max(dp[i+1][min(j+e,a)-k],dp[i][j]+dp2[dp3[c][k]]);
				}
			}
		}
	}
	int ret=-999999999;
	for(int i=0;i<=a;i++)ret=max(ret,dp[f][i]);
	if(ret<0){
		printf("-1\n");return 0;
	}
	printf("%d\n",ret);
}

Measured memory_bytes: 1160
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define REP(i, n) for(int i = 0;i < (n);i++)
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const int mod=1000000007 ;
const llint inf=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool chmin(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool chmax(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void){
	cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);
	int i,n;cin>>n;
	if(n==2){cout<<"-1\n";return 0;}
	vector<int>a(n+1);
	vector<int>g(n+1);
	for(i=1;i<=n;i++){cin>>a[i];g[a[i]]++;}a[0]=0;
	//残り全員がダメ を持ってると優先
	int mae=0;
	deque<int>aaa(n);
	priority_queue<pair<int,int>>que;
	for(i=1;i<=n;i++){aaa[i-1]=i;que.push(mp(g[i],i));}
	vector<bool>use(n+1);
	for(i=1;i<=n-6;i++){
		int t;bool yu=false;
		while(que.size()&&que.top().fir>=n-i){
			t=que.top().sec;
			que.pop();
			if(use[t]){continue;}
			else if(g[t]>=n-i){yu=true;break;}
			else{que.push(mp(g[t],t));}
		}//必ずそいつを入れる
		if(yu){aaa.erase(lower_bound(aaa.begin(),aaa.end(),t));}
		else if(a[mae]==aaa[0]){t=aaa[1];aaa.erase(aaa.begin()+1);}
		else{t=aaa[0];aaa.erase(aaa.begin());}
		
		//for(auto it:aaa){cerr<<it;}cerr<<endl;
		cout<<t<<" ";
		use[t]=1;
		g[a[t]]--;
		mae=t;
	}
	//残りはわずかなのでnext_permutationします
	do{
		int m=aaa.size();
		if(a[mae]==aaa[0]){continue;}
		bool dame=false;
		for(i=0;i<m-1;i++){
			if(a[aaa[i]]==aaa[i+1]){dame=true;break;}
		}
		if(dame){continue;}
		for(i=0;i<m;i++){cout<<aaa[i]<<" ";}
		return 0;
	}while(next_permutation(aaa.begin(),aaa.end()));
	cout<<"-1\n";
	return 0;
}


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

const int MAX = 1e5 + 5;

#define dbg(a) cout << "-> " << __LINE__ << ": " << #a << " = " << a << endl

int median (vector <int> &a) {
	int n = (int) a.size();
	sort(a.begin(), a.end());
	if (n & 1) {
		return a[n / 2];
	}
	return a[n / 2] + a[n / 2 - 1];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector <int> l(n), r(n);
	for (int i = 0; i < n; i++) {
		cin >> l[i] >> r[i];
	}
	int med1 = median(l), med2 = median(r);
	cout << med2 - med1 + 1 << '\n';
	return 0;
}


Measured memory_bytes: 4720
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int K = sc.nextInt();
		String S = sc.next();
		char[] arys = S.toCharArray();
		arys[K - 1] += 32;
		String ans = new String(arys);
		System.out.println(ans);
	}
	static class ex{
		int v;
		int q;
		public ex(int q, int v) {
			this.v = v;
			this.q = q;
		}
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

Measured memory_bytes: 19412
s = input()

while s != "":
	is_match = False
	for word in ("dream", "dreamer", "erase", "eraser"):
		if s[-len(word):] == word:
			s = s[:-len(word)]
			is_match = True
	if is_match == False:
		print("NO")
		exit()
print("YES")

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

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define deb(x)	cout << #x << " " << x << endl;

typedef long long int ll;

int main() {

	IOS

	ll x, k, d;
	cin >> x >> k >> d;

	x = abs(x);

	ll t = x / d;

	if (t <= k) {
		ll z = x - t*d;
		ll y = abs(z - d);

		if (k%2 == 1) {
			if (t%2 == 0)
				cout << y;
			else
				cout << z;

		} else {
			if (t%2 == 1)
				cout << y;
			else
				cout << z;
		}

	} else {
		cout << x - k*d;
	}

	ll z = x % d;

	return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <vector>
using namespace std;
const long long INF = (1e9);
int main(){
  int N, W;
  cin >> N >> W;
  vector<long long> DP(W+1,-INF);
  DP[0] = 0;
  for(int i = 0; i < N; ++i){
    vector<long long> DP_ = DP;
    int v, w;
    cin >> v >> w;
    for(int j = 0; j <= W-w; ++j){
      DP_[j+w] = max(DP_[j+w], DP[j] + v);
    }
    DP = DP_;
  }
  long long ans = 0;
  for(int i = 0; i <= W; ++i) ans = max(ans, DP[i]);
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3280
#include<bits/stdc++.h>
using namespace std;
string st1,st2;
int main()
{
    cin>>st1;
    int m=-1;
    for (int i=st1.size()-1;i>=0;i--) 
    {
    	m++;
        st2+=st1[i];
        if (st2[m]=='b') st2[m]='d'; else
        if (st2[m]=='d') st2[m]='b';
        if (st2[m]=='p') st2[m]='q'; else
        if (st2[m]=='q') st2[m]='p';
    }
    if (st1==st2) cout<<"Yes"; else cout<<"No";
    return 0;
}

Measured memory_bytes: 512
'use strict'

const main = arg => {
    const input = arg.trim().split("\n");
    const nums = input[1].split(" ").filter((obj, i) => i < Number(input[0]))
                                    .map(num => parseInt(num, 10));
    const result = [];
    for(let i=nums.length-1;i>=0;i--){
        result.push(nums[i]);
    }

    console.log(result.join(" "));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 15544
#include<iostream>
#include<deque>
using namespace std;
int n,l,a[1<<20];
main()
{
	cin>>n>>l;
	deque<int>P;
	for(int i=0;i<l;i++)
	{
		cin>>a[i];
		while(!P.empty()&&a[P.back()]>=a[i])P.pop_back();
		P.push_back(i);
	}
	cout<<a[P.front()];
	if(P.front()==0)P.pop_front();
	for(int i=l;i<n;i++)
	{
		if(!P.empty()&&P.front()==i-l)P.pop_front();
		cin>>a[i];
		while(!P.empty()&&a[P.back()]>=a[i])P.pop_back();
		P.push_back(i);
		cout<<" "<<a[P.front()];
	}
	cout<<endl;
}



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

int dp[2001];

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

    int n,K; cin>>n>>K; vector<int> b[10];
    for (int i = 0; i < n; i++){
        int v,s; cin>>v>>s; b[--s].push_back(v);
    }
    fill(dp,dp+K+1,-1);
    dp[0]=0;
    for (int i = 0; i < 10; i++){
        sort(b[i].rbegin(),b[i].rend());
        for (int j = K-1; j >= 0; j--){
            if(dp[j]==-1)continue;
            int sum=0;
            for (int k = 0; k < b[i].size() && j+k < K; k++){
                sum+=b[i][k];
                dp[j+k+1]=max(dp[j+k+1],dp[j]+sum+k*(k+1));
            }
        }
    }
    cout<<dp[K]<<'\n';
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

int n;
int a[111];

int main(){
	cin>>n;
  rep(i,n)cin>>a[i];
  cout<<a[0];
  repl(i,1,n){
    cout<<" "<<a[i];
  }
  cout<<endl;
  repl(i,1,n){
    int v=a[i];
    int j=i-1;
    while(j>=0&&a[j]>v){
      a[j+1]=a[j];
      j--;
    }
    a[j+1]=v;
    cout<<a[0];
    repl(i,1,n){
      cout<<" "<<a[i];
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3076
N = int(input())

h_list = list(map(int, input().split()))

pre_j = h_list[0]
f = 0
for j in h_list[1:]:
    if pre_j > j:
        f = 1
        break
    else:
        if pre_j < j:
            pre_j = j - 1

if f == 1:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 15020
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
  int a, b;
  char op;
  while(1){
    cin >> a >> op >> b;
    if(op == '+'){
      cout << a + b << endl;
    }else if(op == '-'){
      cout << a - b << endl;
    }else if(op == '*'){
      cout << a * b << endl;
    }else if(op == '/'){
      cout << a / b << endl;
    }else{
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 3124
#include<bits/stdc++.h>
using namespace std;
string s,t;
int dp[3007][3007];
int main()
{
	cin>>s>>t;
	int n=s.length(),m=t.length();
	s="*"+s;
	t="."+t;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=max(max(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]+(s[i]==t[j]));
		}
	}
	string ans;
	while(dp[n][m])
	{
		if(dp[n][m]==dp[n][m-1])
		{
           m--;
		}
		else if(dp[n][m]==dp[n-1][m]) n--;
		else
        {
           ans=s[n]+ans;
          n--,m--;
        } 
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 38864
def main():
    S = input()

    str_ = {'a': 0, 'b': 0, 'c': 0}
    for s in S:
        str_[s] += 1

    if abs(str_['a'] - str_['b']) < 2 and \
            abs(str_['b'] - str_['c']) < 2 and \
            abs(str_['c'] - str_['a']) < 2:
        print('YES')
    else:
        print('NO')

main()


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e5 + 5, M = 1e9 + 7;
ll a[N][3], dp[N][3];
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++)
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    for (ll j = 0; j < 3; j++)
        dp[0][j] = a[0][j];
    for (ll i = 1; i < n; i++)
        for (ll j = 0; j < 3; j++)
            for (ll k = 0; k < 3; k++)
                if (j != k)
                    dp[i][k] = max(dp[i][k], dp[i - 1][j] + a[i][k]);
    cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});
}

Measured memory_bytes: 4992
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>

using namespace std;

int main()
{
	int n;
	while(cin >> n , n!=0)
	{
		vector<string> s(n);
		for(int i=0;i<n;i++)
			cin >> s[i];
		for(int i=0;i<n;i++)
		{
			for(int j=s[i].size()-1;j>=0;j--)
			{
				if(s[i][j]=='.')
				{
					s[i][j]='+';
					break;
				}
			}
		}
		vector<bool> line(2000,false);
		for(int i=n-1;i>=0;i--)
		{
			for(int j=0;j<s[i].size();j++)
			{
				if(line[j]==true and s[i][j]=='.')
				{
					s[i][j]='|';
				}
				else if(s[i][j]!='.')
				{
					line[j]=true;
					for(int k=j+1;k<line.size();k++)
						line[k]=false;
					break;
				}
			}
		}
		for(int i=0;i<n;i++)
			for(int j=0;j<s[i].size();j++)
				if(s[i][j]=='.')
					s[i][j]=' ';
		
		for(int i=0;i<n;i++)
			cout << s[i] << endl;
	}



	
}


Measured memory_bytes: 3704