akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

using namespace std;

int main(){
  int N;
  cin >> N;
  int v[20] = {};
  int c[20] = {};
  int ans = 0;
  for(int i=0; i<N; i++){
    cin >> v[i];
  }
  for(int i=0; i<N; i++){
    cin >> c[i];
  }
  for(int i=0; i<N; i++){
    if(v[i] - c[i] > 0){
      ans += v[i] - c[i];
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

const int mod = 1000000007;


struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}

    mint &operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod - 2);
    }

    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }

    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }

    friend std::istream &operator>>(std::istream &in, mint &o) {
        ll a;
        in >> a;
        o = a;
        return in;
    }

    friend std::ostream &operator<<(std::ostream &out, const mint &o) {
        out << o.x;
        return out;
    }

};


int main() {
    int n;
    cin >> n;
    vector<mint> a(n);
    rep(i, n)cin >> a[i];

    mint ans = 0;
    mint p = 1;
    vector<mint> sum(n + 1);
    for (int i = 2; i <= n; i++) p = p * i;
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + p * mint(i).pow(mod - 2);
    for (int i = 0; i < n; i++) ans = ans + a[i] * (sum[i + 1] + sum[n - i] - p);
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long
using namespace std;
  
int main(){
  int n;
  ll t;
  cin >> n >> t;
  ll a[n], cur = 0, sum = 0, reset = 0;
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 1; i < n; i++){
    if(a[i] - cur <= t) cur = a[i];
    else{
      sum += cur + t - reset;
      reset += a[i] - cur - t;
      cur = a[i];
    }
  }
  sum = cur + t - reset;
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 1792
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        double tmp = (double)N;
        System.out.println(tmp *  3.14159265358979323846264338327950288 * 2.0000000000000000000000);
    }
}


Measured memory_bytes: 35972
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.solve();
    }
    public void solve() throws Exception {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n = scan.nextInt();
        int[] h = new int[n+2];
        for (int i = 0; i < n; i++) {
            h[i] = scan.nextInt();
        }
        long[] dp = new long[n+2];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            dp[i+1] = Math.min(dp[i+1],dp[i] + Math.abs(h[i+1]-h[i]));
            dp[i+2] = Math.min(dp[i+2],dp[i] + Math.abs(h[i+2]-h[i]));
        }
        System.out.println(dp[n-1]);
    }
}


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

int n, m, s, t, u;
vector<vector <int> > a;
int f[100000];

void path(int s1, int w) {
	f[s1] = w;
	for (int i = 0; i < (int) a[s1].size(); i++)
		if (f[a[s1][i]] == 0)
			path(a[s1][i], w);
	return;
}

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

	a.resize(n);

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}

	for (int i = 0; i < n; i++)
		f[i] = 0;

	int j = 0, k = 1;
	while (j < n) {
		if (f[j] == 0) {
			path(j, k);
			k++;
		}
		j++;
	}

	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		cin >> s >> t;

	if(f[s] == f[t])
		cout << "yes" << endl;
	else
		cout << "no" << endl;
	}

	return 0;
}


Measured memory_bytes: 13424
import numpy as np

n=int(input())
a_list=np.array(list(map(int,input().split())))
i_list=np.array([i+1 for i in range(n)])
b_list=a_list-i_list

median_value=np.median(b_list)

print(int(sum([abs(i-median_value) for i in b_list])))




Measured memory_bytes: 34184
//this library has many things needed for arrays, the asterisc means we get everything is inside, the dot says where is is inside, you need the ; to tell the line has ended, like in C
import java.util.*;

//the name of the main function has to be the same name of the program
//what public class mean in java: it means that other function scan also access the class. What happens if we dont make it public? Well, it stil works, but it will be visivle to code only in the same package
public class Main {
	//this is a method, it tells that it will execute the things that are inside, it takes string as args when we execute the program, it is optional. What if instead we use int? It does not work, it has to be String[] args
	public static void main(String[] args){
		//it is a class of the .util that is used to take input from the user. Why it is used as class?
		Scanner sc = new Scanner(System.in);
		// get a integer
		//nextInt is a method, it will take text and turn it into an integer. It is looking for space or line break? Yes, if it is a line break or a space it treats it the same way. How to consider it is different?
		int C = sc.nextInt();
		// get two integers separated with half-width break
		int t = sc.nextInt();
      	if(C>t){
          System.out.println(C-t);
        }
      	else{
          System.out.println(0);
        }
		
	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;

int main(){
    ll N, ans;
    cin >> N;
    for(ll i=1;i*i<=N;i++){
        if(N%i==0) ans = N/i;
    }
    ans = log10(ans)+1;
    cout << ans << endl;
    return 0;
}

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 100010

vector<int> G[MAX_N];
int n,m;
int num[MAX_N],par[MAX_N],low[MAX_N];
int cnt;
vector<pair<int,int> > res;

void dfs(int v,int prev){
	num[v]=low[v]=++cnt;
	for(int i=0;i<G[v].size();i++){
		int nv=G[v][i];
		if(num[nv]==-1){
			par[nv]=v;
			dfs(nv,v);
			low[v]=min(low[v],low[nv]);
			if(num[v]<low[nv]){
				res.push_back(make_pair(min(v,nv),max(v,nv)));
			}
		}else if(nv!=prev){
			low[v]=min(low[v],num[nv]);
		}
	}
}

void bridge(){
	memset(num,-1,sizeof(num));
	cnt=0;
	dfs(0,-1);
	sort(res.begin(),res.end());
}

int main(){
	cin.sync_with_stdio(false);
	cin>>n>>m;
	rep(i,m){
		int a,b;
		cin>>a>>b;
		G[a].pb(b); G[b].pb(a);
	}
	bridge();
	rep(i,res.size()){
		cout<<res[i].fi<<" "<<res[i].se<<endl;
	}
	return 0;
}

Measured memory_bytes: 7528
#[allow(unused_macros)]
macro_rules! get {
    ([$t:ty] ; $n:expr) => {
        (0..$n)
        .map(|_| get!([$t])).collect::<Vec<_>>()
    };
    ($($t:ty),+ ; $n:expr) => {
        (0..$n).map(|_| get!($($t),+)).collect::<Vec<_>>()
    };
    ([$t:ty]) => {
        rl().split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect::<Vec<$t>>()
    };
    ($t:ty) => {
        rl().parse::<$t>().unwrap()
    };
    ($($t:ty),*) => {
        {
            let line =rl();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap()),*)
        }
    };
}
fn rl() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let n = get!(usize);
    let v = get!([usize]);
    let mut count = 0;
    for i in 2..n {
        let mut nv = vec![v[i - 2], v[i - 1], v[i]];
        // println!("{:?}", nv);
        nv.sort();
        if v[i - 1] == nv[1] {
            count += 1;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 4352
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())





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

	int a[] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
	int k;
	cin >> k;
	cout << a[k - 1] << endl;



	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<typeinfo>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int H,W,h,w;
	cin >> H >> W >> h >> w;
	
	cout << H*W - h*W - H*w + h*w << endl;
	return 0;
}

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

    vl a(n);
    rep(i, n) {
        cin >> a[i];
    }
    sort(all(a));

    vl b(n);
    rep(i, n) {
        cin >> b[i];
    }
    sort(all(b));

    vl c(n);
    rep(i, n) {
        cin >> c[i];
    }
    sort(all(c));

    ll ans = 0;
    rep(i, n) {
        ll x = lower_bound(all(a), b[i]) - a.begin();
        ll y = upper_bound(all(c), b[i]) - c.begin();
        ans += x*(n-y);
    }
    
    out(ans);
    re0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <limits>
#include <string>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include "math.h"
#include "assert.h"

using namespace std;

int inf = std::numeric_limits<int>().max();

#define BUFF ios::sync_with_stdio(false)
#define epsilon 1e-07
#define pi 2 * acos(0.0);
#define mod 1000000007   // 1e9+7
#define ll long long
#define cerr if(false)cerr
#define watch(x) cerr << #x << " = " << x << endl;

int main() {

	int n;
	cin >> n; 
	vector<vector<double>> cost(n, vector<double>(n, 0));
	vector<double> x(n), y(n);
	for(int i=0; i<n; i++) {
		cin >> x[i] >> y[i]; 
	}

	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			cost[i][j] = sqrt(pow(x[i]-x[j], 2) + pow(y[i]-y[j], 2));
		}
	}

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

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

	double sum = 0;
	do {
		for(int i=0; i<n-1; i++) {
			sum += cost[v[i]][v[i+1]];
		}
	} while ( next_permutation(v.begin(), v.end()) );

	double f = 1;
	for(int i=1; i<=n; i++) {
		f *= i; 
	}
	cout.precision(15);
	cout << sum / f << endl;

}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<iomanip>

using namespace std;

int main(){
  long long W,H,x,y; cin >> W >> H >> x >> y;
  double U = W * H;
  cout << setprecision(9) << U / 2 << " ";
  if( 2* x == W && 2 * y == H){
    cout << '1' << endl;}
  else{ cout << '0' << endl;}
  return 0;}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20);
#define int long long
#define gcd __gcd
#define all(x) (x).begin(), (x).end()
template<class T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<class T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}
#define _overload(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(...) _overload(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _rev(i, n) revi(i, n, 0)
#define revi(i, a, b) for(int i = (int)(a - 1); i >= (int)(b); i--)
#define rev(...) _overload(__VA_ARGS__, revi, _rev)(__VA_ARGS__)
#define each(i, n) for(auto&& i: n)
const int INF = 1e18, MOD = 1e9 + 7;
signed main() {
    INCANT;
    int n, p, ans = 0;
    cin>>n;
    map<int, int> index;
    rep(i, n) {
        cin>>p;
        index[p] = i;
    }
    multiset<int> s;
    s.insert(-1);
    s.insert(-1);
    s.insert(n);
    s.insert(n);
    rev(i, n + 1, 1) {
        auto itr = s.lower_bound(index[i]);
        int r1, r2, l1, l2;
        r1 = *itr;
        r2 = *++itr;
        l1 = *----itr;
        l2 = *--itr;
        ans += ((r2 - r1) * (index[i] - l1) + (r1 - index[i]) * (l1 - l2)) * i;
        s.insert(index[i]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 11264
#include "bits/stdc++.h"
#define ll long long
using namespace std;
const ll INF = 1e18L + 5;
const int nax = 1e5 + 5;
vector<int> edges[nax];
int in_degree[nax]; // the number of edges going to 'b'
int dist[nax];
bool visited[nax];

void dfs(int a) {
    assert(!visited[a]);
    visited[a] = true;
    for(int b : edges[a]) {
        dist[b] = max(dist[b], dist[a] + 1);
        --in_degree[b];
        if(in_degree[b] == 0) {
            dfs(b);
        }
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        edges[a].push_back(b);
        ++in_degree[b];
    }
    for(int i = 1; i <= n; ++i) {
        if(!visited[i] && in_degree[i] == 0) {
            dfs(i);
        }
    }
    int answer = 0;
    for(int i = 1; i <= n; ++i) {
        answer = max(answer, dist[i]);
    }
    cout<<answer<<endl;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  int sw = W + 2;
  for(int i = 0; i < sw; i++) {
    cout << "#";
  }
  cout << endl;
  for(int i = 0; i < H; i++) {
    string str;
    cin >> str;
    cout << "#" << str << "#" << endl;
  }
  for(int i = 0; i < sw; i++) {
    cout << "#";
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define ss second
#define ff first
#define INF 30000000000001
#define ll_max 9000000000000000001
#define mod 1000000007
#define PI 3.14159265358979323846L
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
typedef vector<pair<ll,ll> > vll;
typedef vector<pair<int,int> > vii ;
typedef pair<ll,ll> pll;
const ll N = 10001;
const ll M = 1;

int main()
{
    fast;
    int _ = 1;
    //cin >> _;
    while(_--)
    {
        ll n, m, x = 0, y, ans = 0, k;
        cin >> n;
        ll dp[n + 1][3] = {}, aux[n][3];
        for(int i = 1; i <= n; i++) cin >> aux[i][0] >> aux[i][1] >> aux[i][2];
        dp[1][0] = aux[1][0];
        dp[1][1] = aux[1][1];
        dp[1][2] = aux[1][2];
        for(int i = 2; i <= n; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                for(int k = 0; k < 3; k++)
                {
                    if(j == k) continue;
                    dp[i][k] = max(dp[i - 1][j] + aux[i][k], dp[i][k]);
                }
            }
        }
        cout << max({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
    }
    return 0;
}


Measured memory_bytes: 4992
#include<stdio.h>
    #include<string.h>
    int main(void){
       int R;
       scanf("%d",&R);
       if(1200>R){
          printf("ABC");
       }else if(2800>R){
          printf("ARC");
       }else{
          printf("AGC");
       }

       return 0;
    }

Measured memory_bytes: 128
#pragma GCC optimize("Ofast")  
#include<bits/stdc++.h>
#include <cmath> 
using namespace std;

#define ll long long
#define rep(i,n) for (int (i) = 0; (i) < (n); (i)++) 
#define REP(i,k,n) for (int (i) = (k); (i) <= (n); (i)++) 
#define REPR(i,k,n) for (int (i) = (k); (i) >= (n); (i)--)
#define watch(x) cout << (#x) << " = " << (x) << endl

int main()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	/*---- continue Coding ;----*/

	ll int n, x, t;
	cin >> n >> x >> t;
	double ans = (double) n/x;
	ll int answer = ceil(ans) * t;
	cout << answer << "\n";

	/*---- break ;----*/

	cerr<<"Execution time: "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl; 
	return 0;
}

Measured memory_bytes: 3796
#include <iostream>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

int main(void) {
    double w, h ,x, y;
    cin >> w >> h >> x >> y;

    cout << w * h / 2;
    cout << " ";
    cout << ((w/2 == x) and (h/2 == y)) << endl;
}



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

int main(){
  int N,M;
  cin>>N>>M;
  int k,d;
  
  vector<int> s(M,0),p(M);
  for(int i=0;i<M;i++){
    cin>>k;
    for(int j=0;j<k;j++){
      cin>>d;
      s[i]+=1<<(d-1);
    }
  }
  for(int i=0;i<M;i++){
    cin>>p[i];
  }
  int ans=0;
  for(int i=0;i<(1<<N);i++){
    bool flag=true;
    for(int j=0;j<M;j++){
      int tmp=i&s[j];
      int count=0;
      for(int n=0;n<N;n++){
        if(tmp>>n&1) count++;
      }
      if(count%2!=p[j]){
        flag=false;
      }
    }
    if(flag) ans++;
  }
  cout<<ans<<endl;
  return 0;
}



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

int main() {
  int A,B;
  cin >> A >> B;
  vector<int> ans(3);
  ans.at(0)=A+B;
  ans.at(1)=A-B;
  ans.at(2)=A*B;
  sort(ans.begin(),ans.end());
  cout << ans.at(2) << endl;
}


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

#define ll long long
// #define endl '\n'

void max_self(int &a, int b){ a = max(a, b);}
void min_self(int &a, int b){ a = min(a, b);}

int n, k; vector< int > v;

bool good(int x){
	int cnt = k;
	for(int i = 0; i<n; i++){
		cnt -= (v[i] - 1) / x;
	}
	return cnt >= 0;
}

void solve(){
	cin>>n>>k;
	v.resize(n);
	for(int &i : v) cin>>i;
	int l = 0; // bad
	int r = 1e9; // good

	while(r > l + 1){
		int mid = (l + r) / 2;
		if(good(mid)){
			r = mid;
		}else{
			l = mid;
		}
	}
	cout<<r<<endl;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;// cin>>t;
	for(int i = 1; i<=t; i++){
		solve();
	}
	return 0;
}


Measured memory_bytes: 3964
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<bits/stdc++.h>
#include<queue>
#include<set>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mod 1000000007

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 namespace std;
using uif=uint_fast64_t;
using ll=long long int;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(void){

  int n,m;
  cin>>n>>m;
  //cout << n << " " << m << endl;
  int k;
  //vector<ll> k(n);
  //vector< vector<ll> > a(n,vector<ll>(0));
  vector<ll> food(m,(ll)0);

  rep(i,n){
    cin>>k;
    //cout << k << " ";
    rep(j,k){
      ll a;
      cin>>a;
      //cout << a << " " ;
      //a[i].pb(_a);
      food[a-1]++;
    }
    //cout << endl;
  }
  ll ans=0;
  rep(i,m){
    if(food[i]==n) ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
from sys import stdin
def ch_max(dp_i, dp_i_1):
    if dp_i < dp_i_1:
        dp_i = dp_i_1
    return dp_i
def chmin(dp_i, dp_i_1):
    if dp_i > dp_i_1:
        dp_i = dp_i_1
    return dp_i
n = int(stdin.readline().rstrip())
h = [int(x) for x in stdin.readline().rstrip().split()]

if n == 2:
    print(abs(h[0] - h[1]))
    exit()
dp = [float('inf')] * n
dp[0] = 0
dp[1] = abs(h[0] - h[1])
for i in range(n - 2):
    dp[i + 2] = chmin(dp[i + 2],dp[i + 1] + abs(h[i + 2] - h[i + 1]))
    dp[i + 2] = chmin(dp[i + 2],dp[i] + abs(h[i + 2] - h[i]))
print(dp[n - 1])



Measured memory_bytes: 14052
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define pf pop_front
#define mp make_pair
using namespace std;
int maxdist[100000];
int n,m;
vector<int> conn[100000];

void initialize()
{
	for(int i=0;i<n;i++)
		maxdist[i]=-1;
}

void dfs(int a)
{
	//cout<<a<<' ';
	if(maxdist[a]!=-1)
		return;
	maxdist[a]=0;
	for(int i=0;i<conn[a].size();i++)
	{
		if(maxdist[conn[a][i]]==-1)
			dfs(conn[a][i]);
		maxdist[a]=max(maxdist[a],1+maxdist[conn[a][i]]);
	}
	//cout<<a<<' '<<maxdist[a]<<endl;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	
	cin>>n>>m;
	initialize();
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		conn[a].pb(b);
		//conn[b].pb(a);
	}
	
	for(int i=0;i<n;i++)
		dfs(i);
	int ans=0;
	for(int i=0;i<n;i++)
		ans=max(ans,maxdist[i]);
	cout<<ans<<endl;

}

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

string solve(int *arr, int n, int k){
    bool dp[k+1];
    memset(dp, 0, sizeof dp);

    for(int i=1;i<=k;i++){
        for(int j=0;j<n;j++){
            if(arr[j] > i){
                continue;
            }
            if(dp[i-arr[j]]==0){
                dp[i] = 1; 
            }
        }
        
    }

    return dp[k] ? "First" : "Second"; 
}

int main() {
    int n, k;
    cin >> n >> k;
    int *arr = new int[n];
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }

    cout << solve(arr, n, k) <<endl;
}


Measured memory_bytes: 3736
#include<stdio.h>
int main(void)
{
  int c=0,c2=0,i=0;
  char s[100001];
  
  scanf("%s",s);
  
  while(1){
        if(s[i]=='\0')
      break;
    if(s[i]=='0'&&i%2==0)
      c++;
    else if(s[i]=='1'&&i%2==1)
      c++;
    i++;
    if(s[i]=='\0')
      break;
  }
i=0;
    while(1){
          if(s[i]=='\0')
      break;
    if(s[i]=='1'&&i%2==0)
      c2++;
    else if(s[i]=='0'&&i%2==1)
      c2++;
    i++;
  }
  if(c2<c)
    c=c2;
  
  printf("%d\n",c);
  return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner (System.in);
        
    //    String s = sc.next();
      //  char a[]= s.toCharArray();
        int b[] = new int[3];
        for(int i= 0 ; i<3; i++){
              b[i] =sc.nextInt();
            
        }
        Arrays.sort(b);
        System.out.println(b[0]+b[1]); 
    }
}


Measured memory_bytes: 22484
N = int(input())
list_blue = [input() for i in range(N)]

M = int(input())
list_red = [input() for i in range(M)]

set_blue = set(list_blue)
set_red = set(list_red)
set_union = set_blue | set_red

list_count = [0 for i in range(len(set_union))]
k = 0

for str in set_union:
    for i in range(N):
        if list_blue[i] == str:
            list_count[k] += 1
    for j in range(M):
        if list_red[j] == str:
            list_count[k] -= 1
    k += 1

n_max = max(list_count)

if n_max >= 0:
    print(n_max)
else:
    print(0)


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

int n,x;
int a[105];

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int cur=0,cnt=0;
    for(int i=1;i<=n&&cur<=x;i++){
        cur+=a[i];
        cnt++;
    }
    if(cur<=x)cnt++;
    cout<<cnt<<endl;

    return 0;
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ASC(x) sort(ALL((x)))
#define DESC(x) sort(ALL((x)),greater<ll>())
#define pb push_back


vec fac(210000), finv(210000), inv(210000);

ll modpow(ll a, ll n, ll m)
{
    if(n == 0) return 1;
    ll t = modpow(a, n >> 1, m);
    t = t * t % m;
    if(n & 1) t = t * a % m;
    return t; 
}

void combinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    REP(i,2,210000) {
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
 
ll combmod(ll n, ll r)
{
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    ll c = 1;
    REP(i,0,r) c = c * (n-i) % MOD;
    c = c * finv[r] % MOD;
    return c;
}

int main()
{
    ll n, a, b;
    cin >> n >> a >> b;

//    vec inv(200010, 0);
//    inv[1] = 1;
//    REP(i,2,200010) inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;

    combinit();

    ll nCa = 1, nCb = 1, c;
    REP(i,1,a+1) nCa = (nCa * (n-i+1) % MOD); nCa = nCa * finv[a] % MOD;
    REP(i,1,b+1) nCb = (nCb * (n-i+1) % MOD); nCb = nCb * finv[b] % MOD;
    c = (modpow(2, n, MOD) - 1- nCa - nCb) % MOD;
    c = (c < 0) ? c + MOD : c;
    PR(c); 

    return 0;
}

/*

nC1 + ... + nCn - nCa - nCb
= 2^n - 1 - nCa - nCb

*/

Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  int a,b,c,d,e,f;
  a=b=0;
  int cf=n,de=0;
  cf+=(1000000000 - n%1000000000);
  de+=(1000000000 - n%1000000000);
  d=1;
  e=de;
  c=1000000000;
  f=cf/1000000000;
  if(n!=1000000000000000000) cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<" "<<f<<endl;
  else cout<<0<<" "<<0<<" "<<1000000000<<" "<<0<<" "<<0<<" "<<1000000000<<endl;

  return 0;
}


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

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

   int n,m;
   cin >> n >> m;
   int a[60],b[60],c[60],d[60];

   rep(i,n) cin >> a[i] >> b[i];

   rep(i,m) cin >> c[i] >> d[i];

   rep(i,n){
      int best = (1 << 29);
      int ans = -1;
      rep(j,m){
         int dist = abs(a[i] - c[j]) + abs(b[i] - d[j]);
         if(dist < best){
            best = dist;
            ans = j;
         }
      }
      cout << ans + 1 << endl;
   }

   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1e9 + 7;

int main(){
    int n, a, b;
    cin >> n >> a >> b;

    long long int ans = 1;// pow(2, n)
    long long int pow = 2;
    for(int i=0; i<31; i++){
        if(((n>>i) & 1)){
            ans *= pow;
            ans %= MOD;
        }

        pow *= pow;
        pow %= MOD;
    }
    //cout << ans << endl;

    vector<long long int> inverse(2*1e5+1,1);
    for (int i=2; i<=2*1e5; i++){
        inverse[i] = MOD - inverse[MOD % i] * (MOD / i) % MOD;
    }

    long long int nCa = 1, nCb = 1;
    for(int i=0; i<a; i++){
        nCa *= (n-i);
        nCa %= MOD;
        nCa *= inverse[i+1];
        nCa %= MOD;
    }
    for(int i=0; i<b; i++){
        nCb *= (n-i);
        nCb %= MOD;
        nCb *= inverse[i+1];
        nCb %= MOD;
    }

    ans -= (1 + nCa + nCb);
    ans = (ans % MOD + MOD) % MOD;

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

Measured memory_bytes: 1792
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iomanip>
//#include <unordered_map>

using namespace std;

template<typename T> void uin(T &a, T b) {if (b < a) a = b;}
template<typename T> void uax(T &a, T b) {if (b > a) a = b;}


#define int long long
#define double long double
#define right right228
#define mp make_pair
#define all(v) v.begin(), v.end()

const int MOD = 1e9 + 7;

int mod(int x) {
	x %= MOD;
	if (x < 0) x += MOD;
	return x;
}

int fp(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = mod(a * a)) {
		if (b & 1) res = mod(res * a);
	}
	return res;
}

const int N = 5005;

int f[N];
int P[N];
vector<int> g[N];
bool used[N], menus = 0;
int comp_size = 0;

void dfs(int v) {
	used[v] = 1;
	++comp_size;
	if (P[v] == -1) {
		menus = 1;
	}
	for (int to : g[v]) {
		if (!used[to]) {
			dfs(to);
		}
	}
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	int n;
	cin >> n;
	int k = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> P[i];
		if (P[i] != -1) {
			g[i].emplace_back(P[i]);
			g[P[i]].emplace_back(i);
		} else {
			++k;
		}
	}
	{
		f[0] = 1;
		for (int i = 1; i <= n; ++i) {
			f[i] = mod( f[i - 1] * i );
		}
	}
	vector<int> A(k + 1);
	int res = mod( fp(n - 1, k) * n );
	int ptr = 0;
	for (int i = 1; i <= n; ++i) {
		if (!used[i]) {
			menus = 0;
			comp_size = 0;
			dfs(i);
			if (!menus) {
				res = mod( res - fp(n - 1, k) );
			} else {
				A[++ptr] = comp_size;
			}
		}
	}
	vector<int> coef(k + k + k + 1), new_coef(k + k + k + 1);
	coef[0] = 1;
	int deg = 0;
	for (int it = 1; it <= k; ++it) {
		for (int i = deg; i >= 0; --i) {
			coef[i + 1] = mod( coef[i + 1] + coef[i] * A[it] );
		}
		++deg;
	}
	for (int i = 2; i <= k; ++i) {
		int cur = mod( coef[i] * f[i - 1] );
		cur = mod( cur * fp(n - 1, k - i) );
		res = mod( res - cur );
	}
	
	for (int i = 1; i <= k; ++i) {
		int cur = mod( (A[i] - 1) * fp(n - 1, k - 1) );
		res = mod( res - cur );
	}
	cout << res << '\n';
	return 0;
}

/*

1
3 2 2
1 2 3 1 
2 3 1 0
1
1 3

01.a
3 3 4
...
.#.
...
1 1 1 3 8 
1 3 1 3 64
2 1 1 3 24
2 1 3 3 40

3 4 3
1 2
2 2
2 4
3
1 1 1 4
2 2 3 3
3 2 2 4

*/


Measured memory_bytes: 4108
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    [A, B] = string_to_int(inputs[0])
    if A >= 10 or B >= 10:
        return -1
    return A * B


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main(void){
    
    int a, b;
    cin >> a >> b;
    
    int seki = a * b;
    if(seki % 2 == 0){
        cout << "Even" << endl;
    }
    else{
        cout << "Odd" << endl;
    }
    
}

Measured memory_bytes: 3640
#include <iostream>
#include <utility>
#include <vector>
#define llint long long
#define inf 1e18

using namespace std;
typedef pair<llint, llint> P;

llint h, w, sup, sig;
llint u[35][35];
P memo[35][35][35][35];
llint sum[35][35];

llint get(llint sx, llint sy, llint tx, llint ty)
{
	return sum[tx][ty] - sum[sx-1][ty] - sum[tx][sy-1] + sum[sx-1][sy-1];
}

P dfs(llint sx, llint sy, llint tx, llint ty)
{
	if(memo[sx][sy][tx][ty].first != -1) return memo[sx][sy][tx][ty];
	
	llint asum = get(sx, sy, tx, ty);
	if(asum < sig - sup) return memo[sx][sy][tx][ty] = P(-inf, -inf);
	
	P ret = P(1, asum);
	for(int x = sx+1; x <= tx; x++){
		P res = dfs(sx, sy, x-1, ty), res2 = dfs(x, sy, tx, ty);
		ret = max(ret, P(res.first+res2.first, min(res.second, res2.second)));
	}
	for(int y = sy+1; y <= ty; y++){
		P res = dfs(sx, sy, tx, y-1), res2 = dfs(sx, y, tx, ty);
		ret = max(ret, P(res.first+res2.first, min(res.second, res2.second)));
	}
	//cout << sx << " " << sy << " " << tx << " " << ty << " " << ret.first << " " << ret.second  << endl;
	return memo[sx][sy][tx][ty] = ret;
}

int main(void)
{
	while(1){
		cin >> h >> w >> sup;
		if(h == 0 && w == 0 && sup == 0) break;
		
		sig = 0;
		for(int y = 1; y <= h; y++){
			for(int x = 1; x <= w; x++){
				cin >> u[x][y];
				sig += u[x][y];
			}
		}
		for(int y = 1; y <= h; y++){
			for(int x = 1; x <= w; x++){
				sum[x][y] = sum[x-1][y] + sum[x][y-1] - sum[x-1][y-1] + u[x][y];
			}
		}
		
		for(int sx = 1; sx <= w; sx++){
			for(int sy = 1; sy <= h; sy++){
				for(int tx = 1; tx <= w; tx++){
					for(int ty = 1; ty <= h; ty++){
						memo[sx][sy][tx][ty] = P(-1, -1);
					}
				}
			}
		}
		P res = dfs(1, 1, w, h);
		cout << res.first << " " << sup-(sig-res.second) << endl;
	}
	
	return 0;
}


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

int a, b;

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	cin >> a >> b;
	if(a % 2 == 1 && b % 2 == 1) cout << "Yes\n";
	else cout << "No\n";
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int n,i;
    scanf("%d",&n);
    int b[n-1];
    for(i=0;i<n-1;i++) scanf("%d",&b[i]);
    int sum=b[0];
    for(i=1;i<n-1;i++){
        if(b[i-1]>b[i]) sum+=b[i];
        else sum+=b[i-1];
    }
    printf("%d",sum+b[n-2]);
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
  
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
        int W = sc.nextInt();
        String S[][] = new String[H][W];
 
		for(int i=0; i<H; i++) {
			S[i] = sc.next().split("");
		}
 
		int count = 0;
		for(int i=0; i<H; i++) {
			for(int j=0; j<W; j++) {
				count = 0;
				if(S[i][j].equals("#")) {
					continue;
				}
 
				if(j-1>=0) {
                    if(i-1>=0&&S[i-1][j-1].equals("#")) 
                    count++;
                    if(S[i][j-1].equals("#")) 
                    count++;
                    if(i+1<H&&S[i+1][j-1].equals("#")) 
                    count++;
				}
 
                if(i-1>=0&&S[i-1][j].equals("#")) 
                count++;
                if(i+1<H&&S[i+1][j].equals("#")) 
                count++;
 
				if(j+1<W) {
                    if(i-1>=0&&S[i-1][j+1].equals("#")) 
                    count++;
                    if(S[i][j+1].equals("#")) 
                    count++;
                    if(i+1<H&&S[i+1][j+1].equals("#")) 
                    count++;
				}
 
				S[i][j] = ""+count;
			}
		}
 
        for(int i=0; i<H; i++){
            System.out.println(String.join("",S[i]));       
        }
        
	}
}





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

using namespace std;

int main(){

  
  int A,B;
  
  cin>>A>>B;
  
  int maxi;
  int result;
  
 if(A<B){
result = B*2-1 ;
 }
  if(A>B){
    
   result = A*2-1;
  }
  if(A==B){
    
    result = A*2;
  }
  
  cout<<result<<endl;
}


Measured memory_bytes: 256
// "header" {{{
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <tuple>
#include <iomanip>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int int64_t
#define Fixed fixed << setprecision(10)
#define moke_pair make_pair
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class T,class U> using umap = unordered_map<T,U>;
template <class T> inline int getint(T s){ 
    int n;
    cout << s;
    cin >> n;
    return n;
}

inline int64_t updiv(int64_t n,int64_t d){
    return ((n + d -1) / d);
}
/*
inline double Sqrt( const double &x) 
{
	double         xHalf = 0.5 * x;
	int64_t  tmp   = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
	double         xRes  = * (double*)&tmp;

	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	return xRes * x;
}
*/
// }}}

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

    string s;
    int k,n;
    vector<string> res;
    
    cin >> s >> k;
    n = s.size();

    rep(i,n){
        reps(j,k){
            if(i + j <= n){
                res.emplace_back(s.substr(i,j));
            }
        }
    }

    sort(all(res));
    res.erase(unique(all(res)),res.end());

    cout << res[k-1] << '\n';

    return 0;
}


Measured memory_bytes: 1660
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

const int maxn = 2100;

ll A,B;
ll ans;

int main()
{
	scanf("%lld%lld",&A,&B);
	if(A==B) return puts("1"),0;
	
	int now=60; ll al=(1ll<<61)-1;
	for(;now>=0;now--) 
	{
		if((A>>now&1)^(B>>now&1)) break;
		A&=al^(1ll<<now),B&=al^(1ll<<now);
	}
	int top=now-1;
	for(;top>=0&&!(B&(1ll<<top));top--); if(top<0) top=now;
	ll l=top==now?B:((1ll<<now)+(1ll<<top+1)-1);
	ll r=(1ll<<now)+A;
	ans=(1ll<<now+1)-A;
	if(l+1<r) ans-=r-1ll-l;
	
	printf("%lld\n",ans);
	
	return 0;
}


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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }
//Write From this Line

int main()
{
	ll N, W;
	cin >> N >> W;
	vector<ll> w(N), v(N);
	rep(i,N) cin >> w[i] >> v[i];

	map<ll,ll> mp;
	vector<ll> v0(0), v1(0), v2(0), v3(0);
	rep(i,N){
		if(w[i] - w[0] == 0){ mp[0]++; v0.push_back(v[i]);}
		if(w[i] - w[0] == 1){ mp[1]++; v1.push_back(v[i]);}
		if(w[i] - w[0] == 2){ mp[2]++; v2.push_back(v[i]);}
		if(w[i] - w[0] == 3){ mp[3]++; v3.push_back(v[i]);}
	}
	SORT(v0); SORT(v1); SORT(v2); SORT(v3);
	rSORT(v0); rSORT(v1); rSORT(v2); rSORT(v3);
	vector<ll> V0(v0.size()+1,0);
	vector<ll> V1(v1.size()+1,0);
	vector<ll> V2(v2.size()+1,0);
	vector<ll> V3(v3.size()+1,0);
	For(i,1,V0.size()) V0[i] = V0[i-1] + v0[i-1];
	For(i,1,V1.size()) V1[i] = V1[i-1] + v1[i-1];
	For(i,1,V2.size()) V2[i] = V2[i-1] + v2[i-1];
	For(i,1,V3.size()) V3[i] = V3[i-1] + v3[i-1];

	ll ans = 0;
	//debug(mp[0]);
	//debug(v0.size());
	//debug(V0.size());
	//debug(mp[0]);
	rep(a,V0.size()){
		rep(b,V1.size()){
			rep(c,V2.size()){
				rep(d,V3.size()){
					ll weight = (a+b+c+d) *w[0];
					weight += b + 2*c + 3*d;
					if(weight <= W){
						ll now = V0[a] + V1[b] + V2[c] + V3[d];
						chmax(ans,now);
					}
				}
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

int v[14];

int t[][3]={
    {0,0,0},
    {1,1,1},
    {2,2,2},
    {3,3,3},
    {4,4,4},
    {5,5,5},
    {6,6,6},
    {7,7,7},
    {8,8,8},

    {0,1,2},
    {1,2,3},
    {2,3,4},
    {3,4,5},
    {4,5,6},
    {5,6,7},
    {6,7,8}
};

bool dfs(vector<int> rest, int depth){
    if(depth==4){
        int ze=0, tw=0;
        for(int x:rest)if(x==0)ze++;else if(x==2)tw++;
        return ze==8 && tw==1;
    }
    bool res=false;
    rep(i,16){
        for(int x:t[i])rest[x]--;
        for(int x:rest)if(x<0)goto UNDO;
        if(dfs(rest,depth+1)){
            res=true;
            goto END;
        }
    UNDO:;
        for(int x:t[i])rest[x]++;
    }
 END:;
    return res;
}

vector<int> solve(){
    vector<int> ans;
    vector<int> rest(9);
    rep(i,13)rest[v[i]]++;
    rep(i,9){
        if(rest[i]!=4){
            rest[i]++;
            if(dfs(rest,0))ans.push_back(i+1);
            rest[i]--;
        }
    }
    return ans;
}

int main(){
    char buf[20];
    while(cin>>buf){
        rep(i,13)v[i]=buf[i]-'0'-1;
        vector<int> ans=solve();
        if(ans.size()){
            rep(i,ans.size()){
                cout<<ans[i];
                if(i==ans.size()-1)cout<<endl;
                else cout<<" ";
            }
        } else cout<<0<<endl;
    }
}

Measured memory_bytes: 1192
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 1000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
const int MAX_V=5100;
int V,E;
struct edge
{
	int to,cap,cost,rev;
	edge(int to,int cap,int cost,int rev):to(to),cap(cap),cost(cost),rev(rev){}
};
vector<edge> G[MAX_V];
int h[MAX_V],dist[MAX_V],prevv[MAX_V],preve[MAX_V];
void add_edge(int from,int to,int cap,int cost)
{
	G[from].pb(edge(to,cap,cost,G[to].size()));
	G[to].pb(edge(from,0,-cost,G[from].size()-1));
}
int min_cost_flow(int s,int t,int f)
{
	int res=0;
	fill(h,h+V,0);
	while(f>0)
	{
		priority_queue<P,vector<P>,greater<P> > q;
		fill(dist,dist+V,INF);
		dist[s]=0;
		q.push(mp(0,s));
		while(!q.empty())
		{
			P p=q.top();q.pop();
			int v=p.sec;
			if(dist[v]<p.fi)continue;
			for(int i=0;i<G[v].size();i++)
			{
				edge &e=G[v][i];
				if(e.cap>0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to])
				{
					dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
					prevv[e.to]=v;
					preve[e.to]=i;
					q.push(mp(dist[e.to],e.to));
				}
			}
		}
		if(dist[t]==INF)
		{
			return -1;
		}
		for(int v=0;v<V;v++)h[v]+=dist[v];
		int d=f;
		for(int v=t;v!=s;v=prevv[v])
		{
			d=min(d,G[prevv[v]][preve[v]].cap);
		}
		f-=d;
		res+=d*h[t];
		for(int v=t;v!=s;v=prevv[v])
		{
			edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
	return res;
}
int N;
int A[1100],B[1100];
vector<int> vs;
int main()
{
	scanf("%d",&N);
	for(int i=0;i<N;i++)scanf("%d %d",&A[i],&B[i]);
	for(int i=0;i<N;i++)vs.pb(A[i]),vs.pb(B[i]);
	sort(all(vs));
	vs.erase(unique(all(vs)),vs.end());
	int M = vs.size();
	// 0 S 1~N N+1~N+M N+M+1 N+M+2
	for(int i=1;i<=N;i++)add_edge(0,i,1,0);
	for(int i=0;i<N;i++)
	{
		int k = lower_bound(all(vs),B[i])-vs.begin();
		add_edge(i+1,N+1+k,1,-A[i]);
		k = lower_bound(all(vs),A[i])-vs.begin();
		add_edge(i+1,N+1+k,1,-B[i]);
	}
	for(int i=0;i<N;i++)add_edge(i+1,N+M+1,1,0);
	for(int i=0;i<M;i++)add_edge(i+N+1,N+M+2,1,0);
	add_edge(N+M+1,N+M+2,5000,0);
	V = N+M+3;
	printf("%d\n",-min_cost_flow(0,N+M+2,N));
	return 0;
}

Measured memory_bytes: 1728
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef unsigned long long int ull;
typedef long long lint;

int main(void){
    lint N,M;
    cin >> N >> M;
    lint A[N];
    rep(i,N) cin >> A[i];
    sort(A,A+N);
    lint sum[N+1]={};
    rep(i,N) sum[i+1]=sum[i]+A[i];
    lint ok=0,ng=2e5+1;
    lint ans=0,count=0;
    while(ng-ok>1){
        ans=0,count=0;
        lint mid=(ok+ng)/2;
        rep(i,N){
            auto itr=lower_bound(A,A+N,mid-A[i]);
            count+=N-(itr-A);
            ans+=A[i]*(N-(itr-A))+sum[N]-sum[itr-A];
        }
        (count>=M?ok:ng)=mid;
    }
    cout << ans-ok*(count-M) << endl;
}


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

void init() {
//#if __GLIBCXX__ == 20160609
#ifdef FIRE_MIND
    freopen("a.in", "r", stdin);
    ///freopen("a.out", "w", stdout);
#else
    ///freopen(TASKNAME".in", "r", stdin);
    ///freopen(TASKNAME".out", "w", stdout);
#endif
}

typedef long long ll;
const int INF = (int)1e9 + 34;
const int N = (int)1e6 + 34;

ll d[2][N], a[2][N];

int main() {
    init();
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[0][i];
    for (int i = 0; i < n; i++) cin >> a[1][i];

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            ll k = 0;
            if (i > 0) k = max(k, d[i - 1][j]);
            if (j > 0) k = max(k, d[i][j - 1]);
            d[i][j] = k + a[i][j];
        }
    }

    cout << d[1][n - 1];

    return 0;
}


Measured memory_bytes: 6400