akhauriyash/Code-Regression huggingface dataset:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

def bound(Z, z):
    l = 0
    r = len(Z) - 1
    while r - l > 1:
        m = (l + r) // 2
        if Z[m] >= z:
            r = m
        else:
            l = m
    return r

for x in X:
    s = [0] * 2
    s[0] = bound(S, x)
    s[1] = s[0] - 1

    t = [0] * 2
    t[0] = bound(T, x)
    t[1] = t[0] - 1

    ans = INF
    # print("--------------")
    for i in range(2):
        for j in range(2):
            val = 0
            if x >= S[s[i]] and x >= T[t[j]]:
                val = max(abs(x - S[s[i]]), abs(x - T[t[j]]))
            elif x <= S[s[i]] and x <= T[t[j]]:
                val = max(abs(x - S[s[i]]), abs(x - T[t[j]]))
            else:
                val = min(abs(x - S[s[i]]) * 2 + abs(x - T[t[j]]), abs(x - S[s[i]]) + abs(x - T[t[j]]) * 2)
            ans = min(ans, val)
    # print(x)
    # print(S[s[0]], S[s[1]])
    # print(T[t[0]], T[t[1]])
    # print("--------------")
    print(ans)

    # print(S[s1], S[s2], T[t1], T[t2], T[t3], T[t4])
    # val1 = abs(S[s1] - x) + abs(T[t1] - S[s1])
    # val2 = abs(S[s1] - x) + abs(T[t2] - S[s1])
    # val3 = abs(S[s2] - x) + abs(T[t3] - S[s2])
    # val4 = abs(S[s2] - x) + abs(T[t4] - S[s2])
    # print(min(val1, val2, val3, val4))

Measured memory_bytes: 94792
// tle wa segmentation fault
#include<bits/stdc++.h>

using namespace std;

long long N;

int dfs(long long s)
{
    if (s > N) return 0;
    int flag = 0;
    string sn = to_string(s);
    
    for (int i = 0; i < sn.size(); ++i){
        if(sn[i] == '3') flag |= 0x01;
        else if (sn[i] == '5') flag |= 0x02;
        else if (sn[i] == '7') flag |= 0x04;
    }
    int ret = 0;
    if (flag == 0x07)  ret = 1;

    ret += dfs(s*10 + 3);
    ret += dfs(s*10 + 5);
    ret += dfs(s*10 + 7);
    return ret;
}

int main()
{
    cin >> N;
    cout << dfs(0) << endl;

    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	//A B C D	C D A B
	if(b<=c || d<=a){
		printf("%d\n",0);
	}
	//A C D B
	else if(a<=c && d<=b){
		printf("%d\n",d-c);
	}
	//C A B D
	else if(c<=a && b<=d){
		printf("%d\n",b-a);
	}
	//A C B D
	else if(a<=c && c<b && b<=d){
		printf("%d\n",b-c);
	}
	//C A D B
	else if(c<=a && a<d && d<=b){
		printf("%d\n",d-a);
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>

int main(){
	int n, q;
	std::string s;
	std::vector<int> lList;
	std::vector<int> rList;
	std::vector<int> cumSum;

	std::cin>>n>>q;
	std::cin>>s;

	lList.resize(q);
	rList.resize(q);
	cumSum.resize(n, 0);

	for(int i=0; i<q; i++)
		std::cin>>lList[i]>>rList[i];

	bool isPrevA= false;
	int curSum=0;

	for(int i=0; i<n; i++){
		if(s[i]=='C')
			if(isPrevA)
				curSum++;

		if(s[i]=='A')
			isPrevA=true;
		else
			isPrevA=false;

		cumSum[i]=curSum;
	}

	for(int i=0; i<q; i++)
		std::cout<<cumSum[rList[i]-1]- cumSum[lList[i]-1]<<std::endl;

	return 0;
	
}

Measured memory_bytes: 2176
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp make_pair
#define fi first
#define se second
#define pr(num) cout << num << "\n"
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define chmax(a, b) (a<b ? a=b : 0)
#define chmin(a, b) (a>b ? a=b : 0)
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 100010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;



int main(void) {
    ll N;
    ll a[MAX], b[MAX], c[MAX]; // c[i]=a[i]-b[i]
    ll i;
    ll sa=0, sb=0;
    cin >> N;
    for(i=0; i<N; i++) {
        cin >> a[i];
        sa+=a[i];
    }
    
    for(i=0; i<N; i++) {
        cin >> b[i];
        sb+=b[i];
    }
    
    for(i=0; i<N; i++) {
        c[i]=a[i]-b[i];
    }
    
    sort(c, c+N);
    
    if(sa<sb) {
        puts("-1");
        return 0;
    }
    
    ll ans=0;
    
    ll mi=0;
    for(i=0; i<N; i++) {
        if(c[i]<0) {
            ans++;
            mi+=-c[i];
        }
    }
    
    ll pl=0;
    for(i=N-1; i>=0; i--) {
        if(pl>=mi) {
            pr(ans);
            return 0;
        }
        
        ans++;
        pl+=c[i];
        
        
    }
    
}













Measured memory_bytes: 2560
Sd = input()
T = input()
if len(Sd) < len(T):
    print("UNRESTORABLE")
else:
    D = []
    for i in range(len(Sd) - len(T) + 1):
        flag = 1
        S = Sd
        for j in range(len(T)):
            if Sd[i+j] == "?" or Sd[i+j] == T[j]:
                S = S[:i+j]+T[j]+S[i+j+1:]
            else:
                flag = 0
        if flag == 1:
            D.append(S.replace("?", "a"))
    D.sort()
    if len(D) == 0:
        print("UNRESTORABLE")
    else:
        print(D[0])


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s; cin>>s;
	if (s.substr(0,4)=="YAKI") cout<<"Yes";
	else cout<<"No";
	cout<<endl;
	return 0;
}


Measured memory_bytes: 256
N,T = map(int,input().split())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i],B[i] = map(int,input().split())

# T-1分以内に完食を目指す，特定の料理のみ使わないで計算したい．
#DP1[i][t]はi番目の料理まででt分後までに完食で得られる幸福度の最大(商品番号は1から振る)
#DP2[i][t]はiからN番目の料理でt分後までに完食で得られる幸福度の最大

dp1 =[[0]*T for _ in range(N+1)]
dp2 =[[0]*T for _ in range(N+1)]

for i in range(N):
    for t in range(1,T):
        dp1[i+1][t] = dp1[i][t]
        if t-A[i]>=0:
            dp1[i+1][t]=max(dp1[i][t],dp1[i][t-A[i]]+B[i])


for i in reversed(range(0,N)):
    for t in range(1,T):
        dp2[i][t] = dp2[i+1][t]
        if t-A[i]>=0:
            dp2[i][t]=max(dp2[i+1][t],dp2[i+1][t-A[i]]+B[i])


ans=0
#i番目の料理を時間ギリギリに注文
for i in range(1,N):
    for j in range(0,T):
        ans = max(ans,dp1[i][j]+dp2[i+1][T-1-j]+B[i])
print(ans)

Measured memory_bytes: 178308
/* Bismillahirrahmanirrahim */
/* Author : Jehian Norman Saviero (@Reiva5) */
#include <bits/stdc++.h>
 
// MACROS SAMPAH
#define Jehian using
#define Norman namespace
#define Saviero std
 
Jehian Norman Saviero;
 
// MACROS TYPE
typedef long l;
typedef unsigned long long ll;
typedef unsigned long ul;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pi;
typedef pair<l,l> pl;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<l> vl;
typedef vector<ll> vll;
 
// MACROS FOR PRINT
#define nl printf("\n")
#define sp printf(" ")
 
// MACROS FOR ATTRIBUTE
#define fi first
#define se second
 
// MACROS FOR FUNCTION AND METHOD
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ALL(x) (x).begin(), (x).end()
#define ALLN(x,n) (x), (x)+(n)
#define CUBE(x) (SQR(x)*(x))
#define SET(x,y) for (int _qwe = sizeof(x)/sizeof(x[0]); _qwe; ) x[--_qwe] = (y)
#define SQR(x) ((x)*(x))
#define SSORT(x,sz) sort(ALLN(x,sz))
#define RESET(x) memset((x), 0, sizeof(x))
#define VSORT(x) sort(ALL(x))
 
// MACROS READ INPUT
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%ld", &x)
#define scll(x) scanf("%lld", &x)
#define scul(x) scl(x)
#define scull(x) scll(x)

int main() {
	int N, K;
	sci(N), sci(K);
	deque<double> curr;
	double ans = 0;
	double totCurr = 0;
	for (int i = 0; i < N; ++i) {
		int tmp;
		sci(tmp);
		curr.pb((double) (tmp + 1) * (tmp) / (2 * tmp));
		totCurr += curr.back();
		if (curr.size() > K) {
			totCurr -= curr.front();
			curr.ppf();
		}
		ans = max(ans, totCurr);
	}
	printf("%.9lf\n", ans);
	return 0;
}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}


int n;


bool f(int a){
  return(1<=a&&a<=12);

}

main(){
  cin>>n;

  int a=n/100;
  int b=n%100;

  if(f(a)&&f(b)){
    cout<<"AMBIGUOUS"<<endl;
  }else if(f(a)){
    cout<<"MMYY"<<endl;
  }else if(f(b)){
    cout<<"YYMM"<<endl;
  }else{
    cout<<"NA"<<endl;
  }

}


Measured memory_bytes: 256
def main():
    X, A, B = [int(ele) for ele in input().split()]
    tmp = B - A
    if tmp <= 0:
        print("delicious")
    elif 0 < tmp <= X:
        print("safe")
    elif X < tmp:
        print("dangerous")
    else:
        print("hoge")


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include <stdio.h>
int main(){
  int a,b,r,n;
  scanf("%d %d",&a,&b);
  if (a<b) {
    r=a;
    a=b;
    b=r;
  }
  n=a%b;
  while (n!=0) {
    a=b;
    b=n;
    n=a%b;
  }
  printf("%d\n",b);
  return 0;
}



Measured memory_bytes: 2140
void main() {
    int x = readln.chomp.to!int;
    int a = readln.chomp.to!int;
    int b = readln.chomp.to!int;
    writeln((x - a) % b);
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

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

ll lcm(ll a,ll b){
    if(b==0){
        return a;
    }else{
        return lcm(b,a%b);
    }
}
int main(){
    ll A,B,C,D;
    cin>>A>>B>>C>>D;
    A--;
    ll E=(A-A/C)+(A-A/D)-(A-A/(C/lcm(C,D)*D));
    ll F=(B-B/C)+(B-B/D)-(B-B/(C/lcm(C,D)*D));
    
    cout<<F-E;
}

Measured memory_bytes: 3636
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include "bits/stdc++.h"

#define REP(i,x,y) for(int i=(x);i<(y);i++)
#define RREP(i,x,y) for(int i=(y)-1;i>=(x);i--)
#define all(x) (x).begin(),(x).end()
//#define int long long

using namespace std;

// conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

typedef long long ll;

const ll MOD = 1e9 + 7;

class CBuildStairs {
public:
	void solve(std::istream& in, std::ostream& out) {
	    int N;
	    in >> N;
	    vector<int> H(N);
	    REP(i,0,N) in >> H[i];
	    int minHeight = H.back();
	    bool answer = true;
	    RREP(i,0,N) {
	        if (minHeight+1 < H[i]) {
	            answer = false;
	            break;
	        }
	        minHeight = min(H[i], minHeight);
	    }
	    out << (answer ? "Yes" : "No") << "\n";
	}
};


signed main() {
	CBuildStairs solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)((x).size()))

typedef long long ll;

const ll mod = 1000000007;
const double pi = 3.1415926535897932384626;

ll powmod(ll a, ll b) {ll res = 1; ll rem = a % mod; for (; b; b >>= 1) {if (b & 1) res = (res * rem) % mod; rem = (rem * rem) % mod;} return res;}

int main()
{	
#ifdef hannibal_08
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
#endif
    
	int n = 0;
	int c = 0;
	scanf("%d", &n);

	int ara[8];

	while (n) {
		ara[++c] = (n % 10);
		n /= 10;
	}

	if ((ara[1] == ara[2] && ara[1] == ara[3]) || (ara[2] == ara[3] && ara[3] == ara[4])) puts("Yes");
	else puts("No");

	return 0;
}


Measured memory_bytes: 256
n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new(0)
sum = 0
a.each do |x|
  sum += x
  h[x] += 1
end
q = gets.to_i
q.times do
  b, c = gets.split.map(&:to_i)
  if h.key?(b)
    sum += (c - b) * h[b]
    h[c] += h[b]
    h.delete(b)
  end
  puts sum
end

Measured memory_bytes: 25696
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum[ohara],pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
ll dp[5000][5000];

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>n>>k;
    rep(i,k)dp[1][i]=1,sum[1]+=dp[1][i];
    rrep(i,2,n+1){
        rep(j,k){
            dp[i][j]=sum[i-1]-dp[i-1][j];
            sum[i]+=dp[i][j];
        }
    }
    rep(i,k){
        ans+=dp[n][i];
    }
    Cout(ans);
    return 0;
}


Measured memory_bytes: 41472
n=int(input())
p=[list(map(int,input().split()))for _ in range(n)]
ax,ay,ah=list(filter(lambda x:x[2],p))[0]
for x in range(101):
  for y in range(101):
    H=ah+abs(ax-x)+abs(ay-y)
    if all(max(H-abs(t[0]-x)-abs(t[1]-y),0)==t[2]for t in p):
      print(x,y,H)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = a; i < n; i++)
#define Repr(i, n, a) for (int i = n; i >= a; i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

int f(int n)
{
    if (n < 0)
        n *= -1;
    return n;
}

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

    int x, y;
    cin >> x >> y;
    int ans;
    if (x == 0)
    {
        if (y > 0)
            ans = y;
        else
            ans = 1 - y;
    }
    else if (y == 0)
    {
        if (x > 0)
            ans = x + 1;
        else
            ans = -x;
    }
    else if (x * y < 0)
    {
        int tmp = f(x) - f(y), d = f(tmp);
        ans = d + 1;
    }
    else if (x < y)
        ans = y - x;
    else
        ans = x - y + 2;
    cout << ans << endl;
}

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

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    string ans = "No";
    for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) {
        if ((n - i) * j + i * (m -  j) == k) ans = "Yes";
    }

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

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

using namespace std;

int N;
int par[200005];
long long sz1[200005], sz2[200005];

int getrt(int n){
    return par[n] = (par[n] == n ? n : getrt(par[n]));
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i<=200000; i++){
        par[i] = i;
        if(i <= 100000){
            sz1[i]++;
        }
        else{
            sz2[i]++;
        }
    }
    for(int i =1 ; i<=N; i++){
        int x, y;
        cin >> x >> y;
        y += 100000;
        int px = getrt(x), py = getrt(y);
        if(px != py){
            par[px] = py;
            sz1[py] += sz1[px];
            sz2[py] += sz2[px];
        }
    }
    long long ans = -N;
    for(int i = 1; i<=200000; i++){
        if(par[i] == i){
            ans += sz1[i] * sz2[i];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include <set>
#include <iostream>
#include <iomanip>
using namespace std;
typedef long long LL;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)

int main(){
    int N;
    cin >> N;
    typedef pair<LL,LL> BA;
    vector<BA> vBA(N);
    REP(i,N){
        LL A, B;
        cin >> A >> B;
        vBA[i] = BA(B,A);
    }

    sort(vBA.begin(), vBA.end());

    LL left_time = 0;
    LL pre_B = 0;
    REP(i,N){
        left_time += vBA[i].first - pre_B;
        left_time -= vBA[i].second;
        if(left_time < 0){
            cout << "No" << endl;
            return 0;
        }
        pre_B = vBA[i].first;

    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 6408
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    int n; cin >> n;
    int Max = 0;
    int ans = 0;
    rep(i,n) {
        int p; cin >> p;
        ans += p;
        Max = max(Max, p);
    }
    cout << ans - Max/2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 200011
#define lSon (node << 1)
#define rSon (lSon | 1)
#define inf (1LL << 60)

struct aint {
    int dim;
    vector<ll> data;

    void init(int _dim) {
        dim = _dim;
        data = vector<ll>(4 * dim + 11, inf);
    }

    void upd(int node, int l, int r, int pos, ll v) {
        if (l == r) {
            data[node] = min(data[node], v);
            return;
        }

        int mid = (l + r) >> 1;
        if (pos <= mid) upd(lSon, l, mid, pos, v);
        else            upd(rSon, mid + 1, r, pos, v);

        data[node] = min(data[lSon], data[rSon]);
    }

    ll que(int node, int l, int r, int qL, int qR) {
        if (qL > qR) return inf;
        if (qL <= l && r <= qR)
            return data[node];

        int mid = (l + r) >> 1;
        ll ans = inf;

        if (qL <= mid)
            ans = min(ans, que(lSon, l, mid, qL, qR));
        if (qR > mid)
            ans = min(ans, que(rSon, mid + 1, r, qL, qR));

        return ans;
    }
};

int n, q, A, B, i, pos, act;
aint incr, decr;
ll bonus_incr, bonus_decr;

ll dist(ll a, ll b) {
    a -= b;
    if (a < 0) return -a;
    return a;
}

int main()
{
  //  freopen("test.in","r",stdin);

    scanf("%d%d%d%d", &n, &q, &A, &B);
    incr.init(n);
    decr.init(n);

    incr.upd(1, 1, n, A, 0 + A);
    decr.upd(1, 1, n, A, 0 + n - A);
    pos = B;

    for (i = 1; i <= q; i++) {
        scanf("%d", &act);

        ll ri = bonus_incr + incr.que(1, 1, n, act, n) - act;
        ll le = bonus_decr + decr.que(1, 1, n, 1, act) - (n - act);
        ll aux = min(le, ri);

        bonus_incr += dist(pos, act);
        bonus_decr += dist(pos, act);

        incr.upd(1, 1, n, pos, aux + pos - bonus_incr);
        decr.upd(1, 1, n, pos, aux + (n - pos) - bonus_decr);

        pos = act;
    }

    ll ans = inf;
    for (i = 1; i <= n; i++)
        ans = min(ans, incr.que(1, 1, n, i, i) - i + bonus_incr);

    printf("%lld", ans);

    return 0;
}


Measured memory_bytes: 12928
#include <iostream>
using namespace std;
int main(void){
    int a,b,c,d;
    int e,f,g,h;
    cin >> a >> b >> c >> d;
    cin >> e >> f >> g >> h;
    int x = a+b+c+d;
    int y = e+f+g+h;
    if(x>y) {
        cout << x << endl;
    }
    else {
        cout << y << endl;
    }
}



Measured memory_bytes: 3084
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
using namespace std;
int main(){
   
    int a,b;
    cin>>a>>b;
    
    if(a==1&&b!=1){
        cout<<"Alice"<<endl;
    }else if(b==1&&a!=1){
        cout<<"Bob"<<endl;
    }else if(a==1&&b==1){
        cout<<"Draw"<<endl;
    }else{
        
        
        
        if(a>b){
            cout<<"Alice"<<endl;
        }else if(b>a){
            cout<<"Bob"<<endl;
        }else if(a==b){
            cout<<"Draw"<<endl;
        }
        
        
        
        
        
        
        
    }
    
    
    
    
    return 0;
}






Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<functional>
#include<string.h>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<list>
#include<queue>
#include<deque>
#include<string>
#include<random>
#include<stack>
#include<limits.h>
#define int long long
using namespace std;

unordered_map<int, int>U;//組み合わせiのときの最小値ｋ＋１
int b[26];
signed main() {
	U[0] = 1;
	string a; cin >> a;
	for (char c : a) {
		b[c-'a']++;
		int k = 0;
		for (int i = 0; i < 26; i++) {
			k *= 2;
			k += (b[i] & 1);
		}
		for (int i = 0; i < 26; i++) {
			int n = 0;
			for (int j = 0; j < 26; j++) {
				n *= 2;
				if(i!=j)n += (b[j] & 1);
				else n += (b[j] + 1) % 2;
			}
			if (U[n]) {
				if (U[k]) {
					U[k] = min(U[k], U[n] + 1);
				}
				else {
					U[k] = U[n] + 1;
				}
			}
		}
	}
	int k = 0;
	for (int i = 0; i < 26; i++) {
		k *= 2;
		k += (b[i] & 1);
	}
	cout << max(1ll,U[k] - 1) << endl;
}


Measured memory_bytes: 170332
#-*- coding: utf-8 -*-
"""
https://yahoo-procon2019-qual.contest.atcoder.jp/tasks/yahoo_procon2019_qual_a
"""


def sol(n, k):
    ans = int(n/2)+1 if n % 2 == 1 else int(n/2)
    return 'YES' if ans >= k else 'NO'

test = False
#test = True
if test:
    n, k = 3, 2
    #S =list( map(int, "1 6 3".split()))
    print(sol(n, k))

    n, k = 5, 5
    #S =list( map(int, "7 4 0 3".split()))
    print(sol(n, k))
    #
    n, k = 31, 10
    #S =list( map(int, "1000000000000".split()))
    print(sol(n, k))

    n, k = 10, 90
    #S =list( map(int, "1000000000000".split()))
    print(sol(n, k))

else:
    n, k = map(int, input().split())
    #S =list( map(int, input().split()))
    print(sol(n, k))




Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
#define _GLIBCXX_DEBUG

using ll = long long;
using ull = unsigned long long;
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; }
const ll mod = 1e9+7;
void chmod(ll &M){
  if(M >= mod) M %= mod;
  else if(M < 0){
     M += (abs(M)/mod + 1)*mod;
    M %= mod;
}
}
ll modpow(ll x, ll n){
   if(n==0) return 1;
  ll res=modpow(x, n/2);
 if(n%2==0) return res*res%mod;
else return res*res%mod*x%mod;
}
int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };
long long GCD(long long a, long long b) {
  if (b == 0) return a;
  else return GCD(b, a % b);
}

using namespace std;
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    rep(i, N) { 
        cin >> p.at(i);
    }
    sort(p.begin(), p.end());
    
    int sum = 0;
    rep(i, K) {
        sum += p.at(i);
    }
    cout << sum << "\n";
}

Measured memory_bytes: 3608
import math

n = int(input())  # リストAの要素数
A = [int(input()) for i in range(n)]

# G = [4, 2, 1]
G = []
cnt = 0

tmp = math.floor(n / 2)
G.append(tmp)
while tmp > 1:
    tmp = math.floor(tmp / 2)
    G.append(tmp)


def insertion_sort(A, n, g):
    """[summary]

    Args:
        A ([type]): ソート対象の配列
        n ([type]): Aの要素数
        g ([type]): シェルソートの間隔
    """
    global cnt
    for i in range(g, n):
        tmp = A[i]
        j = i - g
        while j >= 0 and A[j] > tmp:
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = tmp


def shell_sort(A, n):
    global cnt
    for g in G:
        insertion_sort(A, n, g)


shell_sort(A, n)
print(len(G))
print(' '.join(map(str, G)))
print(cnt)
for a in A:
    print(a)


Measured memory_bytes: 45588
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<61;
const ll mod=1e9+7;

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(){
  int i,j;
  string s;
  cin>>s;
  if(s[0]==s[1]&&s[1]==s[2]) cout<<"No"<<endl;
  else cout<<"Yes"<<endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

using namespace std;
using ll = long long;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

ll Fact(ll n) {
    ll res = 1;
    for (int i = 1; i <= n; i++) {
        res *= i;
        res %= MOD;
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);

    int N;
    cin >> N;
    map<int, int> m;
    REP(i, N) {
        int a;
        cin >> a;
        if (a >= 3200) m[3200 / 4]++;
        else m[a / 400]++;
    }

    int min = 0;
    int max = 0;
    for (auto&& s : m) {
        if (s.first == 3200 / 4)continue;
        min++;
    }
    max = min;
    max += m[3200 / 4];
    if (min == 0)min = 1;
    if (max == 0)max = 1;
    cout << min << " " << max << endl;
    return 0;
}

Measured memory_bytes: 256
<?php
$l=trim(fgets(STDIN));
$c=0;
for($i=0;$i<$l;$i++){
  $n=trim(fgets(STDIN));

  if($n<2){continue;}
  if($n==2){++$c;continue;}
  if($n%2==0){continue;}
  $max=floor(sqrt($n));
  $f=1;
  for($i=3;$i<=$max;$i+=2) if($n%$i==0){$f=0;break;}
  if($f) ++$c;
}
print $c;

?>

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

#define INF 1e18
#define MAX_N 50
#define MAX_A 5050

struct edge{int v,c,cost;};
vector<edge> adj[MAX_N][MAX_A];
ll dist[MAX_N][MAX_A];

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M,S; cin>>N>>M>>S;
    rep(i,M){
        int u,v,a,b; cin>>u>>v>>a>>b; u--; v--;
        FOR(j,a,MAX_A-1){
            adj[u][j].pb({v,j-a,b});
            adj[v][j].pb({u,j-a,b});
        }
    }
    rep(i,N){
        int c,d; cin>>c>>d;
        rep(j,MAX_A)
            adj[i][j].pb({i,min(j+c,MAX_A-1),d});
    }

    using P = tuple<ll,int,int>;
    priority_queue<P,vector<P>, greater<P> > que;
    chmin(S,MAX_A-1);
    que.emplace(0,0,S);
    rep(i,MAX_N)rep(j,MAX_A) dist[i][j] = INF;
    dist[0][S] = 0;
    while(!que.empty()){
        ll cost; int v,c;
        tie(cost,v,c) = que.top(); que.pop();
        if (dist[v][c]<cost) continue;
        for(auto e:adj[v][c]){
            if (dist[v][c]+e.cost < dist[e.v][e.c]){
                dist[e.v][e.c] = dist[v][c]+e.cost;
                que.emplace(dist[e.v][e.c],e.v,e.c);
            }
        }
    }
    FOR(i,1,N-1){
        ll ans=INF;
        rep(j,MAX_A) chmin(ans,dist[i][j]);
        cout<<ans<<"\n";
    }
    return 0;
}


Measured memory_bytes: 38440
n = int(input())
a = [int(s) for s in input().split()]
l_ia = []
for i in range(n):
    # 出席番号i+1の生徒はa[i]番目に登校した
    l_ia.append([a[i], i+1])
l_ia.sort()
turn = [l_ia[i][1] for i in range(n)]
print(*turn)


Measured memory_bytes: 23580
#include <iostream>
using namespace std;
int main(void){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        if(i%3==0){
            cout<< " " << i;
            continue;
        }else{
            int x=i;
            while(x!=0){
        if(x%10==3){
            cout<< " " << i;
            break;
        }else{
            x/=10;
        }
        
        }
    }

    }
    cout<<endl;
}



Measured memory_bytes: 3096
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main() {
    return []() {
        std::function<void()> input;
        std::vector <int> list;
        (input = [&input, &list]() {
            int data;
            if ( std::cin >> data ) {
                list.push_back( data );
                input();
            } else {
                sort( list.rbegin(), list.rend() );
                for_each(
                    list.begin(),
                    list.begin() + 3,
                    [](int x){ std::cout << x << std::endl; }
                );
            }
        })();
        return 0;
    }();
}

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

using namespace std;

using ll = long long;

constexpr int MOD = 1e9 + 7;

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

	int s;
	cin >> s;
	vector<ll> dp(s + 1);
	dp[0] = 1;
	for (int i = 0; i <= s; ++i) {
		for (int j = 0; j <= i - 3; ++j) {
			dp[i] += dp[j];
			dp[i] %= MOD;
		}
	}
	cout << dp[s] << '\n';

	return 0;
}


Measured memory_bytes: 3624
#include<cstdio>
using namespace std;
int n,q,sum[100001]={},l,r,f;
char s[100010];
int main(){
    scanf("%d %d",&n,&q);
    scanf("%s",s);
    for(int i=1;i<n;i++){
        sum[i+1]=sum[i];
        if(s[i-1]=='A'&&s[i]=='C'){
            sum[i+1]++;
        }
    }
    for(int i=0;i<q;i++){
        scanf("%d %d",&l,&r);
        f=0;
        if(l>1){
            f=sum[l]-sum[l-1];
        }
        printf("%d\n",sum[r]-sum[l-1]-f);
    }
}

Measured memory_bytes: 1280
#include<stdio.h>

int main(void)
{
  int k,a,b;
  int ct=0;
  int i;
  scanf("%d",&k);
  scanf("%d %d",&a,&b);
    i=k;
  while(k<=b)
  {
    if(a<=k && k<=b)
    {
      ct++;
    }
    k=k+i;
  }
  if(ct>0) {
    printf("OK");
  }
    else {
      printf("NG");
    }
}

Measured memory_bytes: 1696
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<long double,long double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<62;
const double pi=acos(-1);
const long double eps=1e-7;
const ll mod=1e6+3;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

string s;

int main(){
	cin>>s;
	for(int i=0;i<s.size();i+=2) cout<<s[i];
	cout<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
long long gcd(long long a, long long b) { return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b) { return a/gcd(a,b)*b;}

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

int main() {
  int n;
  cin >> n;
  map<int, int> mp;
  map<int, int>::iterator itr;
  int flag = 0;
  int tmp;
  rep (i, n) {
    cin >> tmp;
    itr = mp.find(tmp);
    if (itr != mp.end()) flag = 1;
    else mp[tmp] = 1;
  }
  if (flag) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
  }
  return 0;
}

Measured memory_bytes: 9600
n,h=gets.chomp.split(" ").map { |e| e.to_i  }
a=Array.new(n)

n.times do |i|
  x,y = gets.chomp.split(" ").map { |e| e.to_i }
  a[i] = {"a" => x,"b" => y}
end

count = 0

def quick_sort_hash(c,x)
  if c==[]
    return []
  end
  same = c.select{ |h| h[x] == c[0][x] }
  smaller = c.select{ |h| h[x] < c[0][x] }
  larger = c.select { |h| h[x] > c[0][x] }

  return quick_sort_hash(smaller,x) + same + quick_sort_hash(larger,x)

end
  max_a = {"a" => 0,"b" => 0}
  indx = 0


for i in 0..n-1 do
  if a[i]["a"] > max_a["a"]
    max_a = a[i]
    indx = i
  end
end

a.slice!(indx,1)
a = quick_sort_hash(a,"b").reverse


i = 0

if h <= max_a["b"]
  puts 1
  exit
end

while h > 0 && i <= n-2 && a[i]["b"] > max_a["a"] && h > max_a["b"]
  h -= a[i]["b"]
  count += 1
  i += 1
end


if h <= 0
  puts count
elsif h <= max_a["b"]
  puts count + 1
else
  puts count + 1 + (h - max_a["b"] + max_a["a"] - 1)/max_a["a"]
end


Measured memory_bytes: 66216
#include <bits/stdc++.h>
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD (1000000000+7)
using namespace std;
#define PI 3.14159265359
#define tMOD 998244353
#define mkpr(x,y) make_pair(x,y)

int main(){
  ll H,N;
  cin>>H>>N;
  vector<ll> A(N);
  for(ll i=0;i<N;i++){
    cin>>A[i];
  }
ll tmp = accumulate(ALL(A),0LL);
if(H<=tmp)
  cout<<"Yes"<<endl;
else
  cout<<"No"<<endl;
  
}

Measured memory_bytes: 1024
import java.util.Scanner;

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

		int continuousRain = 0; // 連続雨の日数
		int weatherYesterday = 0; // 昨日の天気

		String input = sc.next();

		for(int i = 0; i < 3; i++) {
			if(input.charAt(i) == 'R') {
				if(weatherYesterday == 1) {
					continuousRain ++;
				} else {
					continuousRain = 1;
				}
				weatherYesterday = 1;
			} else {
				weatherYesterday = 0;
			}
		}

		System.out.println(continuousRain);

		sc.close();

	}
}


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

int main(void){
    int n, a, b;
    cin >> n >> a >> b;
    
    int temp;
    int sum = 0;
    int i;
    for(i = 1; i <= n; i++){
        temp = i / 10000 + i / 1000 % 10 + i / 100 % 10 + i / 10 % 10 + i % 10;
        if(temp >= a && temp <= b){
            sum += i;
        }
    }
    
    cout << sum << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define INF 9223372036854775807LL
#define inf 1000000007
#define SYOU(x) setprecision(x+1)
#define abs(x,y) (max(x,y)-min(x,y))
#define lol long long
#define mp make_pair
#define fi first
#define se second
using namespace std;
lol a,b,x,y;
lol i[200001];
lol u[200001];
vector<lol> ans;
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    lol c,d=0,e=0,f=0,g=1,h=0;
    cin >>a;
    for(int n=1;n<=a;n++) cin >>i[n];
    for(int n=a;n>a/2;n--){
	if(i[n]==1) ans.push_back(n),u[n]=1;
    }
    for(int n=a/2;n>=1;n--){
	int o=0;
	for(int m=n+n;m<=a;m+=n){
	    if(u[m]==1) o++;
	}
	if(o%2!=i[n]) ans.push_back(n),u[n]=1;
    }
    sort(ans.begin(),ans.end());
    cout <<ans.size()<<'\n';
    for(int n=0;n<ans.size();n++){
	if(n==0) cout <<ans[n];
	else cout <<' '<<ans[n];
    }
    if(ans.size()!=0) cout <<'\n';
    return (0);
}


Measured memory_bytes: 4980
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin >> n;
    vector<pair<pair<string, int>,int>> t(n);
    
    string s;
    int p;
    for(int i=0;i<n;i++){
        cin >> s >> p;
        t.at(i).first = make_pair(s,-p);
        t.at(i).second = i;
    }
    
    sort(t.begin(), t.end());
    
    for (int i=0;i<n;i++){
        cout << t.at(i).second+1 << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())

if a<=b:
  
  if a+t*v >= b+t*w:
    print('YES')
  else:
    print('NO')
else:
  if a-t*v<=b-t*w:
    print('YES')
  else:
    print('NO')

Measured memory_bytes: 61832
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
const int maxn = 2010;
vector<int> edge[maxn];
int n, k, res = maxn;
vector<int> dp[maxn];
int sz[maxn];
void dfs1(int now, int last = -1){
	sz[now] = 1;
	for(int u : edge[now])if(u != last)
		dfs1(u, now), sz[now] += sz[u];
}
void dfs2(int now, int last = -1){
	dp[now] = {0};
	int mx = 1;
	for(int u : edge[now])if(u != last){
		dfs2(u, now);
		mx = max(mx, (int)dp[u].size());
	}
	dp[now].resize(mx);
	if(sz[now] != 1) for(int i = 0;i < dp[now].size();++i){
		int sum = 0;
		auto get = [&](auto &v, int p){
			return p > v.size()-1 ? v.back() : v[p];
		};
		for(int u : edge[now])if(u != last){
			sum += get(dp[u], min(i, k-i));
		}
		dp[now][i] = maxn;
		for(int u : edge[now])if(u != last)
			dp[now][i] = min(dp[now][i], 
					sum - get(dp[u], min(i, k-i)) + get(dp[u], i));
	}
	for(int i = 1;i < dp[now].size();++i)
		dp[now][i] = min(dp[now][i], dp[now][i-1]);
	res = min(res, n - sz[now] + dp[now].back());
		//cout << dp[now].back() << '\n';
	auto tmp = dp[now];
	dp[now].pb(0);
	for(int i = 0;i < tmp.size();++i)
		dp[now][i+1] = tmp[i];
	dp[now][0] = sz[now];
	for(int i = 1;i < dp[now].size();++i)
		assert(dp[now][i] <= dp[now][i-1]);
	while(dp[now].size()-1 > k)
		dp[now].pop_back();
}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	for(int i = 1, a, b;i < n;++i){
		cin >> a >> b;
		edge[a].pb(b);
		edge[b].pb(a);
	}
	dfs1(1);
	dfs2(1);
	cout << res << '\n';

}



Measured memory_bytes: 10752
import std.algorithm;
import std.array;
import std.ascii;
import std.bigint;
import std.complex;
import std.container;
import std.conv;
import std.functional;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

void readlnTo(T...)(ref T t) {
    auto s = readln().split();
    assert(s.length == t.length);
    foreach(ref ti; t) {
        ti = s[0].to!(typeof(ti));
        s = s[1..$];
    }
}

const real eps = 1e-10;

const long p = 1_000_000_000 + 7;

void main(){
    auto n = readLong();
    auto p = readLongs().map!("a-1").array;
    auto x = readLongs();

    auto children = new long[][](n, 0);
    foreach(i; iota(n-1)) {
        children[p[i]] ~= i+1;
    }

    //y(i) : node(i)のxじゃないほうの色の重みの合計の最小値
    auto y = new long[](n);
    
    bool test(long i) {
        if(children[i].empty()) {
            y[i] = 0;
            return true;
        }
        if(children[i].map!(a => test(a)).any!(x => !x)) {
            return false;
        }
        
        auto m = children[i].map!(ci => min(x[ci], y[ci])).array();
        if(sum(m, 0L) > x[i]) {
            return false;
        }
        
        auto canMake = new bool[](x[i] - sum(m, 0L) + 1);
        canMake[0] = true;
        auto M = children[i].map!(ci => abs(x[ci] - y[ci])).array();
        foreach(Mi; M) {
            foreach(j; iota(canMake.length).retro) {
                if(j + Mi >= canMake.length) {
                    continue;
                }
                canMake[j+Mi] |= canMake[j];
            }
        }
        long w = x[i] - sum(m, 0L);
        foreach(j; iota(canMake.length)) {
            if(canMake[j]) {
                w = x[i] - sum(m, 0L) - j;
            }
        }
        y[i] = sum(M, 0L) + 2*sum(m, 0L) + w - x[i];
        return true;
    }
    writeln(test(0) ? "POSSIBLE": "IMPOSSIBLE");
}



Measured memory_bytes: 1404
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <array>
#include <tuple>
#include <utility>
#include <numeric>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <assert.h>
#include <cstdlib>
#include <list>
using namespace std;

#define repeat(i, x) for (long long i = 0; (i) < (long long)(x); (i)++)
#define rrepeat(i, x) for (long long i = (long long)((x) - 1); (i) >= 0; (i)--)
#define traverse(it, ctn) for (auto it = (ctn).begin(); (it) != (ctn).end(); (it)++)
#define rtraverse(it, ctn) for (auto it = (ctn).rbegin(); (it) != (ctn).rend(); (it)++)
#define enumerate(i, a, b) for (long long i = (long long)(a); (i) < (long long)(b); (i)++)

template<typename T> void chmax(T& a1, T a2) { a1 = std::max(a1, a2); }
template<typename T> void chmin(T& a1, T a2) { a1 = std::min(a1, a2); }

template<typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { os << "["; for (int i = 0; i < v.size(); i++) os << (i == 0 ? "" : ", ") << v[i]; os << "]"; return os; }
template<typename T1, typename T2> ostream& operator << (ostream& os, map<T1, T2>& mp) { os << "{"; for (auto it = mp.begin(); it != mp.end(); it++) { os << "(" << it->first << ": " << it->second << ")"; it++; if(it != mp.end()) os << ", "; it--; } os << "}"; return os; }
template<typename T> ostream& operator << (ostream& os, set<T>& st) { os << "{"; for (auto it = st.begin(); it != st.end(); it++) { os << *it; ++it; if(it != st.end()) os << ", "; it--; } os << "}"; return os; }

using int64 = long long;
using Graph = std::vector<std::vector<int>>;

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

    int N, A, B;
    cin >> N >> A >> B;

    if ((B - A) % 2 == 1) {
        cout << "Borys" << endl;
    } else {
        cout << "Alice" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();

		double all = 0; 
		for( int i = 1 ; i <= n ; i++ ) {
			int now = i;
			int p_all = 1;
			while( now < k ) {
				now *= 2;
				p_all *= 2;
			}
			all += 1.0/n/p_all;
		}
		
		System.out.println( (double)all );
		

	}
}


Measured memory_bytes: 35944
n = int(input())
tp = tuple(map(int, input().split()))

even = 0
odd = 0

for i in range(n):
    if tp[i] % 2 == 0:
        even += 1
    elif tp[i] % 2 == 1:
        odd += 1

if odd % 2 == 1:
    print("NO")
else:
    print("YES")

Measured memory_bytes: 14232
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
  int n,i,a[100010],b[100010];
  long ans=0;
  cin >> n;
  for (i=0;i<=n;i++) cin >> a[i];
  for (i=0;i<n;i++) cin >> b[i];
  for (i=0;i<n;i++){
    ans+=min(a[i]+a[i+1],b[i]);
    if (b[i]>a[i]+a[i+1]) a[i+1]=0;
    else if (b[i]>a[i]) a[i+1]-=b[i]-a[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
n, *aa = map(int, open(0).read().split())

count = 0
for i in range(n):
    mini = i
    for j in range(i+1, n):
        if aa[j] < aa[mini]:
            mini = j
    if mini != i:
        aa[i], aa[mini] = aa[mini], aa[i]
        count += 1

print(*aa)
print(count)


Measured memory_bytes: 5612