akhauriyash/Code-Regression huggingface dataset:
X, Y = map(int,input().split())
n = int((2*Y-X)/3)
m = int((2*X-Y)/3)
if (X+Y)%3!=0:
  print(0)
  exit()
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 10 ** 9 + 7
N = 10 ** 6  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
print(cmb(n+m, n, p))

Measured memory_bytes: 122000
MOD=10**9+7
L=input()
N=len(L)
ans,lbit=0,0
for i in range(N):
    if L[i]=='0':
        continue
    ans=(ans+(pow(3,N-i-1,MOD)*pow(2,lbit,MOD)%MOD))%MOD
    lbit+=1
print((ans+pow(2,lbit,MOD))%MOD)

Measured memory_bytes: 3188
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

N_list = [int(s) for s in str(N)]

if sum(N_list) % 9 == 0:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 11948
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#define int long 
using namespace std;

signed main() {
	string A,B,C;
  	cin >> A >> B >> C;
	cout << "A" << B.at(0) << "C" << endl;
}

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

using namespace std;

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

typedef long long ll;

int p[10000];
int d[10000];

int main(){
	int n;
	
	while (cin >> n, n){
		int ma = 0, ma_d = 0;
		REP(i,n){
			int d2;
			scanf("%d %d %d", &p[i], &d[i], &d2);
			d[i] += d2;
			
			if (ma_d < d[i]){
				ma = i;
				ma_d = d[i];
			}
		}
		
		cout << p[ma] << " " << ma_d << endl;
	}
	
	return 0;
}

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

#define ll long long 
#define N 300005
#define m 998244353

ll A[N]={1,1};
ll B[N]={1,1};
ll C[N]={1,1};

ll n,a,b,k,ans ;

ll sum(ll p){
	return A[n]*C[n-p] %m *C[p] %m ;
}

int main(){
	scanf("%lld%lld%lld%lld",&n,&a,&b,&k) ;	
	for (ll i=2;i<=n;i++){
		A[i]=A[i-1]*i%m ;
		B[i]=B[m%i]*(m-m/i)%m ;
		C[i]=C[i-1]*B[i]%m ; 
	}
	for (ll i=0;i<=n;i++){
		ll t=k-a*i ;
		if (t<0) break ;
		if (t%b==0 && t/b<=n) ans+=sum(i)*sum(t/b)%m ;
	}
	printf("%d\n",ans%m) ;
	return 0 ;
}

Measured memory_bytes: 7296
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
 
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt(), Q = sc.nextInt();
    String S = sc.next();
    int A[] = new int[S.length() + 1];
    for (int i = 1; i < S.length(); i++)
    {
      if (S.charAt(i - 1) == 'A' && S.charAt(i) == 'C')
      {
        A[i] = 1;
      }
      else
      {
        A[i] = 0;
      }
    }
    int PSA[] = new int[S.length() + 1];
    for (int i = 1; i <= S.length(); i++)
    {
      PSA[i] = PSA[i - 1] + A[i];
    }
    for (int i = 0; i < Q; i++)
    {
      int l = sc.nextInt(), r = sc.nextInt();
      int result = PSA[r - 1] - PSA[l - 1];
      System.out.println(result);
    }
  }
}


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

#define TYPE(c)   remove_reference_t<decltype(c)>
#define REP(i, n) for(TYPE(n) i = 0; i < n; i++)
#define FOR(v, c) for(TYPE(c.begin()) v = c.begin(); v != c.end(); v++)
#define ALL(c)    c.begin(), c.end()
#define SORT(c)   sort(ALL(c))
#define RSORT(c)  sort(ALL(c), greater<TYPE(c)::value_type>())
#define UNIQUE(c) c.erase(unique(ALL(c)), c.end())

using namespace std;
using ll = long long;

constexpr int MOD  = (int)1e9 + 7;
constexpr int INF  = (int)1e9 + 1;
constexpr ll  LINF = (ll)1e18 + 1;
template<typename T> constexpr bool chmax(T& a, const T& b)
{ if(a < b) { a = b; return true; } else { return false; } }
template<typename T> constexpr bool chmin(T& a, const T& b)
{ if(b < a) { a = b; return true; } else { return false; } }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T>& p)
{ return os << "(" << p.first << "," << p.second << ")"; }
ostream& operator<<(ostream &os, const string& s)
{ FOR(v, s) os << *v; return os; }
template<typename T> auto operator<<(ostream& os, const T& t)
  -> typename conditional<true, ostream&, decltype(*t.begin())>::type
{ os << "["; FOR(v, t) { if(v != t.begin()) os << ","; os << *v; } os << "]"; return os; }

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

  int N;
  std::cin >> N;
  string C;
  std::cin >> C;

  int ans = 0;
  int i_back = N;
  REP(i, N) {
    if(C[i] == 'W') {
      while(i < i_back) {
        if(C[i_back] == 'R') {
          C[i_back] = 'W';
          ans++;
          break;
        }
        i_back--;
      }
    }
    if(i == i_back) break;
  }
  std::cout << ans << std::endl;

  return 0;
}


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

int main(){
  
  int X;
  
  cin >> X;
  
  if(X == 3 || X == 5 || X == 7){
    cout << "YES" << endl;
  }
    
  else{
    cout << "NO" << endl;
  }
    
}

Measured memory_bytes: 256
n=int(input())
al=list(map(int,input().split()))
bl=list(map(int,input().split()))
ail=[(i,a) for i,a in enumerate(al)]
bil=[(i,b) for i,b in enumerate(bl)]
ail=sorted(ail,key=lambda x:x[1])
bil=sorted(bil,key=lambda x:x[1])
if not all([ail[i][1]<=bil[i][1] for i in range(n)]):
    print('No')
    exit()
if any([ail[i+1][1]<=bil[i][1] for i in range(n-1)]):
    print('Yes')
    exit()
c=[(ail[i][0],bil[i][0]) for i in range(n)]
c=sorted(c)
idx=0
for _ in range(n-1):
    idx=c[idx][1]
    if idx==0:
        print('Yes')
        break
else:
    print('No')

Measured memory_bytes: 41716
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		
		while(stdIn.hasNext()){
			int[] a = new int[4];
			int[] b = new int[4];
			for(int i=0;i<4;i++){
				a[i] = stdIn.nextInt();
			}
			for(int i=0;i<4;i++){
				b[i] = stdIn.nextInt();
			}
			int hit = 0;
			int blow = 0;
			for(int i=0;i<4;i++){
				for(int j=0;j<4;j++){
					if(a[i]==b[j]){
						if(i==j){
							hit++;
						}
						else{
							blow++;
						}
					}
				}
			}
			System.out.println(hit+" "+blow);
		}
	}
}

Measured memory_bytes: 16300
n,k=gets.split.map(&:to_i)
v=gets.split.map(&:to_i)

p (0..[n,k].min).map{|a|
  (0..[n-a,k-a].min).map{|b|
    l = (v[0,a]+v[-b,b]).sort
    drop_cnt = k-a-b
    minus_cnt = l.count{|i|i<=0}
    l.drop([drop_cnt,minus_cnt].min).inject(:+)||0
  }.max
}.max

Measured memory_bytes: 2044
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
typedef long long ll;
const int MAXN=2e5+7;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int arr[MAXN];

int n,a,b;
bool check(ll x)
{
    ll lazy=b*x;
    ll need=0;
    for(int i=0;i<n;++i)
    {
        if(arr[i]<=lazy) continue;
        else
        {
            need+=(arr[i]-lazy)/(a-b);
            if((arr[i]-lazy)%(a-b)) need++;
        }
    }
    return need<=x;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>a>>b;
    int mx=0;
    for(int i=0;i<n;++i)
        cin>>arr[i];
    int ans=INF;
    int l=1,r=1e9/b+1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid))
        {
            ans=min(ans,mid);
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<string> a(n), b(m);
	rep(i, n) cin >> a[i];
	rep(i, m) cin >> b[i];
	for (int di = 0; di <= n - m; ++di) {
		for (int dj = 0; dj <= n - m; ++dj) {
			bool ok = true;
			rep(i, m) {
				rep(j, m) {
					if (b[i][j] != a[i + di][j + dj]) ok = false;
				}
			}
			if (ok) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	return 0;
}


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

int digit_sum(int n)
{
    int s = 0;
    while (n != 0) {
        s += n % 10;
        n /= 10;
    }
    return s;
}

int main()
{
    int n, a, b;
    cin >> n >> a >> b;

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int s = digit_sum(i);
        if (a <= s && s <= b) {
            ans += i;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main ()
{
	ll a,z = 1;
	cin>>a;
	ll ar[a];
	for(ll i = 0; i<a; i++)
	{
		cin>>ar[i];
		if (ar[i] == 0)
		{
			cout<<0<<endl;
			exit(0);
		}
		
	}
	for (ll i = 0; i<a; i++)
	{

		if(z>1000000000000000000/ar[i])
		{
			cout<<-1<<endl;
			exit(0);
		}
		z*=ar[i];
	}
	cout<<z<<endl;
	return 0;
}

Measured memory_bytes: 4384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

typedef vector<vector<pair<double,int>>> wgraph;
typedef pair<double,int> pli;

vector<double> bfs(wgraph v,int x){
  priority_queue<pli,vector<pli>,greater<pli>> q;
  vector<double> dist(v.size(),1e18);
  dist[x]=0;
  q.push({0LL,x});

  while(q.size()){
    pli p=q.top(); q.pop();
    double d=p.F;int now=p.S;
    if(dist[now]<d){ continue; }
    for(auto to:v[now]){
      if(dist[to.S]>d+to.F){
        dist[to.S] = d+to.F;
        q.push({dist[to.S], to.S});
      }
    }
  }
  return dist;
}


int main(){
  vector<int> x(1010,0),y(1010,0),r(1010,0);
  rep(i,2){
    cin >> x[i] >> y[i];
  }
  int n;
  cin >> n;
  n+=2;
  REP(i,2,n){
    cin >> x[i] >> y[i] >> r[i];
  }
  wgraph v(n);
  rep(i,n)rep(j,n)if(i!=j){
    double X = (x[i]-x[j]);
    double Y = (y[i]-y[j]);
    double z = sqrtl(X*X+Y*Y)-r[i]-r[j];
//    double z = hypot(x[i]-x[j],y[i]-y[j])-r[i]-r[j]; //どっちでも
    z = max(z,0.0);
    v[i].emplace_back(z,j);
  }
  vector<double> dist=bfs(v,0);
  double ans = dist[1];
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}

Measured memory_bytes: 38000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
ld eps=1e-7,pi=acos(-1);
 
int n,m,x,y,dist[100100];
vector<int>adj[100100];
 
int dfs(int node)
{
if(dist[node])return dist[node];
int res=0;
 
for(auto nx:adj[node])
{
res=max(res,dfs(nx));
}
 
return dist[node]=res+1;
}
 
int main()
{
 
scanf("%d %d",&n,&m);
 
for(int i=0;i<m;i++)
{
scanf("%d %d",&x,&y);
adj[x].push_back(y);
}
 
int ans=0;
 
for(int i=1;i<=n;i++)
ans=max(ans,dfs(i));
 
printf("%d",ans-1);
 
return 0;
}

Measured memory_bytes: 8192
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }
void Taka() { cout << "Takahashi" << endl; }
void Aoki() { cout << "Aoki" << endl; }
void digit(int d) { cout << fixed << setprecision(d); }
void IOup() { cin.tie(0); ios::sync_with_stdio(false); }

int c, n, p[1000][1000], d, y, x;

int main() {
	cin >> c >> n;
	char ch;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> ch;
			p[i][j] = ch - '0';
		}
	}

	int q = 0;
	for (int i = 0; i < n / 2; ++i) {
		for (int j = 0; j < n / 2; ++j) {
			if (p[i][j] != p[i][n - j - 1])
				q++;
			if (p[i][j] != p[n - i - 1][j])
				q++;
		}
	}
	for (int i = n / 2; i < n; ++i) {
		for (int j = n / 2; j < n; ++j) {
			if (p[i][j] != p[i][n - j - 1])
				q++;
			if (p[i][j] != p[n - i - 1][j])
				q++;
		}
	}

	int ans = q == 0 ? 1 : 0;
	for (int i = 0; i < c - 1; ++i) {
		cin >> d;
		for (int j = 0; j < d; ++j) {
			cin >> y >> x;
			y--; x--;
			p[y][x] = !p[y][x];
			if (p[y][x] == p[y][n - x - 1])
				q--;
			else
				q++;
			if (p[y][x] == p[n - y - 1][x])
				q--;
			else
				q++;
		}
		if (q == 0)
			ans++;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 6976
#include <stdio.h>

int main(){
  int i,j,n,count=0,mini;
  scanf("%d",&n);
  int a[n];

  for(i=0; i<n; i++)
    scanf("%d",&a[i]);
  
  for(i=0; i<n; i++){
    mini = i;
    for(j=i; j<n; j++)
      if(a[j] < a[mini])
	mini = j;
    if(mini != i){    
      int tmp = a[i];
      a[i] = a[mini];
      a[mini] = tmp;
      count++;
    }
  }
  
  for(i=0; i<n-1; i++)
    printf("%d ",a[i]);
  
  printf("%d\n%d\n",a[n-1],count);
  return 0;
}

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

int main(){
    int a,b;    cin >> a >> b;
    --a;    --b;
    rep(i, 3){
        if(i != a && i != b){
            cout << i+1 << endl;
        }
    }
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    A=lmis()
    if H<=sum(A):
        print('Yes')
    else:
        print('No')



main()


Measured memory_bytes: 16244
#include <bits/stdc++.h>
using namespace std;
int main(void){
    vector<int> vec(0);
    int s;
    for(int i = 0;i < 3;i++){
        cin >> s;
        vec.push_back(s);
    }
    sort(vec.begin(),vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    cout << vec.size() << endl;
}


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

using namespace std;

int main() {
	string s;
	cin >> s;
	int b = s[0] == 'A'&&s[1] >= 'a'&&s.back() >= 'a';
	int c = 0, a = 0;
	for (int i = 2; i + 1 < s.length(); i++) {
		if (s[i] == 'C') c++;
		if (s[i] < 'a') a++;
	}
	cout << (b&&c == 1 && a == 1 ? "AC" : "WA") << endl;
	return 0;
}


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

void buy (int price, long long& money, long long& stock) {
    stock = money / price;
    money -= price * stock;
}
void sell (int price, long long& money, long long& stock) {
    money += price * stock;
    stock = 0;
}

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<bool> diff(N); // plus のときtrue
    for (int i = 1; i < N; i++) {
        diff[i] = A[i] > A[i-1];
    }

    int last_index = 0;
    for (int i = N-1; i >= 1; i--) {
        if (diff[i]) {
            last_index = i; 
            break;
        }
    }

    int index = 1;
    long long money = 1000;
    long long stock = 0;
    
    while (index <= last_index) {
        while (!diff[index]) index++;
        // cout << "buy:" << index-1 << endl;
        buy(A[index-1], money, stock);
        while (diff[index]) index++;
        // cout << "sell:" << index-1 << endl;
        sell(A[index-1], money, stock);
    }
    cout << money << endl;
}

Measured memory_bytes: 3632
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<random>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde) FUNC(printdu);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ return in >> p.first >> p.second; }
template <class T>
istream& operator >> (istream& in, vector<T>& v){ for(auto& e : v){ in >> e; } return in; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int d; cin >> d;
    cout << "Christmas";
    for(int i = 0; i < 25 - d; i++){
        cout << " Eve";
    }
}


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

using namespace std;

const int MX = 1e9 + 10;
const int N = 2e5 + 10;

pair<int, int> s[N];
pair<int, int> x[N];
int b[N];
int n;

int main() {

  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> s[i].first >> s[i].second;
  }

  int ans = 0;
  int mx = 0, mn = 0;
  for (int i = 0; i < n; ++i) {
    ans = max(ans, s[i].second - s[i].first + 1);
    if (s[i].first > s[mx].first) mx = i;
    if (s[i].second < s[mn].second) mn = i;
  }

  for (int i = 0; i < n; ++i) {
    ans = max(ans, max(s[mn].second - s[mx].first + 1, 0) + s[i].second - s[i].first + 1);
    x[i] = {
      max(0, s[i].second - s[mx].first + 1),
      max(0, s[mn].second - s[i].first + 1)
    };
  }

  sort(x, x+n, [](auto a, auto b) {
      if (a.first == b.first) return a.second < b.second;
      return a.first > b.first;
  });

  for (int i = n-1; i >= 0; --i) {
    b[i] = (i == n-1 ? x[i].second : b[i+1]);
    b[i] = min(b[i], x[i].second);
  }

  for (int i = 0; i < n-1; ++i) {
    ans = max(ans, x[i].first + b[i+1]);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2176
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
#define endn "\n"
typedef pair<int,int> P;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const int MOD = 1000000007;
//const int MOD = 998244353;
template<class T> inline int add(T& a, T b, T M = MOD){a=(a+M)%M;b=(b+M)%M;a=(a+b)%M;return a;};
template<class T> inline int mul(T& a, T b, T M = MOD){if(a>=M)a%=M;if(b>=M)b%=M;a*=b;if(a>=M)a%=M;return a;};
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

////////////////////////////////////////////////////////////////////
///////////////////////___modpow___////////////////////
ll modpow(ll a,  ll n, const ll &MOD = MOD){
  ll ret = n == 0 ? 1 : modpow(a, n/2, MOD);
  (ret *= ret) %= MOD;
  if(n%2)((ret *= a) %= MOD);
  return ret;
}
///////////////////////___modinv___////////////////////
ll modinv(ll d, const ll &MOD = MOD){
  return modpow(d, MOD-2, MOD);
}
////////////////////////////////////////////////////////////////////

int m = 0;
int n;vector<P> g[110000];
int ans[110000];
void dfs(int x, int p, int c){
  int color = 1;
  rep(i,g[x].size()){
    int to = g[x][i].first, ind = g[x][i].second;
    if(to == p)continue;
    if(color == c)color++;
    ans[ind] = color;
    chmax(m, color);
    dfs(to, x, color);
    color++;
  }
}
signed main(){
  cin>>n;
  rep(i,n-1){
    int a, b;cin>>a>>b;a--;b--;
    g[a].push_back(P(b,i));
    g[b].push_back(P(a,i));
  }
  dfs(0,-1,-1);
  cout << m << endl;
  rep(i,n-1){
    cout << ans[i] << endl;
  }
}


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

typedef vector<vector<int>> Graph;

int dfs(int node, Graph& g, vector<int>& values) {
  int answer = 0;
  if ( values[node] != -1 ) return values[node];
  for ( auto i : g[node] ) {
    answer = max(answer, dfs(i, g, values) + 1);
  }
  return values[node] = answer;
}

int main() {
  int n, m, x, y;
  while ( cin >> n >> m ) {
    Graph G(n);
    vector<int> in(n);
    vector<int> answer(n, -1);

    for ( int i = 0; i < m; ++i ) {
      cin >> x >> y; x--; y--;
      G[x].push_back(y);
      in[y]++;
    }

    for ( int i = 0; i < n; ++i ) {
      if ( in[i] == 0 ) {
        dfs(i, G, answer);
      }
    }
    cout << *max_element(answer.begin(), answer.end()) << endl;
  }
  return 0;
}

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

int main (void){
    string s, t, u;
    int a, b;
    cin >> s >> t >> a >> b >> u;
    if (s == u) {
        cout << a - 1 << " " << b << endl;
    }else if(t == u) {
        cout << a << " " << b - 1 << endl;
    } else {
        cout << a << " " << b << endl;
    }
    return 0;
}

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


/// File input & output /////
#define fRead(x)        freopen("x.txt","r",stdin)
#define fWrite(x)       freopen ("x.txt","w",stdout)


#define ld              long double
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define pb              push_back
#define INF             2e16
#define PI              acos(-1.0)
#define mp              make_pair
#define pii             pair<int,int>
#define pll             pair<LL,LL>


#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(a,min(b,min(c,d)))
#define max4(a,b,c,d)   max(a,max(b,max(c,d)))
#define SQR(a)          ((a)*(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define MEM(a,x)        memset(a,x,sizeof(a))
#define ABS(x)          ((x)<0?-(x):(x))

#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())


#define FASTIO        ios_base::sync_with_stdio(0);cin.tie(nullptr);




///..................Sort by second element in a pair in decending order............. ///
bool SortbySecDesc(const pair<long long,long long > &a, const pair<long long,long long > &b)
{
    return a.second>b.second;
}

///.........................first element of pair in descending order..........................//////
bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}



///.............................................................TEMPLATE................................................./////

int main()
{
    FASTIO;

    int a , b , c;

    cin >> a >> b >> c;


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





    return 0;
}



Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_2_D&lang=jp

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    W, H, x, y, r = map(int, input().split())

    ans = 'No'
    if x - r >= 0 and y - r >= 0:
        if x + r <= W and y + r <= H:
            ans = 'Yes'

    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
    

Measured memory_bytes: 7772
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <queue>
#include <numeric>
#include <ctype.h>
#include <limits>
#include <iomanip>

#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

typedef long long ll;

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

	return gcd(b, a % b);
}

int main()
{
	/*int a, b;
	cin >> a >> b;
	int ans = 6 - a - b;
	cout << ans;*/


	/*int n;
	string s, t;
	cin >> n >> s >> t;
	string ans;
	rep(i, n) {
		ans += s[i];
		ans += t[i];

	}
	cout << ans;*/


	/*ll a, b;
	cin >> a >> b;
	ll ans = a * b / gcd(a, b);
	cout << ans;*/


	/*int n;
	cin >> n;
	vector<int>a(n);
	rep(i, n)cin >> a[i];
	int ans = 0;
	int x = 1;
	rep(i, n) {
		if (a[i] == x) {
			ans++;
			x++;
		}
	}
	if (ans == 0)puts("-1");
	else cout << n - ans;*/


	ll n;
	cin >> n;
	ll ans = 0;
	ll two = 0, five = 0;
	ll t = 2, f = 5;
	if (n % 2) {
		cout << 0;
		return 0;
	}
	while (t <= n) {
		two += n / t;
		t *= 2;
	}
	while (f <= n) {
		five += n / f / 2;
		f *= 5;
	}
	ans = min(two, five);
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
long long n,m;
vector<int> G[100010];
int col[100010];

bool dfs(int v,int c){
    col[v]=c;
    for(int i=0;i<G[v].size();i++){
        if(col[G[v][i]]==c)return false;
        if(col[G[v][i]]==0 && !dfs(G[v][i],-c))return false;
    }
    return true;
}

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

    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    long long ans;
    if(dfs(0,1)){
        long long num=0;
        for(int i=0;i<n;i++){
            if(col[i]==1)num++;
        }
        ans=num*(n-num)-m;
    }
    else{
        ans=(n*(n-1))/2-m;
    }

    cout<<ans<<endl;

}

Measured memory_bytes: 6528
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	mi := int(1e15 + 1)
	for i := 1; i*i <= n; i++ {
		if n%i == 0 {
			mi = min(mi, i+n/i)
		}
	}
	fmt.Println(mi - 2)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10 fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
const int INF = 114514810;
const int MOD = 1000000007;
const double EPS = 1e-8;
typedef int weight;
struct edge
{
	int to; weight cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
typedef vector<vector<edge>> Graph;
int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
int place(int x, int y, int w) { return w*x + y; }
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

int n, dist[15][15];
int dp[15][1 << 15];

int solve(int i, int bit)
{
	if (dp[i][bit] >= 0) return dp[i][bit];
	if (bit == (1 << n) - 1) return 0;
	int res = INF;
	REP(j, n)
	{
		if ((bit >> j) & 1) continue;
		int tmp = bit|(1 << j);
		chmin(res, dist[i][j] + solve(j, tmp));
	}
	return dp[i][bit] = res;
}

int main()
{
	while (cin >> n, n)
	{
		MS(dp, -1);
		vs v(n);
		REP(i, n) cin >> v[i];
		vi del;
		REP(i, n)
		{
			REP(j, n)
			{
				if (i == j) continue;
				if (v[i].find(v[j]) != string::npos)
				{
					del.push_back(j);
				}
			}
		}
		vs nv;
		REP(i, n)
		{
			if (find(ALL(del), i) == del.end()) nv.push_back(v[i]);
		}
		vs rv = v;
		v = nv;
		int r = n;
		n = nv.size();

		REP(i, n)REP(j, n)
		{
			/*
			if (i == j || find(ALL(del), i) != del.end() || find(ALL(del), j) != del.end())
			{
				dist[i][j] = 0;
				continue;
			}
			*/
			for (int k = min(v[i].size(), v[j].size()); k >= 0; k--)
			{
				if (v[i].substr(v[i].size() - k) == v[j].substr(0, k))
				{
					dist[i][j] = v[j].size() - k;
					break;
				}
			}
		}

		int ans = INF;
		REP(i, n) chmin(ans, solve(i,1<<i)+(int)v[i].size());
		REP(i, r) chmax(ans, (int)rv[i].size());
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3168
#include <iostream>
#include <vector>
#include <algorithm>
#define vi vector<int>
#define ll long long
#define pub push_back

const ll md = 1e9 + 7;

using namespace std;

int n, k, zero = 0;
vector<ll> pos;
vector<ll> neg;
ll res = 1;

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		int x; cin >> x;
		if (x > 0) {pos.push_back(x);}
		else if (x < 0) {neg.push_back(-x);}
		else {zero++;}
	}
	sort(pos.begin(), pos.end(), greater<ll>());
	sort(neg.begin(), neg.end(), greater<ll>());
	
	int ps = pos.size(), ns = neg.size();

	if (ps >= k)
	{
		int ptr = k - 1, i;
		for (i = 0; i + 1 < ns; i += 2)
		{
			if (ptr > 0 && neg[i] * neg[i + 1] > pos[ptr] * pos[ptr - 1]) {ptr -= 2;}
			else {break;}
		} 
		for (int j = 0; j < i; j++) {res = (res * neg[j]) % md;}
		for (int j = 0; j <= ptr; j++) {res = (res * pos[j]) % md;}
	}

	else if (ps < k && (k % 2 == 0 || ps) && ns + ps - ((ps % 2) ^ (k % 2)) >= k)
	{
		int ptr = ps - 1 - ((ps % 2) ^ (k % 2)), i = k - (ps - ((ps % 2) ^ (k % 2)));
		for (;i + 1 < ns; i += 2)
		{
			if (ptr > 0 && neg[i] * neg[i + 1] > pos[ptr] * pos[ptr - 1]) {ptr -= 2;}
			else {break;}
		} 
		for (int j = 0; j < i; j++) {res = (res * neg[j]) % md;}
		for (int j = 0; j <= ptr; j++) {res = (res * pos[j]) % md;}
	}

	else if (zero) {res = 0;}

	else
	{
		int L = ps - 1, R = ns - 1;
		for (int i = 0; i < k; i++)
		{
			int val = md, btr = 0;
			if (L >= 0) {val = pos[L];}
			if (R >= 0 && neg[R] < val) {val = neg[R]; btr = 1;}
			if (!btr) {res = (res * pos[L--]) % md;}
			else {res = (res * neg[R--]) % md;}
		}
		res = (md - res) % md;
	}

	cout << res << "\n";
	return 0;
}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

// graph by adjacency list
template <typename T>
struct Edge {
  int dst; T weight;
  Edge(int dst, T weight) : dst(dst), weight(weight) { }
  bool operator < (const Edge<T> &e) const {
    return weight > e.weight;
  }
};

template <typename T>
struct Graph {
  int V;
  vector<vector<Edge<T>>> E;

  Graph(int V) : V(V) { E.resize(V); }

  void add_edge(int src, int dst, T weight) {
    E[src].push_back(Edge<T>(dst, weight));
  }
};

template <typename T>
struct Node {
  int v, src; T dist;
  Node(int v, int src, T dist) : v(v), src(src), dist(dist) { };
  bool operator < (const Node<T> &n) const {
    return dist > n.dist; // reverse
  }
};

template <typename T>
struct MinimumSpanningTree {
  Graph<T> g;
  vector<Node<T>> mst;
  int mincost;

  MinimumSpanningTree(const Graph<T> &g) : g(g) { }

  int prim() {
    mincost = 0;

    vector<bool> used(g.V, false);

    priority_queue<Node<T>> que;
    que.push(Node<T>(0, -1, 0));

    while (!que.empty()) {
      Node<T> n = que.top(); que.pop();
      int v = n.v; T cost = n.dist;
      if (used[v]) continue;
      if (n.src != -1) mst.push_back(n);
      used[v] = true;
      mincost += cost;
      for (Edge<T> e : g.E[v]) {
	if (!used[e.dst]) que.push(Node<T>(e.dst, v, e.weight));
      }
    }
    return mincost;
  }
};
int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int V, E; cin >> V >> E;
  Graph<int> g(V);
  REP(_, E) {
    int s, t, w; cin >> s >> t >> w;
    g.add_edge(s, t, w);
    g.add_edge(t, s, w);
  }
  MinimumSpanningTree<int> mst(g);
  cout << mst.prim() << endl;
  return 0;
}

Measured memory_bytes: 9176
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
//ここまでテンプレ
int main(){
	int N,Y;
	cin>>N>>Y;
	for(int i=0;i<=2000;i++){
		for(int j=0;j<=2000;j++){
			int k=Y-(i*10000+j*5000);
			if(k%1000)
				continue;
			if(k<0)
				continue;
			if(k/1000+i+j==N){
				cout<<i<<" "<<j<<" "<<k/1000<<endl;
				return 0;
			}
		}
	}
	cout<<"-1 -1 -1"<<endl;
	return 0;
}

Measured memory_bytes: 256
/*                        ______
 _______   /\     |``\   |        |  /
    |     /  \    |__/   |____    |/
    |    / _ _\   |  \   |        |\
    |   /      \  |   \  |______  |  \

            Dept. of CSE
        Comilla  University

*/
#include<bits/stdc++.h>
#define pi 2*acos(0.0)
#define ll long long
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Node struct node
#define spc " "
#define  E  2.71828182845904523536
#define pb push_back
#define pp pop_back
#define valid(nx,ny) nx>=0 && nx<n && ny>=0 && ny<m
#define ee endl
#define pii pair<int,int>
#define infinity 10000000000000000
#define mod 1000000007
int fx[]={0,0,+1,-1};
int fy[]={+1,-1,0,0};

using namespace std;
///check n=1;
///check corner case;
const int maX=1e5+1;
vector<ll>Graph[maX],cost[maX];
ll visit[maX];
ll x[10];
ll y[10];

int main()
{
    ll a,b,c,d,cc=0;
    cin>>a>>b>>c;
    ll x=c/a;
    cout<<x*b<<endl;
return 0;
}


Measured memory_bytes: 4992
import math
def prime_factorize(n):
    i = 2
    factors = []
    while i <= math.floor(n**0.5):
        if n%i == 0:
            factors.append(i)
            n //= i
        else:
            i += 1
    if n>1:
        factors.append(n)
    return factors
N = int(input())
ans = ""
ans += str(N)
ans += ":"
ans += " "
S = prime_factorize(N)
S.sort()
for i in range(len(S)):
    if i == len(S)-1:
        ans += str(S[i])
    else:
        ans += str(S[i])
        ans += " "
print(ans)


Measured memory_bytes: 5716
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const ull M = 1e18;
#define rep(i, ss, ee) for (int i = (ss); i < (ee); ++i)

inline void chk(ull a, ull b) {
  if (a > M / b) {
    cout << "-1" << endl;
    exit(0);
  }
}

void solve() {
  ull N;
  cin >> N;
  vector<ull> v(N);
  for (auto &e : v) {
    cin >> e;
    if (e == 0) {
      cout << 0 << endl;
      return;
    }
  }

  ull ans = 1;
  rep(i, 0, N) {
    chk(ans, v[i]);
    ans *= v[i];
  }
  cout << ans << endl;
}

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

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

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

    double b,r,t,ansi,year;
    double mx = 0;
    cin >> year;
    for(int i = 1 ; i <= n ; i++ ){
      cin >> b >> r >> t;
      if(t == 1){
	if(mx < 1.0+year*(r/100)){
	  mx = 1.0+year*(r/100);
	  ansi = b;
	}
      }else if(t == 2){
	if(mx < pow(1.0+(r/100),year)){
	  mx = pow(1.0+(r/100),year);
	  ansi = b;
	}
      }
    }
    cout << ansi << endl;
  }
  return 0;
}

Measured memory_bytes: 1376
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000;
double pi=2*acos(0);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll gya[1000010];
ll kai[1000010];
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
void nckinit(ll n,ll md){
  kai[0]=1;
  kai[1]=1;
  for(int i=2;i<=n;i++){
    kai[i]=kai[i-1]*i;
    kai[i]%=md;
  }
  gya[n]=gyaku(kai[n],md);
  for(int i=n-1;i>=1;i--){
    gya[i]=gya[i+1]*(i+1);
    gya[i]%=md;
  }
  gya[0]=1;
}
ll nck(ll n,ll k,ll md){
  if(k<0)return 0;
  if(k==0||n==k)return 1;
  ll ret=kai[n];
  ret*=gya[n-k];
  ret%=md;
  ret*=gya[k];
  ret%=md;
  return ret;
}
ll npk(ll n,ll k,ll md){
  if(k<0)return 0;
  if(k==0)return 1;
  ll ret=kai[n];
  ret*=gya[n-k];
  ret%=md;
  return ret;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    ll h,w,a,b;cin>>h>>w>>a>>b;
    nckinit(600000,mod);
    ll ans=0;
    rep(i,0,h-a){
        ll s=nck(i+b-1,i,mod)*nck(h-1-i+w-1-b,h-1-i,mod);
        s%=mod;
        ans+=s;
        ans%=mod;
    }
    cout<<ans<<endl;
}


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

bool judge_prime(int num) {
  bool can = true;
  for (int i = 3; i < num; i += 2) {
    if (num % i == 0) {
      can = false;
      break;
    }
  }
  if (can) return true;
  else return false;
}

int main() {
  int N;
  cin >> N;
  if (N == 2) cout << 2 << endl;
  else {
    if (N % 2 == 0) N++;
    N -= 2;
    bool prime = false;
    while(!prime) {
      N += 2;
      if (judge_prime(N)) {
        cout << N << endl;
        break;
      }
    }
  }
}


Measured memory_bytes: 3600
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional> // std::function<void(int)>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};
int Dy[8] = {-1,-1,0,1,1,1,0,-1};
int Dx[8] = {0,1,1,1,0,-1,-1,-1};
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 111111;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    int gcnt=0;
    int pcnt=0;
    int res=0;
    for(auto c:s){
        if(c=='g'){
            if(gcnt>pcnt){
                pcnt++;
                res++;
            }
            else{
                gcnt++;
            }
        }
        else{
            if(gcnt>pcnt){
                pcnt++;
            }
            else{
                gcnt++;
                res--;
            }
        }
    }
    cout<<res<<endl;
}

Measured memory_bytes: 512
#include<cstdio>
const long long inf = 1e17+7;
int have[20][20]; long long w[20][20];
long long cost[1<<16];
long long f[20][1<<16];

void preWork(int n){
    for(int i = 0; i < (1<<n); i++){
        int u = i;
        int keep[20]; int size = 0;
        for(int j = 1; j <= n; j++){
            if(u%2) keep[++size] = j;
            u /= 2;
        }
        cost[i] = 0;
        for(int j = 1; j <= size; j++){
            for(int k = j+1; k <= size; k++) cost[i] += w[keep[j]][keep[k]];
        }
    }
}

long long max(long long a,long long b){ return a>b?a:b; }

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    long long sum = 0;
    for(int i = 1; i <= m; i++){
        int u,v; long long c;
        scanf("%d%d%lld",&u,&v,&c);
        have[u][v] = have[v][u] = 1;
        w[u][v] = w[v][u] = c;
        sum += c;
    }
    preWork(n);
    for(int i = 1; i <= n; i++) f[i][0] = -inf;
    for(int s = 1; s < (1<<n); s++){
        for(int i = 1; i <= n; i++){
            if(i==1 && s==1) f[i][s] = 0;
            else{
                f[i][s] = -inf;
                int need = 1<<(i-1);
                if(s&need){
                    for(int j = 1; j <= n; j++){
                        if(have[j][i]) f[i][s] = max(f[i][s],f[j][s^need]+w[i][j]);
                    }
                    for(int s0 = (s-1)&s; s0!=0; s0 = (s0-1)&s){
                        if((s0&need)==0) continue;
                        int add = s0^s;
                        f[i][s] = max(f[i][s],f[i][s0]+cost[add+need]);
                    }
                }
            }
            //printf("f[%d][%d] = %lld\n",i,s,f[i][s]);
        }
    }
    long long answer = 0;
    int all = (1<<n)-1;
    for(int i = 1; i < (1<<n); i++){
        answer = max(answer,f[n][i]+cost[all^i]);
    }
    //printf("answer = %lld\n",answer);
    printf("%lld\n",sum-answer);
    return 0;
}


Measured memory_bytes: 5900
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

namespace C_ABC160
{
    class MainClass
    {

        static int[] s,a;

        public static void Main(string[] args)
        {
            s = Array.ConvertAll(ReadLine().Split().ToArray(), int.Parse);
            a =Array.ConvertAll(ReadLine().Split().ToArray(), int.Parse); 

            // long sum = 0;
            int tmp = -(s[0]-a[s[1]-1]);
            int nowdis = 0;
            int maxdis = 0;
            for(int i = 0;i<s[1];i++){
                nowdis = a[i] - tmp;
                tmp = a[i];
                maxdis = Max(nowdis,maxdis);
                // if(i==s[1]-1){
                //     maxdis=Max(maxdis,s[0]-a[i]);
                // }

            }
            WriteLine(s[0]-maxdis);
        }
    }
}


Measured memory_bytes: 36316
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h,w;cin >> h >> w;
	vector<string> s(h);
	rep(i,h) cin >> s.at(i);
	rep(i,h){
		rep(j,w){
			if(s[i][j]=='#'){
				if((i>0 && s[i-1][j]!='#') && (i<h-1 && s[i+1][j]!='#') && (j>0 && s[i][j-1]!='#') && (j<w-1 && s[i][j+1]!='#')){
					cout << "No" << endl;
					return 0;
				}
			}
		}
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-


N = int(input().strip())
a_list = list(map(int, input().rstrip().split()))
#----------
a_set=set(a_list)
count_dic={}
for X in a_set:
    count_dic[str(X)] = 0
    count_dic[str(X+1)] = 0
    count_dic[str(X-1)] = 0

count = 0
for X in a_list:
    count_dic[str(X)] += 1
    count_dic[str(X+1)] += 1
    count_dic[str(X-1)] += 1
    
print(max(count_dic.values()))


Measured memory_bytes: 24556
//  main.cpp
//  ABC154A
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
    // insert code here...
    string S,T,U;
    int A,B;
    cin>>S>>T;
    cin >>A>>B;
    cin >>U;
    if (S==U) {
        A--;
    }
    if (T==U) {
        B--;
    }
    cout<<A<<" "<<B<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define N 1000

int main(void){
  int i,num;
  double v[N]={0};
  double t,y;
  int n;

  for(i=0;((scanf("%lf",&v[i]))==1);i++){}
  num=i;
  for(i=0;i<num;i++){
    t=v[i]/9.8;
    y=4.9*t*t;
    n=(int)y/5.0;
    if(y-(double)n*5.0>0.0) n++;
    printf("%d\n",n+1);
  }
  return 0;
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MOD = 1000000009;
const long long INF = 1LL << 60;
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; }

ll dp[110][100100]{};

int main() {
    int N, W;
    cin >> N >> W;
    vector<int> weight(N), value(N);
    for (int i = 0; i < N; ++i) cin >> weight[i] >> value[i];
    for (int i = 0; i < N; ++i) {
        for (int sum_w = 0; sum_w <= W; ++sum_w) {
            if (sum_w - weight[i] >= 0) {
                chmax(dp[i+1][sum_w], dp[i][sum_w - weight[i]] + value[i]);
            }
            chmax(dp[i+1][sum_w], dp[i][sum_w]);
        }
    }
    cout << dp[N][W] << endl;
    return 0;
}

Measured memory_bytes: 81672
#include <bits/stdc++.h>
using namespace std;
long long F(long long n){
    long long count = 0;
    for (long long i = 5; n / i >= 1; i *= 5)
        count += n / i;

    return count;
}
int main(){
long long n;
cin>>n;
if(n%2){
    cout<<0;
    return 0;
}
n/=2;
cout<<F(n);
    return 0;
}


Measured memory_bytes: 256