akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define SZ(X) ((int64_t)((X).size()))
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define intmax (std::numeric_limits<int64_t>::max() / 4)
#define doublemax (std::numeric_limits<double>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);


uint popcnt(uint x) {
	x = (x & 0x5555555555555555ULL) + ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1);
	x = (x & 0x3333333333333333ULL) + ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2);
	x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4);

	x *= 0x0101010101010101ULL;

	return x;
}

int solve(vector<int>a, int pos, int leftmax, int K) {
	//建物の現在の高さがaで、a[pos]とそれより右について
	//K個以上の建物が見える状態にするための最小金額を返す。

	if (K <= 0)return 0;
	const int remain = a.size() - pos;
	if (remain < K)return intmax;

	if (pos == 0)return solve(a, pos + 1, a[0], K - 1);
	if (a.size()<=pos) {
		assert(0);
	}
	
	//a[pos]を上げなくても見える
	if (leftmax < a[pos]) {
		return solve(a, pos + 1, a[pos], K - 1);
	}
	//上げないと見えない
	int ans1 = solve(a, pos + 1, leftmax, K);
	int cost = leftmax + 1 - a[pos];
	a[pos] = leftmax + 1;
	int ans2 = cost + solve(a, pos + 1, a[pos], K - 1);
	return min(ans1, ans2);
}


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

	int N, K;
	cin >> N >> K;
	vector<int>a(N);
	rep(i, N)cin >> a[i];

	int ans = solve(a, 0, 0, K);
	cout << ans << endl;

	return 0;
}



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

#define all(x) (x).begin(), (x).end()
#define allp(x) (x)->begin(), (x)->end()

#define pb push_back


using namespace std;
void dout() { cerr << endl; }
typedef long long ll;
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

#define debug(x) cout << #x " = " << (x) << endl


using ll = long long;
using hll = __int128;
using pii = pair<ll, ll>;
using ld = long double;
using pll = pair<long long, long long>;

template <typename T>
void do_uniq(vector<T> vec){
    sort(all(vec));
    vec.resize(unique(all(vec)) - vec.begin());
}


#ifdef _getchar_nolock
#else
#define _getchar_nolock getchar_unlocked
#endif

template <typename T>
void freadT(T &x) {
    x = 0;
    char ch = _getchar_nolock();
    ll sign = 1;

    while (!isdigit(ch)) {
        if (ch == '-')
            sign *= -1;
        ch = _getchar_nolock();
    }

    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = _getchar_nolock();
    }

    x *= sign;
}


#define solvsh
//#define multi

#ifdef solvsh

//const int MAXN = 1e2 + 2;

#define uint ll

uint ml(uint a, uint b){
    return (a*1ll * b);
}

uint add(uint a, uint b){
    return (a*1ll + b);
}

clock_t timestamp_start = clock();
void time_calc()
{
    cerr << (ld)(clock() - timestamp_start) / CLOCKS_PER_SEC << "\n";
}


void solve() {
    int n;
    cin >> n;

    for(int i = 0; i < 8; ++i){
        if (n >= 400 + 200 * i && n < 400 + 200 * (i + 1)){
            cout << 8 - i;
            return;
        }
    }
}

#else

void solve() {

}


#endif


void multisolve() {
//    prec();
    int t;
    cin >> t;

//    scanf("%d", &t);

    int i = 1;
    while (t--) {
        cout << "Case #" << (i++) << ":\n";
        solve();
//        cout << "\n";
    }
}

#define int int
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(20);


#ifdef multi
    multisolve();
#else
    solve();
//    gen();
#endif


}

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

#define f(z) for(int i=1;i<=z;i++)
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int main()
{
    fast
     int n , mx, kt=1;
     cin>>n;
     int a[n+1];
     f(n) cin>>a[i];
      mx=a[1];
     for(int i=2 ; i<=n ; i++){
        if(mx<= a[i]){

            ++kt;
            mx=a[i];
        }
     }

     cout<<kt<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MAX = 1e5;
LL A[MAX];
LL dp[MAX];

int main() {

    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%d", A + i);
    
    // 2. 各山に降った雨の量を計算.
    // ex.
    // 以下のように, 各山に, 雨が降った(リットル: L)とする.
    // 山1 = 2 * x1 [L]
    // 山2 = 2 * x2 [L]
    // 山3 = 2 * x3 [L]
    // 山4 = 2 * x4 [L]
    // 山5 = 2 * x5 [L]
    // 
    // この場合, 各ダムは, 以下のように水が溜まるので, 
    // ダム1 = x1 + x2 [L]
    // ダム2 = x2 + x3 [L]
    // ダム3 = x3 + x4 [L]
    // ダム4 = x4 + x5 [L]
    // ダム5 = x5 + x1 [L]
    // => ダム1 - ダム2 + ダム3 - ダム4 + ダム5 で, 山1 の 降雨量 2 * x1 [L] が 抽出できる.
    // 2-1. 山1 の 降雨量 を 取得.
    LL r = 0;
    for(int i = 0; i < N; i++){
        if(i % 2 == 0) r += A[i];
        else           r -= A[i];
    }
    
    // 2-2. 山2 ～ 山N の 降雨量 を 取得.
    // ex.
    // 山2 は, ダム1: x1 + x2 から 山1 の 降雨量 2 * x1 [L] の 半分 を 引けば, 
    // x2 が残るので, 2 * x2 とすれば, 山2 の 降雨量 が 計算出来たことになる.
    dp[0] = r;
    for(int i = 1; i < N; i++) dp[i] = 2 * (A[i - 1] - dp[i - 1] / 2);

    // 3. 後処理.
    for(int i = 0; i < N; i++) printf("%lld ", dp[i]);
    return 0;

}

Measured memory_bytes: 2816
# from fractions import gcd
# mod = 10 ** 9 + 7
# N = int(input())
# a = list(map(int,input().split()))
# a,b,c = map(int,input().split())
# ans = [0] * N
# math.ceilで切り上げ
# dp = [[0] * 4 for i in range(3)] #2次元配列初期化
# dp = [[[0] * 2 for i in range(3)] for j in range(5)]
# (ord('A'))でASCII出力 Aは65
import math
import numpy as np
import statistics
import string
import sys
from array import array
from collections import deque
from functools import wraps
import time

def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  # xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):#最大公約数 math.gcdが使えない時の手段として入れとく。pythonが更新されたらいらなくなるはず
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)

R = intinput()
print(2*R*3.1415)


Measured memory_bytes: 27148
#include<stdio.h>

int main(void){
   int x1,x2,x3,x4,x5;
   int i;

   scanf("%d %d %d %d %d",&x1,&x2,&x3,&x4,&x5);

   if(x1 == 0){
      printf("%d",1);
   } else if(x2 == 0){
      printf("%d",2);
   } else if(x3 == 0){
      printf("%d",3);
   } else if(x4 == 0){
      printf("%d",4);
   } else if(x5 == 0){
      printf("%d",5);
   }
   return 0;
}
      


Measured memory_bytes: 1696
def perm(n, k, p):
  ret = 1
  for i in range(n, n-k, -1):
    ret = (ret * i)%p
  return ret

def comb(n, k, p):
  a = perm(n, k, p)
  b = perm(k, k, p)
  return (a*pow(b, -1, p))%p

S = int(input())

ans = 0
S -= 3
t = 0
while S >= 0:
    ans += comb(S+t,t, 10**9+7)
    S -= 3
    t += 1

print(ans%(10**9+7))

Measured memory_bytes: 9148
def main():
    N = int(input())
    a = list(map(lambda i: int(i), input().split()))
    a.sort()
    alice = []
    bob = []
    for i in range(len(a)):
        if i % 2 == 0:
            alice.append(a[len(a) - 1 - i])
        else:
            bob.append(a[len(a) - 1 - i])
    print(sum(alice) - sum(bob))

main()


Measured memory_bytes: 3060
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define enld endl //* missspell check
const ll INF = 1LL << 60;


void solve(long long N, std::string S){
    ll cnt = 0;
    REP(i, N-2){
        if(S.substr(i, 3)=="ABC"){
            cnt++;
        }
    }
    cout<< cnt<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::string S;
    std::cin >> S;
    solve(N, S);
    return 0;
}


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

const int INF = 0x6fffffff;

int main(){
    int N;
    int a[1000], b[1000];
    int dp[1001][1010];
    pair<int, int> p[1000];
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        scanf("%d%d", &p[i].second, &p[i].first);
    }
    sort(p, p+N);
    for(int i = 0; i <= N; i++){
        fill(dp[i], dp[i]+N+1, INF);
    }
    dp[0][0] = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j <= N; j++){
            if(dp[i][j] == INF) continue;
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
            if(dp[i][j] + p[i].second <= p[i].first){
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + p[i].second); 
            }
        }
    }
//    for(int i = 0; i <= N; i++){
//        for(int j = 0; j <= N; j++){
//            if(dp[i][j] == INF){
//                printf("INF ");
//            }else{
//                printf("%3d ", dp[i][j]);
//            }
//        }
//        puts("");
//    }
    for(int i = N; i >= 0; i--){
        if(dp[N][i] < INF){
            cout << i << endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 3276
//file_name:ABC102_B.cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts()
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
const int MX = 200005;

    // 整数スキャン（複数）
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&y);

    // n個の整数のスキャン
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // 文字列スキャン
    /*
    string s;
    cin >> s;
    */


int main() {
    int n;
    scanf("%d",&n);
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
        a[i] -= (i+1);
    }

    sort(a,a+n);

    ll ans = 0;
    rep(i,n){
        ans += abs(a[i]-a[n/2]);
    }


    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(t) t.begin(), t.end()
#define inrange(i, a, b) (((i)>= min((a), (b))) && ((i) <= max((a), (b))))
#define show(x) cout << #x << " is " << x << "\n";
typedef vector<ll> vi;
#define fi first
#define se second
const ll inf = 9e18;
const ll mod = 1e9 + 7;

void print(ll a[], ll n){for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";}
ll power(ll x, ll y, ll M = inf){
    ll ans = 1;
    x %= M;
    while(y){
        if(y&1)
            ans = (x * ans) % M;

        x = (x * x) % M;
        y >>= 1;
    }
    return ans;
}
ll modInverse(ll n) {return power(n, mod-2, mod);}
inline ll mul(ll a, ll b){ return (a * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }
inline ll divi(ll a, ll b){ return mul(a, modInverse(b)); }

//const ll N = 1e5 + 1;
//vector<ll> adj[N];
//bool visited[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

	ll n, k;
	cin>>n>>k;
	ll a[n+1];
	for(ll i=1;i<=n;i++){
		cin>>a[i];
	}
	
	ll op=1;
	ll c=0;
	ll vis[n+1] = {0};
	//vis[1] = 1;
	while(vis[op] != 1){
		vis[op] = 1;
		op = a[op];
		c++;
	}
	if(k<=c){
		op = 1;
		while(k--){
			op = a[op];
		}
		cout<<op;
	}
	else{
		k = k-c;
		ll io = a[op];
		c=1;
		while(io != op){
			c++;
			io = a[io];
		}
		k = k%c;
		while(k--){
			op = a[op];
		}
		cout<<op;
	}
	
	
	


	return 0;
}


Measured memory_bytes: 6780
#include <stdio.h>
//#include <string.h>

int main(void){
  
  int a,b = 0;

 
  scanf("%d %d", &a, &b);

 if(2*a-1>=(a+b) && (2*a-1)>=(2*b-1)) printf("%d", 2*a-1);
 else if((2*b-1)>(a+b) && (2*a-1)<(2*b-1)) printf("%d", 2*b-1);
 //else if((2*a-1)<(a+b) && (a+b)>(2*b-1)) printf("%d", a+b);
   else  printf("%d", a+b);



  return 0;
}

Measured memory_bytes: 1732
#include <iostream>
#include <string>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

	int main() {
		ll n;
		ll ans = 1e18;
		cin >> n;
		for (ll i = 1; i * i <= n; ++i) {
			if (n % i != 0) continue;
			ll j = n / i;
			ans = min(ans,i + j - 2);
		}
		cout << ans << endl;
		return 0;
	}

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

#define INF 1000000

using namespace std;

int main(void)
{
	int n, buf, sum, ans;
	vector<int> w;
	int left, right;
	left = 0;
	n = buf = sum = 0;
	ans = INF;
	cin >> n;
	
	for (int i = 0; i < n; ++i) {
		cin >> buf;
		w.push_back(buf);
		sum += buf;
	}

	right = sum;

	for (int i = 0; i < n; ++i) {
		ans = min(ans, abs(right - left));
		left += w[i];
		right = sum - left;
	}

	cout << ans << endl;

	return 0;

}

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

int main()
{
    double a,b,x;
    double theta;
    cin >> a >> b >>x;
    if (x>a*a*b/2)
    {
        theta=atan(2/(a*a)*(a*b-x/a));
    }
    else
    {
         theta=atan(2*x/(b*b*a));
         theta=pi/2-theta;
    }
    cout <<fixed << setprecision(15)<<theta*180/pi << endl;
    return 0; 
    
}

Measured memory_bytes: 4100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
//#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
ll n;
ll L;
vector<pair<ll,ll>>vec;
vector<ll>za;
priority_queue<ll>que;
vector<ll>edge[1300005];
ll cnt[1300005];

int main(){
    cin >> n >> L;
    rep(i,n){
        ll a,b; cin >> a >> b;
        vec.pb(mp(a,b-1));
        if(a-1 >= 0) za.pb(a-1); za.pb(a); if(a+1 < L) za.pb(a+1);
        if(b-2 >= 0) za.pb(b-2); za.pb(b-1); if(b < L) za.pb(b);
    }
    za.pb(0); za.pb(L-1);
    SORT(za); ERASE(za);
    rep(i,n){
        vec[i].fi = POSL(za,vec[i].fi); vec[i].sc = POSL(za,vec[i].sc);
        edge[vec[i].fi].pb(vec[i].sc);
        cnt[vec[i].fi]++; cnt[vec[i].sc+1]--;
    }
    rep(i,edge[0].size()) que.push(edge[0][i]);
    ll ans_min = 0; ll pre = 0;
    while(!que.empty()){
        ll q = que.top(); que.pop(); ans_min++;
        if(q == za.size()-1) break;
        for(int i=pre+1;i<=q+1;i++) rep(j,edge[i].size()) que.push(edge[i][j]);
        pre = q+1;
    }
    for(int i=1;i<za.size();i++) cnt[i] += cnt[i-1];
    ll ans_max = 0;
    for(int i=0;i<za.size();i++) ans_max = max(ans_max,n-cnt[i]+1);
    cout << ans_min << " " << ans_max << endl;
}


Measured memory_bytes: 63876
#include <bits/stdc++.h>
using namespace std; 
int main() {
  int A;
  int B;
  cin>>A>>B;
  int i=0;
  int j=B-A;
  int sum=0;
  int C=A;
  while(i<=j){
    A=C;
    int a=A%10;//A=12345の時5
    A/=10;//A=1234
    int b=A%10;
    A/=10;//A=123
    A/=10;//A=12
    int d=A%10;
    A/=10;//A=1
    int e=A;
    if(a==e&&b==d){
      sum+=1;
    }
    C++;
    i++;
  }
  cout<<sum<<endl;

}


Measured memory_bytes: 3636
#include <iostream>
using namespace std;
int main(){
	int N;
	cin >> N;
	int A[2][N];
	int i,j;
	for(i=0;i<2;i++){
		for(j=0;j<N;j++){
			cin >> A[i][j];
		}
	}
	
	int max = 0;
	int sum, k;
	for(i=0;i<N;i++){
		sum = 0;
		k = 0;
		for(j=1;j<N;j++){
			if(i+1 == j){
				k = 1;
			}
			sum += A[0+k][j-k];
		}
		if(sum > max){
			max = sum;
		}
	}
	
	max = max + A[0][0] + A[1][N-1];
	cout << max << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <random>

using namespace std;

int main()
{

    int N;
    int M;

    cin >> N >> M;

    if (N >= 2 & M >= 2)
    {
        cout << (N * (N - 1) + M * (M - 1)) / 2 << endl;
    }

    if (N >= 2 & M < 2)
    {
        cout << N * (N - 1) / 2 << endl;
    }

    if (N < 2 & M >= 2)
    {
        cout << M * (M - 1) / 2 << endl;
    }

    if (N < 2 & M < 2)
    {
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll, vl/*, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, n) for(ll i = 1; i <= ll(n); ++i)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); ++i)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); ++i)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  string s;
  cin >> s;
  vc ans;
  rep(i, s.size()) {
    if(s[i]=='B') {if(ans.size()) ans.pop_back();}
    else ans.push_back(s[i]);
  }
  for(char i: ans) cout << i;
  cout << newl;
  return 0;
}

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

using namespace std;

const long long MOD = 1e9 + 7;

int n;
long long pw[2000];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int ii = i;
        for (int j = 2; j * j <= ii; j++) {
            while (ii % j == 0) {
                ii /= j;
                pw[j]++;
            }
        }
        if (ii != 1) {
            pw[ii]++;
        }
    }
    long long ans = 1;
    for (int j = 0; j <= n; j++) {
        ans = (ans * (pw[j] + 1)) % MOD;
    }
    cout << ans << "\n";
}



Measured memory_bytes: 256
N, C = gets.split.map(&:to_i)
XVs = readlines.map{|l| l.split.map(&:to_i)}

xv1 = [[0, 0]] + XVs
t = 0; cs1 = xv1.map{|x, v| (t += v) - x}
t = 0; mcs1 = cs1.map{|v| v > t ? t = v : t}
xv2 = [[0, 0]] + XVs.reverse.map{|x, v| [C - x, v]}
t = 0; cs2 = xv2.map{|x, v| (t += v) - x}
t = 0; mcs2 = cs2.map{|v| v > t ? t = v : t}
m1 = (0 .. N).map{|i| cs1[i] - xv1[i][0] + mcs2[N - i]}.max
m2 = (0 .. N).map{|i| cs2[i] - xv2[i][0] + mcs1[N - i]}.max
puts [m1, m2].max

Measured memory_bytes: 31484
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
vector<int>  dx = {1, 0, -1, 0};
vector<int>  dy = {0, 1, 0, -1};
const int INF = 1<<30;
int main(void){
    int h, w;
    cin >> h >> w;
    vector<string> maze(h);
    rep(i, h) cin >> maze[i];
    int ans = 0;
    rep(sx, h) rep(sy, w){
        if(maze[sx][sy] == '#') continue;
        vector<vector<int>> dist(h, vector<int>(w, INF));
        queue<P> que;
        que.push(P(sx, sy));
        dist[sx][sy] = 0;
        while(que.size()){
            P p = que.front();
            que.pop();
            rep(i, 4){
                int nx = p.first + dx[i];
                int ny = p.second + dy[i];
                if(nx < 0 || h <= nx || ny < 0 || w <= ny) continue;
                if(maze[nx][ny] == '#') continue;
                if(dist[nx][ny] != INF) continue;
                que.push(P(nx, ny));
                dist[nx][ny] = dist[p.first][p.second] + 1;
            }
        }
        rep(i, h) rep(j, w){
            if(dist[i][j] == INF) continue;
            ans = max(ans, dist[i][j]);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define min(a, b) ((a<b)?a:b)
#define max(a, b) ((a<b)?b:a)
#define pb push_back
#define endl "\n"
typedef long long ll;

#define max_element mmmmm
#define min_element nnnnn

template<class T>
class BIT {
	public:
		int BIT_size;
		vector<T> BIT_array;
		BIT(int BIT_size) {
			this->BIT_size = BIT_size;
			BIT_array = vector<T>(BIT_size+1);
			fill(BIT_array.begin(), BIT_array.end(), 0);
		}
		void BIT_update(int i, T d) {
			for(; i<=BIT_size; i+=(i&-i)) {
				BIT_array[i] += d;
			}
		}
		T BIT_sum(int i) {
			T BIT_sum_result = 0;
			for(; i>0; i-=(i&-i)) {
				BIT_sum_result += BIT_array[i];
			}
			return BIT_sum_result;
		}				
};

ll pow(ll a, ll b, ll m) {
	a %= m;
	ll result = 1;
	while(b > 0) {
		if(b & 1) {
			result = result*a%m;
		}
		a = a*a%m;
		b /= 2;		
	}
	return result;
}

 
int main() {
	int d, n; cin >> d >> n;
	int sum = 0;
	while(n--) {
		int t; cin >> t;
		sum += t;
	}
	if(sum > d) cout << -1 << endl;
	else cout << d-sum << endl;
}







































































Measured memory_bytes: 3620
n,a,b = list(map(int, input().split()))
if((b - a) % 2 == 0):
  print((b - a) // 2)
else:
  print(min([n-a, b-1, a + (b - a - 1) // 2, (n - b + 1) + ((b - a - 1) // 2)]))

Measured memory_bytes: 3060
n = int(input())
s = input()
dp = [[0 for i in range(n+1)] for j in range(n+1)]
ans = 0
for i in range(n):
  for j in range(n):
    if i == j:
      break
    if s[i] == s[j]:
      t = dp[i][j]
      if j == i-t:
        dp[i+1][j+1]=1
      else:
        dp[i+1][j+1]=1+t
        ans = max(ans, 1+t)

print(ans)


Measured memory_bytes: 247048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<(n);++i)
#define rep2(i,a,b) for (ll i=(a);i<(b);++i)
#define debug(x) cout << #x << '=' << x << endl
#define all(v) (v).begin(),(v).end()
const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=1e9;
const ll IINF=1e18;
const double EPS=1e-8;
const double pi=acos(-1);

template<class T> inline bool chmin(T &a,T b){
    if (a>b){a=b; return true;}
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if (a<b){a=b; return true;}
    return false;
}

template<uint_fast64_t Modulus> class modint{
    using u64=uint_fast64_t;
    public:
    u64 a;
    constexpr modint(const u64 x=0) noexcept:a(x%Modulus){}
    constexpr u64 &value() noexcept{return a;}
    constexpr const u64 &value() const noexcept{return a;}
    constexpr modint &operator+=(const modint rhs) noexcept{
        a+=rhs.a;
        if (a>=Modulus) a-=Modulus;
        return *this;
    }
    constexpr modint operator+(const modint rhs) const noexcept{
        return modint(*this)+=rhs;
    }
    constexpr modint &operator++() noexcept{
        return ++a,*this;
    }
    constexpr modint operator++(int) noexcept{
        modint t=*this; return ++a,t;
    }
    constexpr modint &operator-=(const modint &rhs) noexcept{
        if (a<rhs.a) a+=Modulus;
        a-=rhs.a;
        return *this;
    }
    constexpr modint operator-(const modint &rhs) const noexcept{
        return modint(*this)-=rhs;
    }
    constexpr modint &operator--() noexcept{
        return --a,*this;
    }
    constexpr modint operator--(int) noexcept{
        modint t=*this; return --a,t;
    }
    constexpr modint &operator*=(const modint &rhs) noexcept{
        a=a*rhs.a%Modulus;
        return *this;
    }
    constexpr modint operator*(const modint &rhs) const noexcept{
        return modint(*this)*=rhs;
    }
    constexpr modint &operator/=(const modint &rhs) noexcept{
        u64 exp=Modulus-2;
        while(exp){
            if (exp%2) *this*=rhs;
            rhs*=rhs; exp>>=1;
        }
    }
    constexpr modint operator/(const modint &rhs) const noexcept{
        return modint(*this)/=rhs;
    }
    constexpr modint operator-() const noexcept{
        return modint(Modulus-a);
    }
    constexpr bool operator==(const modint &rhs) const noexcept{
        return a==rhs.a;
    }
    constexpr bool operator!=(const modint &rhs) const noexcept{
        return a!=rhs.a;
    }
    constexpr bool operator!() const noexcept{return !a;}
};

using mint=modint<MOD>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M; cin >> N >> M;
    vector<int> S(N),T(M);
    rep(i,N) cin >> S[i];
    rep(i,M) cin >> T[i];
    vector<vector<mint>> dp(N+1,vector<mint>(M+1,0));
    vector<vector<mint>> sum(N+1,vector<mint>(M+1,0));
    dp[0][0]=sum[0][0]=1;
    rep(i,N) sum[i+1][0]=1;
    rep(i,M) sum[0][i+1]=1;
    rep(i,N) rep(j,M){
        if (S[i]==T[j]) dp[i+1][j+1]=sum[i][j];
        sum[i+1][j+1]=sum[i][j+1]+sum[i+1][j]-sum[i][j]+dp[i+1][j+1];
    }
    cout << sum[N][M].value() << endl;
}

Measured memory_bytes: 62976
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys


def main():
    s = sys.stdin.readline().rstrip()
    y, m, d = list(map(int, s.split('/')))
    if y<2019:
        sys.exit(1)
    elif y>=2019 and m <= 4:
        print("Heisei")
    else:
        print("TBD")

if __name__=="__main__":
    main()


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

int64 Solve(int64 n) {
  if (n == 1) return 1;
  return 1 + Solve(n / 2) * 2;
}

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

  int64 n;
  cin >> n;
  cout << Solve(n) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll i,j,k,l,m,n,o,p,q,r,t;
    ll ans=0;
    string s;
    cin>>n;
    o=n;
    o+=n*n;
    o+=n*n*n;
    cout<<o<<endl;
    return 0;
}

Measured memory_bytes: 3628
import fractions
a,b = map(int,input().split())
g = fractions.gcd(a,b) #最大公約数

#素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
#1または素数が解
lis = prime_factorize(g)
lis = list(set(lis)) #重複を削除
print(len(lis)+1)    #1を追加

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

l , r = 0, max(a)

def ok(L):
  cnt = 0
  for i in a:
    cnt += i // L
    if i % L == 0:
      cnt -= 1
  return cnt <= k

while r - l > 1:
  mid = (r + l) //2

  if ok(mid):
    r = mid
  else:
    l = mid

print(r)

Measured memory_bytes: 30764
#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[14][14];
bool ok,vis[14];
void dfs(int now)
{
	bool o=true;
	if(ok)
	{
		return;
	}
	for(int i=now+1;i<n-now;i++)
	{
		o=false;
		for(int j=0;j<m;j++)
		{
			swap(c[i][j],c[n-now-1][j]);
		}
		dfs(now+1);
		for(int j=0;j<m;j++)
		{
			swap(c[i][j],c[n-now-1][j]);
		}
	}
	if(o)
	{
		for(int i=0;i<m;i++)
		{
			vis[i]=false;
		}
		int cnt=0;
		for(int i=0;i<m;i++)
		{
			if(!vis[i])
			{
				for(int j=i+1;j<m;j++)
				{
					if(!vis[j])
					{
						bool t=true;
						for(int k=0;k<n;k++)
						{
							t&=(c[k][i]==c[n-k-1][j]);
						}
						if(t)
						{
							vis[i]=true;
							vis[j]=true;
							cnt+=2;
							break;
						}
					}
				}
			}
		}
		for(int i=0;i<m;i++)
		{
			if(!vis[i])
			{
				bool t=true;
				for(int j=0;j<n;j++)
				{
					t&=(c[j][i]==c[n-j-1][i]);
				}
				if(t)
				{
					cnt++;
				}
				break;
			}
		}
		if(cnt==m)
		{
			ok=true;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>c[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		if(!ok)
		{
			for(int j=0;j<m;j++)
			{
				swap(c[i][j],c[n/2][j]);
			}
			dfs(0);
			for(int j=0;j<m;j++)
			{
				swap(c[i][j],c[n/2][j]);
			}
		}
	}
	if(ok)
	{
		cout<<"YES"<<endl;
	}
	else
	{
		cout<<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#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;

int main() {
    int N;
    cin >> N;
    vector<int> B(N-1);
    for (int i = 0; i < N-1; ++i) cin >> B[i];
    ll res = B[0];
    for (int i = 0; i+1 < N-1; ++i) {
        res += min(B[i], B[i+1]);
    }
    res += B.back();
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3644
import math

A, B, x = map(int, input().split())
'''
if x == A ** 2 * B:
    print(0)
    exit()

if x <= A * A * B / 2:
    S = x / A
    print(S)
    print('----')
    f = 2 * S / B
    print(f)
    print('----')
    print(math.degrees(math.atan(B / f)))
else:
    S = A * B - x / A
    f = 2 * S /A
    print(90 - math.degrees(math.atan(A / f)))
#A,B,x = map(int,input().split())
'''


fukasa = x / A ** 2
mizu_menseki = fukasa * A
zentai_menseki = B * A
amari_menseki = zentai_menseki - mizu_menseki
amari_takasa  = amari_menseki  * 2 / A
mizu_soko = mizu_menseki * 2 / B


'''
print(mizu_soko * B * 0.5)
print(mizu_menseki)
print('----')
print(A,fukasa,mizu_menseki,zentai_menseki,amari_menseki,amari_takasa,mizu_soko)

print('----')

print(math.atan2(1,3 ** 0.5))
print(math.degrees(math.atan2(1,3 ** 0.5)))

'''

if (A * A * B // 2) == x:
    print(45)
elif (A * A * B / 2) < x:
    print(math.degrees(math.atan(amari_takasa/A)))
else:
    print(math.degrees(math.atan(B/mizu_soko)))

'''
taikakusen = A * 2**0.5
fukasa = x / A ** 2
mizu_menseki = fukasa * taikakusen
zentai_menseki = B * taikakusen
amari_menseki = zentai_menseki - mizu_menseki
amari_takasa  = amari_menseki  / (taikakusen * 0.5)
mizu_soko = mizu_menseki / (B * 0.5)

print(mizu_soko * B * 0.5)
print(mizu_menseki)
print('----')
print(taikakusen,fukasa,mizu_menseki,zentai_menseki,amari_menseki,amari_takasa,mizu_soko)

print('----')

print(math.atan2(1,3 ** 0.5))
print(math.degrees(math.atan2(1,3 ** 0.5)))

if (A * A * B // 2) == x:
    print(45)
    print(math.degrees(math.atan2(amari_takasa,taikakusen)))
elif (A * A * B / 2) > x:
    print(math.degrees(math.atan2(amari_takasa,taikakusen)))
else:
    print(90 - math.degrees(math.atan2(mizu_soko,B)))
'''


Measured memory_bytes: 3064
q=[]
qq=[]
def dfs(j,q,count,n,qq):
    if len(qq)==n:
        count+=1
        return count   
    for j2 in q[j]:
        if not j2 in qq:
            qq.append(j2)
            count=dfs(j2,q,count,n,qq)
            qq.pop()
    return count

n,m=map(int,input().split())
q=[[]*2 for i in range(n)]
for i in range(m):
    ai,bi=list(map(int,input().split()))
    if not q[bi-1] in q[ai-1]:
        q[ai-1].append(bi-1)    
        q[bi-1].append(ai-1)    

count=0
j=0
qq=[j]
count=dfs(j,q,count,n,qq)
print(count)


Measured memory_bytes: 3064
N,M=map(int,input().split())
cnt = [0]*N
for _ in range(M):
    a,b=map(int,input().split())
    cnt[a-1] += 1
    cnt[b-1] += 1
print("YES" if all([cnt[i] % 2 == 0 for i in range(N)]) else "NO")

Measured memory_bytes: 10668
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>

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

int main(){
  int n,k; cin >> n >> k;
  int A[n]; int sum = 0;
  rep(i,n){
    cin >> A[i];
    sum += A[i];
  }
  int ans = 1;
  set<ll> D;
  for(int i=1;i*i<=sum;i++){
    if(sum % i ==0){
      D.insert(i);
      D.insert(sum/i);
    }
  }
  for(int u : D){
    vector<int> a(n);
    rep(i,n){
      a[i] = A[i] % u;
    }
    sort(a.begin(),a.end());
    ll left = 0;
    ll right = 0;
    rep(i,n) right += u-a[i];
    ll need = 1e18;
    rep(i,n){
      left += a[i];
      right -= u-a[i];
      need = min(need,max(left,right));
    }
    if(need <= k) ans = max(ans,u);
  }
  cout << ans << endl;
  return 0;
}

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

typedef pair<int,int> pii;
#define X first
#define Y second
const int mem_max = 1100;
const int mm_max = mem_max*mem_max+100;
struct F{
  int prime[mm_max];
  pii mem2[mm_max];
  int mem[mem_max][mem_max];
  public: void init(){
    make_prime();
    for(int i=0;i<mem_max;i++){
      for(int j=0;j<mem_max;j++){
        mem[i][j]=-1;
      }
    } 
    int x=0,y=0;
    int c=1;
    int dx=1,dy=1;
    int vx=1,vy=-1;
    w(x,y,c);
    while(1){
      for(int i=0;i<dx;i++){
        x+=vx;c++;if(!(c<=mem_max*mem_max))break;
        w(x,y,c);
      }
      if(!(c<=mem_max*mem_max))break;
      vx*=-1;
      dx++;
      for(int i=0;i<dy;i++){
        y+=vy;c++;if(!(c<mem_max*mem_max))break;
        w(x,y,c);
      }
      if(!(c<=mem_max*mem_max))break;
      vy*=-1;
      dy++;
    }
    for(int i=0;i<mem_max;i++){
      for(int j=0;j<mem_max;j++){
        mem2[mem[i][j]] = pii(i-mem_max/2,j-mem_max/2); 
      }
    }
  }
  private:
  void make_prime(){
    for(int i=2;i<mm_max;i++){
      prime[i]=1;
    }
    for(int i=0;i*i<=mm_max;i++){
      if(prime[i])for(int j=i*2;j<mm_max;j+=i){
        prime[j]=0;
      }
    }
  }
  int res(int x){
    x+=mem_max/2;
    if(x<0||mem_max<=x)return -1;
    return x;
  }
  int w(int x,int y,int m){
    if(-1==(x = res(x))) return -1;
    if(-1==(y = res(y))) return -1;
    mem[x][y]=m;
    return mem[x][y];
  }
  public:
  int g(int x,int y){
    if(-1==(x = res(x))) return -1;
    if(-1==(y = res(y))) return -1;
    return mem[x][y];
  }
  int num(int x,int y){return g(x,y);}
  pii pos(int n){
    return mem2[n];
  }
  bool is_prime(int x,int y){
    int tmp = g(x,y);
    return prime[tmp];
  }
};
F f;

#define DEBUG 0
void print(){
  if(!DEBUG)return ;
  for(int i=0;i<20;i++){
    for(int j=0;j<20;j++){
      cout<<setw(4)<<f.g(j-10,i-10);
    }cout<<endl;
  }cout<<endl;

  for(int i=0;i<20;i++){
    cout<<f.pos(i+1).X<<" "<<f.pos(i+1).second<<endl;
  }
}
int m;
vector<pii> dp;
pii req(int x,int y){
  if(f.num(x,y)<0 || f.num(x,y)>=(int)dp.size())return pii();
  if(dp[f.num(x,y)].X!=-1)return dp[f.num(x,y)];
  if(f.num(x,y)>m)return pii();
  pii res = pii(0,0);
  for(int i=-1;i<=1;i++){
    pii tmp = req(x+i,y+1);
    res = max(tmp,res);
  }
  if(f.is_prime(x,y)){
    if(res.first == 0){
      res.second = f.num(x,y);
    }
    res.first++;
  }
  return dp[f.num(x,y)]=res;
}


pii solve(int n){
  dp.clear();dp.resize(m+100);
  for(int i=0;i<(int)dp.size();i++){
    dp[i] = pii(-1,-1);
  }
  return req(f.pos(n).X,f.pos(n).Y);
}

int main(){
  print();
  f.init();
  int n;
  while(1){
    cin>>m>>n;
    if(n==0&&m==0)break;
    pii ans = solve(n);
    cout<<ans.first<<" "<<ans.second<<endl;
  }
  return 0;
}

Measured memory_bytes: 27936
#include <bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define N (int) 3e6
using namespace std;
int r1, r2, c1, c2;

int ksm (int x, int y) {
	int ret = 1;
	while (y) {
		if (y & 1) (ret *= x) %= MOD;
		(x *= x) %= MOD;
		y >>= 1;
	}
	return ret;
}

int Inv (int x) {
	return ksm (x, MOD-2);
}

int fac[N], inv_f[N];
void Getinv () {
	fac[0] = 1;
	for (int i = 1; i <= (int) 2e6+5; i ++) fac[i] = fac[i-1] * i % MOD;
	inv_f[(int) 2e6+5] = Inv (fac[(int) 2e6+5]);
	for (int i = (int) 2e6 + 5 - 1; i >= 0; i --) inv_f[i] = inv_f[i+1] * (i + 1) % MOD;
}

int C (int m, int n) {
	return fac[m] * inv_f[n] % MOD * inv_f[m-n] % MOD;
}

int calc (int x, int y) {
//	int ret = 0;
//	for (int i = 0; i <= x; i ++) (ret += C (i+y+1, i+1)) %= MOD;
//	return ret;
	return C (x+y+2, y+1);
}

signed main () {
	cin >> r1 >> c1 >> r2 >> c2;
	
	Getinv ();
	
//	cout << calc (r1, c2) << " " << calc (r1, c2) << endl;
	
	cout << ((4ll * MOD + calc (r2, c2) - calc (r1-1, c2) - calc (r2, c1-1) + calc (r1-1, c1-1)) % MOD) << endl;
	
	return 0;
}

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rrep(i, n) for (ll i = (n)-1; i >= 0; i--)

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll X;
    cin >> X;

    vector<ll> v;
    for (ll i = 1; i < 32; i++) {
        for (ll j = 2; j < 10; j++) {
            if (pow(i, j) <= X) {
                v.push_back(pow(i, j));
            }
        }
    }

    ll ans = 0;
    rep (i, v.size()) {
        ans = max(ans, v[i]);
    }

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

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


signed main(){
   int n;
   cin>>n;
   map<int, int>mp;
   map<int,int>r_mp;
   int count=0;
   int f=0;
   for(int i=0; i<n; i++){
      int a;
      cin>>a;
      if(!mp.count(a)){
         mp[a]++;
      }
      else {
         // cout<<mp.count(a)<<endl;
         // cout<<a<<endl;
         f=1;
      }
   }
   if(f==1){
      cout<<"NO"<<endl;
   }
   else{
      cout<<"YES"<<endl;
   }
  return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
 
int main() {
  int n;
  cin >> n;
  if(n==1) {
    cout << "! 1" << endl;
    return 0;
  }
  vector<P> v;
  for(int i=2; i<=n; i++) {
    cout << "? " << 1 << " " << i << endl;
    cout.flush();
    int x;
    cin >> x;
    v.push_back(P(x,i));
  }
  sort(v.begin(),v.end(),greater<P>());
  vector<P> a;
  a.push_back(P(0,v[0].second));
  for(int i=1; i<=n; i++) {
    if(i==v[0].second) continue;
    cout << "? " << v[0].second << " " << i << endl;
    cout.flush();
    int x;
    cin >> x;
    a.push_back(P(x,i));
  }
  sort(a.begin(),a.end());
  cout << "!";
  for(int i=0; i<n; i++) cout << " " << a[i].second;
  cout << endl;
  cout.flush();
  return 0;
}


Measured memory_bytes: 3612
import math

def gooddistance(l1, l2):
    calc = []
    
    for i in range(len(l1)):
        calc.append((l1[i] - l2[i])**2)

    if math.sqrt(sum(calc)).is_integer():
        return 1
    else:
        return 0

n, d = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]
count = 0

for i in range(n):
    for j in range(i+1,n):
       count += gooddistance(lst[i],lst[j])

print(count)


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

using namespace std;

int main()
{

    int n;
    cin>>n;

    int cnt;
    if(n>1000)
    {
        if(n%1000==0)
            cout<<0<<endl;
        else
            cout<<((n/1000)+1)*1000-n<<endl;
        }
    else
        cout<<1000-n<<endl;

}


Measured memory_bytes: 3556
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

ll lcm (ll a,ll b){
    return a * b / gcd(a,b);
}
main(){
    ll N,M;
    string S,T;
    cin >> N >> M;
    cin >> S >> T;
    ll l1 = N / gcd(N,M) * M;
    ll g = gcd(N,M);
    ll l2 = lcm(l1 / N, l1 / M);
    string ss,tt;
    rep(i,0,g)ss += S[i * (N / g)];
    rep(i,0,g)tt += T[i * (M / g)];

    if(ss == tt)cout << l1 << endl;
    else        cout << -1 << endl;

}

Measured memory_bytes: 512
n,m=map(int,input().split())
a=[]
b=[]
for i in range(n):
  a.append(input())
for j in range(m):
  b.append(input())
flag=0
for i in range(n-m+1):
  for j in range(n-m+1):
    cnt=0
    for h in range(m):
      if b[h]==a[i+h][j:j+m]:
        cnt+=1
    if cnt==m:
      flag=1
      break
if flag==0:
  print("No")
else:
  print("Yes")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

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; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int T, n, m;

int main(int argc, char *argv[]){
	ios::sync_with_stdio(false);
	ll k;
	n = 50;
	cin >> k;
	vector<ll> v(n, n - 1 + (k + n - 1) / n);
	k = (n - k % n) % n;
	REP(i, n){
		if(i < k % n){
			v[i] = v[i] + k - n - 1;
		}else{
			v[i] = v[i] + k;
		}
	}
	cout << n << endl;
	REP(i, n) cout << v[i] << " \n"[i+1 == n];
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<long long> X(N);
  vector<long long> Y(N);
  long long a, b = 0;
  for(int i = 0; i < N; i++) {
    cin >> X.at(i);
  }
  for(int i = 0; i < N; i++) {
    Y.at(i) = X.at(i);
  }
  sort(Y.begin(), Y.end());
  a = Y.at(N/2-1);
  b = Y.at(N/2);
  for(int i = 0; i < N; i++) {
    if(X.at(i) < b) {
      cout << b << endl;
    }
    else {
      cout << a << endl;
    }
  }
}


Measured memory_bytes: 5376
S = input()
Q = int(input())
Query = [input() for _ in range(Q)]
flag = True
forward = ""
backward = ""
for i in range(Q):
    if Query[i][0] == "1":
        if flag:
            flag = False
        else:
            flag = True
    else:
        if Query[i][2] == '1':
            if flag:
                forward = Query[i][4] + forward
            else:
                backward = backward + Query[i][4]
        else:
            if flag:
                backward = backward + Query[i][4]
            else:
                forward = Query[i][4] + forward

if flag:
    ans = forward + S + backward
else:
    forward = forward[::-1]
    backward = backward[::-1]
    S = S[::-1]
    ans = backward + S + forward
print(ans)

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

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

	int A=in(),P=in();
	
	cout << (3*A+P)/2 << endl;
	return 0;
}

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

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

    long long a, b;
    cin >> a >> b;
    char c;
    cin >> c;
    int d;
    cin >> d;
    b = b * 100 + d;
    long long e = (a * b) / 100;
    cout << e;
}

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


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

  ll n,k;
  cin >> n >> k;
  ll a[n];
  rep(i,n){
    cin >> a[i];
  }

  ll sum[n+1];
  sum[0]=0;
  rep1(i,n){
    sum[i]=a[i-1];
    sum[i]+=sum[i-1];
  }
  vector<ll> all;
  rep(i,n){
    for(int j=i;j<n;j++){
      all.pb(sum[j+1]-sum[i]);
    }
  }
  for(int i=40; i>=0; i--){
    int c=0;
    vector<ll> nxt;
    rep(j,all.size()){
      if((1LL<<i)&all[j]){
	c++;
	nxt.pb(all[j]);
      }      
    }
    if(c>=k){
      all.clear();
      rep(m,nxt.size()){
	all.pb(nxt[m]);
      }
      //      cout << i << endl;
    }
  }
  ll ans=all[0];
  rep(i,all.size()){
    //  cout << all[i] << endl;
    ans&=all[i];
  }
  cout << ans << endl;
  return 0;
    

}


Measured memory_bytes: 6384
from collections import Counter


def main():
    number, product = map(int, input().split())
    prime_factors = []
    while product % 2 == 0:
        prime_factors.append(2)
        product //= 2
    i = 3
    while i * i <= product:
        if product % i == 0:
            product //= i
            prime_factors.append(i)
        else:
            i += 2
    if product != 1:
        prime_factors.append(product)
    prime_factors = Counter(prime_factors)
    answer = 1
    for p, n in prime_factors.items():
        if number <= n:
            answer *= pow(p, n // number)
    print(answer)


if __name__ == '__main__':
    main()



Measured memory_bytes: 3316
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
using namespace std;


int main() {
	//cout << fixed << setprecision(10);
	long long int n, m, a, b, c, d, x, h[30], w, cou = 1, Ma = 0;
	cin >> n;
	cin >> h[1];
	Ma = h[1];
	for (int i = 2; i <= n; i++) {
		cin >> h[i];
		if (Ma <= h[i]) { Ma = h[i]; cou++; }
	}
	cout << cou;

}

Measured memory_bytes: 256