akhauriyash/Code-Regression huggingface dataset:
from sys import stdin

n, p = map(int, stdin.readline().split(' '))
a = map(int, stdin.readline().split(' '))

dp = [ range(n+1), range(n+1) ]
dp[p][n] = 1
dp[p^1][n] = 0
for i in xrange(n-1, -1, -1):
   for k in [0,1]: dp[k][i] = dp[k][i+1] + dp[(k+a[i])%2][i+1]

#print dp

res = dp[0][0]

print res

Measured memory_bytes: 2568
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2) % mod;
}
/*--------Library Zone!--------*/

int n, k;
int dp[2005][2005];
signed main() {
	cin >> n >> k;
	dp[1][1] = 1;
	REP(i, n + 1) {
		REP(j, n + 1) {
			dp[i + 1][j + 1] += dp[i][j];
			dp[i + 1][j] += dp[i][j];
			dp[i + 1][j + 1] %= mod;
			dp[i + 1][j] %= mod;
		}
	}
	REP(i, k + 1) {
		if (n - k + 1 < i) {
			cout << 0 << endl; continue;
		}
		int memo = n - k;
		memo -= i - 1;
		cout << dp[k][i] * comb(memo + i, memo) % mod << endl;
	}
}

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

using namespace std;
const int N=1e5+7;
const int M=1e5*2+50;
int n,m;
int hh[N];

int h[M], w[M], e[M], ne[M], idx;

bool st[N];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int main(){
    cin >>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++) 
	cin >>hh[i];
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin >>a>>b;
        add(a,b);
        add(b,a);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int flag=1;
        for(int j=h[i];j!=-1;j=ne[j])
        {
            int k=e[j];
            if(hh[i]<=hh[k])
            {
                flag=0;
                break;
            }
        }
        if(flag) ans++;
    }
    cout <<ans<<endl;
}


Measured memory_bytes: 6380
import java.time.Instant;
import java.util.*;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

public class Main {
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		String S = sc.next();

		String ans = S.substring(0, K-1) + S.substring(K-1, K).toLowerCase() + S.substring(K, N);
		System.out.println(ans);

	}
}

Measured memory_bytes: 21844
import java.util.Scanner;
public class Main {
	
	static String r = "yuiophjklnm";
	
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)) {
			while(sc.hasNext()) {
				String s = sc.next();
				if(s.equals("#")) break;
				
				int count = 0;
				int m = -1;
				for(char c : s.toCharArray()) {
					boolean right = false;
					for(int i=0; i<r.length(); i++) {
						if(c == r.charAt(i)) right = true;
					}
					if(right) {
						if(m == -1) m = 0;
						else if(m == 1) {
							m = 0;
							count++;
						}
					}
					else {
						if(m == -1) m = 1;
						else if(m == 0) {
							m = 1;
							count++;
						}
					}
				}
				System.out.println(count);
			}
		}
	}
}


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


int main() {
    int n, x;
    cin >> n >> x;
    int count = 1;
    int dist = 0;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        dist += num;
        if (dist <= x) count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cmath>
#include <limits>
#include <algorithm>

constexpr long long MOD = 1000000007;

int main()
{
  int a, b, c, d, e, k;
  std::cin >> a >> b >> c >> d >> e >> k;
  std::cout << (k < (e - a) ? ":(" : "Yay!") << std::endl;
  return 0;
}



Measured memory_bytes: 256
s = input()
K = int(input())

# K <= 5なので5文字のsubstringまで調べれば十分
substrings = set()
for length in [1,2,3,4,5]:
    for idx in range(len(s)):
        if len(s[idx:idx+length]) == length:
            substrings.add(s[idx:idx+length])

substrings = list(substrings)
substrings.sort()

print(substrings[K-1])

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

int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if ( fabs(a - c) <= d )
    cout << "Yes" << endl;
  else if ( fabs(a - b) <= d && fabs(b - c) <= d )
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
n = int(input())
s = str(input())
gomi = str(input())
num = [1]
for i in range(n-1):
  if s[i] == s[i+1]:
    num[-1]+=1
  else:
    num.append(1)
ans = 1
before = 0
for i in range(len(num)):
  if num[i] == 2:
    if before == 1:
      ans *= 2
      before = 2
    elif before == 2:
      ans *= 3
    else:
      ans *= 6
      before = 2
  else:
    if before == 1:
      ans *= 2
    elif before == 2:
      before = 1
    else:
      ans *= 3
      before = 1
  ans %= 10 ** 9 + 7
print(ans)

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

int main() {
    ll n;
    ll t;
    ll neg = 0;
    ll min = 1000000001;
    ll sum = 0;
    cin >> n;
    rep(i, n) {
        cin >> t;
        if(t < 0) {
            neg++;
            t = -t;
        }
        sum += t;
        if(t < min) {
            min = t;
        }
    }
    if(neg % 2 == 1) {
        sum -= min * 2;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>
using namespace std;
typedef  long long int lint;
//typedef pair<int, int> IP;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
#define mp make_pair
#define P pair<int,int>
//#define int long long

#define INF 1000000000000000000

class UnionFindTree {
private:
	std::vector<int> par;   // 親
	std::vector<int> depth; // 木の深さ

public:
	// n要素で初期化
	UnionFindTree(int n) {
		for (int i = 0; i < n; i++) {
			par.push_back(i);
			depth.push_back(0);
		}
	}

	// 木の根を求める
	int find(int x) {
		if (par[x] == x) {
			return x;
		}
		else {
			return par[x] = find(par[x]);
		}
	}

	// xとyの属する集合を併合
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)
			return;

		if (depth[x] < depth[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (depth[x] == depth[y])
				depth[x]++;
		}
	}

	// xとyが同じ集合に属するか否か
	bool same(int x, int y) { return find(x) == find(y); }
};


int main() {
	int N, Q;
	cin >> N >> Q;
	UnionFindTree UFT = UnionFindTree(N);
	rep(i, Q) {
		int com, x, y;
		cin >> com >> x >> y;
		if (com == 0) {
			UFT.unite(x, y);
		}
		else if (com == 1) {
			cout << UFT.same(x, y) << endl;
		}
	}
}


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


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = (l);x<=(u);x++)
#define RREP(x,l,u) for(ll x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 200010;
const int mod = 1e9+7;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n,x,y;

int A[maxn];

int Ans[maxn],ans;

priority_queue<pair<int,PII>,vector<pair<int,PII> >,greater<pair<int,PII> > > Q;

struct Node{
	int l,r,mn[2];
}T[maxn<<2];

int cmp(int x,int y){
	return A[x]<A[y]?x:y;
}

void build(int i,int l,int r){
	T[i].l=l;T[i].r=r;
	if(l==r){
		T[i].mn[l&1]=l;
		return;
	}
	int M=l+r>>1;
	build(i<<1,l,M);build(i<<1|1,M+1,r);
	REP(j,0,1)T[i].mn[j]=cmp(T[i<<1].mn[j],T[i<<1|1].mn[j]);
}

int query(int i,int l,int r,int p){
	if(l<=T[i].l&&T[i].r<=r)return T[i].mn[p];
	int ans=0,M=T[i].l+T[i].r>>1;
	if(l<=M)ans=cmp(ans,query(i<<1,l,r,p));
	if(r>M)ans=cmp(ans,query(i<<1|1,l,r,p));
	return ans;
}

int query(int l,int r){
	x=query(1,l,r,l&1);
	y=query(1,x+1,r,r&1);
	return A[x];
}

void Work(){
	Q.push(MP(query(1,n),MP(1,n)));
	while(!Q.empty()){
		int l=Q.top().se.fi,r=Q.top().se.se;Q.pop();
		query(l,r);
		int X=x,Y=y;
//		cout<<X<<' '<<Y<<endl;
		Ans[++ans]=A[x];Ans[++ans]=A[y];
		if(l<X)Q.push(MP(query(l,X-1),MP(l,X-1)));
		if(X<Y-1)Q.push(MP(query(X+1,Y-1),MP(X+1,Y-1)));
		if(Y<r)Q.push(MP(query(Y+1,r),MP(Y+1,r)));
	}
	REP(i,1,n)printf("%d ",Ans[i]);puts("");
}

void Init(){
	read(n);
	REP(i,1,n)read(A[i]);A[0]=n+1;
	build(1,1,n);
}

int main(){
	Init();
	Work();
	return 0;
}


Measured memory_bytes: 13944
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

static const int kRem = 1000000007;


int64_t pow_rem(int64_t x, int64_t m, int64_t rem)
{
	if (m == 0) {
		return 1;
	}
	if (m == 1) {
		return x;
	}

	if (m & 1) {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		val *= x;
		val %= rem;
		return val;
	}
	else {
		int64_t val = pow_rem(x, m / 2, rem);
		val = val * val;
		val %= rem;
		return val;
	}
}

int64_t pow_remdiv(int64_t val, int64_t rem)
{
	return pow_rem(val, rem - 2, rem);
}

int64_t divide_rem(int64_t divident, int64_t dividor, int64_t rem)
{
	int64_t ret = pow_remdiv(dividor, rem);
	ret *= divident;
	ret %= rem;

	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int64_t n; cin >> n;

	int64_t dp[64][3] = { 0 };

	int b = 0;
	{
		int64_t v = (n >> 1);
		while (v != 0) {
			v >>= 1;
			b++;
		}
	}

	dp[b][0] = 1;
	dp[b][1] = 1;
	dp[b][2] = 0;

	for (b = b - 1; 0 <= b; b--) {
		int bn = (n >> b) & 1;
		if (bn) {
			dp[b][0] = dp[b + 1][0];
			dp[b][1] = dp[b + 1][0] + dp[b + 1][1];
			dp[b][2] = dp[b + 1][2] * 3 + dp[b + 1][1] * 2;
		}
		else {
			dp[b][0] = dp[b + 1][0] + dp[b + 1][1];
			dp[b][1] = dp[b + 1][1];
			dp[b][2] = dp[b + 1][2] * 3 + dp[b + 1][1];
		}

		dp[b][0] %= kRem;
		dp[b][1] %= kRem;
		dp[b][2] %= kRem;
	}

	cout << (dp[0][0] + dp[0][1] + dp[0][2]) % kRem << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define INF INT_MAX
vector<ll> dp;

ll f(vector<ll> &v,ll n)
{
    dp[0]=0;
    dp[1]=abs(v[0]-v[1]);

    for(int i=2;i<=n;i++)
    {
        dp[i]=min(dp[i-1]+abs(v[i]-v[i-1]),
                  dp[i-2]+abs(v[i]-v[i-2])
                  );
    }

    return dp[n];
}

void solve()
{
    ll n,i,ans;
    cin>>n;
    dp.resize(n);
    vector<ll> v(n);

    for(i=0;i<n;i++)
    {
        cin>>v[i];
    }

    ans=f(v,n-1);
    cout<<ans;
}

int main()
{
    solve();
}


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

int main(void){
    char st;
    int cnt = 0;
    int sum = 0;
    int j;
    std::stack<int> s1;
    std::stack<std::pair<int, int>> s2;
    while(std::cin >> st){
        int a = 0;
        if(st == '\\') s1.push(cnt);
        else if(st == '/'){
            if(s1.size() > 0){
                j = s1.top();
                s1.pop();
                sum += cnt - j;
                while(s2.size() > 0 && s2.top().first > j){
                    a += s2.top().second;
                    s2.pop();
                }
                a += cnt - j;
                s2.push(std::make_pair(j, a));
            }
        }
        cnt++;
    }
    std::cout << sum << std::endl;


    std::vector<int> di; 
    while(s2.size() > 0 ){
        di.push_back(s2.top().second);
        s2.pop();
    }

    std::reverse(di.begin(), di.end());
    int s2size = di.size();
    std::cout << s2size;
    if(s2size != 0) std::cout << " ";
    for(int i = 0; i < s2size; i++){
        std::cout << di[i];
        if(i != s2size -1){
            std::cout << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}


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

int main() {
  long n;
  double ans=100;
  cin >> n;
  for(long i=1;i*i<=n;i++) {
    if(n%i==0) {
      ans=min(ans,1+floor(log10(max(i,n/i))));
    }
  }
  cout << ans << endl;
}

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

int n,m,slen,plen,comb1,comb2,num;
string str[20];
int s[10], id[30];
bool head[10];
vector<int> can,comb[6];
vector<int> pre[1<<10], suf[1<<10];
bool use[10];

void rec_pre(int d, int sum){
  if(d == plen){
    pre[comb1].push_back(sum);
    return;
  }

  for(int i=0;i<plen;i++){
    if(!use[i]){
      if(can[i] == 0 && head[d])continue;
      use[i] = true;
      rec_pre(d+1,sum + s[d] * can[i]);
      use[i] = false;
    } 
  }
}

void rec_suf(int d, int sum){
  if(d == slen){
    suf[comb1].push_back(sum);
    return;
  }
  
  for(int i=0;i<slen;i++){
    if(!use[i]){
      if(can[i] == 0 && head[d+plen])continue;
      use[i] = true;
      rec_suf(d+1,sum + s[d+plen] * can[i]);
      use[i] = false;
    } 
  }
}

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

  int lim = 1<<10;
  for(int i=1;i<6;i++){
    int tmp = (1<<i)-1;
    while(tmp < lim){
      comb[i].push_back(tmp);
      int x = tmp & -tmp, y = tmp + x;
      tmp = ( ( (tmp & ~y) /x ) >> 1) | y;
    }
  }

  while(cin >> n,n){
    vector<char> v;
    for(int i=0;i<n;i++){
      cin >> str[i];
      for(int j=0;j<str[i].size();j++){
	v.push_back(str[i][j]);
      }
    }

    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());

    m = v.size();
    for(int i=0;i<m;i++)id[v[i]-'A'] = i;

    for(int i=0;i<m;i++){
      s[i] = 0; head[i] = false;
    }

    for(int i=0;i<n;i++){
      if(str[i].size()>1)head[id[str[i][0]-'A']] = true;

      int tmp = (i==n-1?-1:1);
      for(int j=str[i].size()-1;j>=0;j--){
	s[id[str[i][j]-'A']] += tmp;
	tmp *= 10;
      }
    }

    if(m==1){
      if(s[0] == 0 && !head[0])cout << 1 << endl;
      else cout << 0 << endl;
      continue;
    }

    plen = m/2; slen = m-plen;

    for(int i=0;i<comb[plen].size();i++){
      comb1 = comb[plen][i];
      pre[comb1].clear();

      can.clear();
      for(int j=0;j<10;j++){
	if( (comb1>>j)&1 )can.push_back(j);
	use[j] = false;
      }
      rec_pre(0,0);
      sort(pre[comb1].begin(),pre[comb1].end());
    }
    
    for(int i=0;i<comb[slen].size();i++){
      comb1 = comb[slen][i];
      suf[comb1].clear();

      can.clear();
      for(int j=0;j<10;j++){
	if( (comb1>>j)&1 )can.push_back(j);
	use[j] = false;
      }

      rec_suf(0,0);
      sort(suf[comb1].begin(),suf[comb1].end());
    }

    int ans = 0;
    for(int i=0;i<comb[plen].size();i++){
      for(int j=0;j<comb[slen].size();j++){
	comb1 = comb[plen][i]; comb2 = comb[slen][j];
	if(!(comb1&comb2)){
	  for(int k=0;k<pre[comb1].size();k++){
	    if(!k || (pre[comb1][k] != pre[comb1][k-1])){
	      num = upper_bound(suf[comb2].begin(),suf[comb2].end(),-pre[comb1][k])
		- lower_bound(suf[comb2].begin(),suf[comb2].end(),-pre[comb1][k]);
	    }
	    ans += num;
	  }
	}
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1624
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(a){return a?cin[cid++]:+cin[cid++];}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

var myOut = main();
if(myOut !== undefined)console.log(myOut);

function main(){
  var n = next();
  var x = nexts(n);
  var ans = 1e9;
  for(var i = 1; i <= 100; i++){
    var sum = 0;
    for(var j = 0; j < n; j++){
      var t = i - x[j];
      sum += t * t;
    }
    if(sum < ans)ans = sum;
  }
  return ans;
}

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

int A[255];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&A[i]);
    }
    int p_id, l_id, r_id;
    for(int i=1;i<=n;++i){
        printf("node %d: key = %d",i,A[i]);
        p_id = i/2;
        if(p_id>=1) printf(", parent key = %d",A[p_id]);
        l_id = 2*i;
        r_id = l_id+1;
        if(l_id<=n) printf(", left key = %d",A[l_id]);
        if(r_id<=n) printf(", right key = %d",A[r_id]);
        printf(", \n");
    }
    return 0;
}



Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 200005;
char en = '\n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}

ll dp[105][105];

ll recur(ll pos, ll rem) {

  if (rem < 0)
    return -inf;
  if (pos == 0) {
    return (rem == 0) ? 0 : -inf;
  }

  ll &ans = dp[pos][rem];

  if (ans != -1)
    return ans;

  ans = -inf;
  ans = max(ans, max(1 + recur(pos - 1, rem - pos), recur(pos - 1, rem)));
  return ans;
}

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

  ll n;
  cin >> n;

  ll a[n + 5], b[n + 5];
  for (ll i = 1; i <= n; i++)
    cin >> a[i] >> b[i];

  sort(a + 1, a + n + 1);
  sort(b + 1, b + n + 1);

  if (n & 1) {
    ll lb = a[(n + 1) / 2];
    ll ub = b[(n + 1) / 2];

    cout << ub - lb + 1 << en;
    return 0;
  } else {
    ll lb = a[(n + 1) / 2] + a[1 + (n + 1) / 2];
    ll ub = b[(n + 1) / 2] + b[1 + (n + 1) / 2];

    cout << ub - lb + 1 << en;
  }

  return 0;
}


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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
using namespace std;

using ll = long long;
using ii = pair<ll, ll>;
ll mod = pow(10, 9) + 7;

template <typename T> void output(T, ll);
ll gcd(ll, ll);
ll lcm(ll, ll);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    int n;
    cin >> n;
    int p[n];
    rep(i, n) { cin >> p[i]; }

    int count = 0;
    repd(i, 1, n - 1) {
        if (p[i - 1] < p[i] && p[i] < p[i + 1]) {
            count++;
        } else if (p[i - 1] > p[i] && p[i] > p[i + 1]) {
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

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

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 256
H,W=map(int,input().split())
S=[list(input()) for _ in range(H)]

from itertools import product
def num(i,j):
    c=0
    for p,q in product([-1,0,1],repeat=2):
        if 0<=i+p<H and 0<=j+q<W and S[i+p][j+q]=='#':
            c+=1
    return c

for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            S[i][j]=str(num(i,j))
    print(''.join(S[i]))


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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N,K;
ll dp [16] [1 << 15];
const ll INF = 1e17;

ll bit_count(ll x)
{
	ll res = 0;
	for(;x;x -= x & -x) res++;
	return res;
}

int main()
{
	scanf("%d%d",&N,&K);
	vector<ll> A(N);
	FOR(i,0,N){
		scanf("%lld",&A [i]);
	}

	fill(dp [0],dp [N + 1],INF);
	dp [0] [0] = 0;
	FOR(i,0,N) FOR(mask,0,1 << N) if(dp [i] [mask] < INF){
		ll mx = 0;
		FOR(j,0,i){
			if(mx < A [j]){
				mx = A [j] + 1;
			}
			else if(mask >> j & 1){
				mx++;
			}
		}
		chmin(dp [i + 1] [mask],dp [i] [mask]);
		chmin(dp [i + 1] [mask | (1 << i)],dp [i] [mask] + max(0ll,mx - A [i]));
	}

	ll ans = INF;
	FOR(mask,0,1 << N) if(bit_count(mask) >= K){
		chmin(ans,dp [N] [mask]);
	}

	printf("%lld\n",ans);

	return 0;
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define int long long 
#define rep(i,x,n) for(int i=x;i<n;i++)
#define reprev(i,n,x) for(int i=n;i>=x;i--)
#define mp(a,b) make_pair(a,b)
#define mod 998244353
#define pb push_back
#define vi vector<int>
#define pi pair<int,int>
#pragma GCC target ("sse4.2")
using namespace std; 
void grayserge()
{
  int n;
  cin>>n;
  int weight;
  cin>>weight;
  vector<pair<int,int>> x;
  for(int i=0;i<n;i++){
    int w,v;
    cin>>w>>v;
    x.push_back({w,v});
  }
  int dp[n][weight+1];
  for(int i=0;i<n;i++){
    for(int j=0;j<=weight;j++){
      if(j==0){
        dp[i][j]=0;
      }
      else if(i==0){
        if(j<x[i].first){
          dp[i][j]=0;
        }else{
          dp[i][j]=x[i].second;
        }
      }
      else{
        if(j<x[i].first){
          dp[i][j]=dp[i-1][j];
        }else{
          dp[i][j]=max(dp[i-1][j],dp[i-1][j-x[i].first]+x[i].second);
        }
      }
    }
  }
  // for(int i=0;i<n;i++){
  //   for(int j=0;j<=weight;j++){
  //     cout<<dp[i][j]<<" ";
  //   }
  //   cout<<"\n";
  // }
  cout<<dp[n-1][weight]<<" "; 
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    
    int t=1;
    // cin>>t;
    while(t--){
      grayserge();
    }
    cerr<<"time taken: "<<(float)clock()/CLOCKS_PER_SEC<<endl;
  return 0;
}

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

template<int Max>
class TreeUF
{
public:
	TreeUF() = default;

	TreeUF(int N)
	{
		for (int i = 0; i < N; i++)
			par[i] = i;
	}

	void setSize(int n)
	{
		for (int i = 0; i < n; i++)
			par[i] = i;
	}

	int root(int x)
	{
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) return;
		par[rx] = ry;
	}

	bool same(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}

private:
	int par[Max];

};

int n, k, l;
TreeUF<200005> road;
TreeUF<200005> train;
std::map<std::pair<int, int>, int> cnt;
int main()
{
	std::cin >> n >> k >> l;

	road.setSize(n);
	train.setSize(n);
	for (int i = 0; i < k; ++i) {
		int p, q;
		std::cin >> p >> q;
		--p, --q;
		road.unite(p, q);
	}

	for (int i = 0; i < l; ++i) {
		int r, s;
		std::cin >> r >> s;
		--r, --s;
		train.unite(r, s);
	}

	for (int i = 0; i < n; ++i)
		++cnt[std::make_pair(road.root(i), train.root(i))];

	for (int i = 0; i < n; ++i) {
		std::cout << cnt[std::make_pair(road.root(i), train.root(i))];
		if (i != n - 1)
			std::cout << " ";
		else
			std::cout << std::endl;
	}

	return 0;
}


Measured memory_bytes: 13696
_ = input()
P = [int(i) for i in input().split()]

vmin = max(P)
vmax = 0

cnt = 0
for p in P:
  if p <= vmin:
    cnt += 1
  if p < vmin:
    vmin = p
  if vmax < p:
    vmax = p
    
print(cnt)

Measured memory_bytes: 32232
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int Maxn = 1000005;
 
int t;
int n, a, b;
int seq[Maxn], slen;
 
int main()
{
		scanf("%d %d %d", &n, &a, &b);
		if (a + b - 1 > n || ll(a) * b < n) printf("-1\n");
		else {
			slen = 0;
			int cur = 1;
			int lft = n - a;
			for (int i = 1; i <= a; i++) {
				int tk = min(lft, b - 1); lft -= tk;
				tk++;
				cur += tk;
				for (int j = cur - 1; j >= cur - tk; j--)
					seq[slen++] = j;
			}
			for (int i = 0; i < slen; i++)
				printf("%d%c", seq[i], i + 1 < slen? ' ': '\n');
		}
	return 0;
}
 

Measured memory_bytes: 3328
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using ull = unsigned long long;
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
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 RREP(i,n) for(ll i = (ll)(n)-1;i >= 0;--i)
#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);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
//#define int ll
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
signed main(){
  int sx,sy,tx,ty;
  cin >> sx >> sy >> tx >> ty;
  int dx = tx-sx;
  int dy = ty-sy;
  REP(i,dx) cout << 'R';
  REP(i,dy) cout << 'U';
  REP(i,dx) cout << 'L';
  REP(i,dy) cout << 'D';
  cout << 'D';
  REP(i,dx+1) cout << 'R';
  REP(i,dy+1) cout << 'U';
  cout << "LU";
  REP(i,dx+1) cout << 'L';
  REP(i,dy+1) cout << 'D';
  cout << 'R';
}


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

#define NIL -1

vector<int> pre, ino;

class Node
{
  public:
  int p = NIL, l = NIL, r = NIL;
};

void postorder(vector<Node>& nodes, vector<int>& out, int cur)
{
    if (cur == NIL) return;
    postorder(nodes, out, nodes.at(cur).l);
    postorder(nodes, out, nodes.at(cur).r);
    out.push_back(cur);
}

void itr_print(vector<int>& out)
{
    for (auto itr = out.begin(); itr != out.end(); ++itr) {
        if (itr != out.begin()) cout << " ";
        cout << *itr + 1;
    }
    cout << endl;
}

int crt(vector<Node>& nodes, vector<int>::iterator ino_b, vector<int>::iterator ino_e, vector<int>::iterator pre_cur)
{
    if (ino_b == ino_e) return NIL;
    vector<int>::iterator root;
    while(pre_cur != ino.end()) {
        if (ino_e == (root = find(ino_b, ino_e, *pre_cur++))) continue;
        int l = crt(nodes, ino_b, root, pre_cur);
        nodes.at(*root).l = l;
        if (NIL != l) nodes.at(l).p = *root;
        int r = crt(nodes, root + 1, ino_e, pre_cur);
        nodes.at(*root).r = r;
        if (NIL != r) nodes.at(r).p = *root;
        return *root;
    }
    cout << "error" << endl;
    return NIL;
}

int main()
{
    int i, n, r, el;
    cin >> n;
    vector<Node> nodes(n);
    vector<int> out;
    for (i = 0; i < n; i++) {
        cin >> el;
        if (i == 0) r = el - 1;
        pre.push_back(el - 1);
    }
    for (i = 0; i < n; i++) {
        cin >> el;
        ino.push_back(el - 1);
    }

    crt(nodes, ino.begin(), ino.end(), pre.begin());
    postorder(nodes, out, r);
    itr_print(out);
    return 0;
}

Measured memory_bytes: 3168
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll a(ll L) {  // a(i) : レベルiバーガーの長さ
    if(L == 0) {
        return 1;
    }
    return 2*a(L-1) + 3;
}

ll f(ll L, ll x) {  // レベルLバーガーの下からx層に含まれるパティの枚数
    if(L == 0) {
        return 1;
    }
    else if(x == 1) {
        return 0;
    }
    else if(x <= 1 + a(L-1)) {
        return f(L-1, x-1);
    }
    else if(x == 2 + a(L-1)) {
        return f(L-1, a(L-1)) + 1;
    }
    else if(x <= 2 + 2*a(L-1)) {
        return f(L-1, x - (2 + a(L-1))) + f(L-1, a(L-1)) + 1;
    }
    else if(x == 3 + 2*a(L-1)) {
        return 2*f(L-1, a(L-1)) + 1;
    }
}
 
int main() {
    ll n, x;
    cin >> n >> x;
    out(f(n, x));
    re0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

    final String s = scanner.nextLine();

    StringBuilder o = new StringBuilder();
    for (char c: s.toCharArray()) {
      switch (c) {
        case '0':
        case '1':
          o.append(c);
          break;
        case 'B':
          if (o.length() > 0) {
            o.deleteCharAt(o.length() - 1);
          }
      }
    }

    System.out.println(o.toString());
  }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=155;
int n,k,mo;
namespace solver1{
	int f[N][N];
	void solve(){
		int v1=n/2,v2=n-n/2;
		f[0][0]=1; k/=2;
		For(i,1,v2) For(j,0,k){
			f[i][0]=(f[i][0]+f[i-1][j])%mo;
			f[i][j+1]=(f[i][j+1]+f[i-1][j])%mo;
		}
		int ans1=0,ans2=0;
		For(j,0,k){
			ans1=(ans1+f[v1][j])%mo;
			ans2=(ans2+f[v2][j])%mo;
		}
		printf("%lld\n",1ll*ans1*ans2%mo);
	}
}
namespace solver2{
	int f[2][N][N][N];
	void solve(){
		int v=(k+3)/2,pre=0,suf=1;
		f[0][0][0][(n+3)/2]=1;
		For(i,1,n){
			memset(f[1],0,sizeof(f[1]));
			For(p1,0,v) For(p2,0,v) For(p3,1,(n+3)/2)
				if (f[0][p1][p2][p3]){
					int np1,np2,np3;
					np1=min(v,p2+1); np2=p1; np3=p3-(p2>=v);
					if (np1>=v&&np2) np3=min(np3,k+2-v-np2);
					if (np3) f[1][np1][np2][np3]=(f[1][np1][np2][np3]+f[0][p1][p2][p3])%mo;
					np1=0; np2=p1; np3=(p2>=v?(n+3)/2:p3);
					f[1][np1][np2][np3]=(f[1][np1][np2][np3]+f[0][p1][p2][p3])%mo;
				}
			memcpy(f[0],f[1],sizeof(f[0]));
		}
		int ans=0;
		For(p1,0,v) For(p2,0,v) For(p3,1,(n+3)/2)
			ans=(ans+f[0][p1][p2][p3])%mo;
		printf("%d\n",ans);
	}
}
int main(){
	scanf("%d%d%d",&n,&k,&mo);
	if (k%2==0) solver1::solve();
	else solver2::solve();
}

Measured memory_bytes: 29312
//Vatsal Gupta
#ifdef __APPLE__
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cctype>
#include <stack>
#include <list>
#include <queue>
#include <map>
#include <sstream>
#include <cmath>
#include <limits>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#else
#include<bits/stdc++.h>
#endif

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

#define lli long long int
#define ulli unsigned long long int

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(a) a.begin(),a.end()
#define SZ(a) (int)(a.size())

#define loop(i,a,b) for(int i=a; i<b; i++)

int gcd(int a, int b) {return b==0?a:gcd(b,a%b);}
int lcm(int a, int b) {return a*(b/gcd(a,b));}

#define INF 1000000000  //(10^9)
#define MOD 1000000007  //(10^9+7)

//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);

vi arr(110), freq(110,0);

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

	int n, flag=0;
	cin>> n;
	int maxi=-1;
	loop(i,0,n)
	{
		cin>> arr[i];
		maxi= max(maxi,arr[i]);
		freq[arr[i]]++;
	}
	if(maxi%2==0)
	{
		if(freq[maxi/2]!=1)
			flag=1;
		else
		{
			for(int i=maxi; i>(maxi/2); i--)
			{
				if(freq[i]<2)
					flag=1;
			}
		}
	}
	else
	{
		if(freq[(maxi/2)+1]!=2)
			flag=1;
		else
		{
			for(int i=maxi; i>((maxi/2)+1); i--)
			{
				if(freq[i]<2)
					flag=1;
			}
		}
	}
	if(flag==1)
		cout<< "Impossible\n";
	else
		cout<< "Possible\n";


	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <random>

using namespace std;

static const double EPS = 1e-9;
template<class T> bool INRANGE(T x,T a,T b){return a<=x&&x<=b;}
template<class T> void amin(T &a,T v){if(a>v) a=v;}
template<class T> void amax(T &a,T v){if(a<v) a=v;}
int ROUND(double x) { return (int)(x+0.5); }
bool ISINT(double x) { return fabs(ROUND(x)-x)<=EPS; }
bool ISEQUAL(double x,double y) { return fabs(x-y)<=EPS*max(1.0,max(fabs(x),fabs(y))); }
double SQSUM(double x,double y) { return x*x+y*y; }
#define PI  (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0])) 
#define NG (-1)
#define BIG ((int)1e9)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef unsigned long long ull;
typedef long long ll;

#if 1

int main()
{
	string s;
	cin >> s;

	const int N = SZ(s);
	for (char c = 'a'; c <= 'z'; ++c)
	{
		vector <int> sum(N + 1);
		for (int i = 0; i < N; ++i)
		{
			if (c == s[i])
			{
				sum[i + 1] = sum[i] + 1;
			}
			else
			{
				sum[i + 1] = sum[i];
			}
		}

		for (int len = 2; len <= min(100, N); ++len)
		{
			for (int i = 0; i + len <= N; ++i)
			{
				int freq = sum[i + len] - sum[i];
				if (freq > len / 2)
				{
					printf("%d %d\n", i + 1, i + len);
					return 0;
				}
			}
		}
	}
	printf("%d %d\n", -1, -1);
	return 0;
}


#else

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

	int bestDist = BIG;

	for (int y=-100;y<=100;++y)
	{
		int dist = 0;
		for (int x : a)
		{
			dist += SQ(x - y);
		}

		amin(bestDist, dist);
	}

	cout << bestDist << endl;

	return 0;
}

#endif

Measured memory_bytes: 896
#include<algorithm>     //sort,二分探索,など
#include<bitset>        //固定長bit集合
#include<cmath>         //pow,logなど
#include<complex>       //複素数
#include<deque>         //両端アクセスのキュー
#include<fstream>       //ファイルストリーム（標準入力変更用）
#include<functional>    //sortのgreater
#include<iomanip>       //setprecision(浮動小数点の出力の誤差)
#include<iostream>      //入出力
#include<iterator>      //集合演算(積集合,和集合,差集合など)
#include<map>           //map(辞書)
#include<numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include<queue>         //キュー
#include<set>           //集合
#include<stack>         //スタック
#include<string>        //文字列
#include<unordered_map> //イテレータあるけど順序保持しないmap
#include<unordered_set> //イテレータあるけど順序保持しないset
#include<utility>       //pair
#include<vector>        //可変長配列

//名前
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef map<string, int> msi;
typedef map<string, ll> msll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pllll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;

//定数
const ll MOD = 1000000007;
const ll INF = 1000000000000000000;

//マクロ
#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,s,e) for(int i=s;i<e;i++)
#define repse(i,s,e) for(int i=s;i<=e;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define in1(x1) cin >> x1
#define in2(x1, x2) cin >> x1 >> x2
#define in3(x1, x2, x3) cin >> x1 >> x2 >> x3
#define inN(x, N) rep(i, N) in1(x[i])
#define outl(x) cout << x << endl
#define out2l(x, y) cout << x << " " << y << endl 

//よく使う関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

    //標準入力をファイルに変更
    //std::ifstream in("input.txt");
    //std::cin.rdbuf(in.rdbuf());

    int N, M;
    in2(N, M);

    vi X(M);
    inN(X, M);

    if (N >= M)
    {
        outl(0);
        return 0;
    }

    sort(all(X));

    vi v;
    rep(i, M - 1)
    {
        v.push_back(X[i + 1] - X[i]);
    }

    sort(all(v));

    outl(accumulate(v.begin(), v.begin() + (M - N), 0));

    return 0;
}


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

int main(){
    int N, i, tmp, count = 0;
    cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++){
        cin >> A[i];
        A[i]--;
    }
    i = 0;
    while(A[i] != -1 && i != 1){
        tmp = i;
        i = A[i];
        A[tmp] = -1;
        count++;
    }
    if(i == 1) cout << count << endl;
    else cout << -1 << endl;
}


Measured memory_bytes: 640
A = list(input())
B = list(input())
C = list(input())

card = A.pop(0)
while True:
    if card == 'a':
        if A:
            card = A.pop(0)
        else:
            print('A')
            exit()
    elif card == 'b':
        if B:
            card = B.pop(0)
        else:
            print('B')
            exit()
    else:
        if C:
            card = C.pop(0)
        else:
            print('C')
            exit()

Measured memory_bytes: 38256
N=int(input())
left,right=0,1
parity=1
interval=[]
ansList=[]
digit = -1
for i in range(40):
    if parity == 1:
        interval.append((right-2**i+1,right))
    else:
        interval.append((left,left+2**i-1))
    if left <= N and N <= right:
        digit = i
        break
    else:
        if parity==1:
            left -= 2**(i+1)
            parity=-1
        else:
            right += 2**(i+1)
            parity=1
#for (x,y) in interval:
#    print(x,y,y-x+1)
while digit >= 0:
    left,right = interval[digit]
    #print(N)
    if left <= N and N<= right:
        ansList.append('1')
        N -= parity*(2**digit)
    else:
        ansList.append('0')
    digit -= 1
    parity = -parity
ans = "".join(ansList)
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 3e5+10;
const ll mod =   1e9+7;
ll h1,m1,h2,m2,k;
int main()
{  fast
cin>>h1>>m1>>h2>>m2>>k;
ll x=(h2-h1)*60+(m2-m1);
if(x<0)
x+=60*24;
cout<<max(0ll,x-k)<<endl;
}

Measured memory_bytes: 3668
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int num = 0;
		for(int i=A; i<=B; i++){
			String s = Integer.toString(i);
			if(s.charAt(0)==s.charAt(4) && s.charAt(1)==s.charAt(3))num++;
		}
		System.out.println(num);
	}
}


Measured memory_bytes: 26324
#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iomanip>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
typedef long long ll;
typedef long double ld;
typedef const void cv;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define per(i,n) for((i)=(n)-1;(i)>=0;(i)--)
#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define zt(a,b) (max((a),(b))-min((a),(b)))
#define setpre(n) fixed << setprecision(n)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
#define sankaku(x) (((x)*((x)+1))/2)
int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
int upint(cv *a, cv *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(cv *a, cv *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
int upchar(cv *left, cv *right) {return strcmp((char *)left,(char *)right);}
int downchar(cv *left, cv *right) {return strcmp((char *)right,(char *)left);}
void tmpInit(int *c,ll m) {ll i;rep(i,m) c[i]=i;}
ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1){
      res *= a; if(mod>=1) res %= mod;
    }
    a *= a; if(mod>=1) a %= mod;
    n >>= 1;
  }
  return res;
}
void initialize(){
  
}
int main(void){
  initialize();
  ll n,m,i,j,k,result=0,x,d;
  int a[LIMIT2]={0};
  string s;
  
  cin >> x >> k >> d;
  m = llabs(x)/d;//接近(回数)
  if(m>=k){
    result = min(llabs(x-k*d),llabs(x+k*d));
  }else{
    k -= m;
    if(x>=0){
      x -= m*d;
    }else{
      x += m*d;
    }
    k %= 2;
    if(k==1) result = min(llabs(x+d),llabs(x-d));
    else result = llabs(x);
  }
  //cout << m << endl;
  cout << result << endl;
  
  return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n+1];
    memset(a,0,sizeof(a));
    for(int i=1;i<n;i++)
    {
        int x;
        cin>>x;
        a[x]++;
    }
    for(int i=1;i<=n;i++)
    {
     cout<<a[i]<<endl;
    }
}


Measured memory_bytes: 4404
X = [int(e) for e in input().split()]
sx=X[0]
sy=X[1]
tx=X[2]
ty=X[3]
k=0
dy = ty - sy
dx = tx - sx
ans = 'U'*(dy) + 'R'*(dx) + 'D'*(dy) + 'L'*(dx) + 'L' + 'U'*(dy+1) + 'R'*(dx+1) + 'D' + 'R' + 'D'*(dy+1) + 'L'*(dx+1) + 'U'
print(ans)

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

int main() {
  int N, T, A;
  cin >> N >> T >> A;
  double candidate = (T - A) * 1000.0 / 6.0;
  double comp = 1000000;
  int ans;
  vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    cin >> H.at(i);
    comp = min(comp, abs(H.at(i) - candidate));
    if (comp == abs(H.at(i) - candidate)) ans = i + 1;
  }

  cout << ans;
  return 0;
}


Measured memory_bytes: 256
object Main extends App {

  import scala.io.StdIn._
  import scala.math._

  println(
    readLine.trim.toInt.toBinaryString.let{bin ⇒
      if (bin.forall(_ == '1')) bin.length
      else bin.length - 1
    }
  )
  implicit class Extension[T](val value :T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[R](func: T ⇒ R): R = func(value)
  }
}


Measured memory_bytes: 43976
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<complex>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;

Int a[110], b[110];
Int c[110], d[110];

vector<P> edge2[55 * 2500];

vector<Int> dijkstra(int s, vector<P> *edge){
    priority_queue<P, vector<P>, greater<P>> pq;
    vector<Int> dist(55*2500, LINF);
    dist[s] = 0;
    pq.push(P(dist[s], s));
    while(!pq.empty()){
        auto tmp = pq.top();pq.pop();
        int from = tmp.second;
        int d = tmp.first;
        if(dist[from] < d)continue;
        for(auto p: edge[from]){
            int to = p.first;
            int d = p.second;
            if(dist[to] > dist[from] + d){
                dist[to] = dist[from] + d;
                pq.push(P(dist[to], to));
            }
        }
    }
    return dist;
}

int value(int v, int s){
    return v*2500 + s;
}

vector<P> edge[55];

int main(){
    int n, m ,s, u, v;
    cin >> n >> m >> s;
    for(int i = 0;i < m;i++){
        cin >> u >> v >> a[i] >> b[i];u--,v--;
        edge[u].push_back(P(v, i));
        edge[v].push_back(P(u, i));
    }
    for(int i = 0;i < n;i++){
        cin >> c[i] >> d[i];
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j <= 2499;j++){
            int to = min(j + c[i], 2499ll);
            edge2[value(i,j)].push_back(P(value(i,to), d[i]));
            for(auto p: edge[i]){
                int to = p.first;
                int edge_ind = p.second;
                if(j < a[edge_ind])continue;
                edge2[value(i,j)].push_back(P(value(to, j- a[edge_ind]), b[edge_ind]));
            }
        }
    }
    s = min(s, 2499);
    auto dist = dijkstra(value(0,s), edge2);

    for(int i = 1;i < n;i++){
        Int ans = LINF;
        for(int j = 0;j < 2500;j++){
            ans = min(ans, dist[value(i, j)]);
        }
        cout << ans << endl;
    }
    
    return 0;
}

Measured memory_bytes: 23568
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct jc{
	int h;
	int z;
};
char a[102][102],b[102][102];
int main()
{
	jc jy[10];
	jy[1].h =jy[1].z =1;
	jy[2].h =jy[2].z =-1;
	jy[3].h =1;jy[3].z =0;
	jy[4].h =1;jy[4].z =-1;
	jy[5].h =0;jy[5].z =-1;
	jy[6].h =0;jy[6].z = 1;
	jy[7].h =-1;jy[7].z =0;
	jy[8].h =-1;jy[8].z =1;
	int n,m,k=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	cin>>a[i][j];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		if(a[i][j]=='#') b[i][j]='#';
		else
		{
			for(int h=1;h<=8;h++)
			{
				if(a[i+jy[h].h][j+jy[h].z]=='#')   k++;
			}
			b[i][j]='0'+k;
		}k=0;
	}
	for(int i=1;i<=n;i++)
	{ 
	for(int j=1;j<=m;j++)
	 cout<<b[i][j];
	cout<<endl;
	 } 
	 return 0;
}

Measured memory_bytes: 256