akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main {
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int C = sc.nextInt();
        int K = sc.nextInt();
        
        int[] map = new int[N];
        for (int i = 0; i < N; i++) {
        	map[i] = sc.nextInt();
        }
        
        Arrays.sort(map);
        
        int ans = 0;
        int first = map[0];
        int count = 1;
        for (int i = 1; i < N; i++) {
        	
        	if (first + K < map[i]) {
        		ans++;
        		count = 1;
        		first = map[i];
        	} else {
        		if (count == C) {
            		ans++;
            		count = 1;
            		first = map[i];
            	} else {
            		count++;
            	}
        	}
        }
        
        System.out.println(ans+1);
    }
}


Measured memory_bytes: 50552
#include<iostream>
#include<string>
using namespace std;
int main()
{
  string s;
  int a, b=999;
  cin >> s;
  for(int i=0; i<=s.size()-3; i++){
    a = (s[i]-'0')*100+(s[i+1]-'0')*10+(s[i+2]-'0');
    b = min(abs(753-a), b);
  }
  cout << b << endl;
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/abc138/tasks/abc138
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <set>
#include <bitset>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N), b(N);
    for (int i = 0; i < N - 1; ++i) cin >> a[i] >> b[i], --a[i], --b[i];
    vector<int> p(Q), x(Q);
    for (int i = 0; i < Q; ++i) cin >> p[i] >> x[i], --p[i];

    vector<vector<int>> G(N);
    for (int i = 0; i < N - 1; ++i)
    {
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    vector<int> parent(N, -1); // 頂点 i の親
    queue<int> que;
    que.push(0);
    while(!que.empty())
    {
        int v = que.front();
        que.pop();
        for (const auto& nv : G[v])
        {
            if (parent[v] == nv) continue;
            parent[nv] = v;
            que.push(nv);
        }
    }
    vector<int> res(N, 0);
    for (int j = 0; j < Q; ++j)
    {
        res[p[j]] += x[j];
    }

    que.push(0);
    while(!que.empty())
    {
        int v = que.front();
        que.pop();
        for (const auto& nv : G[v])
        {
            if (parent[v] == nv) continue;
            res[nv] += res[v];
            que.push(nv);
        }
    }
    for (int i = 0; i < N; ++i)
    {
        cout << res[i];
        if (i != N - 1) cout << " ";
        else cout << endl;
    }
    return 0;
}

Measured memory_bytes: 20548
import random
MOD = 10 ** 9 + 7
fac = [1] * (10 ** 6 * 2 + 2)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
x, y = map(int, input().split())
t = min(x, y) // 3
if (2 * x - y) % 3 or (2 * y - x) % 3 or 2 * x < y or 2 * y < x:
    print(0)
    exit(0)
a, b = (2 * x - y) // 3, (2 * y - x) // 3
k = min(a, b)
n = a + b
print((fac[n] * pow(fac[n - k], MOD - 2, MOD)
       * pow(fac[k], MOD - 2, MOD)) % MOD)


Measured memory_bytes: 82548
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
#define inf 998244353
#define LINF 1000000000000000007LL
#define ll long long
using namespace std;
signed main(){
	int n,a,b;
	cin>>n>>a>>b;
	if( n == 1 && a == 0 && b== 1){
		cout<<"YES"<<endl;
		cout<<"0 1"<<endl;
		return 0;
	}
	if( n == 1 && a == 1 && b== 0){
		cout<<"YES"<<endl;
		cout<<"1 0"<<endl;
		return 0;
	}
	vector<int> cycle[18];
	cycle[0].pb(0);
	cycle[1].pb(0);
	cycle[1].pb(1);
	for(int i=2;i<=n;i++){
		for(int j=0;j< cycle[i-1].size() ;j++){
			cycle[i].pb( 2 * cycle[i-1][j] );
		}
		for(int j=0;j< cycle[i-1].size() ;j++){
			cycle[i].pb( 2 * cycle[i-1][ cycle[i-1].size()-1-j ] + 1);
		}
	}
	/* for(int i=1;i<=n;i++){
		for(int j=0;j<cycle[i].size();j++){
			cout<<cycle[i][j]<<" ";
		}
		cout<<endl;
	} */
	int g = a^b;
	vector<int> zbt, obt;
	int cur = g;
	for(int i=0;i<=n-1;i++){
		if( cur % 2 == 1) obt.pb(i);
		else zbt.pb(i); 
		cur = cur/2;
	}
	vector<int> swapper;
	int os = obt.size(), zs = zbt.size();
	int ng = 1<<os; ng--; ng = ng<<zs;
	for(int i=0;i<zbt.size();i++){
		swapper.pb( zbt[i] );
	}
	for(int i=0;i<obt.size();i++){
		swapper.pb( obt[i] );
	}
	if( os % 2 == 0){
		cout<<"NO"<<endl;
		return 0;
	}
	vector<int> ans,res;
	int head = 0;
	while( head <= os ){
		int pw = n - head - 1;
		int curh = 1<<head; curh--; curh = curh<<(n-head);
		//cout<< head << " " << curh << " " << pw << endl;
		if( head == os ) pw++;
		for(int i=0; i< cycle[pw].size();i++ ){
			int nx = curh + cycle[pw][i];
			nx = nx^(head%2);
			ans.pb(nx);
			//cout<<nx<<endl;
		}
		head++;
	}
	for(int i=0;i<ans.size();i++){
		int re = 0;
		int cu = ans[i];
		for(int j=0;j<n;j++){
			if(ans[i] % 2 == 1){
				re += 1 << (swapper[j]);
			}
			ans[i] /= 2;
		}
		re = re^a;
		res.pb(re);
	}
	cout<<"YES"<<endl;
	for(int i=0;i<res.size();i++){
		cout<<res[i]<<" ";
	}
	cout<<endl;
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  int N, M, X; cin >> N >> M >> X;
  int C[N], A[N][M];
  rep(i,N) {
    cin >> C[i];
    rep(j,M) cin >> A[i][j];
  }

  int result = INF;
  rep(i,1<<N) {
    int now = 0;
    int rikai[M] = {};
    rep(j,N) {
      if (i&(1<<j)) {
        now += C[j];
        rep(k,M) rikai[k] += A[j][k];
      }
    }
    bool ok = true;
    rep(j,M) ok &= rikai[j]>=X;
    if (ok) result = min(result,now);
  }
  if (result==INF) result = -1;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 3640
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let n: usize = s.trim().parse().unwrap();

    let mut v: Vec<Vec<usize>> = vec![Vec::new(); 2];
    for i in 0..2 {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        v[i] = s.trim().split(' ').map(|x| x.parse().unwrap()).collect();
    }

    let a: Vec<usize> = v[0].iter().scan(0, |x, y| {*x = *x + *y; Some(*x)}).collect();
    let b: Vec<usize> = v[1].iter().rev().scan(0, |x, y| {*x = *x + *y; Some(*x)}).collect();
    let mut c: Vec<usize> = vec![0; n];
    for i in 0..n {
        c[i] = a[i] + b[n-i-1];
    }
    println!("{:?}", c.iter().max().unwrap());
}



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

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

	int n = s.size();
	std::vector<int> ans(n);
	for (int i = 0; i < n - 1; i++) {
		if (s[i] != 'R' || s[i + 1] != 'L') {
			continue;
		}

		for (int j = i; j >= 0 && s[j] == 'R'; j--) {
			ans[i + (i-j)%2]++;
		}

		for (int j = i + 1; j < n && s[j] == 'L'; j++) {
			ans[i + (j-i)%2]++;
		}
	}

	for (int i = 0; i < n; i++) {
		if (i) std::cout << " ";
		std::cout << ans[i];
	}
	std::cout << std::endl;
	return 0;
}


Measured memory_bytes: 1024
n=int(input())
AB=[list(map(int,input().split())) for _ in range(n)]

A,B=[],[]
for i,j in AB:
    A.append(i+j)
    B.append(-j)

ans=sum(B)
A=sorted(A)[::-1]
for i in range(0,n,2):
    ans +=A[i]

print(ans)

Measured memory_bytes: 37236
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    if (n == 0) {
        cout << "0\n";
    } else if (n > 0) {
        string res(32, '0');
        for (int k = 29; k >= 0; --k) {
            if (n & (1 << k)) {
                for (int i = k; ; ++i) {
                    if (i % 2 == 0) {
                        if (res[i] == '0') {
                            res[i] = '1';
                            break;
                        } else {
                            res[i] = '0';
                        }
                    } else {
                        if (res[i] == '1') {
                            res[i] = '0';
                            break;
                        } else {
                            res[i] = '1';
                        }
                    }
                }
            }
        }
        while (res.back() == '0') {
            res.pop_back();
        }
        reverse(res.begin(), res.end());
        cout << res << '\n';
    } else {
        string res(32, '0');
        n = -n;
        for (int k = 29; k >= 0; --k) {
            if (n & (1 << k)) {
                for (int i = k; ; ++i) {
                    if (i % 2 == 1) {
                        if (res[i] == '0') {
                            res[i] = '1';
                            break;
                        } else {
                            res[i] = '0';
                        }
                    } else {
                        if (res[i] == '1') {
                            res[i] = '0';
                            break;
                        } else {
                            res[i] = '1';
                        }
                    }
                }
            }
        }
        while (res.back() == '0') {
            res.pop_back();
        }
        reverse(res.begin(), res.end());
        cout << res << '\n';
    }
}


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

using namespace std;

bool ver(pair<int, int> &a, pair<int, int> &b){
    return (a.first < b.first);
}

int main(){
    int n, m;
    int64_t total_yen = 0;
    cin >> n >> m;
    vector<pair<int, int>> v;
    for(int i = 1; i <= n; ++i){
        int aux1, aux2;
        cin >> aux1 >> aux2;
        v.emplace_back(aux1, aux2);
    }
    sort(v.begin(), v.end(), ver);


    for(auto it : v){
        if(m > 0){
            total_yen += it.first * 1LL * min(it.second, m);
            m -= min(it.second, m);
        }else break;
    }
    cout << total_yen;
}


Measured memory_bytes: 1400
/*
 * Copyright (c) 2019 ... All rights reserved.
 * ...
 */
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int inputValue(){
    int a;
    cin >> a;
    return a;
};

void inputArray(int * p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

void inputVector(vector<int> * p, int a){
    rep(i, a){
        int input;
        cin >> input;
        p -> push_back(input);
    }
}

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

int main(int argc, const char * argv[]) {
    int N, K;
    cin >> N;
    cin >> K;
    int out = N - K + 1;
    cout << out << endl;
    // source code

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	ll n,k;cin>>n>>k;
	vector<ll> a(n);
	for(int i = 0; i < n; i++) {
		cin>>a[i];
	}
	ll ans = 0;
	
	for(int i = 60; i >= -1; i--) {
		if (!((k >> i) & 1LL) && i != -1){
			continue;
		}
		ll tmp = 0LL;
		for(int j = 60; j >= 0; j--) {
			ll mask = (1LL << j);
			ll count = 0LL;
			for(int k = 0; k < n; k++) {
				if(a[k] & mask){
					count++;
				}
			}
			if (i < j){
				if (k & mask){
					tmp += (n - count) * mask;
				}
				else{
					tmp += count * mask;
				}
			}
			else if (i == j){
				tmp += count * mask;
			}
			else{
				tmp += mask * max(count, n - count);
			}
		}
		// cout << tmp << endl;
		ans = max(ans,tmp);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
from sys import stdin

def getval():
    n,m = map(int,input().split())
    h = list(map(int,stdin.readline().split()))
    p = [list(map(int,stdin.readline().split())) for i in [0]*m]
    return n,m,h,p

def main(n,m,h,p):
    g = [[] for i in range(n)]
    for i in p:
        g[i[0]-1].append(i[1]-1)
        g[i[1]-1].append(i[0]-1)
    ans = 0
    for i in range(n):
        if not g[i]:
            ans += 1
        else:
            temp = h[i]
            flag = True
            for j in g[i]:
                if h[j]>=temp:
                    flag = False
                    break
            if flag:
                ans += 1
    print(ans)
                

if __name__=="__main__":
    n,m,h,p = getval()
    main(n,m,h,p)

Measured memory_bytes: 48148
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (ll i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using ld=long double;
using vin=vector<int>;
using vvin=vector<vin>;
using vll=vector<ll>;
using vvll=vector<vll>;
using vst=vector<string>;
using P = pair<ll,ll>;
const int inf=1e9+7;
const ll INF=9e18;
template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b;return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b;return true;}return false;}
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int main(){cout<<fixed<<setprecision(20);
		   ll n;
           cin>>n;
           vll x(n),y(n);
           rep(i,0,n)cin>>x[i]>>y[i];
           ll ans=0;
           ll mx=-INF;
           ll mn=INF;
           rep(i,0,n){
             chmax(mx,x[i]-y[i]);
             chmin(mn,x[i]-y[i]);
           }
           chmax(ans,mx-mn);
           mx=-INF;
           mn=INF;
           rep(i,0,n){
             chmax(mx,x[i]+y[i]);
             chmin(mn,x[i]+y[i]);
           }
           chmax(ans,mx-mn);
           cout<<ans<<endl;
}

Measured memory_bytes: 6408
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include <string.h>

using namespace std;
int main(){
	int N;
	int A,B,C;
	cin>>N;
	cin>>A>>B;
	cin>>C;
	vector<int> cal,calper;
	int c;
	for(int i=0;i<N;i++){
		cin>>c;
		cal.push_back(c);
	}
	sort(cal.begin(),cal.end());
	reverse(cal.begin(),cal.end());
	int allcal=C;
	for(int i=0;i<=N;i++){
		int price=A+B*(i);
		calper.push_back(allcal/price);
		allcal+=cal[i];
	}
	sort(calper.begin(),calper.end());
	reverse(calper.begin(),calper.end());
	
	cout<<calper[0]<<endl;
	
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
int main(){
int64_t X;
  cin>>X;
  int64_t a,b;
  bool x;
  for(int i=-200;i<=200;i++){
   for(int j=-200;j<=200;j++){
    x=false;
     int64_t A=pow(i,5);
     int64_t B=pow(j,5);
     if(A-B==X){a=i; b=j; x=true;break;}
   
   }if(x)break;
  
  }cout<<a<<" "<<b<<endl;
   return 0;
}

Measured memory_bytes: 4100
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <cassert>
#include <memory>
#include <stack>
#include <set>
#include <map>

#define INF 1000000000
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

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

  int year, month, day;
  scanf("%d/%d/%d", &year,&month,&day);

  string ans = "Heisei";
  if(year >= 2019) {
    if(month >= 5) {
      ans = "TBD";
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES // M_PI
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define rREP(i,a,n) for(int (i)=(n)-1; (i)>=(a);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 2147483647;
constexpr ll mod = 1000000007;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}
 
int main() {
	init();

	string s; cin >> s;
	int ans = 0;
	REP(i, 2, s.size() - 1) {
		string a = s;
		a.erase(s.size() - i);
		string x = a.substr(0, a.size() / 2), y = a.substr(a.size() / 2);
		if (x == y)chmax(ans, (int)s.size() - i);
		++i;
	}
	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
int main(){
    int a,b;
    int x,y,z;
    cin>>a>>b;
    x=a+b;
    y=a-b;
    z=a*b;
    cout<<max(x,max(y,z));
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    string s;
    cin>>s;
    if(regex_match(s,regex("^A[a-z]+C[a-z]+$"))){
        cout<<"AC"<<endl;
    }else{
        cout<<"WA"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
# arc 061 Many Formulas
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

S = read().rstrip().decode('utf-8')

def F(S):
    for i in range(2 ** (len(S) - 1)):
        operator_list = format(i, 'b').zfill(len(S)) # 最大桁は必ず0
        sum_ = 0
        num = 0
        for j, operator in zip(S, operator_list):
            if operator == "0":
                num = num * 10 + int(j)
            else:
                sum_ += num
                num = int(j)
        sum_ += num

        yield sum_

ans = sum(F(S))
print(ans)

Measured memory_bytes: 3064
from fractions import gcd
from functools import reduce


def lcm(a, b):
    return a * b // gcd(a, b)


def count(n):
    c = 0
    while n % 2 == 0:
        c += 1
        n //= 2
    return c


def solve(string):
    n, m, *a = map(int, string.split())
    c = len(bin(a[0]).split("1")[-1])
    for _a in a:
        if count(_a) != c:
            return "0"
    l = reduce(lcm, a)
    return str(max((m - l // 2) // l + 1, 0))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


Measured memory_bytes: 17132
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 998244353
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define MAX_N 100005
#define MOD 998244353

int inv[MAX_N],fac[MAX_N],finv[MAX_N];

void make()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(int i=2;i<MAX_N;i++){
		inv[i] = MOD - (long long)inv[MOD%i] * (MOD/i) % MOD;
		fac[i] = (long long)fac[i-1] * i % MOD;
		finv[i] = (long long)finv[i-1] * inv[i] % MOD;
	}
}

int comb(int a,int b)
{
	if(a < b){
		return 0;
	}
	return fac[a] * ((long long)finv[b] * finv[a-b] % MOD) % MOD;
}
ll dp[3010][6020];
int main(){
    make();
    int n;
    int x;
    cin >> n >> x;
    dp[0][0] = 1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=2*i;j++){
            dp[i+1][j+1] += dp[i][j];
            dp[i+1][j+1] %= mod;
            dp[i+1][j+2] += dp[i][j];
            dp[i+1][j+2] %= mod;
        }
    }
    ll ans = 0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<x;j++){
            ans += dp[i][j]*comb(n,i)%mod;
            ans %= mod;
        }
    }
    cerr << ans << endl;
    for(int k=1;k<=(n)/2;k++){
        for(int p = 0;p<=n-2*k;p++){
            if(x-1-2*k<=0)continue;
            ans += dp[p][x-1-2*k]*comb(n,p+2*k)%mod;
            ans %= mod;
            if(2*p==x-1-2*k){
                ans += mod-comb(n,p+2*k);
                ans %= mod;
            }
        }
        
    }
    cerr << ans << endl;
    if(x%2==0){
        
    }else{
        for(int k = (x+1)/2;k<=n;k++){
            
            ans += comb(n,k);
            ans %= mod;
        }
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

struct segtree
{
	vector<long long> t;
	segtree(int n) :t(n * 2 - 1, 0) {}
	void inc(int a, int o, int l, int r) {
		if (r <= a || a < l)
			return;
		t[o]++;
		if (l + 1 == r)
			return;
		int m = (l + r) / 2;
		inc(a, o + 1, l, m);
		inc(a, o + (m - l) * 2, m, r);
	}
	long long sum(int a, int b, int o, int l, int r) const {
		if (r <= a || b <= l)
			return 0;
		if (a <= l && r <= b)
			return t[o];
		int m = (l + r) / 2;
		return sum(a, b, o + 1, l, m) + sum(a, b, o + (m - l) * 2, m, r);
	}
};

long long bub(const vector<int> &v, int n)
{
	if (n < 1) return 0;
	segtree s(n);
	auto r = 0ll;
	for (auto i : v) {
		r += s.sum(i + 1, n, 0, 0, n);
		s.inc(i, 0, 0, n);
	}
	return r;
}

struct cm {
	bool operator()(const pair<int, int> &p, const pair<int, int> &q) {
		return p.second < q.second;
	}
};

int main()
{
	string s;
	cin >> s;
	vector<pair<int, int>> v(s.length());
	vector<int> u(s.length());
	int ch[26] = {};
	for (int i = 0; i < s.length(); i++) {
		v[i].first = s[i] - 'a';
		ch[v[i].first]++;
	}
	bool o = false;
	for (int i = 0; i < 26; i++) {
		if (ch[i] % 2) {
			if (o) {
				cout << -1 << endl;
				return 0;
			}
			o = true;
		}
	}
	int c[26] = {}, n = 0;
	for (auto &p : v) {
		if (c[p.first] * 2 >= ch[p.first])
			p.second = 2;
		else if (c[p.first] == ch[p.first] / 2)
			p.second = 1;
		u[n++] = p.second;
		c[p.first]++;
	}
	auto r = bub(u, 3);
	stable_sort(v.begin(), v.end(), cm());
	vector<int> chv[26];
	for (int i = 0; i < v.size() / 2; i++)
		chv[v[v.size() - 1 - i].first].push_back(i);
	fill(c, c + 26, 0);
	for (int i = 0; i < v.size() / 2; i++)
		u[i] = chv[v[i].first][c[v[i].first]++];
	u.resize(v.size() / 2);
	cout << r + bub(u, u.size()) << endl;
	return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, Q;
  cin >> N >> Q;
  vector<int> A(N - 1, N - 1), B(N - 1, N - 1);
  int64_t res = static_cast<int64_t>(N - 2) * (N - 2);
  int H = N - 2, W = N - 2;
  for (int q = 0; q < Q; q++) {
    int t, x;
    cin >> t >> x;
    x -= 2;
    if (t == 1) {
      if (x < W) {
        for (int i = x; i < W; i++) {
          B[i] = H;
        }
        W = x;
      }
      res -= B[x] - 0;
    } else {
      if (x < H) {
        for (int i = x; i < H; i++) {
          A[i] = W;
        }
        H = x;
      }
      res -= A[x] - 0;
    }
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 4784
#include<stdio.h>

main(){
 int A,B,C,D;
 int left,right;
 scanf("%d %d %d %d",&A,&B,&C,&D);
 left = A + B;
 right = C + D;
 if(left>right){
     printf("Left");
 }else if(right>left){
     printf("Right");
 }else{
     printf("Balanced");
 }
}

Measured memory_bytes: 128
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        Reader r = new Reader();  
        int[] a = r.ii();        
        println(Math.max(0, Math.min(a[3], a[1])-Math.max(a[0], a[2])));
    }
    static void print(Object o){
        System.out.print(o.toString());
    }
    static void println(Object o){
        System.out.println(o.toString());
    }
    static int Int(String s){
        return Integer.parseInt(s);
    }
    static long Long(String s){
        return Long.parseLong(s);
    }
    static class Reader extends BufferedReader{
        Reader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return s().split(" ");
        }
        int i() throws IOException{
            return Int(s());
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Int(ss[j]);
            return ii;
        }
        long l() throws IOException{
            return Long(s());
        }
        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long(ss[j]);            
            return ll;
        }
    }
}

Measured memory_bytes: 21076
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;
using vpii=vector<pair<int,int>>;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
//試験導入
#define irep(i, end_i, begin_i) for (ll i = (ll)begin_i-1; i >= (ll)end_i; i--)

long long INF = 1LL<<60;
int main( ){
    int n,c;
    cin>>n>>c;
    ll ans=INF;
    vvi D(c,vi(c));
    vvi C(n,vi(n));
    rep(i,0,c){
        rep(j,0,c)cin>>D[i][j];
    }
    vvi prepro(3,vi(c,0));
    rep(i,0,n){
        rep(j,0,n){
            cin>>C[i][j];C[i][j]--;
            prepro[(i+j)%3][C[i][j]]++;
        }
    }
    rep(zc,0,c){
        rep(oc,0,c){
            if(zc==oc)continue;
            rep(tc,0,c){
                if(tc==zc||tc==oc)continue;
                ll res=0;
                rep(rem,0,3){
                    rep(color,0,c){
                        ll remc;
                        if(rem==0)remc=zc;
                        else if(rem==1)remc=oc;
                        else remc=tc;
                        res+=prepro[rem][color]*D[color][remc];
                    }
                }
                chmin(ans,res);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}




Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
const int MOD = 1e9 + 7;

ll N, M, K, Q;
string S;

int main() {
    long long a, b, c;
    cin >> a >> b >> c;

    if ((c - a - b) >= 0 && 4 * a * b < (c - a - b) * (c - a - b)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


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

int main(int argc, char const *argv[])
{
    string S;
    cin >> S;

    int counter = 0;
    int size = S.length();
    for (int i = 0, j = size - 1; i < size / 2; i++, j--)
    {
        if (S.at(i) != S.at(j))
        {
            counter++;
            // cout << S.at(i) << " " << S.at(j) << endl;
        }
    }
    cout << counter << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long LL;
int n, b, a;
int h[100000+10];

bool ok(int x) {
    LL need = 0;
    int add = a - b;
    for(int i=1;i<=n;i++) {
        LL tmp = (LL)b * (LL)x;
        if(tmp < h[i]) {
            //cout << tmp << " " << h[i] << endl;
            need += (h[i] - tmp + add - 1) / add;
            //cout << need << endl;
        } 
    }
    //cout << x << " " << need << endl;
    return need <= x;
}

int main()
{
    scanf("%d %d %d", &n, &a, &b);
    for(int i=1;i<=n;i++) {
        scanf("%d", &h[i]);
    }
    //ok(1); return 0;
    int L = 1, R = 1e9;
    while(R - L > 1) {
        int mid = (R + L) / 2;
        if(ok(mid)) {
            R = mid;
        } else {
            L = mid;
        }
    } 
    if(ok(L)) R = L;
    cout << R << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <queue>
#include <stdio.h>
using namespace std;

int main(){
    int n,q,m,sum=0;
    string s;
    queue<int> Q;
    queue<string> name;
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>s>>m;
        name.push(s);
        Q.push(m);
    }
    while(Q.size()!=0){
        if(Q.front()>q){
            Q.push(Q.front()-q);
            name.push(name.front());
            Q.pop();
            name.pop();
            sum=sum+q;
        }
        else{
            sum=sum+Q.front();
            cout<<name.front()<<" "<<sum<<endl;
            Q.pop();
            name.pop();
        }
    }
    return 0;
}


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

using namespace std;

int main(){
  int A,B;
  cin >> A >> B;

  if(A == 1 && B != 1){
    cout << "Alice\n";
  }

  else if(B == 1 && A != 1){
    cout << "Bob\n";
  }

  else if(A > B){
    cout <<"Alice\n";
  }

  else if(B > A){
    cout << "Bob\n";
  }

  else if(A == B){
    cout << "Draw\n";
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int dist(int x, int y){
  return x * x + y * y;
}

int main(){
  int T;
  cin >> T;
  while(T--){
    int N, X, Y;
    cin >> N >> X >> Y;
    int NX, NY;
    cin >> NX >> NY;
    vector<int> BX(N), BY(N);
    REP(i, N) cin >> BX[i] >> BY[i];
    vector< vector<int> > G(N);
    REP(i, N)FOR(j, i + 1, N){
      if(dist(BX[i] - BX[j], BY[i] - BY[j]) <= 50 * 50){
        G[i].push_back(j);
        G[j].push_back(i);
      }
    }
    int ans = 0;
    vector<int> cnt(N);
    queue<int> que[2];
    int T = Y / X + 1;
    REP(i, N) if(dist(BX[i] - NX, BY[i] - NY) <= 10 * 10){
      que[0].push(i);
      cnt[i] = T + 1;
    }
    while(!que[ans & 1].empty()){
      REP(i, N) if(cnt[i] > 0) cnt[i] --;
      //printf("%d:\n", ans);
      while(!que[ans & 1].empty()){
        int u = que[ans & 1].front(); que[ans & 1].pop();
        //printf("%d : %d %d\n", u, BX[u], BY[u]);
        REP(i, G[u].size()){
          int v = G[u][i];
          if(cnt[v] == 0){
            que[(ans + 1) & 1].push(v);
            cnt[v] = T + 1;
          }
        }
      }
      ans ++;
      if(ans >= 10000) break;
    }
    if(ans >= 10000) cout << "You're always welcome!" << endl;
    else cout << ans * X << endl;
  }

  return 0;
}

Measured memory_bytes: 5228
#include <iostream>
using namespace std;
int main(){
  int a,b;cin>>a>>b;
  int ans = 0;
  for(int i = a; b>= i; i++){
    string s = to_string(i);
    if(s[0]==s[4]&&s[1]==s[3])ans++;
  }
  cout << ans << endl;
}
      

Measured memory_bytes: 256
n, m = gets.to_s.split.map{|t|t.to_i}
a = Array.new(m){ gets.to_s.to_i }

if n == 1
  puts 1
  exit
end

broken = Array.new(n+1){false}
stairs = Array.new(n+1){ 0 }
stairs[0] = stairs[1] = 1

a.each do |k|
  broken[k] = true
end

stairs[1] = 0 if broken[1]

2.upto(n) do |i|
  next if broken[i]
  stairs[i] = stairs[i-1] + stairs[i-2]
end

puts stairs[-1] % (10**9+7)


Measured memory_bytes: 433788
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stdio.h>
using namespace std;
int main()
{
	int n,a[100] = {};
	cin>>n;
	for (int i = 1;i<=n;i++) cin>>a[i];
	sort(a,a+n+1);
	for (int i = 0;i<=n;i++)
	{
		if (i % 2 == 1)
		{
			if (a[i] != 0) a[i] = 24 - a[i];
		}
	}
	sort(a,a+n+1);
	int min = 24 - a[n];
	for (int i = 1;i<=n;i++)
	{
		if (min > a[i] - a[i - 1]) min = a[i] - a[i - 1];
	}
	cout<<min;
}

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

int main() {
  int N;
  cin >> N;
  vector<long long> L(87);
  L.at(0) = 2LL, L.at(1) = 1LL;
  for (int i = 2; i <= N; ++i) {
    L.at(i) = L.at(i-2) + L.at(i-1);
  }
  cout << L.at(N) << endl;
}


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

using namespace std;

int main()
{
    int n;
    int a,b;
    int P[4]={};

    cin >> n;
    cin >> a >> b;

    int x;
    for(int i = 0;i < n;i++){
        cin >> x;
        if(x >= 1 && x <= a){
            P[0]++;
        }
        else if(x >= a+1 && x <= b){
            P[1]++;
        }
        else{
            P[2]++;
        }
    }
    
    sort(P,P+3);

    cout << P[0] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
#include <queue>
#include <deque>
#include <tuple>
#include <iomanip>
#include <iterator>
#include <functional>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int Q;
  ll left_sum=0ll,right_sum=0ll,sumb=0ll;
  cin>>Q;
  priority_queue<ll> left;
  priority_queue<ll, vector<ll>, greater<ll>> right;
  REP(i,Q){
    int q;
    ll a,b;
    cin>>q;
    if(q==1){
      cin>>a>>b;
      sumb+=b;
      if (left.size()>right.size()) {
        int t=left.top();
        if(a>=t){
          right.push(a);right_sum+=a;
        }else{
          left.pop();left_sum-=t;
          left.push(a);left_sum+=a;
          right.push(t);right_sum+=t;
        }
      }else{
        if(left.empty()){
          left.push(a),left_sum+=a;
        }else{
          int t=right.top();
          if(a<=t){
            left.push(a);left_sum += a;
          }else{
            right.pop();right_sum -= t;
            right.push(a);right_sum += a;
            left.push(t);left_sum += t;
          }
        }
      }
    }else{
      ll x=left.top();
      ll res=(x*(int)left.size()-left_sum)+(right_sum-x*(int)right.size())+sumb;
      cout<<x<<" "<<res<< endl;
    }
  }
}


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

int main()
{
    string s;
    long n,i,j,ans=0;
    cin>>s;
    n = s.length();
    j=0;
    for(i=n-1;i>=0;i--)
    {
        if(s[i]=='W')
        {
            j++;
        }
        else
        {
            ans += j;
            s[i] = 'W';
            s[i+j] = 'B';
        }
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int main(void) {
	int a, b;

	scanf("%d %d", &a, &b);

	if(a <= 5)	printf("0\n");
	else if (a <= 12)	printf("%d\n", b / 2);
	else	printf("%d\n", b);

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define debug1(x) cout << #x << " " << x << endl;
#define debug2(x,y) cout << #x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define debug3(x,y,z) cout << #x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define pb push_back
#define mp make_pair
#define f first
#define s second

typedef long long ll;
using namespace std;

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

ll binpow(ll a,ll b) {    // a^b
    if(b==0) return 1;
    long long res = binpow(a,b/2);
    if(b%2)
        return res*res*a;
    else
        return res*res;
}

bool possible(ll *arr,int n,ll mid,ll k) {
    int i;bool pos=1;
    for(i=n-1;i>=0 && arr[i]>mid;i--) {
        if(k<=0) {
            pos = 0;
            break;
        }
        k = k-((arr[i]%mid!=0)?arr[i]/mid:arr[i]/mid-1);
    }
    if(k<0)
        pos = 0;
   // debug3(mid,pos,k);
    return pos;
}

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

    int n;ll k;
    cin >> n >> k;
    ll arr[n];
    for(int i=0;i<n;i++)
        cin >> arr[i];
    sort(arr,arr+n);
    ll l = 1,r=arr[n-1];
    while(l<=r) {
        ll mid = (l+r)/2;
        if(possible(arr,n,mid,k))
            r = mid-1;
        else
            l = mid+1;
    }
    cout << l << endl;
    return 0;
}


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

using namespace std;
int main() {
  int n;
  cin >> n;
  int maxPrice = 0;
  int total = 0;
  for (int i = 0; i < n; i++) {
    int price;
    cin >> price;
    total += price;
    maxPrice = max(maxPrice, price);
  }
  int result = total - maxPrice + maxPrice / 2;
  cout << result << endl;

  return 0;
}

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

using namespace std;

#define ll long long
#define mod 1000000007

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

    int h, w, k;
    cin >> h >> w >> k;
    char arr[h][w];
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j) cin >> arr[i][j];
    }
    ll ans = 0;
    for(int xbit = 0; xbit < (1<<h); ++xbit){
        for(int ybit = 0; ybit < (1<<w); ++ybit){
            int count = 0;
            for(int i = 0; i < h; ++i){
                if((1<<i) & xbit) continue;
                for(int j = 0; j < w; ++j){
                    if((1<<j) & ybit) continue;
                    if(arr[i][j] == '#') ++count;
                    if(count > k) break;
                }
                if(count > k) break;
            }
            if(count == k) ++ans;
        }
    }
    
    cout << ans << endl;    
    
	return 0;
}

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

const int MOD = 1000000007;

int main() {
    int N, M; cin >> N >> M;
    vector<bool> is_safe(N+1, true);
    for(int i = 0; i < M; ++i) {
        int a; cin >> a;
        is_safe[a] = false;
    }
    
    vector<int> dp(N+2, 0);
    dp[0] = 1;
    for(int i = 0; i < N; ++i) {
        if(is_safe[i+1] && is_safe[i]) dp[i+1] += dp[i], dp[i+1] %= MOD;
        if(is_safe[i+2] && is_safe[i]) dp[i+2] += dp[i], dp[i+2] %= MOD;
    }
    
    cout << dp[N] << endl;
}


Measured memory_bytes: 640
# -*- coding: utf-8 -*-
import bisect
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


ans = [-1] * (2*10**5+1)


@mt
def slv(N, A, UV):
    A.insert(0, -1)
    g = [list() for _ in range(0, N+1)]
    for u, v in UV:
        g[u].append(v)
        g[v].append(u)

    def dfs(u, p, dp):
        global ans

        for v in g[u]:
            if v == p:
                continue

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF)
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+1)
    dp[0] = A[1]
    dfs(1, 0, dp)

    ans[1] = 1
    for i in range(1, N+1):
        print(ans[i])


def main():
    N = read_int()
    A = read_int_n()
    UV = [read_int_n() for _ in range(N-1)]
    slv(N, A, UV)


if __name__ == '__main__':
    main()


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

#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define sc(a) scanf("%c",&a)
#define ss(a) scanf("%s",a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%lld\n",a)
#define pc(a) putchar(a)
#define ms(a) memset(a,0,sizeof(a))
#define repi(i, a, b) for(register int i=a;i<=b;++i)
#define repd(i, a, b) for(register int i=a;i>=b;--i)
#define reps(s) for(register int i=head[s];i;i=Next[i])
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pii pair<int,int>
#define mii unordered_map<int,int>
#define msi unordered_map<string,int>
#define lowbit(x) ((x)&(-(x)))
#define ce(i, r) i==r?'\n':' '
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define pr(x) cout<<#x<<": "<<x<<endl
using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + c - 48;
        c = getchar();
    }
    return f * fu;
}

int main() {
    pi(qr() ^ 1);
    return 0;
}

Measured memory_bytes: 3632
using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var array = new long[N];
        //trueのとき奇数番目が先
        var isEven = N % 2 == 0;
        var middle = N / 2;
        for (int i=0;i<N;++i)
        {
            if (isEven)
            {
                if (i % 2 == 0) array[middle + (i / 2)] = a[i];
                else array[middle - ((i + 1) / 2)] = a[i];
            }
            else
            {
                if (i % 2 == 0) array[middle - (i / 2)] = a[i];
                else array[middle + ((i + 1) / 2)] = a[i];
            }
        }
        for (int i=0;i<N;++i)
        {
            Console.Write(array[i]);
            if(i!=N-1) Console.Write(" ");
        }
        Console.WriteLine();
    }
}

Measured memory_bytes: 42040
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a1, a2, a3;
  cin >> a1 >> a2 >> a3;
  if (( a1 + a2 + a3) >= 22) {
    cout << "bust" << endl;
  }
  else cout << "win" << endl;
}

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

using namespace std;

const int MAXN = 100005;
int candles[MAXN];

int main() {
    int n, k, minDist = INT32_MAX;
    cin >> n >> k;
    int zeroIndex = -1;
    for (int i = 0; i < n; i++){
        cin >> candles[i];
    }
    for (int i = 0; i < n; i++){
        if (candles[i] > 0) {
            zeroIndex = i;
            break;
        }
    }
    if (zeroIndex == -1)
        cout << abs(candles[max(0, n - k)]) << endl;
    else if (zeroIndex == 0)
        cout << abs(candles[min(k - 1, n - 1)]) << endl;
    else {
        for (int i = max(0, zeroIndex - k); i < min(zeroIndex, n - k + 1); i++){
            minDist = min(minDist, abs(candles[i]) > abs(candles[i + k - 1]) ? abs(candles[i + k - 1]) * 2 + abs(candles[i]) : abs(candles[i]) * 2 + abs(candles[i + k - 1]));
        }
        cout << minDist << endl;
    }
}




Measured memory_bytes: 640
#include <cstdio>
#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
using namespace std;

typedef complex<double> Point;
const double EPS = 1e-10;

class Route
{
public:
	Point s, t;
	int o, l;
	Route(Point p1, Point p2, int oo, int ll)
		:s(p1), t(p2), o(oo), l(ll) {}
};

class Intersection
{
public:
	int o, l;
	double d;
	Intersection(int oo, int ll, double dd)
		:o(oo), l(ll), d(dd) {}
};

class LessDistance
{
public:
	bool operator() (const Intersection& lhs, const Intersection& rhs)
	{
		return lhs.d < rhs.d;
	}
};

double cross(Point a, Point b)
{
	return (a.real() * b.imag() - a.imag() * b.real());
}

int is_intersected_ls(Point a1, Point a2, Point b1, Point b2)
{
	return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) &&
		( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS );
}

Point intersection_ls(Point a1, Point a2, Point b1, Point b2) {
	Point b = b2-b1;
	double d1 = abs(cross(b, a1-b1));
	double d2 = abs(cross(b, a2-b1));
	double t = d1 / (d1 + d2);

	return a1 + (a2-a1) * t;
}

int main()
{
	int t;
	cin >> t;
	while (t--) {
		double xa, ya, xb, yb;
		scanf("%lf %lf %lf %lf", &xa, &ya, &xb, &yb);
		Point A(xa, ya), B(xb, yb);

		int n;
		cin >> n;
		vector<Route> route;
		for (int i = 0; i < n; ++i) {
			double xs, ys, xt, yt;
			int o, l;
			scanf("%lf %lf %lf %lf %d %d", &xs, &ys, &xt, &yt, &o, &l);
			if (l == 0)
				l = -1;
			route.push_back(Route(Point(xs, ys), Point(xt, yt), o, l));
		}

		vector<Intersection> inter;
		for (unsigned int i = 0; i < route.size(); ++i) {
			if (abs(cross(B-A, route[i].t-route[i].s)) < EPS)
				continue;
			if (is_intersected_ls(A, B, route[i].s, route[i].t)) {
				Point p = intersection_ls(A, B, route[i].s, route[i].t);
				inter.push_back(Intersection(route[i].o, route[i].l, abs(B-p)));
			}
		}

		sort(inter.begin(), inter.end(), LessDistance());

		int ans = 0, location;
		if (!inter.empty()) {
			if (inter.front().o == 1)
				location = inter.front().l;
			else
				location = -inter.front().l;

			for (unsigned int i = 1; i < inter.size(); ++i) {
				if (inter[i].o == 1) {
					if (inter[i].l != location) {
						++ans;
						location = -location;
					}
				} else {
					if (inter[i].l == location) {
						++ans;
						location = -location;
					}
				}
			}
		}

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

Measured memory_bytes: 0