akhauriyash/Code-Regression huggingface dataset:
N = int(input())

cnt = [0] * 4

for i in range(N):
    s = input()
    if s == "AC":
        cnt[0] += 1
    elif s == "WA":
        cnt[1] += 1
    elif s == "TLE":
        cnt[2] += 1
    else:
        cnt[3] += 1

print("AC x {}".format(cnt[0]))
print("WA x {}".format(cnt[1]))
print("TLE x {}".format(cnt[2]))
print("RE x {}".format(cnt[3]))

Measured memory_bytes: 9204
import glob
import os

bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        N = self.input_data()

        result = 0
        for i in range(len(N)):
            result += int(N[i])

        if result % 9 == 0:
            print("Yes")
        else:
            print("No")



solver = Solver(REL_PATH)
solver.exec_resolve()


Measured memory_bytes: 10100
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int cnt[26];
set<int>t[26];
int bit[400000];

void add(int k,int x){
	k++;
	while(k<400000){
		bit[k]+=x;
		k+=k&-k;
	}
}
int sum(int k){
	k++;
	if(k<=0)return 0;
	int res=0;
	while(k){
		res+=bit[k];
		k-=k&-k;
	}
	return res;
}
signed main(){
	string s;cin>>s;
	for(char c:s)cnt[c-'a']++;
	rep(i,s.size()){
		add(i,1);
		t[s[i]-'a'].insert(i);
	}
	ll ans=0;
	while(1){
		bool flag=false;
		int Min=INT_MAX,id=-1;
		rep(i,26){
			if(cnt[i]==1||cnt[i]==0)continue;
			flag=true;
			int f=*t[i].begin(),e=*t[i].rbegin();
			int d=sum(f-1)+sum(s.size()-1)-sum(e);
			if(Min>d){
				Min=d;
				id=i;
			}
		}
		if(!flag)break;
		ans+=Min;
		cnt[id]-=2;
		add(*t[id].begin(),-1);
		add(*--t[id].end(),-1);
		t[id].erase(t[id].begin());
		t[id].erase(--t[id].end());
	}
	int t=0;
	rep(i,26)t+=cnt[i];
	if(t>1)puts("-1");
	else cout<<ans<<endl;
}

Measured memory_bytes: 10756
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = inp()

def query(x):
	print(x)
	sex = input()
	if sex == 'Male':
		return True
	elif sex == 'Female':
		return False
	else:
		print(x)
		sys.exit()


l,r = 0,N
ls = rs = query(0)

while True:
	mid = (l+r)//2
	ms = query(mid)

	if (mid-l+1)%2 == 1 and ls != ms:
		r = mid
		rs = ms
	elif (mid-l+1)%2 == 0 and ls == ms:
		r = mid
		rs = ms
	elif (r-mid+1)%2 == 1 and rs != ms:
		l = mid
		ls = ms
	elif (r-mid+1)%2 == 0 and rs == ms:
		l = mid
		ls = ms


Measured memory_bytes: 4800
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<61;
const ll mod=1e9+7;

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


int main(){
    int i,j;
    int m;
    while(1){
        cin>>m;
        if(m==0) break;
        vector<P> r(m);
        for(i=0;i<m;i++){
            int x,y;
            cin>>x>>y;
            r[i]=P(x,y);
        }
        int n;
        cin>>n;
        set<P> s;
        for(i=0;i<n;i++){
            int x,y;
            cin>>x>>y;
            s.insert(P(x,y));
        }
        for(auto it=s.begin();it!=s.end();++it){
            int xx = it->fi-r[0].fi;
            int yy = it->se-r[0].se;
            bool ok=1;
            for(i=1;i<m;i++){
                if(s.find(P(r[i].fi+xx,r[i].se+yy))==s.end()) {
                    ok=0;
                    break;
                }
            }
            if(ok) cout<<xx<<" "<<yy<<endl;
        }

    }
    
}


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

using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<pair<int, int>> fld(M);

  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    fld[i] = make_pair(a, b);
  }

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

  int f = fld[0].first;
  int e = fld[0].second;
  int ans = 1;
  for (int i = 0; i < M; i++) {
    if (fld[i].first >= e) {
      ans++;
      f = fld[i].first;
      e = fld[i].second;
      continue;
    }
    e = min(e, fld[i].second);
  }
  
  cout << ans << endl;

  return 0;
}


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

int main(){
    int a,b;
    int d,r;
    double f;
    
    cin>>a>>b;
    d=a/b;
    r=a%b;
    f=(double)a/b;
    cout<<d<<" "<<r<<" "<<fixed<<setprecision(5)<<f<<endl;
}

Measured memory_bytes: 3280
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int n;
	cin >> n;
	
	ll ans = 0LL;
	ll mini = MOD_LL;
	int minus = 0;
	
	for(int i = 0; i < n; ++i) {
		ll a;
		cin >> a;
		ans += abs(a);
		mini = min(mini, abs(a));
		
		if( a < 0 ) minus++;
	}
	
	if( minus % 2 == 0 ) {
		cout << ans << endl;
	} else {
		cout << ans - 2LL * mini << endl;
	}
	
	return 0;
}


Measured memory_bytes: 384
#include<iostream>
#define int long long
using namespace std;
bool compare(int u){
	char c;
	cout<<"? "<<u<<endl;
	cin>>c;
	return c=='Y';
}
int nibutan(int l,int r){
	while(r-l){
		int m=(l+r)/2;
		if(!compare(m*10))
			l=m+1;
		else
			r=m;
	}
	return l;
}
signed main(){
	bool f,g;
	f=compare(9);
	if(f){	//9から始まるか1桁
		if(!compare(10)){	//2~9
			int ans=nibutan(2,10);
			cout<<"! "<<ans<<endl;
		}
		else if(compare(1145141919810))	//1
			cout<<"! "<<1<<endl;
		else{
			int juu=10;
			while(compare(juu))
				juu*=10;
			int ans=nibutan(juu/10*9,juu);
			cout<<"! "<<ans<<endl;
		}
	}
	else{
		int juu=100;
		while(!compare(juu-1))
			juu*=10;
		int ans=nibutan(juu/10,juu/10*9);
		cout<<"! "<<ans<<endl;
	}
}

Measured memory_bytes: 684
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

long long pow_mod(long long n, long long p, long long m)
{
    if (p == 0) {
        return 1;
    }

    if (p % 2 == 0) {
        long long t = pow_mod(n, p / 2, m);
        return t * t % m;
    }
    return n * pow_mod(n, p - 1, m) % mod;
}

long long nCr_mod(long long n, long long r)
{
    long long x = 1;
    for (long long i = n - r + 1; i <= n; i++) {
        x *= i;
        x %= mod;
    }

    long long a = 1;
    for (long long i = 1; i <= r; i++) {
        a *= i;
        a %= mod;
    }

    long long y = pow_mod(a, mod - 2, mod) % mod;

    return x * y % mod;
}

bool is_prime(long long n)
{
    if (n == 1) {
        return false;
    }

    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int main()
{
    long long a, b;
    std::cin >> a >> b;

    std::cout << 6 - a - b << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define long long long int
static const int MOD = 2019;
using namespace std;

// @author: pashka

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

    string s;
    cin >> s;
    int n = s.size();
    int c = 0;
    
    int inv10 = 1;
    while ((inv10 * 10) % MOD != 1) inv10++;
    
    int p10 = 1;
    vector<int> cnt(MOD);
    cnt[0]++;
    long res = 0;
    for (int i = 0; i < n; i++) {
        c = (c * 10 + (s[i] - '0')) % MOD;
        p10 = (p10 * inv10) % MOD;
        int x = (c * p10) % MOD;
        res += cnt[x];
        cnt[x]++;
    }
    cout << res << "\n";

    return 0;
}

Measured memory_bytes: 3716
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const long long INF = 1LL <<60;
typedef long long ll;
using namespace std;

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

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

ll choose2(ll n){
    return n*(n-1)/2;
}

vector<ll> ans(0);

void dfs(ll a){
    if(a>3234566667) return;
    ans.push_back(a);
    int m = a % 10;
    if(m>0) dfs(a*10 + m-1);
    dfs(a*10 + m);
    if(m<9) dfs(a*10 + m+1);
}

int main(){
    int a,b;
    cin>>a>>b;
    if(b%a==0) cout<<a+b<<endl;
    else cout<<b-a<<endl;
    return 0;
}

Measured memory_bytes: 256
k,x = (int(x) for x in input().split())

length = k * 2 - 1

if x - k < -1000000:
	firstNo = -1000000
elif x + k > 1000000:
	firstNo = 1000000 - length + 1
else:
	firstNo = x - k + 1
for i in range(length):
	print(str(firstNo + i) + " ", end = "")

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

long long euclidean_gcd(long long a, long long b) {
    if(a < b) return euclidean_gcd(b, a);;
    long long r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
};

int main() {
    int n, k, gcd, m = 0, f = 1;
    cin >> n >> k;
    int a[n];
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        m = max(m, a[i]);
    }
    gcd = euclidean_gcd(a[0], a[1]);
    for(int i = 1; i < n; ++i) {
        gcd = euclidean_gcd(gcd, a[i]);
    }
    if(k > m || k%gcd) {
        f = 0;
    }
    if(f) {
        cout << "POSSIBLE" << '\n';
    } else {
        cout << "IMPOSSIBLE" << '\n';
    }
}

Measured memory_bytes: 640
import sys
input = sys.stdin.readline
import numpy as np

N, W = map(int, input().split())
dp = np.zeros(W+1, dtype=int)

for i in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w]+v)
print(dp[-1])

Measured memory_bytes: 15424
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;

int main() {
	int case_id=0;
	while (true) {
		int W,H,N;cin>>W>>H>>N;
		if(!W)break;
		vector<vector<vector<int>>>walls(H,vector<vector<int>>(W,vector<int>(4)));
		int dx[4] = { -1,0,1,0 };
		int dy[4] = { 0,-1,0,1 };
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				if(i==0)walls[i][j][1]=true;
				if(i==H-1)walls[i][j][3]=true;
				if(j==0)walls[i][j][0]=true;
				if(j==W-1)walls[i][j][2]=true;
			}
		}
		for (int i = 0; i < N; ++i) {
			int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
			if (x1 == x2) {
				int u=max(y1,y2);
				int d=min(y1,y2);
				assert(x1>0&&x1<W);
				for (int y = d; y < u; ++y) {
					walls[y][x1-1][2]=true;
					walls[y][x1][0]=true;
				}
			}
			else {
				int l=min(x1,x2);
				int r=max(x1,x2);
				assert(y1>0&&y1<H);
				for (int x = l; x < r; ++x) {
					walls[y1][x][1]=true;
					walls[y1-1][x][3]=true;
				}
			}
		}
		int sx,sy,gx,gy,sway;
		{
			int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
			if (x1 == x2) {
				if (x1 == 0) {
					sway=2;
					sx=0;
					sy=min(y1,y2);
				}
				else {
					sway=0;
					sx=W-1;
					sy=min(y1,y2);
				}
			}
			else {
				if (y1 == 0) {
					sway=3;
					sy=0;
					sx=min(x1,x2);
				}
				else {
					sway=1;
					sy=H-1;
					sx=min(x1,x2);
				}
			}
		}
		cin>>gx>>gy;
		int ans=0;
		{
			int nx=sx;
			int ny=sy;
			int nway=sway;
			while (true) {
				if(nx==gx&&ny==gy)break;
				if (ans > 100000) {
					ans=-1;
					break;
				}
				if (walls[ny][nx][(nway+1)%4]) {
					if (walls[ny][nx][nway]) {
						if (walls[ny][nx][(nway + 3) % 4]) {
							if (walls[ny][nx][(nway + 2) % 4]) {
								ans=-1;
								break;
							}
							else {
								nway=(nway+2)%4;
							}
						}
						else {
							nway=(nway+3)%4;
						}
					}
					else {
						nway=nway;
					}
				}
				else {
					nway=(nway+1)%4;
				}
				nx+=dx[nway];
				ny+=dy[nway];
				ans++;
			}
		}
		if (ans == -1) {
			cout<<"Impossible"<<endl;
		}
		else {
			cout<<ans+1<<endl;
		}
	}
	
	return 0;
}


Measured memory_bytes: 3720
#include <stdio.h>

int main() {
	int m, f, r;
	char grade;
	while (1)
	{
		scanf("%d %d %d", &m, &f, &r);
		if (m == -1 && f == -1 && r == -1)break;
		if (m == -1 || f == -1)grade = 'F';
		else if (m + f >= 80)grade = 'A';
		else if (m + f >= 65)grade = 'B';
		else if (m + f >= 50)grade = 'C';
		else if (m + f >= 30 && r >= 50)grade = 'C';
		else if (m + f >= 30)grade = 'D';
		else grade = 'F';
		printf("%c\n", grade);
	}
	return 0;
}

Measured memory_bytes: 2620
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
typedef long long ll;
#define MAX 100100
using namespace std;

vector<int> e[MAX];
int vu[MAX], vv[MAX];

void f(int x, int* v) {
	for (int i = 0; i < e[x].size(); i++) {
		if (v[e[x][i]] == 0) {
			v[e[x][i]] = v[x] + 1;
			f(e[x][i], v);
		}
	}
}
int main()
{	
	int N, u, v; 
	scanf("%d%d%d", &N, &u, &v);
	for (int i = 0; i < N - 1; i++) {
		int x, y; scanf("%d%d", &x, &y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	vu[u] = 1;
	f(u, vu);
	vv[v] = 1;
	f(v, vv);
	int max = 0;
	for (int i = 1; i <= N; i++) {
		if (vu[i] < vv[i] && max < vv[i]) max = vv[i];
	}
	printf("%d", max - 2);
	return 0;
}

Measured memory_bytes: 10368
N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
a = A.sort

n = N
max = a[-1]

res =  (1..max).bsearch do |d|
    c = 0
    failed = false
    a.each do |x|
        next if x <= d
        c += (x.to_f / d).floor
        if c > K
            failed = true
            break
        end
    end
    if failed
        false
    else
        true
    end
end
puts res

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

int main(){
  int n,i,buf;

  cin >> n;

  for(i=1 ; i<=n ; i++){
    buf = i;
    if(i%3==0){
      cout << " " << i;
    }else{
      while(buf != 0){
        if(buf%10 == 3){
          cout << " " << i;
          break;
        }
        buf/=10;
      }
    }
  }
  cout << endl;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
string s,t;
ll memo[3000][3000];
ll dir[3000][3000];

ll dp(ll i,ll j){
	if(i < 0 || j < 0) return 0;
	if(memo[i][j] != -1) return memo[i][j];
	ll ret;
	if(s[i] == t[j]){
		ret = 1 + dp(i-1,j-1);
		dir[i][j] = 1;
	}else{
		ll a = dp(i-1,j), b = dp(i,j-1);
		if(a > b){
			ret = a;
			dir[i][j] = 2;
		}else{
			ret = b;
			dir[i][j] = 3;
		}
	}
	memo[i][j] = ret;
	return ret;
}

void print(int i,int j){
	if(i < 0 || j < 0) return;
	if(dir[i][j] == 1){
		print(i-1,j-1);
		cout<<s[i];
	}else if(dir[i][j] == 2){
		print(i-1,j);
	}else{
		print(i,j-1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(memo,-1,sizeof(memo));
	cin>>s>>t;
	dp(s.length()-1,t.length()-1);
	print(s.length()-1,t.length()-1);
	cout<<"\n";
	return 0;
}

Measured memory_bytes: 141056
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	string X;
	cin >> X;
    if (X == "ABC") {
		cout << "ARC" << "\n";
	} else {
		cout << "ABC" << "\n";
	}
	
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define rev(v) reverse(v.begin(), v.end())
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
#define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin());
#define dab(v) for(auto i:v)cout<<i<<' '; cout << endl;
#define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
 
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    //cout << fixed << setprecision(15);
    
	int X,Y,A,B,C;cin>>X>>Y>>A>>B>>C;
	vl p(A), q(B),r(C);
	rep(i,A)cin>>p[i]; rep(i,B) cin>>q[i]; rep(i,C) cin>>r[i];
 
	ll ans = 0LL;
 
	sort(rall(p)); sort(rall(q)); sort(rall(r));
 
	rep(i,X) ans += p[i];
	rep(i,Y) ans += q[i];
	int id = 0;
	int nowp = X - 1; int nowq = Y - 1;
	while(true) {
 
		int nowid = id;
 
		if( nowp==-1 and nowq==-1) break;
		if(id >= C) break;
		if(nowp == -1 and r[id] <= q[nowq]) break;
		if(nowq == -1 and r[id] <= p[nowp]) break;

		if(nowq == -1) {
			while(r[id] > p[nowp]) {
				ans += r[id] - p[nowp];
				nowp -= 1;
				id++;
			}
			if( nowp==-1 and nowq==-1) break;
			if(id >= C) break;
			if(nowp == -1 and r[id] <= q[nowq]) break;
			if(nowq == -1 and r[id] <= p[nowp]) break;
			cout << ans << endl;
			return 0;
		}

		if(nowp == -1) {
			while(r[id] > q[nowq]){
				ans += r[id] - q[nowq];
				nowq -= 1;
				id++;
			}
			if( nowp==-1 and nowq==-1) break;
			if(id >= C) break;
			if(nowp == -1 and r[id] <= q[nowq]) break;
			if(nowq == -1 and r[id] <= p[nowp]) break;
			cout << ans << endl;
			return 0;
		}
 
 
		if(p[nowp] >= q[nowq]) {
			if(r[id] > q[nowq]) {
				ans += r[id] - q[nowq];
				nowq -= 1;
				id++;
			}
		}
 
		else {
			if(r[id] > p[nowp]) {
				ans += r[id] - p[nowp];
				nowp -= 1;
				id++;
			}
		}
		if(id == nowid) break;
	}
	cout << ans << endl;
    
}

Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<set>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
#define INF 1000000100
#define rep(i,n) for (int i=0;i<n;i++)

int main(){
    string s;
    cin >> s;
    bool ok=true;
    rep(i,s.size()){
        if((i+1)%2==1){
            if(s[i]!='R' && s[i]!='U' && s[i]!='D') ok=false;
        }else{
            if(s[i]!='L' && s[i]!='U' && s[i]!='D') ok=false;
        }
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3128
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void) {
int A,B;
scanf("%d %d",&A,&B);
if (A*B>=A-B && A*B>=A+B) printf("%d",A*B);
else if (A-B>=A*B && A-B>=A+B) printf("%d",A-B);
else if (A+B>=A-B && A+B>=A*B) printf("%d",A+B);
return EXIT_SUCCESS;
}


Measured memory_bytes: 128
#ABC050B

n=int(raw_input())
t=map(int,raw_input().split())
m=int(raw_input())
v=[]
for i in xrange(m):
 u=t[:]
 p,x=map(int,raw_input().split())
 u[p-1]=x
 v.append(sum(u))
for i in xrange(m):
 print v[i]


Measured memory_bytes: 2568
#include <iostream>
#include <string>
#include <bitset>
#include <vector>

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



int main(void) {
	int L, R, d;
	cin >> L >> R >> d;
	int ans;
	ans = (int)(R / d) - (int)(L / d);
	if (L%d == 0) ans++;

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

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

int d; //日数
const int z=26; //コンテスト数
vector<int> c(z); //コンテストiが開催されないペナルティ
vector<vector<int>> s; //i日目にコンテストjが開催された時の満足度

int score(vector<int> &t)
{
    int sum = 0;
    vector<int> last(z, -1); //コンテストが最後に開催された日
    for (int i = 0; i < t.size(); i++)
    {
        sum += s[i][t[i]];
        last[t[i]] = i;
        for (int j = 0; j < z; j++)
        {
            sum -= c[j] * ((i+1) - (last[j]+1));
        }
        
    }
    return sum;
}

void mix(vector<int> &a, vector<int> &b, int index)
{
    assert(index < d);
    assert(index >= 1);
    for (int i = 0; i < index; i++)
    {
        swap(a[i], b[i]);
    }
}


void Main()
{
    cin >> d;
    s = vector<vector<int>>(d, vector<int>(z));
    for (int i = 0; i < z; i++)
    {
        cin >> c[i];
    }
    for (int i = 0; i < d; i++)
    {
        for (int j = 0; j < z; j++)
        {
            cin >> s[i][j];
        }
    }

    const int n_change = 100;
    const int best_n = 64;
    const int mix_n = 128;

    std::mt19937 mt(rand());
    std::uniform_int_distribution<> randz(0, z-1);
    std::uniform_int_distribution<> rand_mix(1, d-1);
    std::uniform_int_distribution<> rand_sample(0, best_n-1);

    vector<vector<vector<int>>> ts(2, vector<vector<int>>(best_n+mix_n*2, vector<int>(d)));
    for (int i = 0; i < ts[0].size(); i++)
    {
        for (int j = 0; j < d; j++)
        {
            ts[0][i][j] = randz(mt);
        }
    }

    vector<pair<int, int>> scores;
    scores.reserve(ts[0].size());
    int w0 = 0, w1 = 1;
    for (int i = 0; i < n_change; i++)
    {
        scores.resize(0);
        for (int j = 0; j < ts[w0].size(); j++)
        {
            scores.push_back(make_pair(score(ts[w0][j]), j));
        }
        sort(scores.rbegin(), scores.rend());
        cerr << scores[0].first << endl;
        
        for (int j = 0; j < best_n; j++)
        {
            for (int k = 0; k < d; k++)
            {
                ts[w1][j][k] = ts[w0][scores[j].second][k];
            }
        }
        for (int j = 0; j < mix_n; j++)
        {
            int rand_a = rand_sample(mt);
            int rand_b = rand_sample(mt);
            for (int k = 0; k < d; k++)
            {
                ts[w1][best_n + 2*j][k] = ts[w1][rand_a][k];
                ts[w1][best_n + 2*j+1][k] = ts[w1][rand_b][k];
            }
            mix(ts[w1][best_n + 2*j], ts[w1][best_n + 2*j+1], rand_mix(mt));
        }

        swap(w0, w1);
    }

    for (int i = 0; i < d; i++)
    {
        cout << ts[w0][scores[0].second][i] + 1 << endl;
    }
    
}

int main(int argc, char **argv)
{
    Main();
    return 0;
}



Measured memory_bytes: 4852
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e8
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

struct P{
    int order;
    int pre;
    int year;
    string ans;
};
int main() {
    int n, m; cin >> n >> m;
    vector<P> v(m);
    rep(i,m){
        cin >> v[i].pre >> v[i].year;
        v[i].order = i;
    }

    sort(ALL(v),[](P a, P b){
        if(a.pre == b.pre){
            return a.year < b.year;
        }
        return a.pre < b.pre;
    });
    v[0].ans = string(6-to_string(v[0].pre).size(),'0') + to_string(v[0].pre) + "000001";
    int num = 1;
    REP(i,1,m){
        if(v[i].pre==v[i-1].pre){
            num++;
            v[i].ans = string(6-to_string(v[i].pre).size(),'0') + to_string(v[i].pre) + string(6-to_string(num).size(),'0') + to_string(num);
        }else{
            num = 1;
            v[i].ans = string(6-to_string(v[i].pre).size(),'0') + to_string(v[i].pre) + string(6-to_string(num).size(),'0') + to_string(num);
        }
    }
    sort(ALL(v),[](P a, P b){return a.order<b.order;});
    rep(i,m) cout << v[i].ans << endl;
    return 0;
}

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

static const ll MOD = 1000000007;
const int MAX = 100005;
static const int INF = 1 << 15;
int n, k;
int used[100005];
vector<int> G[100005];

ll ans = 0; 
ll node[100005];

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;
    }
}
 
long long Per(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[n - k] % MOD) % MOD;
}
 
void dfs(int v) {
    for (int i = 0; i < G[v].size(); i++) {
        if (node[G[v][i]] == 0) {
            node[v] += 1;
            dfs(G[v][i]);
        }
    }
    return;
}

void bfs() {
    queue<int> q;
    q.push(0);
    for (int i = 0; i < n; i++) {
        used[i] = INF;
    }
    used[0] = 0;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == 0) {
            ans += Per(k, node[0]);
            ans %= MOD;
        }
        else {
            ans *= Per(k - 2, node[u]);
            ans %= MOD;
        }
        for (int v: G[u]) {
            if (used[v] != INF) continue;
            used[v] = 0;
            q.push(v);
        }
    }
}
 
int main() {
    int u, v;
    cin >> n >> k;
    for (int i = 0; i < n-1; i++) {
        cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    COMinit();
    for (int i = 0; i < n; i++) node[i] = 0;
    node[0] = 1;
    dfs(0);
    bfs();
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int n;
long long k, x;

main(){
    cin >> k >> n;
    for (int i = 1; i <= n; i++){
        cin >> x;
        k -= x;
    }
    if (k < 0) cout << -1 << endl;
    else
        cout << k << endl;
}

Measured memory_bytes: 3636
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var ts = Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray();

        var zero = 0;
        var negative = 0;
        for (int i = 0; i < ts.Length; i++)
        {
            if (ts[i] < 0)
            {
                negative++;
            }
            else if (ts[i] == 0)
            {
                zero++;
            }
        }
        var k = ts.Sum(x => Math.Abs(x));
        if (negative % 2 == 1 && zero == 0)
        {
            var nonZeroMinimum = ts.Where(x => x != 0).Min(x => Math.Abs(x));
            k -= nonZeroMinimum * 2;
        }
        Console.WriteLine(k);
    }
}


Measured memory_bytes: 29404
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=1e5+10;
int a[maxn];
int b[maxn];
int c[maxn];
int sum=0;
int ans=0;
int kk=0;
struct Node
{
    int x,y;
}ss[maxn];
void solve(int sum,int pr,int ed,int pr2,int ed2)
{

      int f=b[0];
      int z=c[0];
      for(int i=pr;i<ed;i++)
      {
          ss[kk].x=z,ss[kk++].y=b[i];

          z=z-b[i];
      }
      for(int i=pr2;i<ed2;i++)
      {
         // cout<<f<<' '<<c[i]<<endl;
          ss[kk].x=f,ss[kk++].y=c[i];
          f=f-c[i];
      }
      ss[kk].x=z,ss[kk++].y=f;

     ans=z-f;

}
int main()
{

  	cin>>n;
	int k=0,j=0;
	for(int  i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int m=-a[0]+a[n-1];
    for(int i=1;i<n-1;i++)
        m+=abs(a[i]);
        cout<<m<<endl;
        int x=a[0];int y=a[n-1];
    for(int i=1;i<n-1;i++)
    {
        if(a[i]<0)
            printf("%d %d\n",y,a[i]),y-=a[i];
        else
            printf("%d %d\n",x,a[i]),x-=a[i];
    }
    cout<<y<<' '<<x<<endl;

	return 0;
}


Measured memory_bytes: 2304
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

using Pi = pair<int, int>;
using ll = long long;
const int INF = 1 << 28;

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

void get() {}

template <class Head, class... Tail>
void get(Head& head, Tail&... tail) {
  cin >> head;
  get(tail...);
}

template <class T>
void getv(vector<T>& vec) {
  for (int i = 0; i < vec.size(); ++i)
    cin >> vec[i];
}

int main() {
  int N;
  get(N);
  vector<int> p(N);
  getv(p);
  vector<int> a(N), b(N);
  FOR(i, N) {
    a[i] = (i + 1) * 30000;
    b[i] = (N - i) * 30000;
  }
  FOR(i, N) { a[p[i] - 1] += i; }
  FOR(i, N) cout << a[i] << " ";
  cout << endl;
  FOR(i, N) cout << b[i] << " ";
  cout << endl;
  return 0;
}

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


int main(){
    ll n;   cin >> n;
    ll ans=1e+15;
    for(ll i=1; i<=sqrt(n); i++){
        if(n%i==0)
            ans = min(ans, abs(n/i+i)-2);

    }
    if(ans==1e+15) ans=n-1;
    cout << ans << endl;
}

Measured memory_bytes: 256
//




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


#define spdio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define pp pop_back()
#define pf push_front
#define ppf pop_front()
#define ff first
#define ss second
#define mp make_pair
#define fr(i,j,n) for(ll i=j; i<n; i++)
#define rfr(i,j,n) for(ll i=n-1; i>=j; i--)
#define pll pair<ll,ll>
#define plb pair<ll,bool>
#define psl pair<string,ll>
#define psb pair<string,bool>
#define srt(v) sort((v).begin(),(v).end())
#define ub(v,val) upper_bound((v).begin(),(v).end(),(val))-(v).begin()
#define lb(v,val) lower_bound((v).begin(),(v).end(),(val))-(v).begin()


typedef long double ld;
typedef long long int ll;


//getline(cin,string);
const ll inf = (ll) 1e18 + 19;
const ll mod = (ll) 1e9  +  7;




void cazz() {
    ll t=1,i=0,j,n;
    //cin>>t;
    while(t--) {
        string s1,s2;
        cin>>s1>>s2;
        vector <vector <ll> > dp(s1.length()+1,vector <ll> (s2.length()+1));
        //lcs(dp,s1,s2,0,0);
        rfr(i,0,s1.length()) {
            rfr(j,0,s2.length()) {
                if(s1[i]==s2[j]) dp[i][j]=dp[i+1][j+1]+1;
                else dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
            }
        }
        i=j=0;
        string s="";
        while(i<s1.length() && j<s2.length()) {
            if(s1[i]==s2[j]) {
                s+=s1[i];
                i+=1;
                j+=1;
            }
            else if(dp[i+1][j]>dp[i][j+1]) i+=1;
            else j+=1;
        }
        cout<<s<<"\n";
    }
}




int main() {
    spdio;
	cazz();
	return 0;
}


Measured memory_bytes: 73636
#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 2010

using namespace std;

int n,m,q;
int a[N][N];
int b[N][N],c[N][N];
char s[7007];
inline int calc(int a[N][N],int x1,int y1,int x2,int y2){
    if(x1>x2||y1>y2) return 0;
    return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}
int main() {
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1);
		for(int j=1;j<=m;j++)
            a[i][j]=s[j]-'0';
    }
    for(int i=2;i<=n;i++)
        for(int j=1;j<=m;j++)
            b[i][j]=a[i][j]&a[i-1][j];
    for(int i=1;i<=n;i++)
        for(int j=2;j<=m;j++)
            c[i][j]=a[i][j]&a[i][j-1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) { 
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            b[i][j]=b[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
            c[i][j]=c[i][j]+c[i-1][j]+c[i][j-1]-c[i-1][j-1];
    }
    while(q--) {
        int x1,x2,y1,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",calc(a,x1,y1,x2,y2)-calc(b,x1+1,y1,x2,y2)-calc(c,x1,y1+1,x2,y2));
    }
    return 0;
}

Measured memory_bytes: 49024
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
s=input()
if s[-1]=="s":
    print(s+"es")
else:
    print(s+"s")

Measured memory_bytes: 9332
// #define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef map<int, int> MAPII;

#define MP make_pair
#define fastIO	cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
//for gcc (未test)
// #define FOREACH_IT(it,c)	for(typeof(c)::iterator it=(c).begin(); it!=(c).end(); ++it)
//for Visual Studio
#define foreach_it(type,it,c) for(type::iterator it=c.begin(), c_end=c.end(); it!=c_end; ++it)

bool solve2(int i){
	while (i % 5 == 0)	i /= 5;
	while (i % 3 == 0)	i /= 3;
	while (i % 2 == 0)	i /= 2;
	if (i == 1)	return true;
	return false;
}

int main(){
	// respect http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=226655#1
	fastIO;
	int m = 0, n = 0, out = 0;

	while (cin >> m, m){
		cin >> n;
		out = 0;
		for (int i = m; i <= n; i++)
			if (solve2(i))
				out++;
		cout << out << endl;
	}
	return 0;
}

Measured memory_bytes: 1192
#include <stdio.h>
#include <stdlib.h>
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

void yes_or_no(char boolean){
    if(boolean){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
}

int comp(const void *a, const void *b){
    return *(long long*)b - *(long long *)a > 0? 1 : -1;
}

int main(){
    long long N, H;
    long long i;
    scanf("%lld %lld", &N, &H);

    long long use[N], throw[N];
    long long max = 0;

    for(i = 0; i < N; ++i){
        scanf("%lld %lld", &use[i], &throw[i]);

        if(max < use[i]){
            max = use[i];
        }
    }

    qsort(throw, N, sizeof(long long), comp);

    long long count = 0;
    for(i = 0; i < N; ++i){
        if(throw[i] < max || H <= 0){
            break;
        }
        H -= throw[i];
        count++;
    }
    if(max > 1 && H > 0){
        count += H/max;

        if(H % max > 0){
            count++;
        }
    }else if(max == 1 && H > 0){
        count += H;
    }
    printf("%lld\n", count);
    return 0;
}

Measured memory_bytes: 2556
#include<iostream>
#include<vector>

using namespace std;

int main()
{
  int n,m;
  cin >> m >> n;
  
  vector<int> per;
  vector<vector<int> > G;
  G.resize(m);
  bool used[m]; 
  per.resize(m);
  for(int i=0;i<m;i++)
    per[i] = 0,used[i] = false;
  for(int i=0;i<n;i++)
    {
      int x,y;
      cin >> x >> y;
    
      x--,y--;
      per[y]++;
      G[x].push_back(y);
    }
  used[1] = true;
  
  
  for(int i=0;i<m;i++)
    {
      for(int j=0;j<m;j++)
	{
	  if(used[j])
	    continue;
	  if(!per[j])
	    {
	      used[j] = true;
	      cout << j+1 << endl;
	      for(int k=0;k<G[j].size();k++)
		per[G[j][k]]--;
	    }
	}
    }

  cout << 2 << endl;
  return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
const long long mod=1e9+7;
typedef long long ll;
using namespace std;

ll f[1000010],revf[1000010];

ll qpow(ll a,ll b){
  ll ret=1;
  while(b){
    if(b&1) ret=(ret*a)%mod;
    a=(a*a)%mod;
    b>>=1;
  }
  return ret;
}

void init(){
  f[0]=1; revf[0]=qpow(f[0],mod-2);
  for(ll i=1;i<1000010;i++){
    f[i]=i*f[i-1]%mod;
    revf[i]=qpow(f[i],mod-2);
  }
}

ll C(ll n,ll m){
  return (f[n]*revf[m])%mod*revf[n-m]%mod;
}

ll count_ways(ll a,ll b,ll c,ll d){
  ll tot=(c-a)+(d-b);
  ll down=(c-a);
  ll ret=C(tot,down);
  return ret;
}

int main()
{
    init();
    ll h,w,a,b;
    cin>>h>>w>>a>>b;
    ll tot=count_ways(1,1,h,w);
    for(ll i=1;i<=b;i++){
        ll tmp=count_ways(1,1,h-a,i)*count_ways(h-a+1,i,h,w)%mod;
        while(tot<tmp) tot+=mod;
        tot=(tot-tmp)%mod;
    }
    cout<<tot<<endl;
    return 0;
}

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

int main()
{
	int a, b;
	cin >> a >> b;
	int d = a + b;
	int e = a - b;
	int f = a * b;
	int g;
	if (a + b > a - b)
	{
		g = a + b;
	}
	else
	{
		g = a - b;
	}
	if (a * b > g)
	{
		g = a * b;
	}
	cout << g;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#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;i>=0;i--)
#define INF 100000005
#define MAX 1002
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

int main(){
	int n, a, b, c, d, t1, t2, t3;
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	t1 = a/c;t2 = b/d;
	if(t1*c != a)t1++;
	if(t2*d != b)t2++;
	t3 = max(t1, t2);
	printf("%d\n", n-t3);
	return 0;
}

Measured memory_bytes: 3208
#include <bits/stdc++.h>
using namespace std;
const int MAX = 500005;
int block;
struct Query
{
    int L, R, index, result;
};
bool compare(Query x, Query y)
{
    if (x.L / block != y.L / block)
        return x.L / block < y.L / block;
    return x.R < y.R;
}
bool compare1(Query x, Query y)
{
    return x.index < y.index;
}
void queryResults(int a[], int n, Query q[], int m)
{
    block = (int)sqrt(n);
    sort(q, q + m, compare);
    int currL = 0, currR = 0;
    int curr_Diff_elements = 0;
    int freq[MAX] = {0};
    for (int i = 0; i < m; i++)
    {

        int L = q[i].L, R = q[i].R;

        while (currL < L)
        {

            freq[a[currL]]--;
            if (freq[a[currL]] == 0)
                curr_Diff_elements--;

            currL++;
        }

        while (currL > L)
        {
            freq[a[currL - 1]]++;

            if (freq[a[currL - 1]] == 1)
                curr_Diff_elements++;

            currL--;
        }
        while (currR <= R)
        {
            freq[a[currR]]++;

            if (freq[a[currR]] == 1)
                curr_Diff_elements++;

            currR++;
        }

        while (currR > R + 1)
        {

            freq[a[currR - 1]]--;

            if (freq[a[currR - 1]] == 0)
                curr_Diff_elements--;

            currR--;
        }
        q[i].result = curr_Diff_elements;
    }
}

void printResults(Query q[], int m)
{
    sort(q, q + m, compare1);
    for (int i = 0; i < m; i++)
    {
        cout << q[i].result << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    int a[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    Query q[m];
    for (int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        q[i].index = i;
        q[i].L = l - 1;
        q[i].R = r - 1;
        q[i].result = 0;
    }
    queryResults(a, n, q, m);
    printResults(q, m);
    return 0;
}


Measured memory_bytes: 15472
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <iomanip>
#include <map>
#include <stack>
#include <queue>
#include <sstream>
#include <bitset>

using namespace std;

typedef long long ll;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n,a,b,c,d;
    string s;
    cin>>n>>a>>b>>c>>d;
    cin>>s;
    bool flag = 1;
    if(c>d){
        flag=0;
        for(ll i=b-2;i<d-1;i++){
            if(s[i]=='.' && s[i+1]=='.' && s[i+2]=='.') flag=1;
        }
    }
    for(ll i=a;i<max(c,d)-1;i++){
        if(s[i-1]=='#' && s[i]=='#') flag=0;
    }
    
    
    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 592
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
int main(){
  ll N,M,i,a,b,c;scanf("%lld%lld",&N,&M);
  priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q;
  for(i=0;i<N;i++){
    scanf("%lld",&a);
    q.push(make_pair(a,1));
  }
  pair<ll,ll> t[M];
  for(i=0;i<M;i++) scanf("%lld%lld",&t[i].second,&t[i].first);
  sort(t,t+M,greater<pair<ll,ll>>());
  ll fc,fn,tn;
  for(i=0;i<M;i++){
    b = t[i].second;c = t[i].first;
    tn = 0;
    while(b){
      fc = q.top().first;fn = q.top().second;q.pop();
      if(fc >= c){
        q.push(make_pair(fc,fn));
        break;
      }
      if(fn <= b){
        tn += fn;
        b -= fn;
      } else {
        tn += b;
        q.push(make_pair(fc,fn-b));
      }
    }
    if(tn) q.push(make_pair(c,tn));
  }
  ll ans = 0;
  while(!q.empty()){
    ans += q.top().first*q.top().second;
    q.pop();
  }
  printf("%lld\n",ans);
}


Measured memory_bytes: 6356
/// In The Name Of God

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)1000 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, m;
char a[N][N];

bool was[N][N];

bool check(int x, int y) {
	return 1 <= x && x <= n && 1 <= y && y <= m;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> m;

	vector < pair <int, int> > q;
	rep(i, 1, n) {
		cin >> a[i] + 1;
		rep(j, 1, m) {
			if (a[i][j] == '#') {
				q.pb({i, j});
				was[i][j] = 1;
			}
		}
	}

	int ans = 0;
	while (sz(q)) {
		vector < pair <int, int> > nq;
		++ans;
		while (sz(q)) {
			pair <int, int> v = q.back();
			q.pp();
			rep(i, 0, 3) {
				int nx = v.f + dx[i], ny = v.s + dy[i];
				if (check(nx, ny) && a[nx][ny] == '.') {
					a[nx][ny] = '#';
					nq.pb({nx, ny});
				}
			}
		}
		q = nq;
	}

	cout << max(0, ans - 1);
	ioi
}


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

ll a[200010], b[200010];

int main()
{
    ll n, m, k;
    ll ans;

    cin >> n >> m >> k;
    a[0] = 0;
    for (int i = 1;i <= n;++i) {
        cin >> a[i];
        a[i] += a[i-1];
    }
    b[0]=0;
    for (int i = 1;i <= m;++i) {
        cin >> b[i];
        b[i] += b[i-1];
    }

    ans = 0;
    ll j = m;
    for (int i = 0;i <= n;++i) {
        if (a[i] > k)
            break;

        while (a[i] + b[j] > k){
            --j;
        }
        ans = max(ans, i + j);
    }

    std::cout << ans << endl;

    return(0);
}



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

constexpr auto mod = static_cast<ulong>(1e9+7);

int main() 
{
    ulong N;
    cin>>N;
    vector<ulong>A(N);
    vector<ulong>sum(N+1,0);
    for (size_t i = 0; i < N; i++)
    {
        cin>>A[i];
        sum[i+1]=sum[i]+A[i];
    }

    ulong ans = 0;
    for (size_t i = 0; i < N; i++)
    {
        ulong s=(sum[N]-sum[i+1])%mod;
        ans += A[i] * s;
		ans %= mod;
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 6416
#include <bits/stdc++.h>
const int INF = 1e17;
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a, b;
    cin >> a >>b;
    a = "#"+a;
    b = "#"+b;
    int tab[a.size()][b.size()];
    for(int  i= 0; i < a.size();i++){
        tab[i][0] = 0;
    }
    for(int  i= 0; i < b.size();i++){
        tab[0][i] = 0;
    }
    for(int i = 1; i <a.size(); i++){
        for(int j = 1; j <b.size(); j++){
            if(a[i] == b[j]){
                tab[i][j] = tab[i-1][j-1]+1;
            }else{
                tab[i][j] = max(tab[i-1][j], tab[i][j-1]);
            }
        }
    }
    string odp = "";
    int x = b.size()-1;
    int y = a.size()-1;
    while(x >= 1 && y>=1){
        if(a[y] == b[x]){
                odp+=b[x];
                x--;
                y--;
        }else{
                if(tab[y][x-1] > tab[y-1][x]){
                    x--;
                }else{
                    y--;
                }
        }
    }
    for(int  i = odp.size()-1; i > -1; i--){
        cout << odp[i];
    }
    return 0;
}



Measured memory_bytes: 35456