akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

    int n;
    int A[50];

bool solve(int i, int m)
{
    if(m == 0){
        return true;
    }
    if(i >= n){
        return false;
    }
    bool res = solve(i + 1, m) || solve(i + 1, m - A[i]);
    return res;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }
    int q, m;
    cin >> q;
    for(int i = 0; i < q; i++){
        cin >> m;
        if(solve(0, m)){
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
  ll n;
  string s,t;
  cin >> n;
  cin >> s >> t;
  string out = "";
  for (int i = 0;i < n;i++){
    out = out +  s[i] + t[i];
  }
  cout << out << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  char s[3], t[3];
  int ct=0, i;
  for(i=0; i<3; i++)
    cin >> s[i];
  for(i=0; i<3; i++)
    cin >> t[i];
  for(i=0; i<3; i++)
    if(s[i]==t[i]) ct++;
  cout << ct << endl;
  return 0;
}


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

using namespace std;

const int kMod = 1e9 + 7;

struct AhoCorasick {
  struct Node {
    int link;
    bool bad = false;
    map<char, int> leg;
  };
  vector<Node> T;
  int root = 0, nodes = 1;

  AhoCorasick(int sz) : T(sz) {}

  // Adds a word to trie and returns the end node
  int AddWord(const string &word) {
    int node = root;
    for (auto c : word) {
      auto &nxt = T[node].leg[c];
      if (nxt == 0) nxt = nodes++;
      node = nxt;
    }
    T[node].bad = true;
    return node;
  }

  // Advances from a node with a character (like an automaton)
  int Advance(int node, char chr) {
    while (node != -1 && T[node].leg.count(chr) == 0)
      node = T[node].link;
    if (node == -1) return root;
    return T[node].leg[chr];
  }

  // Builds links
  void BuildLinks() {
    vector<int> Q;
    Q.push_back(root);
    T[root].link = -1;

    for (int i = 0; i < (int)Q.size(); ++i) {
      int node = Q[i];

      for (auto &p : T[node].leg) {
        int vec = p.second;
        char chr = p.first;
        T[vec].link = Advance(T[node].link, chr);
        Q.push_back(vec);
      }
    }
    
    for (int i = 0; i < (int)Q.size(); ++i) {
        if (T[i].link == -1) continue;
        if (T[T[i].link].bad) T[i].bad = true;
    }
  }
};

AhoCorasick aho(1000000);

void Backtrack(vector<int> x, string s) {
    while (x.size() && x.back() == 0) x.pop_back();
    if (x.empty()) {
        // cerr << "FOUND " << s << endl;
        aho.AddWord(s);
    }
    else {
        for (int i = 1; i <= x.back(); ++i) {
            s += i + '0';
            x.back() -= i;
            Backtrack(x, s);
            x.back() += i;
            s.pop_back();
        }    
    }
}

int main() {
    int n, x, y, z; cin >> n >> x >> y >> z;
    Backtrack({z, y, x}, "");
    aho.BuildLinks();

    vector<int> dp(aho.nodes), nxt(aho.nodes);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        fill(nxt.begin(), nxt.end(), 0);
        for (int j = 0; j < aho.nodes; ++j) {
            for (int k = 0; k < 10; ++k) {
                int nj = aho.Advance(j, k + '0');
                if (aho.T[nj].bad) continue;
                nxt[nj] += dp[j];
                if (nxt[nj] >= kMod)
                    nxt[nj] -= kMod;
            }
        }
        dp = nxt;
    }

    int total = 1;
    for (int i = 0; i < n; ++i) {
        total = 10LL * total % kMod;
    }

    for (auto x : dp) {
        total -= x;
        if (total < 0)
            total += kMod;
    }

    cout << total << endl;


    return 0;
}


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

using namespace std;

inline int ctoi(char c) { if(c < '0' || '9' < c) throw invalid_argument("ctoi error"); return c - '0'; }
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for(int i = (int)(k); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

template <typename T>
inline T gcd(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("gcd error: x <= 0 or y <= 0");
	
	if(x < y) swap(x, y);
	T r = x % y;

	while(r != 0){
		x = y;
		y = r;
		r = x % y;
	}

	return y;
}
template <typename T>
inline T lcm(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("lcm error: x <= 0 or y <= 0");

	return x * y / gcd(x, y);
}

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

	int ans = 0;

	rep(i, n){
		int a;
		cin >> a;

		if(i % 2 == 0 && a % 2 == 1) ans++;
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define rep(i, up) for (ll i = 0; i < up; ++i)
#define repp(i, up) for (ll i = 0; i <= up; ++i)
#define rrep(i, lo, up) for (ll i = lo; i < up; ++i)
#define rrepp(i, lo, up) for (ll i = lo; i <= up; ++i)

#define rdi(i) ll i; scanf("%lld", &i)
#define rds(s) string s; cin >> s
#define rdc(c) char c; cin >> c

#define INF 10000000000
#define MOD 1000000007

ll gcd(ll a, ll b)
{
    if (a < b) {
        return gcd(b, a);
    }
    ll r;
    while (r = a % b) {
        a = b;
        b = r;
    }
    return b;
}

int main()
{
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    if ((c + b - 1) / b <= (a + d - 1) / d) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3128
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,n) for(lli i=0;i<n;i++)
#define repb(i,n) for(lli i=n-1;i>=0;i--)
#define pb push_back
#define mp make_pair
#define bg() begin()
#define en() end()
#define ft first
#define sc second
#define vect_lli_it vector<lli>::iterator
#define set_lli_it set<lli>::iterator
#define inf 1e18
#define all(X) X.begin(),X.end()
#define iterate(X) for(it=X.begin();it!=X.end();it++)
#define pii pair<lli,lli>
#define vi vector <lli>
lli combi(lli n,lli k)
{
    lli ans=1;
    k=k>n-k?n-k:k;
    lli j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}
lli gcd(lli a, lli b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
lli findlcm(vector <lli> arr, lli n)
{
    lli ans = arr[0];
    for (lli i = 1; i < n; i++)
        ans = (((arr[i] * ans)) /
                (gcd(arr[i], ans)));

    return ans;
}
lli power(lli x, lli y, lli p)
{
    lli res = 1;
    x = x % p;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
lli gcdExtended(lli a, lli b, lli *x, lli *y);
lli modInverse(lli b, lli m)
{
    lli x, y;
    lli g = gcdExtended(b, m, &x, &y);
    if (g != 1)
        return -1;
    return (x%m + m) % m;
}
lli modDivide(lli a, lli b, lli m)
{
    a = a % m;
    lli inv = modInverse(b, m);
    return (inv * a) % m;
}
lli gcdExtended(lli a, lli b, lli *x, lli *y)
{
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }
    lli x1, y1;
    lli gcd = gcdExtended(b%a, a, &x1, &y1);
    *x = y1 - (b/a) * x1;
    *y = x1;
    return gcd;
}
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli l,r,d;
    cin>>l>>r>>d;
    lli ans=0;
    for(lli i=l;i<=r;i++){
    	if(i%d==0)
    	ans++;
	}
	cout<<ans;
    return 0;
}


Measured memory_bytes: 3652
#include <stdio.h>

#define MOD 1000000007

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

int N, K;
mint dp0[100002];
mint dp1[100002];

int min(int x, int y) {
    return x < y ? x : y;
}

int main() {
    scanf("%d %d", &N, &K);
    dp0[0] = 1;
    for (int i = 0; i < N; i++) {
        int a;
        scanf("%d", &a);
        for (int j = 0; j <= K; j++) {
            dp1[j] = dp0[j];
            dp0[j] = 0;
        }
        for (int j = 0; j <= K; j++) {
            int k = min(j + a + 1, K + 1);
            dp0[j] += dp1[j];
            dp0[k] -= dp1[j];
        }
        for (int j = 0; j <= K; j++) {
            dp0[j + 1] += dp0[j];
        }
    }
    printf("%d\n", dp0[K].n);
    return 0;
}



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

long long oddsolve(long long a){return (a+1)/2 % 2;}
long long solve(long long a){
    if(a % 2== 1)return oddsolve(a);
    else return oddsolve(a+1) ^ (a+1);
}



int main(){
    long long A,B; cin >> A >> B;
    cout << (solve(B) ^solve(A-1)) <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define rev(i,s,e) for(i64 (i) = (s);(i) --> (e);)
#define all(x) x.begin(),x.end()

int main() {
  i64 N;
  cin >> N;
  vector<i64> A(N);
  rep(i,0,N) cin >> A[i];

  multiset<i64> st;
  st.insert(A[0]);
  rep(i,1,N) {
    auto iter = st.lower_bound(A[i]);
    if(iter != st.begin()) {
      --iter;
      st.erase(iter);
    }
    st.insert(A[i]);
  }
  cout << st.size() << endl;
}


Measured memory_bytes: 5760
using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 1; i < 10; i++)
            {
                for(int w=1;w<10;w++)
                {
                    Console.WriteLine(i + "x" + w + "=" + i * w);
                } 
                }
        }
    }
}

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

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

ll MOD = 1e9+7;

class mint{
    ll n;
public:
    mint(ll m = 0){
        n = ((m % MOD) + MOD) % MOD;
    }
    mint operator-() const {
        return mint(-n);
    }
    mint& operator+=(const mint& m){
        n += m.n;
        if(n >= MOD) n -= MOD;
        return *this;
    }
    mint& operator-=(const mint& m){
        n += MOD - m.n;
        if(n >= MOD) n -= MOD;
        return *this;
    }
    mint& operator*=(const  mint& m){
        n *= m.n;
        n %= MOD;
        return *this;
    }
    mint operator+(const mint& m) const{
        mint res(*this);
        res += m;
        return res;
    }
    mint operator-(const mint& m) const{
        mint res(*this);
        res -= m;
        return res;
    }
    mint operator*(const mint& m) const{
        mint res(*this);
        res *= m;
        return res;
    }
    mint pow(ll t) const{
        if(t == 0) return mint(1);
        mint m = pow(t>>1);
        m *= m;
        if(t & 1 == 1) m *= *this;
        return m;
    }
    // for prime modulo
    mint inv() const{
        return pow(MOD-2);
    }
    mint& operator/=(const mint& m){
        (*this) *= m.inv();
        n %= MOD;
        return *this;
    }
    mint operator/(const mint& m) const{
        mint res(*this);
        res /= m;
        return res;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.n;
        return os;
    }
};

string s;
mint dp[200000][5];

int main(){
    cin >> s;
    dp[0][0] = mint(1);
    for(int i=0;i<s.size();i++){
        if(s[i] == '?'){
            for(int j=0;j<4;j++){
                dp[i+1][j] += dp[i][j] * mint(3);
                dp[i+1][j+1] += dp[i][j];
            }
        }else{
            for(int j=0;j<4;j++){
                dp[i+1][j] += dp[i][j];
            }
            dp[i+1][s[i]-'A'+1] += dp[i+1][s[i]-'A'];
        }
    }
    cout << dp[s.size()][3] << endl;
    return 0;
}

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string a, b;
    cin >> a >> b;
    a += a;
    if (a.find(b) != string::npos) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

}



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

int main(){
    char c[3][3];
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin >> c[i][j];
        }
    }
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(i==j){
                cout << c[i][j];
            }
        }
    }
    cout << "\n";
    return 0;
}

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

if n%2:
  for i in range(1, m+1):
    print(i, n-i)
else:
  for i in range(1, m+1):
    if 2*i >= n/2:
      print(i, n-i-1)
    else:
      print(i, n-i)

Measured memory_bytes: 9276
// May this submission get accepted!

#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define STEP(i, is, ie, step) for (long long i=(is), i##_end=(ie), i##_step = (step); i<=i##_end; i+=i##_step)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) do { cerr << "[DEBUG] " #q ": ["; REP(i, (q).size()) { cerr << (q)[i] << (i == i_len-1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; } while (false)
template<class T> T gcd(T a, T b) { if (a < b) std::swap(a, b); while (b) std::swap(a %= b, b); return a; }
template<class T> T lcm(const T a, const T b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
#define DANCE_ long
#define ROBOT_ unsigned
#define HUMAN_ signed
#define CHOKUDAI_ const
using  ll = DANCE_ HUMAN_ DANCE_;
using ull = DANCE_ ROBOT_ DANCE_;
using cll = DANCE_ DANCE_ CHOKUDAI_;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    // インタラクティブ問題では除去した方がいいかも
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll a, b; cin >> a >> b;

    cout << (a < 10 && b < 10 ? a * b : -1) << endl;
    
}

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

int main()
{
	int w,h,x,y,r;
	cin >> w >> h >> x >> y >> r;
	if (x - r >= 0 && x + r <= w && y - r >= 0 && y + r <= h)
		cout << "Yes" << endl;
	else cout << "No" << endl;
    return 0;
}




Measured memory_bytes: 3100
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N := ReadInt64()
	fmt.Println(solve(N))
}

func solve(N int64) string {
	as := helper(N)
	// // first
	// ans := itoa(as[0])
	// // rest
	ans := ""
	for _, a := range as {
		ans = itoa(a) + ans
	}
	return ans
}

func helper(N int64) []int {
	if N == 0 {
		return []int{0}
	}
	vs := []int{}
	for N > 0 {
		vs = append(vs, int(N%26))
		N -= 1
		N /= 26
		if N == 0 {
			break
		}
	}
	return vs
}

func itoa(i int) string {
	i = (i + 26 - 1) % 26
	return string([]byte{byte(i) + 'a'})
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt64() (i int64) { Scan(&i); return }


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

int a, b, c;

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

    if (a == b) {
        cout << c << endl;
    } else if (b == c) {
        cout << a << endl;
    } else if (c == a) {
        cout << b << endl;
    }
}

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

#define ll long long
#define INF_LL 1LL << 60
#define INF 99999999
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

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; }


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

    if( A == B ) cout << "Draw" << endl;
    else if( A < B )
    {
        if( A == 1 && B == 13 ) cout << "Alice" << endl;
        else cout << "Bob" << endl;
    }
    else
    {
        if( A == 13 && B == 1 ) cout << "Bob" << endl;
        else cout << "Alice" << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#define BurstStream ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;

int main()
{
    BurstStream
    long long x, y;
    while (cin >> x >> y)
    {
        long long n = y / x, i = 1, l = 0;
        while (i <= n)
        {
            l++;
            i *= 2;
        }
        cout << l << '\n';
    }
    return 0;
}


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

using s64 = long long;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  s64 answer = numeric_limits<s64>::max();
  answer = min(answer, (s64)(a & 1) * b * c);
  answer = min(answer, (s64)(b & 1) * a * c);
  answer = min(answer, (s64)(c & 1) * a * b);
  cout << answer << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <math.h> // sqrt
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <iomanip> // setprecision
#include <bitset> // bitset
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<long long>;
using pii = pair<int, int>;
using psi = pair<string, int>;

int main() {
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    int ans = A * X + B * Y;
    int N = max(X, Y);
    for (int i = 1; i <= N; i++) {
        int sum = A * max((X - i), 0) + B * max((Y - i), 0) + C * i * 2;
        ans = min(ans, sum);
    }
    cout << ans << endl;
}


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

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

int main(){
  int n; cin >> n;
  int S[n];
  rep(i, n) cin >> S[i];
  int q; cin >> q;
  int T[q];
  rep(i, q) cin >> T[i];
  //ここまで入力

  int count = 0;
  rep(i, q)
    if(S[lower_bound(S, S+n, T[i])-S] == T[i])
      count++;
  
  cout << count << endl;

  return 0;
}



Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <utility>
using namespace std;
 
int main() {
    int n, d, ans = 0;
    double sum;
    cin >> n >> d;
    int x[n][d];
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < d; ++j) {
            cin >> x[i][j];
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int ii = i+1; ii < n; ++ii) {
            sum = 0;
            for(int j = 0; j < d; ++j) {
                sum += pow(x[i][j]-x[ii][j], 2);
            }
            sum = pow(sum, 0.5);
            if(ceil(sum) == floor(sum)) ans++;
        }

    }
    cout << ans << '\n';
}


Measured memory_bytes: 384
#include <cstdio>

int N, X, T;

int main() {
  scanf("%d %d %d", &N, &X, &T);

  if (N % X == 0) {
    printf("%d\n", N / X * T);
  } else {
    printf("%d\n", (N / X + 1) * T);
  }
}


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

"""
input:
5
5
1
3
2
4

or

3
1
1
1

output:
3

or

1
"""

import sys
from bisect import bisect_left


def solve():
    dis_rec = [float('inf')] * array_length
    dis_rec[0] = array[0]
    length = 1
 
    for ele in array:
        if dis_rec[length - 1] < ele:
            dis_rec[length] = ele
            length += 1
        else:
            position = bisect_left(dis_rec, ele)
            dis_rec[position] = ele

    return length


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1:]))
    print(solve())

Measured memory_bytes: 19480
import collections
N=int(input())
S=[list(input()) for i in range(N)]
x=[]
ans=0
for i in S:
  a=sorted(i)
  a="".join(a)
  x.append(a)
x=collections.Counter(x)
for i in list(x.values()):
  ans+=i*(i-1)/2
print(int(ans))
  

Measured memory_bytes: 41116
import datetime
from sys import stdin
h1, m1, h2, m2, k = [int(x) for x in stdin.readline().rstrip().split()]

d1 = datetime.datetime(year=2018, month=1, day=7, hour=h1, minute=m1, second=0, microsecond=0)
d2 = datetime.datetime(year=2018, month=1, day=7, hour=h2, minute=m2, second=0, microsecond=0)

delta = d2 - d1

dt2 = delta.seconds / 60

dt2 -= k

if dt2 < 0 :
	dt2 = 0

print(int(dt2))

Measured memory_bytes: 63808
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin>>n;
  set<int> s;
  vector<int> vec(n, 0);
  for(int i = 0; i < n; ++i)cin>>vec[i];
  for(int i = 0; i < n; ++i)s.insert(vec[i]);
  if(s.size() == n){
    cout<<"YES"<<endl;
  }
  else{
    cout<<"NO"<<endl;
  }
  return 0;
}


Measured memory_bytes: 10368
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    A, B, C = [int(a) for a in input().split()]
    # A = [int(a) for a in input().split()]
    K = int(input())
    # A = [int(a) for a in input().split()]
    # T1, T2, T3 = [int(a) for a in input().split()]
    c = 0
    while A >= B:
        B *= 2
        c += 1
    while B >= C:
        C *= 2
        c += 1
    if c <= K:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()


Measured memory_bytes: 74412
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    int n;

    while (cin >> n, n) {
        int map[15][15];
        int x, y;
        int num = 0;

        for (int i = 0; i < 15; i++)
            for (int j = 0; j < 15; j++) 
                map[i][j] = 0;

        x = n / 2;
        y = x + 1;
        map[y][x] = ++num;

        while (num < n * n) {
            bool right = true;
            
            while (true) {
                if (right) 
                    x++;
                else 
                    x--;
                y++;
                
                if (y == n) 
                    y = 0;
                if (x == n)
                    x = 0;
                else if (x == -1)
                    x = n - 1;

                if (map[y][x] != 0) {
                    right = false;
                    continue;
                }
                else {
                    map[y][x] = ++num;
                    break;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                cout << std::setw(4) << std::right << map[i][j];
            cout << endl;
        }
                
    }

    return 0;
}

Measured memory_bytes: 1172
#include <stdio.h>
 
int main()
{
  int a,b,c;
  
  scanf("%d %d %d",&a,&b,&c);
  
  if(a==5&&b==5&c==7||a==5&&b==7&c==5||a==7&&b==5&c==5)
  {
	printf("YES\n");
  }
  else{
    printf("NO\n");
  }
}

Measured memory_bytes: 128
N = int(input())
#print(N)
max_cnt = 0
max_num = 1
for n in range(1, N+1, 1):
  #print("n", n)
  orig_n = n
  cnt = 0
  while True: 
    if n % 2 == 0:
      #print(n)
      n /= 2
      cnt += 1
    else:
      if cnt > max_cnt:
        max_cnt = cnt
        max_num = orig_n
        #print("max_num", max_num)
      break

print(max_num)

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

int main(){
	char s;
  	cin>>s;
  
  	if(s=='a'|| s=='i' || s=='u' ||s=='e' ||s=='o'){
    	cout<<"vowel"<<endl;
    }else{
    	cout<<"consonant"<<endl;
    }
}    

Measured memory_bytes: 256
def f(S):
    if S=="R":
        return 1
    else:
        return -1

S=input()
N=len(S)
K=334
L=list(map(f,S))

A=[[0]*N for _ in range(K)]

for i in range(N):
    A[0][i]=i+L[i]

for k in range(1,K):
    for x in range(N):
        A[k][x]=A[k-1][A[k-1][x]]

Z=[0]*(N)
for k in range(N):
    P=10**100
    a=k
    i=0
    while P>0:
        if P%2:
            a=A[i][a]
        i+=1
        P>>=1
    Z[a]+=1

print(" ".join(map(str,Z)))


Measured memory_bytes: 345740
#include <bits/stdc++.h>
using namespace std;
char s[105];
int n;
int main(){
    scanf("%d",&n);
    scanf("%s",s);
    if(n%2==1){
        printf("No\n");
        return 0;
    }
    for(int i=0;i<n/2;i++){
        if(s[i]!=s[i+n/2]){
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}

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

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


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

    if (s.size() < 4) {
        cout << "No" << endl;
        return 0;
    }

    string yaki;
    REP(i,4) {
        string ss{s[i]};
        yaki += ss;
    }

    auto ans = yaki == "YAKI" ? "Yes" : "No";
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
H,W,N = map(int,input().split())
B = set([])
for i in range(N):
  a,b = map(int,input().split())
  a-=1;b-=1
  B.add((a,b))
#print(B)
BB = list(B)
ans = [0 for _ in range(10)]
for i in range(N):
  cnt = 0; temp = 0
  x,y = BB[i]
  #print(x,y)
  for sx in range(max(0,x-2),min(x,H-3)+1):
    for sy in range(max(0,y-2),min(y,W-3)+1):
      temp = 0
      for p in range(3):
        for q in range(3):
          if (sx+p,sy+q) in B:
            temp += 1
      #print(sx,sy,temp)
      ans[temp] += 1
for i in range(1,10):
  ans[i] = ans[i]//i
ans[0] = (H-2)*(W-2)-sum(ans[1:])
for t in ans:
  print(t)
        

Measured memory_bytes: 89944
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 	int a, b, count=0;
 	int n1,n2,n3,n4;
 	cin >> a >> b;

 	for(int i=a;i<=b;i++){
 		n1 = i / 10000;
 		n2 = i % 10000 / 1000;
 		n3 = i % 100 / 10;
 		n4 = i % 10;
 		if(n1==n4 && n2==n3)
 			count += 1;
 	}
 	cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#define int long long
using namespace std;
signed main() {
	int N, K;
	cin >> N >> K;
	int A = 0;

	vector<int>h(N);
	for (int i = 0; i < N; i++) {
		cin >> h.at(i);
		if (h.at(i) >= K) {
			A++;
		}
	}
	cout << A << endl;

}

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

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
// #define int long long
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000               // 2e9
#define LLINF 2000000000000000000ll  // 2e18 (llmax:9e18)
#define fi first
#define sec second
#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define dmp(x) cerr << #x << ": " << x << endl;

template <class T>
void chmin(T &a, const T &b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T &a, const T &b) {
  if (a < b) a = b;
}

template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
vector<T> vect(int len, T elem) {
  return vector<T>(len, elem);
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.fi << ',' << p.sec;
  return os;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.fi >> p.sec;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) {
    os << vec[i];
    if (i + 1 < vec.size()) os << ' ';
  }
  return os;
}
template <class T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) is >> vec[i];
  return is;
}
void fastio() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
}

void solve() {
  int N, P;
  cin >> N >> P;
  string s;
  cin >> s;
  vector<ll> dp(P, 0ll);
  vector<int> ten(N);
  ten[0] = 1;
  for (int i = 1; i < N; i++) ten[i] = (ten[i - 1] * 10) % P;
  int start = 0;
  ll ans = 0ll;
  if (P == 2) {
    for (int i = 0; i < s.size(); i++) {
      int d = (int)(s[i] - '0');
      if (d % 2 == 0) ans += i + 1;
    }
    cout << ans << endl;
    return;
  }
  if (P == 5) {
    for (int i = 0; i < s.size(); i++) {
      if (s[i] == '0' || s[i] == '5') ans += i + 1;
    }
    cout << ans << endl;
    return;
  }
  reverse(all(s));
  for (int i = 0; i < s.size(); i++) {
    int digit = (int)(s[i] - '0');
    int d = (digit * ten[i]) % P;
    start = ((start - d) % P + P) % P;
    dp[(start + d) % P]++;
    ans += dp[start];
    // dmp(dp);
    // dmp(start);
    // dmp(ans);
  }
  cout << ans << endl;
  return;
}

signed main() {
  fastio();
  solve();
  // int t; cin >> t; while(t--)solve();
  return 0;
}


Measured memory_bytes: 1428
# coding:utf-8

def main():
    N = int(input())
    mountain = input().split()
    #print(mountain)
    ans = 0
    mountain_max = -1
    for i in range(N):
        if mountain_max <= int(mountain[i]):
            mountain_max = int(mountain[i])
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
// 数直線と N 個のコマを用いて 1 人でゲームを行います。
// はじめ、これらのコマをそれぞれ好きな整数座標に置きます。
// このとき、同じ座標に複数のコマを置いても構いません。
// 以下の移動を繰り返して、座標 X1,X2,...,XM の M 個の地点全てをいずれかのコマで訪れることが目的です。
// 移動: コマを 1 つ選び、そのコマの座標を x とする。そのコマを座標 x+1 もしくは座標 x−1 に移動する。
// ただし、最初にコマを置いた座標はその時点で訪れたとみなします。
// 目的を達成するまでに移動を行う回数の最小値を求めてください。

// https://atcoder.jp/contests/abc117/tasks/abc117_c

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main()
{
    // さぁ！問題を解くわよ！
    // はい！


    int N, M;
    cin >> N >> M;

    // vector をお使いになられたら？
    // 不勉強でございました
    vector<int> X(M);
    for (auto& x : X) {
        cin >> x;
    }
    // さて、次はどういたしますの？
    // まずはソートするのがよくてよ

    std::sort(X.begin(), X.end());

    // int sum = 0;
    // for (int i = 0; i < N - 1, i++) {
    //     sum += X[i + 1] - X[i] - 1;
    // }
    // cout << sum;

    // これでどうかしら？ (髪をかき上げながらパーティクルが出る)
    // 例よ！ 1, 2, 10, 12, 14 だったとしたら、
    // (1, 2), (10, 12, 14) にわけたいわね。
    // なぜかって？ このグループにわける、ということは 2 ~ 10 はいかなくてよい、ということよ。
    // そうよ
    vector<int> diffs;
    for (int i = 0; i < M-1; i++) {
        diffs.push_back(X[i + 1] - X[i]);
    }

    sort(diffs.begin(), diffs.end(), [](int l, int r) { return l > r; });

    int ret = accumulate(diffs.begin(), diffs.end(), 0);
    for (int i = 0; i < N-1 && i < diffs.size(); i++) {
        ret -= diffs[i];
    }

    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 1276
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);};};
const int MOD = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<62;



int main(void) {
    int n,a;
    cin>>n>>a;
    int x[n];
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    vector<vector<vector<ll> > > dp(n+1,vector<vector<ll> >(n+1,vector<ll>(5000,0)));
    
    dp[0][0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<5000;k++){
                dp[i+1][j][k]+=dp[i][j][k];
                if(k+x[i]<5000){
                    dp[i+1][j+1][k+x[i]]+=dp[i][j][k];
                }
            }
        }
    }
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<5000;j++){
    //         cout<<dp[n][i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=dp[n][i][a*i];
    }
    fin(ans);

}



Measured memory_bytes: 103936
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){

int n,w;
cin>>n>>w;
vector<int> weight(n) , value(n);

for(int i=0;i<n;i++){
	cin>>weight[i]>>value[i];
}

ll dp[n+1][w+1];
memset(dp, 0 ,sizeof(dp));

for(int i=1;i<=n;i++){
	ll cn = weight[i-1];
	for(int wt =1 ;wt<=w;wt++){
         if(wt>=cn){
         	dp[i][wt] = max( value[i-1]+ dp[i-1][wt-cn] , dp[i-1][wt]  );
         }
         else{
         	dp[i][wt] = dp[i-1][wt];
         }
	}
}
cout<<dp[n][w];

}

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

int main(){
	int n;
	cin >> n;
	vector<char> color(n);
	for(int i=0;i<n;++i) cin >> color[i];
	sort(color.begin(),color.end());
	int cnt=0;
	char temp=0;
	for(auto i:color){
		if(temp!=i){
			temp=i;
			cnt++;
		}
	}
	if(cnt==3) cout << "Three" << endl;
	if(cnt==4) cout << "Four" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int N, K, A, B;
    int now = 1;
    cin >> N >> K;
    for (int i = 0; i < N;i++){
        A = now * 2;
        B = now + K;
        if (A<=B)
            now = A;
        else
            now = B;
    }
    cout << now << endl;
}

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

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

    string s;
    int diff = 'A' - 'a';

    cout << char(a[0]+diff) << char(b[0]+diff) << char(c[0]+diff) << endl;
}

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

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

  int amount = 1000;

  while (amount < n) {
    amount += 1000;
  }

  cout << amount - n << endl;

  return 0;
}


Measured memory_bytes: 3668
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#define _GLIBCXX_DEBUG // check []
#define DIVISOR 1000000007

using namespace std;
typedef pair<int,int> pii;
typedef pair<int64_t, int64_t> pII;

template<typename T>
void cins(vector<T>& arr) { for(T& e: arr) cin >> e; }

#ifdef DEBUG
#define debug(fmt, ...) \
    printf("[debug: %s] " fmt, __func__, __VA_ARGS__)
#define ps(arr) \
    debug("size %ld: ", arr.size()); \
    for(auto e: arr) cout << e << " "; \
    cout << endl;
#else
#define debug(fmt, ...)
#define ps(arr)
#endif

int64_t combi2(int n) {
    if(n < 2) return 0;
    int64_t ans = 1;
    ans *= n;
    ans *= (n-1);
    return ans/2;
}

int main(void) {
    int num;
    cin >> num;
    vector<int> arr(num);
    cins(arr);
    vector<int> map(num+1);
    for(int i = 0; i < num; i++) {
        map[arr[i]]++;
    }

    int64_t sum = 0;
    for(int i = 1; i <= num; i++) {
        int cnt = map[i];
        sum += combi2(cnt);
    }

    for(int i = 0; i < num; i++) {
        int64_t res = sum;
        int cnt = map[arr[i]];
        res = res - combi2(cnt) + combi2(cnt-1);
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 4800
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
	if(a%b==0)
		return b;
	else
		return gcd(b,a%b);
}
int main()
{
	set<int> a,b;
	int n,x,k=0,i,ans=1;
	cin>>n;
	for(i=0;i<n;i++)
	{
		b.clear();
		swap(a,b);
		cin>>x;
		for(set<int>::iterator it=b.begin();it!=b.end();it++)
			a.insert(gcd(*it,x));
		a.insert(k);
		k=gcd(k,x);
	}
	for(set<int>::iterator it=a.begin();it!=a.end();it++)
		ans=max(ans,*it);
	cout<<ans<<endl;
}

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

int n, m;
ll a[MAX];

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    ll ans = 0;
    for(int i = 2; i <= n; i++){
        ans = max(ans, a[i]-a[i-1]);
    }
    ans = max(ans, a[1]+m-a[n]);
    cout << m-ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional> //operator[]
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

const int MAX = 10010010;
const ll MOD = 1000000007;

ll fac[MAX],finv[MAX],inv[MAX];
void COMinit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i % MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i) % MOD;
        finv[i]=finv[i-1]*inv[i] % MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0 || k<0) return 0;
    return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;
}
signed main(){
    COMinit();
    int h,w,a,b; cin >> h >> w >> a >> b;
    ll ans=0;
    rep(i,h-a){
        ll res=(COM(b+i-1,b-1)*COM(w-b-1+h-i-1,w-b-1))%MOD;
        ans+=res;
        ans%=MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 234880
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

void mark(vvi &a, vi const &b) {
    for_each(a.begin(), a.end(), [&](auto &r){
        for_each(r.begin(), r.end(), [&](auto &x){
            if (find(b.begin(), b.end(), x) != b.end()) x = 0;
        });
    });
}

bool check(vvi const &a) {
    return (!a[0][0] && !a[0][1] && !a[0][2])
        || (!a[1][0] && !a[1][1] && !a[1][2])
        || (!a[2][0] && !a[2][1] && !a[2][2])
        || (!a[0][0] && !a[1][0] && !a[2][0])
        || (!a[0][1] && !a[1][1] && !a[2][1])
        || (!a[0][2] && !a[1][2] && !a[2][2])
        || (!a[0][0] && !a[1][1] && !a[2][2])
        || (!a[0][2] && !a[1][1] && !a[2][0]);
}

int main() {
    vvi a(3, vi(3));
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            cin >> a[i][j];

    int N; cin >> N;
    vi b(N);
    copy_n(istream_iterator<int>(cin), N, b.begin());

    mark(a, b);
    cout << (check(a) ? "Yes"s : "No"s) << endl;

    return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
SC = [list(map(int, input().split())) for _ in range(M)]

def check(string):
    for s, c in SC:
        if string[s - 1] != str(c):
            return False
    return True 

if N == 1:
    for i in range(10 ** 1):
        if check(str(i)):
            print (i)
            exit()
    print (-1)
    exit()
else:
    for i in range(10 ** (N - 1), 10 ** (N)):
        if check(str(i)):
            print (i)
            exit()
    print (-1)
    exit()
       

Measured memory_bytes: 3064
/*  HARD WORK FOREVER PAYS  */
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define turbo(){	\
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL); \
}
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int main()
{
	turbo();
	string s;
	cin>>s;
	ll cnt=0,sz=s.size(),j=0,i;
	for(i=0;i<sz;i++){
		if(s[i]=='B') j++;
		else cnt+=j;
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 720
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll  pair <long long,long long>
#define ss second
#define ff first
#define inf 9223372036854775807
#define maa 1000000007
#define ld long double
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bug(x) cout << #x <<": " << x << '\n';
const ll N=10001 ;
ll  power(ll  i,ll  j)
{
    if(j==0)
    return 1 ;
    ll t=power(i,j/2)%maa ;
    if(j%2==0)
    return (t%maa*t%maa)%maa ;
    else
    return ((t%maa*t%maa)%maa*(i%maa)%maa)%maa ;
}
int main()
{
   fast ;
   ll tests=1 ;
  // cin>>tests ;
   for(ll testcase=1;testcase<=tests;testcase++)
   {
      ///cout<<"Case #"<<testcase<<": " ;
      ///Read,Think ans Test Properly,then code
      ///Try to avoid using print statements debug on your own

     ll h,w ;
     cin>>h>>w ;

     ll ans=(h*w)/2 ;
     ll x=h*w ;
     if(x%2==1)
        ans++ ;

     if(h==1||w==1)
        ans=1 ;


     cout<<ans ;



   }
}
/// ans ->for answer
/// cur ->for local answer
/// level ->for depth in tree
/// v -> adjacency matrix
/// r -> array
/// s ->string



Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int> p[210000];
int ret[210000];
int ans[210000];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<c;i++){
		int s,t;
		scanf("%d%d",&s,&t);
		s--;t--;
		p[i]=make_pair(s,t);
	}
	std::sort(p,p+c);
	for(int i=0;i<b;i++){
		ret[i]=i;
	}
	for(int i=0;i<c;i++){
		int s=p[i].first;
		int t=p[i].second;
		int Lnum=t+1+(s%(2*b));
		int Rnum=t-(s%(2*b));
		if(Lnum>=b)Lnum=b-1-(Lnum-b);
		if(Lnum<0)Lnum=-Lnum-1;
		if(Rnum<0)Rnum=-Rnum-1;
		if(Rnum>=b)Rnum=b-1-(Rnum-b);
		swap(ret[Lnum],ret[Rnum]);
	}
	for(int i=0;i<b;i++){
		int s=a;
		int t=i;
		if((a+i)%2==0){
			int Rnum=t-(s%(2*b));
			if(Rnum<0)Rnum=-Rnum-1;
			if(Rnum>=b)Rnum=b-1-(Rnum-b);
			ans[ret[Rnum]]=i+1;
		}else{
			int Lnum=t+(s%(2*b));
			if(Lnum>=b)Lnum=b-1-(Lnum-b);
			if(Lnum<0)Lnum=-Lnum-1;
			ans[ret[Lnum]]=i+1;
		}
	}
	for(int i=0;i<b;i++)printf("%d\n",ans[i]);
}

Measured memory_bytes: 4232
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long n;
  cin >> n;
  vector<long> v(n, 0);
  for(int i = 0; i < n; i++){
    long k;
    cin >> k;
    v[k]++;
  }
  int s = 1;
  if(n%2 == 1) s = 0;
  for(int i = s; i < n; i+=2){
    if(i == 0 && v[i] == 1) continue;
    if(v[i] != 2){
      cout << 0 << endl;
      return 0;
    }
  }
  long long res = 1LL;
  for(int i = 0; i < n/2; i++){
    res = res*2%1000000007;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 1024
wdays = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
loop do
	xs = gets.split.map{|v| v.to_i}
	if xs[0] == 0 && xs[1] == 0 then break; end
	puts wdays[Time.new(2004, xs[0], xs[1]).wday]
end

Measured memory_bytes: 6096
let n = Scanf.scanf " %d" (+) 0
let a_s = Array.init n @@ fun i -> Scanf.scanf " %d" @@ fun a -> a, i + 1
let _ = Array.(sort compare a_s; iteri (fun i (_, j) -> Printf.printf (if i = 0 then "%d" else " %d") j) a_s; print_newline ())

Measured memory_bytes: 7424
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define inf 1000000007
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define mt make_tuple

int n;
ll d[303][303], sum=0;
bool ans;


int main(){
cin >> n;
rep(i, 1, n){
rep(j,1,n){
cin >> d[i][j];
sum+=d[i][j];
}
}

rep(k, 1, n){
rep(i, 1, n){
rep(j, 1, n){
if(d[i][j]>d[i][k]+d[k][j])ans=true;
}
}
}
if(ans)return 0*printf("%d", -1);

sum=0;

rep(i, 1, n){
rep(j, 1, n){
ans=false;
rep(k, 1, n){
if(d[i][k]+d[k][j]==d[i][j] && i!=k && j !=k)ans=true;
}
if(!ans)sum+=d[i][j];
}
}



cout << sum/2 << endl;

return 0;}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int n,a[400001],b[400001],ta[400001],tb[400001],l=1,r=1;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),ta[a[i]]++;
	for(int i=1;i<=n;i++)scanf("%d",&b[i]),tb[b[i]]++;
	for(int i=1;i<=n;i++)if(ta[i]+tb[i]>n)puts("No"),exit(0);
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=tb[i];j++)
		{
			while(b[l])++l;
			while(a[r]<=a[l]&&r<=n)++r;
			while(b[r])++r;
			if(a[l]!=i)b[l++]=i;
			else b[r++]=i;
		}
	}
	l=1;
	for(int i=n+1;b[i];i++)
	{
		while(b[l])++l;
		if(a[l]!=b[i])a[l]=b[i];
		else 
		{
			while(a[r=(rand()%n+1)]==b[i]||b[r]==a[l]);
			b[l]=b[r],b[r]=b[i];
		}
	}
	puts("Yes");
	for(int i=1;i<=n;i++)printf("%d ",b[i]);
	return 0;
}


Measured memory_bytes: 7552