akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<queue>
#include <cmath>
#include<algorithm>
#include<stack>
#include<map>
#include<ctime>
//#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
 
int main(){
    long int N,K;
    cin>>N>>K;
    long int P[N],C[N];
    for (int i=0;i<N;i++){
        cin>>P[i];
        P[i]--;
    }
    for (int i=0;i<N;i++) cin>>C[i];
    long long ans=-1000000001;
    for (int i=0;i<N;i++){
        int n=i,period=1;
        long long sum=0;
        for (int j=0;j<N;j++){
            sum+=C[n];
            n=P[n];
            if (n==i){
                period=j+1;
                break;
            }
        }
        if (sum>0){
            int m=K/period;
            long long sum2=0,x=-1000000001;
            long int k2=K;
            if (m>1){
                k2-=(m-1)*period;
                sum2+=sum*(m-1);
            }
            sum=0;
            n=i;
            for (int j=0;j<k2;j++){
                sum+=C[n];
                n=P[n];
                x=max(x,sum);
            }
            sum2+=x;
            ans=max(ans,sum2);
        }
        else{
            n=i;
            sum=0;
            long long sum2=-1000000001;
            for (int j=0;j<min(N,K);j++){
                sum+=C[n];
                n=P[n];
                sum2=max(sum2,sum);
            }
            ans=max(ans,sum2);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3704
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
using namespace std;

struct list{
	int num;
	list *left, *right;
};

list *nill;


void insert(int);
void init(void);
void deleteList(list *dl);
list *seachList(int);
void deleteFirst(void);
void deleteLast(void);
void listOutput(void);

int main(void){
	char c[50];
	int n;
	int s;
	scanf("%d", &s);
	init();
	for(int i = 0; i < s; i++){
		scanf("%s", c);
		if(c[0] == 'i'){
			scanf("%d", &n);
			insert(n);
		}
		else if(c[0] == 'd' && strlen(c) == 6){
			scanf("%d", &n);
			deleteList(seachList(n));
		}
		else if(c[6] == 'F'){
			deleteFirst();
		}
		else{
			deleteLast();
		}
	}
	listOutput();
	return 0;
}



void insert(int nu){
	list *p;
	p = (list*)malloc(sizeof(list));
	p->num = nu;

	p->right = nill->right;
	nill->right->left = p;
	nill->right = p;
	p->left = nill;
}

void init(void){
	nill = (list*)malloc(sizeof(list));
	nill->right = nill;
	nill->left = nill; 
}

list *seachList(int sl){
	list *x = nill->right;
	while(x != nill && x->num != sl){
		x = x->right;
	}
	return x;
}

void deleteList(list *dl){
	if(dl == nill) return;
	dl->left->right = dl->right;
	dl->right->left = dl->left;
	free(dl);
}

void deleteFirst(void){
	deleteList(nill->right);
}

void deleteLast(void){
	deleteList(nill->left);
}

void listOutput(void){
	list *y = nill->right;
	while(y != nill){
		if(y==nill->left){
			printf("%d\n", y->num);
		}
		else{
			printf("%d ", y->num);
		}
		y = y->right;
	}
}



Measured memory_bytes: 34348
#include<iostream>
#include<cstring>

using namespace std;

#define REP(i, n) for(int i=0; i<n; i++)
#define ll long long

struct edge{
    int from, to;
    ll cost;
};

ll INF = 10e17;
edge es[2000];
ll d[1000];
int n, m; // vertex, edge

bool shortest_path(int s){
    REP(i, n) d[i] = INF;
    d[s] = 0;
    REP(i, 2*n){
        REP(j, m){
            edge e = es[j];
            if(d[e.from]!=INF && d[e.to]>d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;

                if(i>=n-1 && e.to==n-1) return true;
            }
        }
    }
    return false;
}

int main(){
    cin >> n >> m;
    REP(i, m){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        a -= 1;
        b -= 1;
        edge e;
        e.from = a; e.to = b; e.cost = -c;
        es[i] = e;
    }

    bool flag = shortest_path(0);
    if(flag){
        cout << "inf" << endl;
    } else {
        cout << -d[n-1] << endl;
    }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 101
void push(int);
int pop(void);
void dealOperator(char);
int isOperator(char);
void printStack(void);
int stack[MAX];
int top=0;
int main(void)
{
  char s[10];//input comes here
  int ans;//calculation result comes here
  for(;;)
    {
      if(scanf("%s ",s)==EOF) break;
      if(isOperator(s[0])==1) dealOperator(s[0]);
      else push(atoi(s));
      //printStack();
    }
  ans=pop();
  printf("%d\n",ans);
  return 0;
}
void push(int x)
{
  if(top>=MAX-1) exit(1);//stack is full
  else
    {
      top++;
      stack[top]=x;
      //printf("stack[%d]=%d is pushed\n",top,x);
    }
}
int pop(void)
{
  if(top<=0) exit(2);//stack is empty
  else
    {
      top--;
      //printf("stack[%d]=%d is poped\n",top+1,stack[top+1]);
      return stack[top+1];
    }
}
void dealOperator(char c)
{
  int b=pop();//value on the top
  int a=pop();//value on the 2nd top
  switch(c)
    {
    case '+':
      push(a+b);
      break;
    case '-':
      push(a-b);
      break;
    case '*':
      push(a*b);
      break;
    default:
      exit(3);//undefined operator
    }
}
int isOperator(char c)
{
  if(c=='+'||c=='-'||c=='*') return 1;
  else return 0;
}
void printStack(void)
{
  int i;
  for(i=1;i<=top;i++)
    {
      if(i>1) printf(" ");
      printf("%d",stack[i]);
    }
  printf("\n");
}


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

using namespace std;
using ll = long long;

class UnionFind {
public:
  vector<int> par;

  UnionFind(int n) {
    par = vector<int>(n, -1);
  }

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

  int size(int x) {
    return -par[root(x)];
  }

  bool same(int x, int y) {
    if (root(x) == root(y))
      return true;
    else
      return false;
  }

  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) return;
    if (size(x) < size(y)) swap(x, y);
    par[x] += par[y];
    par[y] = x;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  vector<vector<int>> AB(M, vector<int>(2));
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    AB[i][0] = --a;
    AB[i][1] = --b;
  }
  UnionFind uf(N);
  vector<ll> res;
  ll K = 1LL * N * (N - 1) / 2;
  for (int i = M - 1; i >= 0; i--) {
    int a = AB[i][0], b = AB[i][1];
    res.push_back(K);
    if (uf.same(a, b)) continue;
    int sa = uf.size(a), sb = uf.size(b);
    K -= 1LL * sa * sb;
    uf.unite(a, b);
  }
  reverse(res.begin(), res.end());
  for (int i = 0; i < M; i++)
    cout << res[i] << '\n';
  return 0;
}


Measured memory_bytes: 8180
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef long long ll;
namespace mp = boost::multiprecision;
using Mint = mp::cpp_int;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = int(a); i < int(b); i++)
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define sort_g(v) sort(all(v), greater<int>())
#define dump(x) cerr << #x << ' ' << '=' << ' ' << x << endl

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

    int A = 0, B = 0, C = 0;
    rep(i, S.size()) {
        char H = S.at(i);
        switch(H) {
            case 'a':
                A++;
                break;
            case 'b':
                B++;
                break;
            case 'c':
                C++;
                break;
            default:
                break;
        }
    }

    if(abs(A - B) <= 1 && abs(B - C) <= 1 && abs(C - A) <= 1) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int a[55];
int n,i,ans;

int main(){
	cin>>n;
	
	for(i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]!=i) ans++;
	}
	
	if(ans==2||ans==0){
		cout<<"YES";
	}else{
		cout<<"NO";
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <utility>
  
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n) for(int i=1;i<=(n);i++)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;
      
int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,d;
  cin>>n>>d;
  d*=2;
  d++;

  if(n%d==0){
    cout<<n/d<<'\n';
  }
  else{
    cout<<n/d+1<<'\n';
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;


int main() {
    string s, t;
    cin >> s >> t;
    string s1, s2;
    for (int i = 0; i < s.size(); ++i) {
        if(i&1) s1 += s[i];
        else s2 += s[i];
    }
    s1 += '?', s2 += '?';
    int cnt = 0;
    for (char i : t) {
        if(s1[cnt] == i) cnt++;
    }
    if(cnt+1 == s1.size()) {
        puts("Yes");
        return -0;
    }
    cnt = 0;
    for (char i : t) {
        if(s2[cnt] == i) cnt++;
    }
    if(cnt+1 == s2.size()) {
        puts("Yes");
        return -0;
    }
    puts("No");
    return 0;
}



Measured memory_bytes: 3232
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define MOD 1000000007 //10^9+7
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int INF = numeric_limits<int>::max();

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

//greatest common divisor
long long gcd(ll a, ll b) 
{
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

//least common multiple
long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

int main()
{
    int n; cin >> n;
    if (n == 1) {
        cout << "1 1" << endl;
        return 0;
    }
    set<int> s;
    int over = 0;
    rep(i,n) {
        int a;
        cin >> a;
        if (a >= 3200) {
            over++;
        } else {
            s.insert(a/400);
        }
    }
    if (s.size() == 0) {
        cout << 1 << " ";
    }else {
        cout << s.size() << " ";
    }
    cout << s.size() + over << endl;


    return 0;
}


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

int n,t,m[1000],l[1000],k[1000];

bool check(int x){
  int c[1001]={},used[1000]={},cnt=n;
  for(int i=0;i<t;i++,x+=c[i])
    for(int j=0;j<n&&x;j++){
      if(used[j])continue;
      if(i+m[j]>t)return 0;
      if(i%(l[j]+k[j])<=l[j])c[i+m[j]]++,cnt--,used[j]=1,x--;
    }
  return !cnt;
}

int main(){
  while(scanf("%d%d",&n,&t),n){
    for(int i=0;i<n;i++)scanf("%d%d%d",&m[i],&l[i],&k[i]);
    int ans=0;
    for(int i=1;i<=n&&!ans;i++)if(check(i))ans=i;
    cout<<ans<<endl;
  }
  return 0;
}

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

using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

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

    int a, b;
    cin >> a >> b;
    cout << (a <= 9 && b <= 9 ? a * b : -1) << "\n";

    return 0;
}


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

using namespace std;
#define int long
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

signed main() 
{
	int A[3], sum = 0;;
	for (int i = 0; i < 3; i++)
	{
		cin >> A[i];
		sum += A[i];
	}
	if (sum >= 22)cout << "bust";
	else cout << "win";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n);
  int all = 0;
  REP(i, n){
    cin >> a[i];
    all ^= a[i];
  }
  for(int ii = 0; ii < n; ii++){
      if(ii) cout << ' ';
      cout << (all ^ a[ii]);
  }
  cout << endl;
}

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

int N,Q;
vector<int> adjlist[200000];
int counter[200000];

signed main() {
  cin >> N >> Q;
  for(int i=0; i<N-1; i++) {
    int a, b; cin >> a >> b; a--; b--;
    adjlist[a].push_back(b);
    adjlist[b].push_back(a);
  }
  for(int i=0; i<Q; i++) {
    int p, x; cin >> p >> x; p--;
    counter[p]+=x;
  }

  vector<int> ans(N, -1);
  ans[0] = counter[0];
  queue<int> q;
  q.push(0);
  while(q.size()) {
    int from = q.front(); q.pop();
    for(auto to : adjlist[from]) {
      if(ans[to] != -1) continue;
      ans[to] = ans[from] + counter[to];
      q.push(to);
    }
  }
  for(int i=0; i<N; i++) cout << ans[i] << (i==N-1 ? "\n" : " ");
}


Measured memory_bytes: 15480
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int ab = a+b;
        int ans = ab%2==0? (ab/2):(ab/2+1);
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    if(a==b) {
        cout << c << endl;
    } else if(b==c) {
        cout << a << endl;
    } else {
        cout << b << endl;
    }
    return 0;
}

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

int main(){
  int a;
  cin>>a;
  if(a==22){
    cout<<"Christmas Eve Eve Eve"<<endl;
  }else if(a==23){
    cout<<"Christmas Eve Eve"<<endl;
  }else if(a==24){
    cout<<"Christmas Eve"<<endl;
  }else{
    cout<<"Christmas"<<endl;
  }
  return 0;
}

  

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i,a,b)  for(int i = a; i < b; i++)
#define endl '\n'

using ll = long long;
using db = long double;
using ii = pair<int, int>;

const int N = 2e5 + 5, LG = 19, MOD = 1e9 + 7;
const int SQ =225;
const long double EPS = 1e-7;
int n, d, A;
ll sweep[N];
vector<ii> vx;
int32_t main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif

  cin >> n >> d >> A;
  vx.resize(n);
  f(i,0,n){
    cin>>vx[i].F>>vx[i].S;
  }

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

  ll cur = 0;
  ll ans = 0;
  f(i,0,n){
    cur -= sweep[i];
    vx[i].S -= cur;
    if(vx[i].S > 0){
      int cnt = (vx[i].S + A - 1) / A;
      cur += 1ll * cnt * A;
      int nxt = upper_bound(vx.begin(),vx.end(),ii(vx[i].F+min(d+d,vx.back().F-vx[i].F), INT_MAX)) - vx.begin();
      sweep[nxt] += 1ll * cnt * A;
      ans += cnt;
    }
  }

  cout <<ans<<'\n';

  return 0;
}


Measured memory_bytes: 3328
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    int b;
    int c;
}node;

void swap(int* a,int* b){
    int c=*a;
    *a=*b;
    *b=c;
}

void p_push(int* heap, int* len, int target){
    *(heap+*(len)) = target;
    *len += 1;
    int x = *len;
    while(x > 1){
        if(*(heap+(x/2)-1) > *(heap+x-1)){
            swap(heap+(x/2)-1, heap+x-1);
        }
        x = x/2;
    }
}

int p_pop(int* heap, int* len){
    int top = *heap;
    int x=1;
    swap(heap, heap+*(len)-1);
    *len -= 1;
    while(x <= (*(len)-1)/2){
        if(*(heap+(2*x)-1) > *(heap+(2*x)+1-1)){
            if(*(heap+x-1) > *(heap+(2*x)+1-1)){
                swap(heap+x-1, heap+(2*x)+1-1);
            }
            x = 2*x+1;
        }else{
            if(*(heap+x-1) > *(heap+(2*x)-1)){
                swap(heap+x-1, heap+(2*x)-1);
            }
            x = 2*x;
        }
    }
    if(*len > 0 && (*len)%2 == 0){
        if(x == (*len)/2 && *(heap+x-1) > *(heap+*(len)-1)){
            swap(heap+x-1, heap+*(len)-1);
        }
    }
    return top;
}

int cmp(const void* a, const void* b){
    return ((node*)b)->c - ((node*)a)->c;
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    int a[n], a_len = 0;
    node x[m];
    for(int i=0; i<n; i++){
        int buf;
        scanf("%d", &buf);
        p_push(a, &a_len, buf);
    }
    for(int i=0; i<m; i++){
        scanf("%d%d", &(x[i].b), &(x[i].c));
    }
    qsort(x, m, sizeof(node), cmp);
    int f;
    for(int i=0; i<m; i++){
        f = 0;
        int p = x[i].b;
        int q = x[i].c;
        for(int j=0; j<p; j++){
            int z = p_pop(a, &a_len);
            if(z >= q){
                p_push(a, &a_len, z);
                f = 1;
                break;
            }else{
                p_push(a, &a_len, q);
            }
        }
        /*for(int j=0; j<n; j++){
            printf("%d ", a[j]);
        }
        printf("\n");*/
        if(f){
            break;
        }
    }
    long long int ans = 0;
    for(int i=0; i<n; i++){
        ans += a[i];
    }
    printf("%lld", ans);

    return 0;
}

Measured memory_bytes: 2172
#include<stdio.h>
#include<math.h>
int main()
{
	int n,i;
	double root,ch;
	scanf("%d",&n);
	for(i=n; i>0; i--)
	{
		root=sqrt(i);
		ch=floor(root);
		if(ch==root)
		{
			printf("%d\n",i);
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n)for(int i=0;i<(int)(n);i++)
#define PI 3.141592653589793
//vector < vector<int>>a(0, vector<int>(0));二次元配列宣言


int main()
{
	long long int n, a, b;
	cin >> n >> a >> b;
	long long int c, sum = 0;
	sum += n / (a + b) * a;
	c = n % (a + b);
	if (c <= a)
		sum += c;
	else
		sum += a;
	cout << sum << endl;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define contains(v, t) (find(v.begin(), v.end(), t) != v.end())
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;

int main() {
  int k;
  string s;
  cin>>k>>s;
  if (s.length() <= k) {
    cout << s;
  } else {
    cout << s.substr(0, k) << "...";
  }
}


Measured memory_bytes: 3624
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

class Main{
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final PrintWriter out = new PrintWriter(System.out);
    public static void main(String[] Args) throws IOException{
        Integer.parseInt(br.readLine());
        final String[] a = br.readLine().split(" ");
        for(int i = a.length-1; i>=0; i--){
            out.print(a[i]);
            if(i!=0) out.print(' ');
        }
        out.println();
        out.flush();
    }
}

Measured memory_bytes: 24288
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False
# show_flg = True


def check(x, N, M, V, P, A):
    if (N - x) <= P:
        return True

    if V <= x + P:
        return (A[x] + M) >= A[N-P]

    x_score = A[x] + M
    total_v = (V - x - P) * M
    show('x =', x, 'A[x] =', A[x], 'x_score =', x_score, 'total_v =', total_v)

    if A[N-P] > x_score:
        return False

    for i in range(x+1, N-P+1):
        show('i = ', i, 'A[i] =', A[i], 'total_v =', total_v,
             '(x_score - A[i]) =', (x_score - A[i]))
        total_v -= min(M, (x_score - A[i]))

    show('total_v =', total_v)
    if total_v <= 0:
        return True
    else:
        return False


def main():
    N, M, V, P = MI()
    A = LI()
    A.sort()

    if(check(0, N, M, V, P, A)):
        print(N)
        return

    # isOK = N-1
    # isNG = 0
    # while(isOK-isNG > 1):
    #     middle = (isOK+isNG)//2
    #     if(check(middle, N, M, V, P, A)):
    #         isOK = middle
    #     else:
    #         isNG = middle
    # print(N-isOK)
    r = N - 1
    l = 0
    while r-l > 1:
        mid = (l+r) // 2
        # print('brefore l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
        if check(mid, N, M, V, P, A):
            r = mid
        else:
            l = mid
        # print('after l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
    print(N - r)
    return
    # A = sorted(A)
    # show('N =', N, 'M =', M, 'V =', V, 'P =', P)
    # show(A)

    # l = 0
    # r = N - 1
    # while r-l > 1:
    #     mid = (l+r) // 2
    #     # print('brefore l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
    #     if check_(mid, N, M, V, P, A):
    #         r = mid
    #     else:
    #         l = mid
    #     # print('after l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
    # print(N - r)


if __name__ == '__main__':
    main()


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

map<int,int> prime_factor(int n) {
  map<int,int> ret;
  for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ++ret[i];
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

vector<int> d(101,0);
int c_2, c_4, c_14, c_24, c_74;

signed main() {

  int N;
  cin >> N;

  for (int i = 1; i <= N; ++i) {
    auto p_f = prime_factor(i);
    for (auto itr=p_f.begin(); itr!=p_f.end(); ++itr) {
      d[itr->first] += itr->second;
    }
  }

  for (auto& e : d) {
    if (e >=  2)  c_2++;
    if (e >=  4)  c_4++;
    if (e >= 14) c_14++;
    if (e >= 24) c_24++;
    if (e >= 74) c_74++;
  }

  int res = 0;
  // a^2 * b^4 * c^4 -> C(c_4,2) * (c_2 - 2)
  res += max(0,c_4*(c_4-1)/2*(c_2-2));
  // a^2 * b^24 -> c_24 * (c_2 - 1)
  res += max(0,c_24*(c_2-1));
  // a^4 * b^14 -> c_14 * (c_4 - 1)
  res += max(0,c_14*(c_4-1));
  // a^74
  res += c_74;
  cout << res << endl;

}


Measured memory_bytes: 256
n = int(input())
ls = list(map(int, input().split()))

cnt2 = 0
cnt4 = 0

for i in range(n):
    if ls[i] % 4 == 0:
        cnt4 += 1
    elif ls[i] % 2 == 0:
        cnt2 += 1

if 2 * cnt4 + 1 >= n:
    print("Yes")
elif 2 * cnt4 + cnt2 >= n:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 15020
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define M 100000007
void addSelf(ll &a,ll b)
{
    a+=b;
    while(a>=M)a-=M;
}
 
void subSelf(ll &a,ll b)
{
    a-=b;
    while(a<0)a+=M;
}

void solve()
{
    ll n; cin >> n;
    ll a[n];
    for(ll i=0;i<n;i++){
        cin >> a[i];
    }
    ll ans=0;
    for(ll i=1;i<n;i++){
        if(a[i]>=a[i-1]){
            //its fine
        }else{
            ans+=(a[i-1]-a[i]);
            a[i]=a[i-1];
        }
    }
    cout << ans << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

   /*  #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif */

    clock_t start, end; 
    start = clock(); 
  
    solve(); 
  
    end = clock(); 
  /* 
    double time_taken = double(end - start) / double(CLOCKS_PER_SEC); 
    cout << "Time taken by program is : " << fixed  
         << time_taken << setprecision(5); 
    cout << " sec " << endl;  */
}



Measured memory_bytes: 5176
S = input()
OPs =["+++","++-","+-+","+--","-++","-+-","--+","---"]
for op in OPs:
    if eval(S[0]+op[0]+S[1]+op[1]+S[2]+op[2]+S[3]) == 7:
        print(S[0]+op[0]+S[1]+op[1]+S[2]+op[2]+S[3]+"=7")
        break

Measured memory_bytes: 3060
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def main():
    n = ri()
    ld = rli()
    ans = 0
    for i in range(len(ld)):
        for j in range(len(ld)):
            if j <= i:
                continue
            ans += ld[i]*ld[j]
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
//                   ********** YATIN KWATRA **********

// AC BAKSHI RABBA

#include <bits/stdc++.h>
#define ll                      long long 
#define ld                      long double
#define ull                     unsigned long long 
#define FIO                     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl                    "\n"
#define fo(i,a,b)               for(int i = a; i<=b ; i++)
#define rfo(i,a,b)              for(int i = a; i>=b ; i--)
#define vii                     vector<int>
#define vll                     vector<ll>
#define pq                      priority_queue
#define uom                     unordered_map                
#define all(v)                  v.begin(),v.end()
#define mp                      make_pair
#define pb                      push_back
#define pob                     pop_back
#define ff                      first
#define ss                      second
#define pii                     pair<int,int> 
#define pll                     pair<long,long>
#define mll                     map<ll,ll>
#define mii                     map<int,int>
#define vvii                    vector<vii>
#define vvll                    vector<vll>
#define mod                     1000000007
#define MIN                     -1e9
#define pi                      3.1415926535897932384626433832795

using namespace std;

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

/*
    
   -> Check For Overflows
   -> Out of Bounds
   -> Initialisations of global arrays and variables
   -> Read the Question and the sample test cases carefully
   -> Its not Always Complex, Try to simplify
   -> write it down and try to solve
   -> Have Faith in urself and in ur approach
   -> If it seems totally out of reach, switch to next :)
   -> And Come Back later, if possible ..
*/





void solve()
{ 
        int n;
        cin >> n;
        
        vll v(n);
        
        fo(i,0,n-1) cin >> v[i];

        int ans = 0;

        fo(i,0,n-1)
        {
          if((i+1)&1 and v[i]&1) ans++;
        }
        cout << ans << endl;

       
}
int main() {
    
    FIO
    INPUT();
    
    int t;
    t = 1;
    //cin >> t;
    
    while(t--)
    {
       solve();
    }
    return 0;
}


Measured memory_bytes: 3612
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		int X = int.Parse(str[0]);
		int Y = int.Parse(str[1]);
		int Z = int.Parse(str[2]);
		int K = int.Parse(str[3]);
		long[]A = new long[X];
		string[] str2 = Console.ReadLine().Split();
		for(var i=0;i<X;i++){
			A[i] = long.Parse(str2[i]);
		}
		long[]B = new long[Y];
		string[] str3 = Console.ReadLine().Split();
		for(var i=0;i<Y;i++){
			B[i] = long.Parse(str3[i]);
		}
		long[]C = new long[Z];
		string[] str4 = Console.ReadLine().Split();
		for(var i=0;i<Z;i++){
			C[i] = long.Parse(str4[i]);
		}
		Array.Sort(A,(x,y)=>x.CompareTo(y));
		Array.Sort(B,(x,y)=>x.CompareTo(y));
		Array.Sort(C,(x,y)=>x.CompareTo(y));
		int x1 = X-1;
		int y1 = Y-1;
		int z1 = Z-1;
		var dic = new Dictionary<int,int>();
		var pq = new PriorityQueue<int>((x,y)=>(A[y/1000000]+B[y/1000%1000]+C[y%1000]).CompareTo(A[x/1000000]+B[x/1000%1000]+C[x%1000]));
		pq.Enqueue(x1*1000000+y1*1000+z1);
		dic[x1*1000000+y1*1000+z1] = 1;
		var list = new List<long>();
		while(list.Count<K){
			int w = pq.Dequeue();
			int x2 = w/1000000;
			int y2 = w/1000%1000;
			int z2 = w%1000;
			long a2 = A[x2]+B[y2]+C[z2];
			list.Add(a2);
			if(x2>0 && !dic.ContainsKey(w-1000000)){
				dic[w-1000000] = 1;
				pq.Enqueue(w-1000000);
			}
			if(y2>0 && !dic.ContainsKey(w-1000)){
				dic[w-1000] = 1;
				pq.Enqueue(w-1000);
			}
			if(z2>0 && !dic.ContainsKey(w-1)){
				dic[w-1] = 1;
				pq.Enqueue(w-1);
			}
		}
		for(var i=0;i<list.Count;i++){
			Console.WriteLine(list[i]);
		}
	}
}

class PriorityQueue<T>
{
    private readonly List<T> heap;
    private readonly Comparison<T> compare;
    private int size;
    public PriorityQueue() : this(Comparer<T>.Default) {} 
    public PriorityQueue(IComparer<T> comparer) : this(16, comparer.Compare) { }
    public PriorityQueue(Comparison<T> comparison) : this(16, comparison) { }
    public PriorityQueue(int capacity, Comparison<T> comparison)
    {
        this.heap = new List<T>(capacity);
        this.compare = comparison;
    }
    public void Enqueue(T item)
    {
        this.heap.Add(item);
        var i = size++;
        while (i > 0)
        {
            var p = (i - 1) >> 1;
            if (compare(this.heap[p], item) <= 0)
                break;
            this.heap[i] = heap[p];
            i = p;
        }
        this.heap[i] = item;

    }
    public T Dequeue()
    {
        var ret = this.heap[0];
        var x = this.heap[--size];
        var i = 0;
        while ((i << 1) + 1 < size)
        {
            var a = (i << 1) + 1;
            var b = (i << 1) + 2;
            if (b < size && compare(heap[b], heap[a]) < 0) a = b;
            if (compare(heap[a], x) >= 0)
                break;
            heap[i] = heap[a];
            i = a;
        }
        heap[i] = x;
        heap.RemoveAt(size);
        return ret;
    }
    public T Peek() { return heap[0]; }
    public int Count { get { return size; } }
    public bool Any() { return size > 0; }
}

Measured memory_bytes: 14048
#include <bits/stdc++.h>
using namespace std;
const int MAX = (1e5)+1;

int n, xora, xorb, a[MAX], b[MAX], dsu[MAX], cnt[MAX];
vector<int> tmpa, tmpb;
map<int,int> compress;
int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
void merge(int u, int v) {
	if((u = root(u)) == (v = root(v))) {
		cnt[u]++;
		return;
	}
	if(dsu[u] > dsu[v]) swap(u, v);
	dsu[u] += dsu[v];
	dsu[v] = u;
	cnt[u] += cnt[v]+1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	fill(dsu, dsu+MAX, -1);
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		tmpa.push_back(a[i]);
		xora ^= a[i];
	}
	for(int i = 0; i < n; i++) {
		cin >> b[i];
		tmpb.push_back(b[i]);
		xorb ^= b[i];
	}
	a[n] = xora;
	b[n] = xorb;
	tmpa.push_back(xora);
	tmpb.push_back(xorb);
	sort(tmpa.begin(), tmpa.end());
	sort(tmpb.begin(), tmpb.end());
	for(int i = 0; i <= n; i++) if(tmpa[i] != tmpb[i]) cout << -1, exit(0);
	tmpa.resize(distance(tmpa.begin(), unique(tmpa.begin(), tmpa.end())));
	for(int i = 0; i < tmpa.size(); i++) compress[tmpa[i]] = i;
	for(int i = 0; i <= n; i++) {
		a[i] = compress[a[i]];
		b[i] = compress[b[i]];
		if(a[i] != b[i]) merge(a[i], b[i]);
	}
	int ans = cnt[root(a[n])] - (a[n] != b[n]);
	for(auto p: compress) if(root(p.second) == p.second && root(p.second) != root(a[n]) && cnt[root(p.second)]) ans += cnt[root(p.second)]+1;
	cout << ans;
}

Measured memory_bytes: 7288
import java.util.*; 
	public class Main {
	public static void main( String[] args) {			
					
					Scanner in = new Scanner(System.in);
					String a = in.next();
					int l = a.length();
					int flag =0;
					for(int i = 0;i<l;i++) {
						if(a.charAt(i)=='7') {
							flag = 1;
							break;
						}
					}
					if(flag ==1)
					System.out.println("Yes");
					
					else {
						System.out.println("No");
					}
					
			}}

Measured memory_bytes: 35536
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a,b) ((a<b)?a:b)
#define _max(a,b) ((a<b)?b:a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a)?1:-1)
#define SORT(v) sort(v.begin(),v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

LLI power(LLI a, LLI b) { LLI res = 1; while (b > 0) { if (b & 1)res = res * a % MOD; a = a * a % MOD; b >>= 1; }return res; }

int main() {
    cout << fixed << setprecision(10);
    int n,a,b;
    cin >> n>>a>>b;
    LLI ans = power(2,n);
    ans--;
    LLI x = 1;
    LLI y = 1;
    REP(i, a) {
        x = (x * (n - i)) % MOD;
        y = (y * (i + 1)) % MOD;
    }
    LLI ma = (x * power(y, MOD - 2)) % MOD;
    x = 1;
    y = 1;
    REP(i, b) {
        x = (x * (n - i)) % MOD;
        y = (y * (i + 1)) % MOD;
    }
    LLI mb = (x * power(y, MOD - 2)) % MOD;
    ans = (ans + MOD - ma) % MOD;
    ans = (ans + MOD - mb) % MOD;
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
     int w, n, a, b, i, x[31]={0}, tmp;
  scanf("%d",&w);
  scanf("%d",&n);
 
  for( i=1 ; i<=w ; i++ ){
    x[i]=i;
  }
 
  for( i=0 ; i<n ; i++ ){
    scanf("%d,%d",&a,&b);
    tmp=x[a];
    x[a]=x[b];
    x[b]=tmp;
  }
 
  for( i=1 ; i<=w ; i++ ){
    printf("%d\n",x[i]);
  }
  return 0;
}

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

int main(){
  int n,l;
  int a[100010];
  cin >> n >> l;
  for(int i = 0;i < n;i++) cin >> a[i];

  int last = -1;
  for(int i = 0;i < n-1;i++){
    if(a[i+1] + a[i] >= l){
      last = i;
      break;
    }
  }
  if(last == -1){
    cout << "Impossible" << endl;
    return 0;
  }else{
    cout << "Possible" << endl;
  }

  for(int i = 0;i < last;i++){
    cout << i+1 << endl;
  }

  for(int i = n-2;i > last;i--){
    cout << i+1 << endl;
  }

  cout << last+1 << endl;
  return 0;
}


Measured memory_bytes: 1152
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    a, b = mi()
    print('No') if a % 2 == 0 or b % 2 == 0 else print('Yes')


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=int(a);i<=int(b);i++)
#define ROF(i,a,b) for(int i=int(b);i>=int(a);i--)
#define pb push_back
#define pq priority_queue
#define ps push
#define x first
#define y second
using namespace std;
int n,m,anw;
string a,b;
int main(){
    cin>>a>>b;
    FOR(i,0,2) if(a[i]==b[i]) anw++;
    cout<<anw;
}


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

using namespace std;

const int N=100010;

int n,a[N];

int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  sort(a+1,a+1+n,greater<int>());
  int p=0;
  while(p+1<n && p+1<a[p+2]) p++;
  int A=(a[p+1]-p)&1,B=1;
  for(int i=p+2;i<=n && a[i]>p;i++) B^=1;
  if(A && B) puts("Second"); else puts("First");
  return 0;
}


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

int n;
int arr[100100];
int res[100100];
char str[100100];

bool test() {
    int i;
    for (i=1;i<=n;i++) arr[i+1] = arr[i]^res[i]^arr[i-1];
    return (arr[0]==arr[n])&&(arr[1]==arr[n+1]);
}

void print() {
    int i;
    for (i=0;i<n;i++) printf("%c",((arr[i])?'W':'S'));
    exit(0);
}

int main() {
    int i, j;
    scanf("%d",&n);
    scanf("%s",str);
    for (i=0;i<=n;i++) res[i] = (str[i%n]=='x');

    for (i=0;i<2;i++) for (j=0;j<2;j++) {
        arr[0] = i;
        arr[1] = j;
        if (test()) print();
    }
    printf("-1\n");

    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using P = pair<int, int>;
using PL = pair<lint, lint>;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
void yes(bool expr) {cout << (expr ? "Yes" : "No") << "\n";}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  lint N;
  cin >> N;
  vector<lint> A(N);
  REP(i, N) cin >> A[i];
  lint allxor = 0;
  REP(i, N) allxor ^= A[i];
  REP(i, N) REP(j, 60) if(allxor>>j&1 && A[i]>>j&1) A[i] -= 1LL<<j;
  set<lint, greater<lint>> st;
  REP(i, N) {
    for(lint x : st) A[i] = min(A[i], A[i]^x);
    if(A[i] > 0) st.insert(A[i]);
  }
  lint alland = 0;
  for(lint x : st) alland = max(alland, alland^x);
  cout << allxor + alland * 2 << endl;
}

Measured memory_bytes: 3992
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np


def main():
	n,m=map(int,input().split())
	li=[set() for _ in range(n)]
	ans=[]
	for i in range(m):
		s,c=map(int,input().split())
		li[s-1].add(c)
	for i in range(n):
		if len(li[i])>=2:
			print(-1)
			exit(0)
		if li[0]=={0} and n>=2:
			print(-1)
			exit(0)
		elif li[i]==set():
			if i==0:
				ans.append(1)
			else:
				ans.append(0)
		else:
			for k in li[i]:
				ans.append(k)
	
	if m==0 and n==1:
		ans=[0]
	
	print(*ans,sep="")
	
	
	
	
	
	
	

if __name__ == "__main__":
	main()


Measured memory_bytes: 38384
<?php
function solve($a, $b) {
    $hit = 0;
    $blow = 0;
    $aa = str_split($a);
    $ab = str_split($b);
    foreach ($aa as $ka => $va) {
        foreach ($ab as $kb => $vb) {
            if ($va != $vb) continue;
            if ($ka == $kb) $hit++;
            if ($ka != $kb) $blow++;
        }
    }
    echo $hit.' '.$blow.PHP_EOL;
}

while (true) {
    $in = explode(' ', trim(fgets(STDIN)));
    $a = $in[0];
    $b = $in[1];
    if ($a == 0 && $b == 0) break;
    solve($a, $b);
}


Measured memory_bytes: 9276
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int mod = 1e9+7;

typedef pair<ll, ll> pairs;
typedef vector<pairs> p;

struct edge{
    ll to, cost;
};


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

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

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

// 回文
bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ---------------------------------------------

int main(){
    ll n;
    cin>>n;
    vector<pair<ll, char> > c(n), y(n), z(n);
    for(ll i=0;i<n;++i){
        char a;
        ll b;
        cin>>a>>b;
        c[i] = make_pair(b, a);
    }

    y = c;
    for(ll i=0;i<n;++i){
        for(ll j=n-1;j>=i+1;--j){
            if(y[j].first < y[j-1].first){
                swap(y[j], y[j-1]);
            }
        }
    }

    z = c;
    for(ll i=0;i<n;++i){
        ll index = i;
        for(ll j=i;j<n;++j){
            if(z[j].first < z[index].first){
                index = j;
            }
        }
        swap(z[i], z[index]);
    }

    for(ll i=0;i<n;++i){
        if(i != 0){
            cout<<' ';
        }
        cout<<y[i].second<<y[i].first;
    }
    cout<<endl;
    cout<<"Stable"<<endl;
    

    bool fl = true;
    for(ll i=0;i<n;++i){
        if(y[i].first != z[i].first or y[i].second != z[i].second){
            fl = false;
        }
        if(i != 0){
            cout<<' ';
        }
        cout<<z[i].second<<z[i].first;
    }
    cout<<endl;
    if(fl){
        cout<<"Stable"<<endl;
    }else{
        cout<<"Not stable"<<endl;
    }

    return 0;
}


Measured memory_bytes: 3092
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=10100;
map<int,int> dp,v,c;
VI cand,d[N];
int w,h,k,n,x,y;
//v[N],c[N],dp[N];
int query(int x) { return (--dp.upper_bound(x))->se;}
int solve(VI x) {
	v.clear(); c.clear();
	cand.clear();
	for (auto p:x) {
		if (p%2==0) c[p/2+1]=2;
		else v[p/2+1]=1;
		cand.pb(p/2+1);
		if (p/2+2<=(w+1)/2) cand.pb(p/2+2);
		if (p/2+3<=(w+1)/2) cand.pb(p/2+3);
	}
	cand.pb((w+1)/2);
	cand.pb(0);
	sort(all(cand));
	cand.erase(unique(all(cand)),cand.end());
	dp.clear();
	dp[0]=0;
	rep(x,1,SZ(cand)) {
		int i=cand[x];
		dp[i]=query(i-1)+v[i];
		if (i-2>=0) dp[i]=min(dp[i],query(i-2)+c[i]);
	}
	return dp[w/2+1];
/*	rep(i,1,w/2+2) {
		v[i]=c[i]=0;
	}
	for (auto p:x) {
		if (p%2==0) c[p/2+1]=1; else v[p/2+1]=1;
	}
	dp[0]=0;
	rep(i,1,w/2+2) {
		dp[i]=dp[i-1]+v[i];
		if (i>=2) dp[i]=min(dp[i],dp[i-2]+2*c[i]);
	}
	return dp[w/2+1];*/
}
int main() {
	scanf("%d%d%d",&w,&h,&k);
	k-=(w+1)/2;
	if (k<0) {
		puts("-1");
		return 0;
	}
	scanf("%d",&n);
	rep(i,0,n) {
		scanf("%d%d",&x,&y);
		if (y%2==0) d[y/2].pb(x);
	}
	int r=0;
	rep(i,1,h/2+1) r+=solve(d[i]);
	int cur=(h/2)*(w/2+1)-r;
	int dd=min(r,k); r-=dd; k-=dd;
	dd=min(cur,k); cur-=dd; k-=dd;
	printf("%d\n",cur+r*2);
}

Measured memory_bytes: 4096
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

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

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define CLR(a) memset((a), 0 ,sizeof(a))

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

long long mod=1000000007;
long long memo[200000];

long long fact(long long n){
  if(memo[n] != 0) return memo[n];
  if(n == 0) return 1;
  memo[n] = (n*fact(n-1))%mod;
  return memo[n];
}
/*
long long modpow(long long n, long long p){
  long long P = p;
  long long res = 1;
  while(P > 0){
  if(p%2 == 0) return (modpow(n, p/2)*modpow(n, p/2))%mod;
  else return (n*modpow(n, (p-1)/2)*modpow(n, (p-1)/2))%mod;
}
*/
long long modpow(long long _x, long long _n)
{
	long long ret = 1;
	while(0 < _n)
	{
		if((_n % 2) == 0)
		{
			_x *= _x;
      _x = _x%mod;
			_n >>= 1;
		}
		else
		{
			ret *= _x;
      ret = ret%mod;
			--_n;
		}
	}
	return ret;
}

long long path(long long a, long long b){
  return (((fact(a+b)*modpow(fact(a), mod-2))%mod)*modpow(fact(b), mod-2))%mod;
}

int main(void){
  long long H, W, A, B;
  cin >> H >> W >> A >> B;

  REP(i, 200001) memo[i] = 0;
  long long ans = path(H-1, W-1);
  long long sub = 0;

  for(long long i=1;i<=B;i++){
    sub += (path(H-A-1, i-1)*path(W-i, A-1))%mod;
    sub = sub%mod;
  }
  ans = ans-sub;
  if(ans < 0) ans += mod;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4864