akhauriyash/Code-Regression huggingface dataset:
//#include <bits/stdc++.h>
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <iomanip>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define ROF(i, j, k) for(int i = (int)(j); i >= (int)(k); --i)
#define FORLL(i, n, m) for(long long i = n; i < (long long)(m); i++)
#define SORT(v, n) sort(v, v+n)
#define REVERSE(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;
const ll MOD=1000000007LL;
typedef pair<int, int> P;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

const int MAXN = 310;

ll n;
map<int,int> mp;
double dp[MAXN][MAXN][MAXN];

double dfs(ll i, ll j, ll k){
  if(dp[i][j][k]>=0) return dp[i][j][k];
  if(i == 0 && j == 0 && k == 0) return 0.0;
  double res=0.0;
  double ijk = (double)i+j+k;
  res += n/ijk;
  if(k > 0) res += dfs(i, j+1, k-1) * (double)k/ijk;
  if(j > 0) res += dfs(i+1, j-1, k) * (double)j/ijk;
  if(i > 0) res += dfs(i-1, j, k) * (double)i/ijk;
  return dp[i][j][k] = res;  
}

int
main(void){
  cin >> n;
  REP(i,n) {
    int a;
    cin >> a;
    mp[a]++;
  }
  int one=0, two=0, three=0;
  for(auto &m: mp){
    if(m.first == 1) one+=m.second;
    if(m.first == 2) two+=m.second;
    if(m.first == 3) three+=m.second;
  }
  //cout << one << " " << two << " " << three << endl;
  memset(dp, -1, sizeof(dp));
  cout << fixed << setprecision(10) << dfs(one,two,three) << endl;
  
  return 0;
}


Measured memory_bytes: 233088
import java.util.*;
public class Main {
	static Scanner sc = new Scanner(System.in);
	static int n, s, res;
	public static void main(String[] args) {
		while(read()){
			solve();
		}
	}

	static boolean read(){
		n = sc.nextInt();
		s = sc.nextInt();
		if( n == 0 && s == 0)return false;
		return true;
	}
	
	static void solve(){
		res = 0;
		dfs(0, n, 0);
		System.out.println(res);
	}
	
	static void dfs(int i, int n, int sum){
		if(n == 0){
			if(sum == s)res++;
			return;
		}
		
		if(i > 9)return;
		for(int k = i; k <= 9; k++){
			dfs(k+1, n-1, sum+k);
		}
	}
}

Measured memory_bytes: 12000
#include <stdio.h>

int main(){
  int n,x[105],i,m=0,r;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&x[i]);
    m+=x[i];
  }
  r=((m<<1)/n+1)>>1;
  m=0;
  for(n--;n>=0;n--){
    i=x[n]-r;
    m+=i*i;
  }
  printf("%d",m);
  return(0);
}

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

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

using namespace std;

vector<int> primes(int n) {
  vector<int> p(n+1, 1);
  for (int i = 2; i*i <= n; ++i)
    if (p[i])
      for (int j = i*i; j <= n; j += i)
        p[j] = 0;
  vector<int> res;
  for (int i = 2; i <= n; ++i)
    if (p[i])
      res.push_back(i);
  return res;
}

int main() {
  auto pl = primes(1000000);
  int n = pl.size();
  while(1){
    int m,a,b;
    cin>>m>>a>>b;
    if(!m)break;
    int sp,sq,st=0;
    REP(i,n) {
      REP(j,i+1) {
        int p=pl[j],q=pl[i];
        if (p*q > m) break;
        if (a*q > b*p) continue;
        if (p*q > st) {
          st = p*q;
          sp=p;sq=q;
        }
      }
    }
    cout << sp << ' ' << sq << endl;
  }
  return 0;
}

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

#define fi first
#define se second

const int N = 1000100;

using namespace std;

int n;
char a[N];
char b[N];
int last[N][26];

int main()
{
        ios_base::sync_with_stdio(false);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

        cin >> n;
        for(int i = 1; i <= n; i++){
                cin >> a[i];
                for(int j = 0; j < 26; j++){
                        last[i][j] = last[i - 1][j];
                }
                last[i][a[i] - 'a'] = i;
        }
        bool good = true;
        for(int i = 1; i <= n; i++){
                cin >> b[i];
                if(a[i] != b[i]){
                        good = false;
                }
        }
        if(good){
                cout << 0 << "\n";
                return 0;
        }

        queue < int > v;
        int res = 0, gg = n;
        for(int i = n; i >= 1; i--){
                if(gg > i){
                        gg = i;
                }
                if(a[gg] == b[i]){
                        continue;
                }

                int h = last[gg][b[i] - 'a'];
                if(h == 0){
                        cout << -1 << "\n";
                        return 0;
                }
                gg = h;
                while(!v.empty() && v.front() - v.size() >= i){
                        v.pop();
                }
                v.push(h);
                res = max(res, (int)v.size());
        }
        cout << res << "\n";
}


Measured memory_bytes: 107904
/*
AizuOnline A0203
A New Plan of Aizu Ski Resort
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int X,Y;
char ski[15][16];
long int ways[16][16];
#define DEBUG 0
display_ski()
{
  int i,j;

  for(i=0;i<=Y;i++)
    {
      for(j=0;j<X;j++)
	printf("%ld:",ways[i][j]);
      printf("\n");
    }
}
display_cource()
{
  int i,j;

  for(i=0;i<=Y;i++)
    {
      for(j=0;j<X;j++)
	printf("%c:",ski[i][j]);
      printf("\n");
    }
}
main()
{
  int i,j;
  long int sum;
  char buffer[50];
  char *p;

  while(EOF != scanf(" %d %d ",&X,&Y) && (X||Y))
    {
      for(i=0;i<16;i++)
	for(j=0;j<16;j++)
	  ways[i][j]=0;

      for(i=0;i<Y;i++)
	{
	  fgets(buffer,50,stdin);
	  for(j=0;j<X;j++)
	  {  
	    ski[i][j]=buffer[j*2];
	  }
	}


      for(j=0;j<X;j++)
	{
	  ways[0][j] = (ski[0][j]=='0')?1:0;
	}
      for(i=1;i<Y;i++)
	for(j=0;j<X;j++)
	  {
	    if(ski[i][j] == '1')
	      ways[i][j] = 0;
	    if(ski[i][j] == '2')  
	      { 
		ways[i][j]=0;
		if (ski[i-1][j]=='0')
		  ways[i][j]+=ways[i-1][j];
		if( ski[i-2][j]=='2')
		  ways[i][j]+=ways[i-2][j];
	      }
	    else if(ski[i][j] == '0')
	      { 
		ways[i][j]=0;
		if(ski[i-1][j]=='0')
		  ways[i][j] +=ways[i-1][j];
		if(j>0&&ski[i-1][j-1]=='0')
		  ways[i][j] += ways[i-1][j-1];
		if(j<X&&ski[i-1][j+1]=='0')
		  ways[i][j] += ways[i-1][j+1];
		if(ski[i-2][j]=='2')
		  ways[i][j] += ways[i-2][j];
	      }
	  }

      for(j=0;j<X;j++)
	if(ski[Y-2][j] == '2')
	  ways[Y][j] = ways[Y-2][j];
	else
	  ways[Y][j] = 0;
      sum=0;
      for(j=0;j<=X;j++)
	{
	  sum += ways[Y-1][j];
	  sum += ways[Y][j];
	}
      /*display_ski();*/
      printf("%ld\n",sum); 
    }
return(0);
}
 

Measured memory_bytes: 0
import java.util.*;
import java.lang.Math;
public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int counter = 0;
        for(int i = 0; i < 10001; i ++){
                if(i - N >= 0){
                    counter = i - N;
                    System.out.println(counter);
                    break;
                }else{
                    i = i + 999;
                }
            }
    }
}


Measured memory_bytes: 35560
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using lint=int64_t;
using namespace std;

int main()
{
	int N,M;
	int S,T;

	cin >> N >> M;
	vector<vector<int>> graph(N);
	for(int i=0;i<M;i++)
	{
		int u,v;
		cin >> u >> v;
		u--;
		v--;
		graph[u].push_back(v);
	}
	cin >> S >> T;
	S--;
	T--;

	int dist[100010][3]={};
	queue<pair<int,pair<int,int>>> que;
	bool visited[100010][3]={};
	que.push(make_pair(0,make_pair(S,0)));
	visited[S][0]=true;
	while(!que.empty())
	{
		int cnode=que.front().second.first;
		int cmod=que.front().second.second;
		int cdist=que.front().first;
		que.pop();

		dist[cnode][cmod]=cdist;

		for(auto& i:graph[cnode])
		{
			if(visited[i][(cmod+1)%3])
				continue;
			que.push(make_pair(cdist+1,make_pair(i,(cmod+1)%3)));
			visited[i][(cmod+1)%3]=true;
		}
	}

	if(dist[T][0]!=0)
		cout << dist[T][0]/3;
	else
		cout << -1;
	cout << endl;
	return 0;
}


Measured memory_bytes: 7168
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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;

int main(){
    Init();
    ll n, sum = 0; cin >> n;
    vi a(n+1, 0);
    repf(i, n){
        cin >> a[i];
        if(a[i-1] > a[i]){
            ll sub = (a[i-1]-a[i]);
            a[i] += sub;
            sum += sub;
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 4720
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <queue>
#include <functional>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

using ll = long long;

#define INF (1LL << 62)

struct edge {
  int to;
  ll cost;
  edge() {}
  edge(int to, ll cost) : to(to), cost(cost) {}
};

int N, M, L, R;
ll D;
std::vector<edge> g[100001];

std::vector<int> tsort() {
  int n = N;
  enum { YET, VISITED, DONE };
  std::vector<int> res, flg(n, YET);
  static const std::function<bool(int)> dfs = [&](int v) {
    flg[v] = VISITED;
    for (auto &e : g[v]) {
        int w = e.to;
        if (flg[w] != DONE && (flg[w] == VISITED || !dfs(w))) return false;
    }
    flg[v] = DONE;
    res.push_back(v);
    return true;
  };
  for (int i = 0; i < n; ++i)
    if (flg[i] == YET && !dfs(i)) return {};
  std::reverse(res.begin(), res.end());
  return res;
}

bool used[100001];
ll d[100001];

bool check(int s, ll dist) {
  used[s] = true;
  d[s] = dist;
  bool ret = true;
  for (edge v : g[s]) {
    if (!used[v.to]) {
      ret &= check(v.to, dist + v.cost);
    }
    else if (used[v.to] && d[v.to] != -1) {
      if (dist + v.cost != d[v.to]) {
        return false;
      }
    }
  }
  return ret;
}

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

  int s = -1;
  std::map<int, bool> mp;

  cin >> N >> M;
  for (int i = 0; i < M; ++i) {
    cin >> L >> R >> D;
    L--, R--;
    mp[L] = mp[R] = true;
    if (s == -1) s = L;
    g[L].push_back({R, D});
    //g[R].push_back({L, D});
  }

  std::vector<int> retG = tsort();
  std::memset(d, -1, sizeof d);
  bool ans = (retG.size() != 0), k = true;
  for (int i : retG) if (mp[i] && !used[i]) k &= check(i, 0);
  ans &= k;

  if (ans) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 16500
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<string>> vvs;
typedef vector<vector<char>> vvc;
typedef vector<vector<bool>> vvb;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define vrep(v,n) for(int i=0;i<n;i++){cin >> v.at(i);} 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repn(i, n) for (int i = 0; i <= (int)(n); i++)
#define srep(i, l, n) for (int i = l; i < (int)(n); i++)
#define srepn(i, l, n) for (int i = l; i <= (int)(n); i++)
#define pb push_back 
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; }

const int mod = 1000000007;
const int inf = 1e9;
#define PI 3.14159265369;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    int a, b, c;
    cin >> a >> b >> c;
    printf("%d", b+c-a>=0?b+c-a:0);
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
using namespace std;

typedef unsigned int U;
#define L 1<<21
bool HA[L];
char T[256];

int main() {
    U n, s, t;
    char c;
    T['A'] = 1, T['C'] = 2, T['G'] = 3, T['T'] = 4;
    scanf("%d", &n);
    getchar();
    while (n--) {
        s = 0;
        t = 1;
        bool flag = ( c = getchar() ) == 'i';
        while ( ( c = getchar() ) != ' ' );
        while ( ( c = T[getchar()] ) != 0 ) {
            s += c * t;
            t *= 4;
        }
        if ( flag ) {
            HA[s] = true;
        } else {
            puts( HA[s] ? "yes" : "no" );
        }
    }
    return 0;
}

Measured memory_bytes: 2100
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	int N,K;
	cin>>N>>K;
	int l[50];
	rep(i,N)cin>>l[i];
	sort(l,l+N);
	
	int ans=0;
	for(int i=1;i<=K;i++) ans+=l[N-i];
	cout<<ans;
}

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

int main() {
    string S,T;
    cin >> S;
    sort(S.begin(),S.end());

    if (S.at(0) == S.at(1) && S.at(2) == S.at(3) && S.at(0) != S.at(2)) {
        T = "Yes";
    }

    else {
        T = "No";
    }

    cout << T << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pfi(a) printf("%d",a);
#define pfl(a) printf("%lld",a);
#define pfin(a) printf("%d\n",a);
#define pfln(a) printf("%lld\n",a);
#define sfi(a) scanf("%d",&a);
#define sfl(a) scanf("%lld",&a);
#define pb push_back
#define f(i,a,b) for(int i=a;i<b;i++)
#define ll long long
const int MAXN=2e5+5;
const int M= 998244353;
const int modi6=166666668;



int main(){	

	string s;
	cin>>s;

	vector<ll> dp(2020,0);

	//dp[0]=1;

	ll ans=0;

	for(int i=0;i<s.length();++i){
		vector<ll> dp1(2020,0);
		for(int j=0;j<2019;j++){
			dp1[(j*10+(s[i]-'0'))%2019]+=dp[j];
		}
		dp1[s[i]-'0']++;
		ans+=dp1[0];
		dp=dp1;
		
	}

	cout<<ans;
	
	return 0;	
}

Measured memory_bytes: 3752
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

#define ll long long
//typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define revrep(i, n) for(ll i = n-1; i >= 0; i--)
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll Mypow(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}


ll INFL = 1LL << 60;//10^18 = 2^60
int INF = 1 << 30;//10^9
ll MOD  = 1000000007;
//vector<int> dy = {0,0,1,-1};
//vector<int> dx = {1,-1,0,0};



int main(){
  int a, b, c;
  cin >> a >> b >> c;
  set<int> x;
  x.insert(a), x.insert(b), x.insert(c);
  cout << x.size() << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 99999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl
#define Vecpr(K,L1,L2,N) vector<pair<L1,L2>> K(N)
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,R) vector<vector<L>> K(N, vector<L>(M,R))
#define pint pair<int,int>
#define Lower(v,X) lower_bound(v.begin(),v.end(),X)-v.begin();
#define mod 1000000007
#define MAX 5100000
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
   lli A,B,C,L,R,N,M,K,X=0,Y=0,W,H=INF,sum=0,num=0,flag=0;string S,T,O;
   cin >> N >> K;
   Vec(P,int,K,0);
   rep(i,0,K)cin >> P[i];
   rep(i,N,10*N+1){
      A=i;
      while(A){
         B=A%10;
         flag=0;
         rep(i,0,K)if(B==P[i])flag++;
         if(flag)break;
         A/=10;
      }
      if(!flag){
         Out(i);break;
      }
   }
}


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

int q;
int a[50], b[50], c[50], d[50];
int mmax = 0;

void rec(vector<int> v, int n, int m)
{
    int s = v.size();
    if (s == n) {
      int sum = 0;

      for (int i = 0; i < q; i++) {
        if (v[b[i] - 1] - v[a[i] - 1] == c[i] ) {
          sum += d[i];
        }
      }
      mmax = mmax > sum ? mmax : sum;
/*
      cout << "s:" << sum << endl;
      for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
      }
      cout << endl;
      */
      return ;
    }
  
	for (int i = v[s - 1]; i <= m; i++) {
      vector<int> v2 = v;
      v2.push_back(i);
      rec(v2, n, m);
    }
}

int main() {
    int n, m;
    
    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    
    for (int i = 1; i <= m; i++) {
        vector<int> v;
        v.push_back(i);
        rec(v, n, m);
    }
	cout << mmax << endl;
}

Measured memory_bytes: 3600
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	public static int MAXN = 200000;
	public static long MOD = 1000000007;

	static class TaskX {
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int h = in.nextInt();
			int w = in.nextInt();
			int a = in.nextInt();
			int b = in.nextInt();

			long ans = 0;
			for (int i = 0; i < h - a; i++) {
				ans += comb(b - 1 + i, i)*comb(w - b - 1 + h - i - 1, w - b - 1)%MOD;
			}
			ans %= MOD;
			out.println(ans);

		}
	}
	static long[] fact = factorialArray(MAXN, MOD);
	static long[] factInv = factorialInverseArray(MAXN, MOD, inverseArray(MAXN, MOD));
	public static long comb(int n,int r) {
		return fact[n] * factInv[r] % MOD * factInv[n-r] % MOD;
	}

	public static long[] inverseArray(int maxN,long modP) {
		long[] inv = new long[maxN+1];
		inv[1] = 1;
		for(int i=2;i<=maxN;i++) {
			inv[i] = modP - (modP / i) * inv[(int) (modP%i)] % modP;
		}
		return inv;
	}
	public static long[] factorialArray(int maxN,long mod) {
		long[] fact = new long[maxN+1];
		fact[0] = 1 % mod;
		for(int i=1;i<=maxN;i++) {
			fact[i] = fact[i-1] * i % mod;
		}
		return fact;
	}
	public static long[] factorialInverseArray(int maxN,long modP,long[] inverseArray) {
		long[] factInv = new long[maxN+1];
		factInv[0] = 1;
		for(int i=1;i<=maxN;i++) {
			factInv[i] = factInv[i-1] * inverseArray[i] % modP;
		}
		return factInv;
	}

	static class ArrayUtils {
		public static Map<Integer, Integer> getCountMap(int[] array) {
			Map<Integer, Integer> map = new TreeMap<>();
			for (int x : array)
				map.merge(x, 1, Integer::sum);
			return map;
		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}

	}

}


Measured memory_bytes: 25556
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(" ").map(String::toInt)
    val s = readLine()!!
        .split("")
        .let { it.slice(1 until it.size - 1) }
        .map { if (it == "L") -1 else 1 }

    val result = s.countHappy() + 2 * k
    
    println(if(s.lastIndex < result) s.lastIndex else result)
}

fun List<Int>.countHappy(): Int {
    return this.withIndex().fold(0) { count, elm ->
        val indexFront = elm.index + elm.value
        if (0 <= indexFront && indexFront < this.size && this[indexFront] == elm.value) count + 1 else count
    }
}

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

using namespace std;

typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;

int main() {
	int N, H, W;
	cin >> N >> H >> W;
	int ans = 0;
	for(int i = 0; i < N; i++) {
		int A, B;
		cin >> A >> B;
		ans += A >= H && B >= W;
	}
	cout << ans << endl;
}


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

int64_t f (int64_t x, int64_t i) {
    int64_t ans = (int64_t(1) << i) * (x >> (i + 1));
    if (x % (int64_t(1) << (i + 1)) >= (int64_t(1) << i))
        ans += x % (int64_t(1) << (i + 1)) - (int64_t(1) << i) + 1;
    return ans;
}

signed main () {
    int64_t a, b;
    cin >> a >> b;
    int64_t ans = 0;
    for (int64_t i = 0; i < 40; ++i) 
        ans += int64_t(((f(b, i) - f(max(a - 1, int64_t(0)), i)) & 1)) * (int64_t(1) << i);
    cout << ans << '\n';
}


Measured memory_bytes: 256
S = input()
N = len(S)
ans = [0]
x = 0

for i in range(N):
    s = S[i]
    if s == 'A' or s == 'C' or s == 'G' or s == 'T':
        x += 1
        if i == N -1:
            ans.append(x)
    
    else:
        if x != 0:
            ans.append(x)
        x = 0
    
print(max(ans))
    

Measured memory_bytes: 8936
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yn(int o){
    if (o == 0) cout << "No" << endl;
    else cout << "Yes" << endl;
}

int main() {
    int a, b, c, d; cin >> a >> b >> c >> d;
    vector<int> ar(101,0);
    vector<int> al(101,0);
    repp(i,b,a) ar[i] = 1;
    repp(i,d,c) al[i] = 1;
    int ans = 0;
    rep(i,101) ans += ar[i] * al[i];
    cout << ans << endl;
}

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

int main(){
    int n,m,cnt=0,t=0;
    vector<pair<int,int>>lnds;
    cin >> n >> m;
    lnds.resize(m);
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        lnds.at(i) = {b,a};
    }
    sort(lnds.begin(),lnds.end());
    for(int i=0;i<m;i++)
        if(t<=lnds.at(i).second){
            cnt++;
            t=lnds.at(i).first;
        }
    cout << cnt << endl;
}

Measured memory_bytes: 1024
n = int(input())
hoge = []

for i in range(n):
    hoge.append(list(map(int, input().split())))
hoge.sort(key = lambda x: x[1])

total = 0
able = True
for i in hoge:
    total += i[0]
    if i[1]<total:
        able = False

if able:
    print("Yes")
else:
    print("No")

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

#define PB push_back

int main(int argc,char* argv[]){
  int n,q,x,ans=0,i;
  vector<int> vis,vit;

  cin>>n;
  for(i=0;i<n;i++){
    cin>>x;
    vis.PB(x);
  }
  cin>>q;
  for(i=0;i<q;i++){
    cin>>x;
    vit.PB(x);
  }

  sort(vis.begin(),vis.end());sort(vit.begin(),vit.end());

  vector<int>::iterator itvis,itvit;
  itvis=vis.begin();itvit=vit.begin();

  while(itvis!=vis.end() && itvit!=vit.end()){
    if(*itvis==*itvit){
      ans++;
      itvis++;
      itvit++;
    }
    else if(*itvis>*itvit){
      itvit++;
    }
    else if(*itvis<*itvit){
      itvis++;
    }
  }

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

Measured memory_bytes: 1804
n,k=list(map(int,input().split()))

ans=0

if k==(n+1):
  print(1)

else:
  for i in range(k,n+2):
    num=int((i/2*(n+(n-i+1)))-((i-1)*i/2)+1)
    ans+=num
    
  print(ans%(10**9+7))

Measured memory_bytes: 9208
import heapq
N,M = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
heapq.heapify(An)
BC_list = []
for i in range(M):
    BC = list(map(int,input().split(' ')))
    BC_list.append(BC)
BC_list.sort(reverse=True,key=lambda x: x[1])
flag = False
decided_sum = []
for val in BC_list:
    B = val[0]
    C = val[1]
    for i in range(B):
        tmp_min = heapq.heappop(An)
        if tmp_min > C:
            #heapq.heappush(An,tmp_min)
            decided_sum.append(tmp_min)
            flag = True
            break
        decided_sum.append(C)
        if len(An) == 0:
            flag = True
            break
    if flag:
        break
print(sum(decided_sum) + sum(An))

Measured memory_bytes: 102100
package main

import "fmt"

func main() {
	var A, B int

	fmt.Scan(&A, &B)

	if B%2 == 0 {
		switch {
		case A >= 13:
			fmt.Print(B)
		case A >= 6 && A <= 12:
			fmt.Print(B / 2)
		case A <= 5:
			fmt.Print("0")
		}
	}

}


Measured memory_bytes: 1768
import sys
def input(): return sys.stdin.readline().strip()

def main():
    x, y = map(int, input().split())
    if y % 2 == 0 and y // 2 - x >= 0 and 2 * x - y // 2 >= 0:
        print("Yes")
    else:
        print("No")
    

if __name__ == "__main__":
    main()


Measured memory_bytes: 61676
n,m = map(int,input().split())
k = []
s = []
for i in range(m):
    ks = list(map(int,input().split()))
    k.append(ks[0])
    s.append(ks[1:])
p = list(map(int,input().split()))
count = 0
for bit in range(2**n):
    counta = 0
    sw = [False for i in range(n)]
    for i in range(n):
        if bit >> i & 1:
            sw[i] = True
    for i in range(m):
        countb = 0
        for j in s[i]:
            if sw[j-1]:
                countb += 1
        if countb % 2 == p[i]:
            counta+=1
    if counta == m:
        count+=1
print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n);++i)
using namespace std;
using ll = long long; 
using P = pair<int,int>;
using vv = vector<vector<ll> >;
template <class _t> inline bool chmax (_t& a,_t b){if(a<b){a=b;return true;}return false;} template <class _t> inline bool chmin (_t& a,_t b){if(a>b){a=b;return true;}return false;}

const int INF = 2147483647;
const long long inf = 1ll << 60;
const long long mod = 1000000007;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
int main(){
    int a,b,d;cin >> a >> b >> d;
    int ans=0;
    for(int i=a;i<=b;i++){
        if(i%d==0) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll h;cin>>h;
  ll ans=0;
  ll cnt=1;
  while(h>0){
    ans+=cnt;cnt*=2;
    h/=2;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//clock_t start=clock();clock_t end=clock();cout<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef pair<pii,pii> P;
typedef tuple<ll,ll,ll> tl;
typedef pair<double,double> pdd;
typedef vector<vector<ll>> mat;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll mod5=1000000009;
ll inf=1LL<<60;
double pi=3.141592653589793238462643383279L;
double eps=1e-14;
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
#define srep(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
#define mrep(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#define umh unordered_map<ll,ll,custom_hash>
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll c=gcd(a,b);
    return a*b/c;
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
    now%=md;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
ll popcount(ll n){
    ll ret=0;
    ll u=n;
    while(u>0){
        ret+=u%2;
        u/=2;
        
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n;cin>>n;
    rep(i,0,3){
        int u=n%10;
        if(u==7){
            cout<<"Yes"<<endl;
            return 0;
        }
        n/=10;
    }
    cout<<"No"<<endl;
}



Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define REP(i,n) for (int i = 0; i < n; ++ i)
#define FOR(i,a,b) for (int i = a; i <= b; ++ i)
#define FORD(i,b,a) for (int i = b; i >= a; -- i)
#define debug(x) cerr << #x << ": " << x << "\n"
#define task ""
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> li;
typedef vector<int> vi;

const int N = 1000 + 5;
const int M = 2000 + 5;
const ll md = 1e9 + 7;
const int oo = 1e9 + 7;
struct Edge{
	int u, v, c;
	bool inMST;
	bool operator < (Edge oth) {
		return c < oth.c;
	}
} e[M]; 
int n, m, lab[N], rnk[N];
int cntLower, cntEqual, cntUpper;
vector<ii> adj[N];
ll x, mst;

ll Pow(int x) {
	if (x == 0) return 1;
	else {
		ll res = Pow(x / 2);
		res = res * res % md;
		if (x % 2) res = res * 2 % md;
		return res;
	}
}
int root(int u) {
	if (lab[u] == -1) return u;
	else return lab[u] = root(lab[u]);
}
void join(int u, int v) {
	u = root(u), v = root(v);
	if (rnk[u] > rnk[v]) {
		lab[v] = u;
	} else {
		lab[u] = v;
		if (rnk[u] == rnk[v]) rnk[v] ++;
	}
}
int maxEdge(int u, int des, int par) {
	if (u == des) return 0;
	else {
		REP(j, adj[u].size()) {
			ii v = adj[u][j];
			if (v.fi != par) {
				int tmp = maxEdge(v.fi, des, u);
				if (tmp != -1) return max(v.se, tmp);
			}
		}
		return -1;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen(task".inp", "r", stdin);
	//freopen(task".out", "w", stdout);
	cin >> n >> m >> x;
	REP(i, m) {
		cin >> e[i].u >> e[i].v >> e[i].c;
		e[i].inMST = 0;
	}	
	sort(e, e+m);
	memset(lab, -1, sizeof lab);
	REP(i, m) {
		int u = e[i].u, v = e[i].v;
		//cerr << u << " " << v << "\n";
		if (root(u) != root(v)) {
			mst += e[i].c;
			e[i].inMST = 1;
			join(u, v);
			adj[u].pb(mp(v, e[i].c));
			adj[v].pb(mp(u, e[i].c));
			//cerr << u << " " << v << " " << e[i].c << "\n";
		}
	}
	//cerr << "ok\n";
	REP(i, m) if (!e[i].inMST) {
		//cerr << i << "\n";
		ll tmp = mst + e[i].c - maxEdge(e[i].u, e[i].v, -1);
		//cerr << e[i].u << " " << e[i].v << " " << maxEdge(e[i].u, e[i].v, -1) << "\n";
		if (tmp < x) cntLower ++;
		else if (tmp == x) cntEqual ++;
		else cntUpper ++;
	}
	//cerr << cntLower << " " << cntEqual << " " << cntUpper << "\n";
	if (mst > x) cout << 0;
	else if (mst == x) cout << ((Pow(n-1) - 2) * Pow(m-n+1) % md + 2 * (Pow(cntEqual) - 1) * Pow(cntUpper) % md) % md;
	else cout << 2 * (Pow(cntEqual) - 1) % md * Pow(cntUpper) % md;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <chrono>
#include <random>
#include <unordered_map>
#include <cassert>
#pragma GCC optimize("O3")
#pragma comment(linker, "STACK:36777216")
using namespace std;
using i64 = int64_t;
constexpr i64 MOD = 1e9 + 7;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
using vi = vector<i64>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ii = pair<i64, i64>;

int cnt[26];

int main() {
    int h, w;
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            char c;
            cin >> c;
            cnt[c - 'a']++;
        }
    }
    
    if (h % 2 == 0 && w % 2 == 0) {
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 4) {
                cout << "No" << endl;
                return 0;
            }
        }
        cout << "Yes" << endl;
        return 0;
    }
    
    if (h % 2 && w % 2) {
        int odd = 0;
        int two = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                odd++;
                continue;
            }
            if (cnt[i] % 4 == 2) {
                two++;
            }
        }
        if (odd > 1) {
            cout << "No" << endl;
            return 0;
        }
        if (two <= h / 2 + w / 2) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
        return 0;
    }
    
    if (h % 2 == 0 && w % 2) {
        int two = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                cout << "No" << endl;
                return 0;
            }
            if (cnt[i] % 4 == 2) {
                two++;
            }
        }
        if (two <= h / 2) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
        return 0;
    }
    
    assert(h % 2 && w % 2 == 0);
    int two = 0;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] % 2 == 1) {
            cout << "No" << endl;
            return 0;
        }
        if (cnt[i] % 4 == 2) {
            two++;
        }
    }
    if (two <= w / 2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
var
 s,t:string;
 i:longint;
begin
 read(t);
 for i:=1 to length(t) do 
 begin
  if t[i]='0' then s:=s+'0';
  if t[i]='1' then s:=s+'1';
  if t[i]='B' then delete(s,length(s),1);
 end;
write(s);
end.

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <queue>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

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

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

    long long sum = 0;
    for (int i = 0; i < k; i++) {
        sum += li[i];
    }

    cout << sum << endl;
}   

Measured memory_bytes: 3596
class UnionFind:
    __slots__ = ["N", "root"]

    def __init__(self, N):
        self.N = N
        self.root = [-1] * N


    def find(self, x):
        r = x
        while self.root[r] >= 0:
            r = self.root[r]

        while self.root[x] >= 0:
            self.root[x], x = r, self.root[x]

        return r

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.root[y] < self.root[x]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
uf = UnionFind(n)
res = []
for i in range(q):
    t, u, v = map(int, input().split())
    if t:
        res.append(int(uf.same(u, v)))
    else:
        uf.union(u, v)
print("\n".join(map(str, res)))


Measured memory_bytes: 83356
#include <iostream>
using namespace std;
int main(){
	int H,W;
	for(;;){
	cin>>H>>W;
	if(H==0 && W==0){
				break;
			}

	for(int i=0; i<H; i++ ){
		for(int j=0; j<W; j++){	
			if((i+j)%2==0){	
				cout<<"#";
			}else if((i+j)%2==1){
				cout<<".";
			}
		}
		cout<<endl;
	}
	cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 3080
def is_valid? bin
  return false if bin.include? "11"
  true
end

h, w, k = gets.split.map(&:to_i)

transition = Array.new(w + 1) { Array.new(w + 1, 0) }
transition[0][0] = 1 if w == 1
(2 ** (w - 1)).times do |i|
  bin = i.to_s(2)
  if is_valid? bin
    bin = bin.rjust(w - 1, '0')
    (w - 1).times do |k|
      if bin[k] == "1"
        transition[k][k + 1] += 1
        transition[k + 1][k] += 1
      elsif k == 0
        transition[0][0] += 1
      elsif bin[k - 1] == "0"
        transition[k][k] += 1
      end
      transition[w - 1][w - 1] += 1 if bin[k] == "0" && k == w - 2
    end
  end
end

dp = Array.new(h + 1) { Array.new(w + 1, 0) }
dp[0][0] = 1

mod = 1000000007
1.upto (h) do |i|
  w.times do |j|
    dp[i][j] = (dp[i - 1][j - 1] * transition[j - 1][j] + dp[i - 1][j] * transition[j][j] + dp[i - 1][j + 1] * transition[j + 1][j]) % mod
  end
end

p dp[h][k - 1]

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

using namespace std;

int main()
{
    int a;
    scanf("%d", &a);
    int L = a / 100;
    int R = a % 100;
    if (1 <= L && L <= 12)
    {
        if (1 <= R && R <= 12)
            printf("AMBIGUOUS\n");
        else
            printf("MMYY\n");
    }
    else
    {
        if (1 <= R && R <= 12)
            printf("YYMM\n");
        else
            printf("NA\n");
    }
}

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

// Bit Matrix
const int MAX_ROW = 110; // to be set appropriately
const int MAX_COL = 110000; // to be set appropriately
struct BitMatrix {
    int H, W;
    bitset<MAX_COL> val[MAX_ROW];
    BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
    inline bitset<MAX_COL>& operator [] (int i) {return val[i];}
};

// 掃き出し法
void GaussJordan(BitMatrix &A, bool is_extended = false) {
    vector<bool> used(A.H, 0);
    for (int col = 0; col < A.W; ++col) {
        if (is_extended && col == A.W - 1) break;
        int pivot = -1;
        for (int row = 0; row < A.H; ++row) {
            if (used[row]) continue;
            if (A[row][col]) {
                pivot = row;
                break;
            }
        }
        if (pivot == -1) continue;
        for (int row = 0; row < A.H; ++row) {
            if (row != pivot && A[row][col]) A[row] ^= A[pivot];
        }
        used[pivot] = true;
    }
}

const int MD = 60;
int main() {
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    // 方程式を立てる
    long long res = 0;
    BitMatrix B(MD+1, N+1);
    vector<bool> cannot(MD+1, 0);
    for (long long d = MD; d >= 0; --d) {
        // d 桁目が 1 が何個か
        int num = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] & (1LL<<d)) ++num;
        }
        if (num == 0) {
            cannot[d] = 1;
            continue;
        }
        else if (num & 1) {
            cannot[d] = 1;
            res += (1LL<<d);
            continue;
        }

        for (int i = 0; i < N; ++i) {
            if (A[i] & (1LL<<d)) B[MD-d][i] = 1;
        }
        B[MD-d][N] = 1;
    }
    GaussJordan(B, true);

    // 集計
    for (int d = MD; d >= 0; --d) {
        if (cannot[d]) continue;

        // d 行目が (0 0 0 ... 0 | 1) だったらダメ
        bool ok = false;
        for (int i = 0; i < N; ++i) if (B[MD-d][i]) ok = true;
        if (!B[MD-d][N]) ok = true;

        // 結果に 2 × 2^d が寄与
        if (ok) res += (2LL<<d);
    }
    cout << res << endl;
}


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

void color(int v,int d,int c,vector<int> &ans,vector<vector<int>> &edge,vector<int> &visitd){
  if(d<0) return;
  if(visitd[v]>=d){
    return;
  }
  visitd[v]=d;
  if(ans[v]==0) ans[v]=c;
  for(int i=0;i<edge[v].size();i++){
    int to=edge[v][i];
    color(to,d-1,c,ans,edge,visitd);
  }
  return;
}

int main(){
  int n,m;
  cin>>n>>m;
  vector<vector<int>> edge(n);
  for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    a--,b--;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  int q;
  cin>>q;
  vector<int> v(q),d(q),c(q);
  for(int i=0;i<q;i++){
    int vv,dd,cc;
    cin>>vv>>dd>>cc;
    vv--;
    v[i]=vv,d[i]=dd,c[i]=cc;
  }
  vector<int> ans(n,0);
  vector<int> visitd(n,-1);
  for(int i=q-1;i>=0;i--){
    color(v[i],d[i],c[i],ans,edge,visitd);
  }
  for(int i=0;i<n;i++) cout<<ans[i]<<endl;
  return 0;
}


Measured memory_bytes: 8440
N = int(input())

adj = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    adj[-a].append(b)
    adj[-b].append(a)

def calc_dist(K):
    # dist[-i]:頂点Kから頂点iまでの距離
    dist = [-1 for i in range(N)]
    dist[-K] = 0

    # 深さ優先探索（スタック）
    from collections import deque
    stack = deque()
    stack.append(K)

    while stack:
        v = stack.pop()
        for nxt in adj[-v]:
            if dist[-nxt] == -1:
                dist[-nxt] = dist[-v] + 1
                stack.append(nxt)

    return dist

dist1 = calc_dist(1)
distN = calc_dist(N)

Fennec = 0
Snuke = 0
for v in range(N):
    if dist1[-v] <= distN[-v]:
        Fennec += 1
    else:
        Snuke += 1

if Fennec > Snuke:
    print('Fennec')
else:
    print('Snuke')


Measured memory_bytes: 29484
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = map(int, args[1].split())

    ret = 'APPROVED'
    for a in A:
        if a % 2 == 0:
            if a % 3 != 0 and a % 5 != 0:
                ret = 'DENIED'

    return ret


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Measured memory_bytes: 2940
#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int
main()
{
  int A, B;
  cin >> A >> B;
  int sum = A + B;
  if (sum % 2 == 0)
  {
    cout << sum / 2 << endl;
  }
  else
  {
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}


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


using namespace std;

int main(){
	
	int A, B,i;
	int resultA,resultB;
	
	cin>>A; cin>>B;
	
	for(i = 13; i <= 1000; i++){
		resultA = i * 0.08;
		resultB = i * 0.1; 
		if(resultA == A){
			if(resultB == B){
				cout<<i;
				break;
			}
		}
		
	}
	
	if(i > 1000){
		cout<<-1;
	}

	}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long double PI = acos(-1.0);
// cout << fixed << setprecision(14);

set<int> st[26];
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
 
	int D;
	cin >> D;
	rep(i,26){
		st[i].insert(-1);
		st[i].insert(D);
	}
	int c[26];
	int s[D][26];
	int t[D];
	int ok[26];
	rep(i,26) ok[i] = -1;
	rep(i,26) cin >> c[i];
	rep(i,D){
		rep(j,26){
			cin >> s[i][j];
		}
	}
	int num;
	rep(i,D){
		int maxi = -INF;
		rep(k,26){
			int ans = 0;
			ans += s[i][k];
			// ok[t[i]] = i;
			rep(j,26){
				if(j == k) continue;
				ans -= c[j] * (i-ok[j]);
			}
			if(maxi < ans){
				maxi = ans;
				num = k;
			}
		}
		ok[num] = i;
		t[i] = num;
		st[num].insert(i);
	}	
	rep(loop,1000){
		rep(i,D-1){
			int dx = 0;
			int old1 = t[i], old2 = t[i+1];
			// st[_].erase(d[i]);
			auto itr = st[old1].upper_bound(i);
			int W2 = *itr;
			--itr;
			--itr;
			int W1 = *itr; 
			dx -= c[old1] * (i - W1) * (W2 - i);
			auto itr1 = st[old2].upper_bound(i);
			int A2 = *itr1;
			--itr1;
			int A1 = *itr1;
			dx += c[old2] * (i - A1) * (A2 - i);
			// st[q[i]].insert(d[i]);
			dx += s[i][t[i+1]] - s[i][t[i]];

			++i;
			// st[_].erase(d[i]);
			itr = st[old2].upper_bound(i);
			W2 = *itr;
			--itr;
			--itr;
			W1 = *itr;
			dx -= c[old2] * (i - W1) * (W2 - i);
			itr1 = st[old1].upper_bound(i);
			A2 = *itr1;
			--itr1;
			A1 = *itr1;
			dx += c[old1] * (i - A1) * (A2 - i);
			// st[q[i]].insert(d[i]);
			dx += s[i][t[i-1]] - s[i][t[i]];
			--i;
			if(dx > 0){
				t[i] = old2;
				t[i+1] = old1;
			}
		}
	}
	rep(i,D) cout << t[i]+1 << endl;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  
  int count = 0;
  for (int i = a; i <= b; i++) {
    string s = to_string(i);
    if(s[0] == s[4] && s[1] == s[3]) {
      count++;
    }
  }
  cout << count << endl;
}
    

Measured memory_bytes: 256