akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  ll n=3;
  ll a[n];
  rep(i,n) R a[i];
  sort(a,a+n);
  ll k;
  R k;
  rep(i,k) a[2]*=2;
  ll ans=0;
  rep(i,n) ans+=a[i];
  pr(ans);
}

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


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <map>
#include <vector>
#include <string>
#include <vector>
#include <cassert>
#include <cmath>
#include <cctype>
#include <queue>
#include <algorithm>
#include <memory>
#include <memory.h>

using namespace std;

int main(){
	int a, b, c, d;
	while(cin >> a >> b >> c >> d){
		int sum = a + b + c + d;
		cout << sum / 60 << endl;
		cout << sum % 60 << endl;
	}
	return 0;
}

Measured memory_bytes: 592
#include <iostream>
#include <stack>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <map>

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

int main()
{
    int x, last = 0;
    cin >> x;

    for (int i = x; i > 0; i--)
    {
        for (int j = 1; j < 1000; j++)
        {
            for (int k = 2; k < 1000; k++)
            {
                if (pow(j, k) == i)
                {
                    cout << i << endl;
                    return 0;
                }
                if (pow(j, k) > i) break;
            }
        }
    }
    return 0;
}

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

using namespace std;

int w, h;
string field[50];
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

bool isIn(int x, int y){
     return 0 <= x && x < h && 0 <= y && y < w;
}

int check(int x, int y){
    bool used[50][50];
    for(int i=0; i < 50; i++) for(int j=0; j< 50; j++) used[i][j] = false;
    int result = 0;

    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
    while(!q.empty()){
        pair<int, int> p = q.front(); q.pop();
        if(used[p.first][p.second]) continue;
        used[p.first][p.second] = true;
        for(int i=0; i< 4; i++){
            int nx = p.first+dx[i], ny = p.second+dy[i];
            if(!isIn(nx, ny)) continue;
            if(field[nx][ny] != '.'){
                if(result == 0){
                    if(field[nx][ny] == 'W') result = 1;
                    else result = 2;
                }
                else {
                    if(result == 2 && field[nx][ny] == 'W') return -1;
                    else if(result == 1 && field[nx][ny] == 'B') return -1;
                }
            } else {
                q.push(make_pair(nx, ny));
            }
        }
    }
    return result;
}

int main(){
    while(cin >> w >> h, w+h){
        for(int i=0; i< h; i++) cin >> field[i];

        int a = 0, b = 0;
        for(int i=0; i < h; i++){
            for(int j=0; j < w; j++){
                if(field[i][j] == '.'){
                    int r = check(i, j);
                    if(r == 1) a++;
                    else if(r == 2) b++;
                }
            }
        }
        cout << b << " " << a << endl;
    }
}

Measured memory_bytes: 1240
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*200001
C=[]
p=0
for i in A:
  B[i]+=1
cnt=0
for i in range(N+1):
  if B[i]!=0:
    cnt+=1
    C.append(B[i])
C.sort()
if K>=cnt:
  print(0)
else:
  j=0
  while K<cnt:
    p=p+C[j]
    cnt=cnt-1
    j=j+1
  print(p)

Measured memory_bytes: 24996
#include <iostream>

using namespace std;

int main()
{
    int a,b;
    cin>>a>>b;
    if(a*b>=a+b && a*b>=a-b)
        cout<<a*b;
    else if (a+b>=a*b && a+b>=a-b)
        cout<<a+b;
    else
        cout<<a-b;

}


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

int main() {
    /* Input */
    string S, T;
    cin >> S;
    cin >> T;
    
    /* Main Logic */      
    int ans = T.size();
    rep(i, (int)S.size() - (int)T.size() + 1) {
        int times = 0;
        rep(j, (int)T.size()) {
            if (S[i+j] != T[j]) {
                times++;
            }
        }
        ans = min(ans, times);
    }

    /* Output */
    cout << ans << endl;
    return 0;
}

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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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 (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

struct P
{
	double x, y, r;
	P(double x, double y) :x(x), y(y), r(atan2(y, x) + M_PI) {}
	P() :P(0.0, 0.0) {}
	bool operator<(const P& other)const
	{
		return r < other.r;
	}
};

int N;
vector<P> Ps;
vector<double> ct;

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

	cin >> N;
	double x, y;
	rep(i, 0, N)
	{
		cin >> x >> y;
		Ps.push_back(P(x, y));
	}

	sort(all(Ps));

	double ans = 0.0;
	rep(i, 0, N)
	{
		pdd res = mp(Ps[i].x, Ps[i].y);
		int j = (i + 1) % N;
		chmax(ans, sqrt(res.first*res.first + res.second*res.second));
		while (j != i)
		{
			res.first += Ps[j].x;
			res.second += Ps[j].y;
			chmax(ans, sqrt(res.first*res.first + res.second*res.second));
			j = (j + 1) % N;
		}

	}

	cout << fixed << setprecision(12) << ans << endl;

	return 0;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		try (Scanner sc = new Scanner(System.in)) {
			int n = sc.nextInt();			
			Integer w[] = new Integer[n];
			
			int s1 = 0;
			int s2 = 0;
			
			for (int i = 0; i < n; i++) {
				w[i] = sc.nextInt();
				s1 += w[i];
			}
			
			int result = 10000;
			int temp = 0;
			for (int i = n - 1; i > 0; i--) {
				s1 -= w[i];
				s2 += w[i];
				temp = Math.abs(s1-s2);
				if (temp < result) {
					result = temp;
				}
			}
			
			System.out.println(result);
			
		}

	}

}


Measured memory_bytes: 22996
#include <iostream>
#include <vector>
using namespace std;
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 long long INF = 1LL<<60;

// 入力
int N, M;
vector<vector<int> > G; // グラフ

// メモ化再帰
int dp[100100];
int rec(int v) {
    if (dp[v] != -1) return dp[v]; // 既に更新済み

    int res = 0;
    for (auto nv : G[v]) {
        chmax(res, rec(nv) + 1);
    }
    return dp[v] = res; // メモしながらリターン
}


int main() {
    // 入力受け取り
    cin >> N >> M;
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int x, y; cin >> x >> y;
        --x, --y; // 0-indexed にする
        G[x].push_back(y);
    }

    // 初期化
    for (int v = 0; v < N; ++v) dp[v] = -1;

    // 全ノードを一通り更新しながら答えを求める
    int res = 0;
    for (int v = 0; v < N; ++v) chmax(res, rec(v));
    cout << res << endl;
}

Measured memory_bytes: 11004
#from collections import deque
import bisect

a, b, q = [int(x) for x in input().split()]
s = [-10**12] + [int(input()) for i in range(a)] + [10**12]
t = [-10**12] + [int(input()) for i in range(b)] + [10**12]
#x = [int(input()) for i in range(q)]

#s_que = deque(s)
#s_que.appendleft(-10 ** 12)
#s_que.append(10 ** 12)

#t_que = deque(t)
#t_que.appendleft(-10 ** 12)
#t_que.append(10 ** 12)

for i in range(q):
    x = int(input())
    k = bisect.bisect_left(s, x)
    sb = s[k]
    sa = s[k-1]
    j = bisect.bisect_left(t, x)
    tb = t[j]
    ta = t[j-1]

    y = []
    for h in [sa, sb]:
        for g in [ta, tb]:
            y.append(abs(x-h) + abs(h-g))
    for h in [ta, tb]:
        for g in [sa, sb]:
            y.append(abs(x-h) + abs(h-g))

    print(min(y))


Measured memory_bytes: 12816
#include<iostream>

int main(){
  int n, m, l;
  std::cin >> n >> m >> l;

  int a[n][m];
  int b[m][l];
  long c[n][l];

  for(int i = 0; i< n; i++){
    for(int j = 0; j < l; j++){
      c[i][j] = 0;
    }
  }

  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      std::cin >> a[i][j];
    }
  }

  for(int i = 0; i < m; i++){
    for(int j = 0; j < l; j++){
      std::cin >> b[i][j];
    }
  }
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < l; j++){
      for(int k = 0; k < m; k++){
	c[i][j] += a[i][k]  * b[k][j];
      }
    }
  }

  for(int i = 0; i < n; i++){
    for(int j = 0; j < l; j++){
      std::cout << c[i][j];
      if(j < l - 1) std::cout << ' ';
    }
    std::cout << std::endl;
  }

  return 0;
}

Measured memory_bytes: 3184
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) throws Exception{    
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int k = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();

        int ans;
        
        if(n <= k){
        	ans = n*x;
        }else{
        	ans = k*x + (n-k)*y;
        }
        
        System.out.println(ans);
        
        sc.close();
    }
 
}

Measured memory_bytes: 9804
str1 = input()
A = input()

list1 = str1.split()
list2 = A.split()
N = list1[0]
M = list1[1]

M_count = 0

all = 0
for i in range(len(list2)):
    all = all + int(list2[i])
#print("all" + str(all))

judge =  1/(4*int(M)) * all
#print("judge" + str(judge))

for i in list2:
    #print("list2 = "+ i )
    if int(i) >= judge:
        M_count = M_count + 1
        #print("M_count" + str(M_count))
    
if M_count >= int(M):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
sx, sy, tx, ty = map(int,input().split())
ans = ''

ans += 'U'*(ty-sy)
ans += 'R'*(tx-sx)
ans += 'D'*(ty-sy)
ans += 'L'*(tx-sx)
ans += 'L'
ans += 'U'*((ty-sy)+1)
ans += 'R'*((tx-sx)+1)
ans += 'D'
ans += 'R'
ans += 'D'*((ty-sy)+1)
ans += 'L'*((tx-sx)+1)
ans += 'U'

print(ans)
# print(len(ans))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
int DP[60][30][60][30], w, h;
const int INF = (1e9);
char S[60][30];
struct state{int lx, ly, rx, ry;};
bool operator<(const state &x, const state &y){ return x.lx < y.lx;}

bool in_range(int a, int b){ return a >= 0 && a < b;}

int solve(){
  priority_queue< pair<int, state> > wait;
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      if(S[i][j] == 'S'){
        wait.emplace(0,(state){i,j,-1,-1});
        wait.emplace(0,(state){-1,-1,i,j});
      }
    }
  }
  while(!wait.empty()){
    state s = wait.top().second;
    int t = -wait.top().first, lx = s.lx, ly = s.ly, rx = s.rx, ry = s.ry;
    wait.pop();
    //printf("%d %d %d %d %d\n",lx,ly,rx,ry,t);
    if(lx >= 0 && rx >= 0 && DP[s.lx][s.ly][s.rx][s.ry] < t) continue;
    if(lx >= 0 && ly >= 0){
      for(int i = -2; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
          int rx_ = lx + i, ry_ = ly + j + 1;
          if((!in_range(rx_,h)) || (!in_range(ry_,w)) ||
             (abs(j)+abs(i) > 2) || (S[rx_][ry_] == 'X')) continue;
          int t_;
          if(S[rx_][ry_] > '9' || S[rx_][ry_] < '0') t_ = t;
          else t_ = t + S[rx_][ry_] - '0';
          if(t_ >= DP[lx][ly][rx_][ry_]) continue;
          DP[lx][ly][rx_][ry_] = t_;
          wait.emplace(-t_,(state){lx,ly,rx_,ry_});
        }
      }
    }
    if(rx >= 0 && ry >= 0){
      for(int i = -2; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
          int lx_ = rx + i, ly_ = ry - j - 1;
          if((!in_range(lx_,h)) || (!in_range(ly_,w)) ||
             (abs(j)+abs(i) > 2) || (S[lx_][ly_] == 'X')) continue;
          int t_;
          if(S[lx_][ly_] > '9' || S[lx_][ly_] < '0') t_ = t;
          else t_ = t + S[lx_][ly_] - '0';
          if(t_ >= DP[lx_][ly_][rx][ry]) continue;
          DP[lx_][ly_][rx][ry] = t_;
          wait.emplace(-t_,(state){lx_,ly_,rx,ry});
        }
      }
    }
  }
  //  cout << "while loop finished" << endl;
  int ret = INF;
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      if(S[i][j] != 'T') continue;
      for(int k = 0; k < h; ++k)
        for(int l = 0; l < w; ++l)
          ret = min({ret, DP[i][j][k][l], DP[k][l][i][j]});
    }
  }
  return ret;
}

int main(){
  while(cin >> w >> h, w){
    for(int i = 0; i < h; ++i)
      for(int j = 0; j < w; ++j)
        cin >> S[i][j];
    for(int i = 0; i < h; ++i)
      for(int j = 0; j < w; ++j)
        for(int k = 0; k < h; ++k)
          for(int l = 0; l < w; ++l)
            DP[i][j][k][l] = INF;
    int ans = solve();
    if(ans >= INF) ans = -1;
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 15768
object Main {
  def main(args: Array[String]): Unit = {
    io.Source.stdin.getLines().foreach(rec)
  }

  def rec(s: String): Unit = {
    if (check(s)) {
      println(s)
      return
    }

    rec(next(s))

    def check(s: String): Boolean = {
      val list = List("the", "this", "that")
      list.foreach { ss =>
        if (s.contains(ss)) {
          return true
        }
      }
      return false
    }

    def next(s: String): String = {
      val sss = s.map({
        case cc if 'a' to 'z' contains cc => (((cc - 'a' + 1) % 26) + 'a').toChar
        case ch => ch
      })
      sss.toString
    }
  }
}

Measured memory_bytes: 46224
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>

using namespace :: std;

const ll mod=1e9+7;
const ll inf=1e17+500;
const ll maxn=5e5+500;

ll a[maxn];
ll n;
bool b[maxn];

bool find_ans(){
    bool hashor=1;

    ll naz[2];
    naz[0]=inf;
    naz[1]=inf;

    for(ll i=2;i<2*n;i++){
        if(b[i]==b[i-1]){
            if(i<=n){
                naz[b[i]]=min(naz[b[i]],n-i);
            }else{
                naz[b[i]]=min(naz[b[i]],i-n-1);
            }
        }
    }
    if(naz[0]==inf && naz[1]==inf){
        return b[1];
    }
    if(naz[0]<naz[1]){
        return 0;
    }
    return 1;
}

bool ans_kamtar_az(ll mid){
    for(ll i=1;i<2*n;i++){
        if(a[i]<mid){
            b[i]=1;
        }else{
            b[i]=0;
        }
    }
    if(find_ans()==1){
        return 1;
    }
    return 0;
}

int main(){
    cin>>n;
    for(ll i=1;i<=2*n-1;i++){
        cin>>a[i];
    }
    ll b=1;
    ll e=2*n;
    while(e-b>1){
        ll mid=(e+b)/2;
        if(ans_kamtar_az(mid)){
            e=mid;
        }else{
            b=mid;
        }
    }
    cout<<b;
}




Measured memory_bytes: 4096
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int dp[105][105];
int slow(vector<pii> edges) {
  memset(dp, 1, sizeof(dp));
  for(int i = 1; i <= 100; i++) dp[i][i] = 0;
  for(pii out: edges) {
    dp[out.first][out.second] = 1;
    dp[out.second][out.first] = 1;
  }
  for(int i = 1; i <= 100; i++) for(int j = 1; j <= 100; j++) for(int k = 1; k <= 100; k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
  for(int i = 1; i <= 100; i++) for(int j = 1; j <= 100; j++) for(int k = 1; k <= 100; k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
  for(int i = 1; i <= 100; i++) for(int j = 1; j <= 100; j++) for(int k = 1; k <= 100; k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
  int ans = 0;
  for(int i = 1; i <= 100; i++) {
    for(int j = 1; j < i; j++) {
      ans += dp[i][j] == 2;
    }
  }
  return ans;
}
 
void solve() {
  // n vertices
  // k pairs of vertices that are have shortest distance 2
  // maximum is star graph, (n-1) choose 2
  int n, k;
  cin >> n >> k;
  if(2*k > (n-1) * (n-2)) {
    cout << "-1\n";
    return;
  }
  // make 1 the center
  vector<pii> edges;
  for(int i = 2; i <= n; i++) {
    edges.emplace_back(1, i);
  }
  // incrementally connect 2 to 3 through n
  int curr = (n-1)*(n-2)/2;
  for(int i = 2; i <= n; i++) {
    for(int j = i+1; curr > k && j <= n; j++) {
      edges.emplace_back(i, j);
      curr--;
    }
  }
  assert(slow(edges) == k);
  cout << edges.size() << "\n";
  for(pii out: edges) {
    cout << out.first << " " << out.second << "\n";
  }
}
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  ll t;
  cin >> t;
  for(ll i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}

Measured memory_bytes: 3720
#include <stdio.h>

int main(void)
{
    int a,b;
    scanf("%d %d",&a,&b);
    if(a >= -1000 && a <= 1000 && b>= -1000 && b <= 1000){
        if(a>b)
            printf("a > b\n");
        else if(a<b)
            printf("a < b\n");
        else if(a=b)
            printf("a == b\n");
    }
}


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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

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

    vector<llint> a(n);
    for(llint in=0;in<n;in++) {
        cin >> a[in];
    }
    
    sort(a.begin(), a.end(), greater<llint>());

    llint ans = a[0], cnt = 1, in = 1;
    bool again = true;
    while(cnt<=n-2) {
        ans += a[in];
        // cout << a[in];
        if(!again) { 
            in++;
            again = true;
        }
        else {
            again = false;
        }
        cnt++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4828
#include<bits/stdc++.h>
#define LL long long
#define P 1000000007
#define M 2005
using namespace std;
int A[M],B[M],sum[M][M];
void Add(int &x,int y){
	y%=P;
	x+=y;
	x%=P;
	if(x<0)x+=P;
}
int main() { 
	int n,m,h,x,y; 
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&A[i]);
	for(int i=1;i<=m;i++)scanf("%d",&B[i]);
	int ans=1; 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(A[i]==B[j]){
				sum[i][j]=sum[i-1][j-1]+1;
				Add(ans,sum[i][j]);
			}
			Add(sum[i][j],sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]);
		}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;

#define allof(x) (x).begin(), (x).end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

set<string> found;

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

    string str;
    cin >> str;

    int K;
    cin >> K;

    for(int a = 0; a < (int)str.size(); a++){
        for(int b = 1; b <= 5 && a + b - 1 < (int)str.size(); b++){
            found.insert(str.substr(a, b));
        }
    }

    auto iter = found.begin();
    advance(iter, K - 1);
    cout << *iter;
}


Measured memory_bytes: 1664
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] a = new int[n];

    for (int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }

    int count = (int) Math.ceil((double) (n - k) / (k - 1)) + 1;

    System.out.println(count);
    sc.close();
  }

}

Measured memory_bytes: 52520
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
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; }
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;
const long double PI = acos((long double)(-1));
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

int n, m, p, a, b;
int cnv(int x, int S) {
    return x * (1 << n) + S;
}

vector<ld> dijkstra(int start, vector<vector<pair<int, ld>>>& graph) {
    vector<ld> dist(graph.size(), INF); dist[start] = 0;
    priority_queue<pair<ld, int>, vector<pair<ld, int>>, greater<pair<ld, int>>> pq; pq.emplace(0, start);
    while (!pq.empty()) {
        ld cost; int idx; tie(cost, idx) = pq.top(); pq.pop();
        if (dist[idx] < cost) continue;
        for (auto next : graph[idx]) if (chmin(dist[next.first], cost + next.second)) pq.emplace(dist[next.first], next.first);
    }
    return dist;
}

void solve() {
    scanf("%d %d %d %d %d", &n, &m, &p, &a, &b); if (n == 0) exit(0);
    a--; b--;
    vector<int> t(n); for (int i = 0; i < n; i++) scanf("%d", &t[i]);
    vector<vector<pair<int, ld>>> g(m * (1 << n));
    for (int i = 0; i < p; i++) {
        int x, y, z; scanf("%d %d %d", &x, &y, &z);
        x--; y--;
        for (int S = 0; S < (1 << n); S++) {
            for (int i = 0; i < n; i++) {
                if (S >> i & 1) {
                    int T = S - (1 << i);
                    g[cnv(x, T)].emplace_back(cnv(y, S), (ld)z / t[i]);
                    g[cnv(y, T)].emplace_back(cnv(x, S), (ld)z / t[i]);
                }
            }
        }
    }
    auto d = dijkstra(cnv(a, 0), g);
    ld res = 1e18;
    for (int S = 0; S < (1 << n); S++) {
        chmin(res, d[cnv(b, S)]);
    }
    if (1e15 < res) puts("Impossible");
    else cout << fixed << setprecision(12) << res << "\n";
}

int main()
{
    /*
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    */

    int kkt = 89;
    while (kkt) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 48156
#include <stdio.h>

/* prototype declaration */
int interest(int principal, int rate, int week);

int main(int argc, const char *argv[])
{
	int dept, week, principal = 100000, rate = 5;
	scanf("%d", &week);
	
	dept = interest(principal, rate, week);	
	
	printf("%d\n", dept);
	return 0;
}

int interest(int principal, int rate, int week)
{
	int i, ans = principal;
	double dept = principal, r = 1.0+rate/100.0;
	
	for(i=0; i<week; i++){
		dept = ans*r;
		if((int)dept%1000) ans = ((int)(dept/1000) + 1)*1000;
		else ans = (int)dept;
	}
	
	return ans;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 29;
const ll INF64 = 1ll << 55;
const int mod = 1000000007;
//const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int n; cin >> n;
  vector<ll> a(3*n);
  rep(i, 3*n) cin >> a[i];
  vector<ll> l(n+1, 0), r(n+1, 0);
  priority_queue<ll, vector<ll>, greater<ll>> pql;
  ll sum = 0;
  rep(i, n) {
    sum += a[i];
    pql.push(a[i]);
  }
  l[0] = sum;
  for(int i = n; i < 2*n; ++i) {
    if(pql.top() < a[i]) {
      sum -= pql.top();
      sum += a[i];
      pql.pop();
      pql.push(a[i]);
    }
    l[i-n+1] = sum;
  }
  priority_queue<ll> pqr;
  sum = 0;
  reverse(ALL(a));
  rep(i, n) {
    sum += a[i];
    pqr.push(a[i]);
  }
  r[0] = sum;
  for(int i = n; i < 2*n; ++i) {
    if(pqr.top() > a[i]) {
      sum -= pqr.top();
      sum += a[i];
      pqr.pop();
      pqr.push(a[i]);
    }
    r[i-n+1] = sum;
  }
  ll ans = -INF64;
  for(int i = 0; i <= n; ++i) chmax(ans, l[i]-r[n-i]);
  cout << ans << endl;
}


Measured memory_bytes: 6516
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,x,m,mn;
    cin>>m;
    n=5;
    mn=1e15;
    while(n--)
    {
        cin>>x;
        mn=min(mn,x);
    }
    x=ceil((m*1.0)/mn);
    x=x+4;
    printf("%lld\n",x);
    return 0;
}


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

#define int long long int

const int M = 998244353;

int arr[15][15], amount[15];

int32_t main() {
    
    int n, m, x;
    cin >> n >> m >> x;
    
    for(int i = 0; i < n; i++){
        cin >> amount[i];
        for(int j = 0; j < m; j++){
            cin >> arr[i][j];
        }
    }
    
    int ans = 1e17;
    for(int i = 0; i < (1ll<<n); i++){
        int cost[15];
        memset(cost, 0, sizeof(cost));
        int sum = 0;
        for(int j = 0; j < n; j++){
            if(((1ll<<j)&i)){
                sum += amount[j];
                for(int k = 0; k < m; k++)
                    cost[k] += arr[j][k];
            }
        }
        bool flag = false;
        for(int k = 0; k < m; k++){
            if(cost[k] < x){
                flag = true;
            }
        }
        if(flag == false){
            ans = min(ans, sum);
        }
    }
    if(ans == 1e17)
        cout << -1 << endl;
    else
        cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>

using namespace std;

const int mod = 1e9 + 7;

struct modint {
	int n;
	modint(int n = 0) : n(n) {}
};

modint operator+(modint a, modint b) { return modint((a.n += b.n) >= mod ? a.n - mod : a.n); }
modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + mod : a.n); }
modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % mod); }
modint &operator+=(modint &a, modint b) { return a = a + b; }
modint &operator-=(modint &a, modint b) { return a = a - b; }
modint &operator*=(modint &a, modint b) { return a = a * b; }

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

	vector<modint> dp(n * 2 + 10);
	vector<modint> imos(n * 2 + 10);

	modint ans = 0;
	dp[0] = 1;
	for (int i = 0; i < n - 1; i++) {
		imos[i + 1] += imos[i];
		dp[i] += imos[i];

		ans += dp[i] * (n - 1) * (n - 1);
		imos[i + 3] += dp[i];
		imos[i + n + 2] -= dp[i];
		dp[i + 1] += dp[i];
	}

	for (int i = n - 1; i < imos.size() - 1; i++) {
		imos[i + 1] += imos[i];
		dp[i] += imos[i];
		if (i > n - 1) {
			ans += dp[i];
		} else {
			ans += dp[i] * n;
		}
	}

	cout << ans.n << endl;
}

Measured memory_bytes: 15872
#include <stdio.h>
#include <string.h>

int main() {
  int height,length,i,j,t,max,depth,left,right,last_height,sum;
  char section[20001],reverse[20001];
  int L[10000] = {0},reverse_L[10000] = {0};

  scanf("%s", section);
  length = strlen(section);
  for(i = 0; i < length; i++) reverse[i] = section[length-i-1];
  reverse[i] = '\0';
  
  max = 0;height = 0;t = 0;
  for(i = 0; i < length; i++) {
    if(section[i] =='\\') height--;
    if(section[i] == '/') {
      height++;
      if(max == height) t++;
      if(max < height) {
	max = height;
	t = 0;
      }
    }
  }
  last_height = height;

  
  height = 0;depth = 0;i = 0;j = 0;
  while(height < max) {
    if(section[i] =='\\') {
      height--;
      depth++;
    }
    if(section[i] == '/') {
      height++;
      if(depth > 0) depth--;
      if(depth == 0 && L[j] > 0) j++;
    }
    L[j] += depth;
    i++;
  }
  
  while(t > 0) {
    if(section[i] =='\\') {
      height--;
      depth++;
    }
    if(section[i] == '/') {
      height++;
      if(depth > 0) depth--;
      if(depth == 0 && L[j] > 0) {
	j++;
	t--;
      }
    }
    L[j] += depth;
    i++;
  }
  left = j;
  
  height = last_height;depth = 0;i = 0;j = 0;
  while(height < max) {
    if(reverse[i] =='/') {
      height--;
      depth++;
    }
    if(reverse[i] == '\\') {
      height++;
      if(depth > 0) depth--;
      if(depth == 0 && reverse_L[j] > 0) j++;
    }
    reverse_L[j] += depth;
    i++;
  }
  right = j;

  for(i = 0; i < right; i++) L[left+i] = reverse_L[right-i-1];
  sum = 0;
  for(i = 0; i < left+right; i++) sum += L[i];

  printf("%d\n", sum);
  printf("%d", left+right);
  if(left+right != 0) printf(" ");
  for(i = 0; i < left+right-1; i++) printf("%d ", L[i]);
  if(left+right != 0) printf("%d", L[i]);
  printf("\n");

  return 0;
}

Measured memory_bytes: 668
#include <bits/stdc++.h>
using namespace std;
void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}
#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define MOD 1000000007
#define zeros(x) x&(x-1)^x
#define fi first
#define se second
#define Nmax 500005
const long double PI = acos(-1);

char mat[1003][1003];
int n,m,mn[1003][1003],ans;
queue<pii>H;
int dx[] = {0,1,-1,0};
int dy[] = {1,0,0,-1};

bool OK(int x, int y){
    if (x <= n && x >= 1 && y <= m && y >= 1) return 1;
    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    memset(mn,0xff,sizeof(mn));
    for (int i=1;i<=n;i++){
        cin >> mat[i]+1;
        for (int j=1;j<=m;j++){
            if (mat[i][j] == '#'){
                H.push({i,j});
                mn[i][j] = 0;
            }
        }
    }

    while (!H.empty()){
        pii crt = H.front();
        H.pop();

        for (int i=0;i<4;i++){
                int X = crt.first + dx[i];
                int Y = crt.second + dy[i];
                if (OK(X,Y) && mn[X][Y] == -1){
                    mn[X][Y] = mn[crt.first][crt.second] + 1;
                    ans = max(ans, mn[X][Y]);
                    H.push({X,Y});
                }
        }
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 13328
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <cstring>
using namespace std;
long long A[100001];
long long cumsum_A[100001];
long long max_non_leaf_num[100001];
int main(){
  int N;
  cin >> N;
  for(int i = 0; i < N + 1; i++){
    cin >> A[i];
  }

  cumsum_A[N] = A[N];
  for(int i = N - 1; i >= 0; i--){
    cumsum_A[i] = A[i] + cumsum_A[i + 1];
  }

  if(N == 0){
    if(A[0] == 1){
      cout << 1 << endl;
    } else {
      cout << - 1 << endl;
    }
    return 0;
  }

  max_non_leaf_num[0] = (long long) 1 - A[0];
  if(max_non_leaf_num[0] <= 0){
    cout << -1 << endl;
    return 0;
  }
  for(int i = 1; i < N + 1; i++){
    if(max_non_leaf_num[i - 1] == LLONG_MAX){
      max_non_leaf_num[i] = LLONG_MAX;
      continue;
    }
    max_non_leaf_num[i] = (long long) 2 * max_non_leaf_num[i - 1] - A[i];
    if(max_non_leaf_num[i] >= (long long) 100 * cumsum_A[i + 1]){
      max_non_leaf_num[i] = LLONG_MAX;
    }
    if(max_non_leaf_num[i] <= 0){
      cout << - 1 << endl;
      return 0;
    }
  }

  long long ans = 0;
  ans += A[N];
  long long prev_node_num = A[N];
  for(int i = N - 1; i >= 0; i--){
    ans += A[i];
    if(max_non_leaf_num[i] >= prev_node_num){
      ans += prev_node_num;
      prev_node_num += A[i];
    } else {
      prev_node_num = max_non_leaf_num[i] + A[i];
      ans += max_non_leaf_num[i];
    }
    //cout << i << " " << ans << " " << prev_node_num << endl;
  }
  cout << ans << endl;

  /*
  for(int i = 0; i < N; i++){
    cout << max_non_leaf_num[i] << endl;
  }
  */
  return 0;
}


Measured memory_bytes: 5968
#include <stdio.h>
int main(void) {
	int a, b, c, x, y, m, n, sum;
	scanf("%d %d %d %d %d",&a, &b, &c, &x, &y);
	if(a <= b && a <= c)
		m = a;
	else if(b <= c)
		m = b;
	else
		m =c;
	if(x <= y)
		n = x;
	else
		n = y;
	sum = m + n - 50;
	printf("%d\n",sum);
	
	return 0;
}

Measured memory_bytes: 592
import java.util.*

fun main(args: Array<String>) {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(Scanner(System.`in`), pw)
    pw.flush()
}

object Problem {
    data class Way(val to: Int, val t: Int)

    fun solve(sc: Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        pw.println((1000 - N % 1000) % 1000)
    }
}


Measured memory_bytes: 36440
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN=405;
const int MAXM=1e5+5;

int n,m;
int S[MAXN][MAXN],alive[MAXN];
pair<int,int> a[MAXM];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d",&a[i].first,&a[i].second);
    for(int i=1;i<=n;i++){
        alive[i]=1;
        S[i][i]=1;
        for(int j=m;j>=1;j--){
            int x=a[j].first,y=a[j].second;
            if(!S[i][x]&&!S[i][y]) continue;
            if(S[i][x]&&S[i][y]){
                alive[i]=0;
                break;
            }
            S[i][x]=S[i][y]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            if(!alive[i]||!alive[j]) continue;
            bool flag=1;
            for(int k=1;k<=n;k++)
                if(S[i][k]&&S[j][k]){
                    flag=0;
                    break;
                }
            if(flag) ans++;
        }
    printf("%d",ans);
}


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

int main() {
	// your code goes here
	int n; cin>>n;
	int arr[n];
	for(int i=0; i<n; i++) cin>>arr[i];
	
	long long int dp[n];
	dp[0]=0;
	dp[1]=abs(arr[1]-arr[0]);
	
	for(int j=2; j<n; j++){
	    dp[j]=min(dp[j-2]+abs(arr[j]-arr[j-2]), dp[j-1]+abs(arr[j]-arr[j-1]));
	    //cout<<dp[j]<<"\n";
	}
	
	cout<<dp[n-1];
	
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef set<int> si;

const int SIZE = 100 + 10;

int board[SIZE][SIZE] = {0};

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

    int h, w;
    int n;
    cin >> h >> w >> n;
    vi v(n);
    for (auto &i : v)
        cin >> i;
    int i = 0, j = 0, k = 0;
    while (i != h && j != w)
    {
        if (v[k] == 0)
            k++;
        board[i][j] = k + 1;
        v[k]--;
        if (i & 1)
            j--;
        else
            j++;
        if (j == -1)
            i++, j = 0;
        else if (j == w)
            i++, j = w - 1;
    }

    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
            cout << board[i][j] << " ";
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 384
import collections


def solve():
    pass


n = int(input())
A = []
for i in range(n):
    a = int(input())
    A.append(a)

c = collections.Counter(A)
cnt = 0
for k, v in c.items():
    if v % 2 == 0: continue
    else: cnt += 1
print(cnt)

Measured memory_bytes: 20828
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) std::cout<<arg<<"\n"
#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) std::memset(arg,n,sizeof(arg))
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
using std::cin;
typedef long long ll;
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::set<int> si;
typedef std::string str;
const int INF=1e+9;
const ll INFLL=1e+17;
const ll MOD=1e+9+7;
const ll MAX_P=200010;
ll fact[MAX_P];
ll H,W,A,B;
void make_fact(){
  fact[0]=fact[1]=1;
  for(ll i=2;i<MAX_P;i++){
    fact[i]=(fact[i-1]*i)%MOD;
  }
}
ll Extgcd(ll a,ll b,ll &x,ll &y){
  ll d=a;
  if(b!=0){
    Extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }
  else{
    x=1;y=0;
  }
  return d;
}

ll mod_inv(ll a,ll p){//mod pでのaの逆元を求める
  ll x,y;
  Extgcd(a,p,x,y);
  return (x%p+p)%p;
}
//n!=a*p^e (a,p互いに素,p素数) とした時のeとa mod p を求める
ll mod_fact(ll n,ll p,ll& e){
  e=0;
  if(n==0) return 1;
  
  ll res=mod_fact(n/p,p,e);
  e+=n/p;

  if(n/p%2!=0) return res*(p-fact[n%p])%p;
  return res*fact[n%p]%p;
}

//nCk mod pを求める
ll mod_comb(ll n,ll k,ll p){
  if(n<0||k<0||n-k<0) return 0;
  ll e1,e2,e3;
  ll a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3);
  if(e1>e2+e3) return 0;
  return a1*mod_inv(a2*a3%p,p)%p;
}


int main(){
  make_fact();
  cin>>H>>W>>A>>B;
  ll res=0;
  rep(i,H-A){
    ll temp=(mod_comb(B-1+i,i,MOD)*mod_comb(W-B+H-2-i,H-1-i,MOD))%MOD;
    res=(res+temp)%MOD;
  }
  prin(res);
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
struct ios_accelerate { ios_accelerate() { ios::sync_with_stdio(false); cin.tie(nullptr); } } CALL;

#define REP(i, n) for(auto (i) = (n)*0; (i) < (n); (i)++)
#define RNG(i, a, b) for(auto (i) = (a); (i) < (b); (i)++)
#define RBF(i, v) for(auto& (i) : (v))
#define ALL(x) (x).begin(), (x).end()

using LL = long long;
using UL = unsigned long;
using ULL = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using P = pair<T, T>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = static_cast<LL>(1e18) + 2;
const int INF = static_cast<int>(1e9) + 2;

template<typename T> inline void upsort(vector<T>& x) { sort(x.begin(), x.end()); }
template<typename T> inline void downsort(vector<T>& x) { sort(x.begin(), x.end(), greater<T>()); }
template<typename T> inline void col(T x) { cout << x << '\n'; }
template<> inline void col(double x) { cout << fixed << setprecision(12) << x << '\n'; }

signed main() {
	LL h;
	cin >> h;

	LL cnt = 0;
	while (h > 0) {
		h /= 2;
		cnt++;
	}

	LL ans = pow(2, cnt) - 1;
	col(ans);

	return 0;
}


Measured memory_bytes: 4032
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define pb push_back
#define F first
#define S second
const int mod = 1e9+7, A = 4e4+5;
int add(ll a, ll b) {return (a + b + mod) % mod;}
int mul(ll a, ll b) {return (a * b) % mod;}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, m;
    cin >> n >> m;
    int a[n], b[m], suma = 0, sumb = 0;
    for (int i = 0; i < n; i++)
        cin >> a[i], suma = add(suma, a[i]);
    for (int i = 0; i < m; i++)
        cin >> b[i], sumb = add(sumb, b[i]);
    int x = 0, y = 0;
    for (int i = 0; i < n; i++)
    {
        suma = add(suma, -a[i]);
        x = add(x, suma);
        x = add(x, -mul(a[i], n - i - 1));
    }
    for (int i = 0; i < m; i++)
    {
        sumb = add(sumb, -b[i]);
        y = add(y, sumb);
        y = add(y, -mul(b[i], m - i - 1));
    }
    cout << mul(x, y);
    return 0;
}


Measured memory_bytes: 1024
N = int(input())
D,X = map(int,input().split())
A = [int(input()) for i in range(N)]

sum = N

for i in range(N):
    cnt = 1    
    while True: 
        if cnt*A[i]+1 <= D:
            sum += 1
            cnt += 1
        else :
            break
            
print(sum + X)

Measured memory_bytes: 3060
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int k, a, b;
    cin >> k >> a >> b;
    
    long long ans = 1;
    
    if (b < a + 2){
        ans += k;
    }
    else{
        
        int i = 1;
        
        while(i <= k){
            
            if (i == k){
                ans += 1;
                break;
            }
            else if (ans >= a){
                ans -= a;
                i += 1;
                ans += b;
                i += 1;
            }
            else{
                ans += 1;
                i += 1;
            }
            
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
/*************************************
 * @contest:      dwacon6th-prelims.
 * @user_name:    hkxadpall.
 * @time:         2020-01-11.
 * @language:     C++.
 * @upload_place: AtCoder.
*************************************/ 

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

typedef signed char          int8;
typedef unsigned char       uint8;
typedef short                int16;
typedef unsigned short      uint16;
typedef int                  int32;
typedef unsigned            uint32;
typedef long long            int64;
typedef unsigned long long  uint64;

template <typename Int>
inline Int read()       
{
    Int flag = 1;
    char c = getchar();
    while ((!isdigit(c)) && c != '-') c = getchar();
    if (c == '-') flag = -1, c = getchar();
    Int init = c & 15;
    while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
	return init * flag;
}

template <typename Int>
inline Int read(char &c)       
{
    Int flag = 1;
    c = getchar();
    while ((!isdigit(c)) && c != '-') c = getchar();
    if (c == '-') flag = -1, c = getchar();
    Int init = c & 15;
    while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
	return init * flag;
}

template <typename Int>
inline void write(Int x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar((x % 10) | 48);
}  

template <typename Int>
inline void write(Int x, char nextch)
{
    write(x);
    putchar(nextch);
}

#define P 1000000007

int n, main_k;
int a[20 + 3];
long long fac[1000 + 3], invf[1000 + 3];
long long _f[2][1000 + 3];

long long fpow(long long a, int n, const long long p)
{
    long long res = 1;
    while (n) {
        if (n & 1) res = res * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return res;
}

#define inv(x) fpow(x, P - 2, P)

int C_init()
{
    fac[0] = 1;
    invf[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % P;
        invf[i] = inv(fac[i]);
    }
    return 0;
}

long long C(int n, int m)
{
    static bool C_init_tag = !C_init();
    // printf("query C(%d, %d) ret = %lld.\n", n, m, fac[n] * invf[m] % P * invf[n - m] % P);
    return fac[n] * invf[m] % P * invf[n - m] % P;
}

#define f _f[(i) & 1]
#define g _f[((i) & 1) ^ 1]

int main()
{
    n = read<int>();
    main_k = read<int>();
    _f[0][0] = 1;
    for (int i = 1; i <= main_k; i++) {
        a[i] = read<int>();
        memset(f, 0, sizeof(f));
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= min(n - j, a[i]); k++) {
                // printf("f[%d + %d] from g[%d](= %d)\n", j, k, j, g[j]);
                f[j + k] = (f[j + k] + g[j] * C(n - j, k) % P * C(n - k, a[i] - k) % P) % P;
                // printf(" = %lld.\n------------------------------\n", f[j + k]);
            }
        }
        // printf("f = {");
        // for (int j = 0; j <= n; j++) {
        //     printf("%lld", f[j]);
        //     if (j < n) printf(", ");
        // }
        // printf("}\n");
    }
    write(_f[main_k & 1][n]);
    return 0;
}

Measured memory_bytes: 256
n=int(input())
f=[list(map(int,input().split())) for _ in range(n)]
p=[list(map(int,input().split())) for _ in range(n)]
ans=-float('inf')
for i in range(1,2**10):
    tmp=list(map(int,list(format(i, '010b'))))
    p_tmp=[0 for _ in range(n)]
    for i in range(n):
        cnt=0
        for j in range(10):
            if tmp[j]==1 and f[i][j]==tmp[j]:
                cnt+=1
        p_tmp[i]=cnt
    P=0
    for k in range(n):
        P+=p[k][p_tmp[k]]
    ans=max(ans,P)
print(ans)

Measured memory_bytes: 3064
# include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+30;
int a[maxn];
int main()
{
    int n, k, m, cnt=0,ans=0;;
    scanf("%d%d",&n,&k);
    for(int i=0; i<n; ++i)
    {
        scanf("%d",&m);
        if(++a[m]==1) ++cnt;
    }
    if(cnt <= k) return 0*puts("0");
    sort(a+1, a+1+n, greater<int>());
    for(int i=k+1; i<=n; ++i)
        ans += a[i];
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 1024
N = int(raw_input())
P = map(int, raw_input().split())

N = P[:]
N.sort()

cnt = 0
for i, j in zip(N, P):
    if i != j:
        cnt += 1

if cnt == 0 or cnt == 2:
    print 'YES'
else:
    print 'NO'

Measured memory_bytes: 2568