akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 2e5 + 87;
    ll n, k, a[N];
    ll c0, cn, cp;
    ll solvene()
    {
        vector<ll> x(a, a + cn);
        vector<ll> y(a + n - cp, a + n);
        ll lo = x[0] * y.back();
        ll hi = x.back() * y[0];
        //cerr << "lo hi "<< lo << ' '<< hi << endl;
        reverse(x.begin(), x.end());
        reverse(y.begin(), y.end());
        //cerr << "x= "; for (ll t : x) cerr << t << ' '; cerr << endl;
        //cerr << "y= "; for (ll t : y) cerr << t << ' '; cerr << endl;
        while (lo <= hi) {
            ll mi = lo + (hi - lo) / 2;
            ll c = 0;
            for (ll i = 0, j = 0; i < x.size(); ++i) {
                for (; j < y.size() && x[i] * y[j] <= mi; ++j);
                //cerr << "i,j,x[i] " << i << ' ' << j << ' ' << x[i]<< endl;
                c += j;
            }
            //cerr << "mi, c "<< mi << ' ' << c << endl;
            if (c < k)
                lo = mi + 1;
            else
                hi = mi - 1;
        }
        return lo;
    }
    ll solvenp(ll k)
    {
        vector<ll> x(a, a + cn);
        reverse(x.begin(), x.end());
        vector<ll> y(a + n - cp, a + n);
        ll lo = LLONG_MAX;
        ll hi = LLONG_MIN;
        if (x.size() >= 2) {
            lo = min(lo, x[0] * x[1]);
            hi = max(hi, x[cn - 1] * x[cn - 2]);
        }
        if (y.size() >= 2) {
            lo = min(lo, y[0] * y[1]);
            hi = max(hi, y[cp - 1] * y[cp - 2]);
        }
        while (lo <= hi) {
            ll mi = lo + (hi - lo) / 2;
            ll c = 0;
            for (ll i = cp - 1, j = 0; i >= 0; --i) {
                for (; j < i && y[i] * y[j] <= mi; ++j);
                c += min(j, i);
            }
            for (ll i = cn - 1, j = 0; i >= 0; --i) {
                for (; j < i && x[i] * x[j] <= mi; ++j);
                c += min(j, i);
            }
            //cerr << "mi, c " << mi << ' ' << c << endl;
            if (c < k)
                lo = mi + 1;
            else
                hi = mi - 1;
        }
        return lo;
    }
    int main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cin >> n >> k;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            if (a[i] == 0)
                ++c0;
            else if (a[i] > 0)
                ++cp;
            else
                ++cn;
        }
        sort(a, a + n);
        ll ne = cn * cp;
        ll n0 = c0 * (c0 - 1) / 2 + c0 * (n - c0);
        ll np = cp * (cp - 1) / 2 + cn * (cn - 1) / 2;

        ll ans;
        if (k <= ne) {
            ans = solvene();
        } else if (k <= ne + n0) {
            ans = 0;
        } else {
            ans = solvenp(k - ne - n0);
        }
        cout << ans << "\n";
    }

Measured memory_bytes: 3200
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

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

const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)


int main() {
	IO;
	ll n;
	cin>>n;
	vector<pair<ll,ll>> prs;
	for(ll i=2;i*i<=n;++i) {
		if(n%i==0) {
			prs.push_back({i,0});
			while(n%i==0) {
				prs.back().yy++;
				n/=i;
			}
		}
	}
	if(n>1) prs.push_back({n,1});
	
	ll ans=0;
	for(auto& i:prs) {
		for(int j=1;j<=i.yy;j++) {
			ans++;
			i.yy-=j;
		}
	}
	cout<<ans<<"\n";
	
	return 0;
}


Measured memory_bytes: 3608
#include <stdio.h>

int main(void){
	int N = 0;
	scanf("%d",&N);
	if(N%2 == 0){
		printf("%d\n", N);
		return 0;
	}else{
		printf("%d\n", 2*N);
		return 0;
	}
	return 0;
}

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

int main(){
	int N,W;
	vector<vector<int> > item;
	cin>>N>>W;
	item.resize(N+1);
	for(int i=0;i<=W;i++){
		item[0].push_back(0);
	}
	for(int i=1;i<=N;i++){
		int v,w;
		cin>>v>>w;
		for(int j=0;j<=W;j++){
			int Max = item[i-1][j];
			if(j>=w){	
				Max = max(item[i][j-w]+v,item[i-1][j]);
			}
			
			item[i].push_back(Max);
		}
	}
	cout<<item[N][W]<<endl;	
	
	
	return 0;
}

Measured memory_bytes: 5492
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define print(A,n) for(ll i=0;i<n;++i)cout<<A[i]<<' ';cout<<endl;
#define take(A,n) for(ll i=0;i<n;++i)cin>>A[i];
//    for(auto& it : m)
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);}
//  priority_queue<ll int> pq;
//  priority_queue <ll int, vector<ll int>, greater<ll int> > pq;
//  vector<ll int> v;
//  vector< pair<ll int,ll int> > v;
//  set<ll int>::iterator it=s.begin();
//  unordered_map<  pair<ll int,ll int>, ll int> mp;

ll int power(ll int x, ll int y, ll int p)  
{  
   ll int res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}  
 
int main()
{
  fastio();
ll int T;
T=1;

while(T--)
{
ll int n,ans=0,i;
cin>>n;
ll int a[n];
map<ll int,ll int> mp;
for(i=0;i<n;i++)
  {cin>>a[i];ans+=mp[i-a[i]];mp[a[i]+i]++;}
cout<<ans<<endl;

}


    return 0;
}

Measured memory_bytes: 27760
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=2e5+10;

ll N;
int c[MAX_N];
ll sub[MAX_N],ans[MAX_N],cnt[MAX_N];
vector<int> G[MAX_N];

void dfs(int v,int p){
    sub[v]=1;
    ll pre=cnt[c[v]];
    for (int u:G[v]){
        if (u==p) continue;
        cnt[c[v]]=0;
        dfs(u,v);
        sub[v]+=sub[u];
        ans[c[v]]+=(sub[u]-cnt[c[v]])*(sub[u]-cnt[c[v]]+1)/2;
    }
    cnt[c[v]]=pre+sub[v];
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i=0;i<N;++i) cin >> c[i],--c[i];
    for (int i=0;i<N-1;++i){
        int a,b; cin >> a >> b; --a,--b;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
    dfs(0,-1);
    for (int i=0;i<N;++i) cout << N*(N+1)/2-ans[i]-(N-cnt[i])*(N-cnt[i]+1)/2 << '\n';
}

Measured memory_bytes: 38692
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n,d[MAXN],p[MAXN],sz[MAXN];
ll f[MAXN],g[MAXN];
vector<P> v;
vector<ll> G[MAXN];
vector<P> E;
void add_edge(ll u,ll v)
{
    G[u].push_back(v);G[v].push_back(u);
    E.push_back(P(u,v));
}
void dfs1(ll v,ll p)
{
    sz[v]=1;
    for(auto to:G[v])
    {
        if(to==p) continue;
        dfs1(to,v);
        sz[v]+=sz[to];
        f[v]+=sz[to]+f[to];
    }
}
void dfs2(ll v,ll p)
{
    for(auto to:G[v])
    {
        if(to==p) continue;
        g[to]=g[v]+n-2*sz[to];
        dfs2(to,v);
    }
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) scanf("%lld",&d[i]);
    for(ll i=1;i<=n;i++) v.push_back(P(d[i],i));
    sort(v.begin(),v.end());
    bool fl=true;
    for(ll i=n-1;i>0;i--)
    {
        sz[v[i].S]++;
        ll to=d[v[i].S]+2*sz[v[i].S]-n;
        auto it=lower_bound(v.begin(),v.end(),P(to,0));
        if(it==v.end()||it->F!=to) 
        {
            fl=false;
            break;
        }
        add_edge(v[i].S,it->S);
        p[v[i].S]=it->S;
        sz[it->S]+=sz[v[i].S];
    }
    if(!fl)
    {
        puts("-1");
        return 0;
    }
    dfs1(v[0].S,0);g[v[0].S]=f[v[0].S];dfs2(v[0].S,0);
    for(ll i=1;i<=n;i++) if(g[i]!=d[i]) {puts("-1"); return 0;}
    for(auto p:E) printf("%lld %lld\n",p.F,p.S);
    return 0;
}



Measured memory_bytes: 15216
#include<stdio.h>

int main(){
    long long N, K;
    long long ans=0;
    long long tmpa, tmpb;
    int i, j ,k;

    scanf("%lld %lld", &N, &K);

    if(K==0){
        printf("%lld", N*N);
    }else{
        for(i=K+1; i<=N; i++){
            tmpa = i-K;
            ans += (N/i)*tmpa;
            if(N%i>=K){
                ans += N%i-K+1;
            }
            //printf("%d %d\n", i, ans);
        }
        printf("%lld", ans);
    }
    return 0;
}

Measured memory_bytes: 128
from numba import jit
import sys
input = sys.stdin.readline


@jit
def solve(n, k, X):
    for _ in range(k):
        Y = [0]*(n+1)
        for i, x in enumerate(X):
            Y[max(0, i-x)] += 1
            Y[min(n, i+x+1)] -= 1
        for j in range(1, n):
            Y[j] += Y[j-1]
        if X == Y[:-1]:
            break
        X = Y[:-1]
    return X


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    ans = solve(N, K, A)
    print(*ans)


if __name__ == '__main__':
    main()


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

using namespace std;

void solve()
{
	int n, p, q;
	while (cin >> n >> p >> q, n || p || q)
	{
		p = p % 100 + p / 100 * 60;
		q = q % 100 + q / 100 * 60;
		vector<int> cmCount(q - p);
		for (int i = 0; i < n; ++i)
		{
			int a;
			cin >> a;
			for (int j = 0; j < a; ++j)
			{
				int start, end;
				cin >> start >> end;
				start = (start % 100 + start / 100 * 60) - p;
				end = (end % 100 + end / 100 * 60) - p;
				for (int k = start; k < end; ++k)
				{
					cmCount[k]++;
				}
			}
		}
		int maxv = 0;
		int tvTime = 0;
		for (int i = 0; i < cmCount.size(); ++i)
		{
			if (cmCount[i] < n)
			{
				++tvTime;
				maxv = max(maxv, tvTime);
			}
			else
			{
				tvTime = 0;
			}
		}
		cout << maxv << endl;
	}
}

int main()
{
	solve();
	return(0);
}

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

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

  long long A, C;
  double B;
  cin >> A >> B;

  C = B * 100.000001;

  cout << (long long)(A * C) / 100 << endl;

  return 0;
}


Measured memory_bytes: 3676
#include <stdio.h>
#define S(x,y,a,b,l,r) ((x*b+a*r+l*y-y*a-l*b-r*x)>0?0:((x*b+a*r+l*y-y*a-l*b-r*x)<0?1:2))
int main() {double a,b,c,d,o,p,q,r;while (scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",&a,&b,&c,&d,&o,&p,&q,&r)!=EOF) {int T[4]={0,0,0,0};T[S(a,b,c,d,o,p)]++,T[S(c,d,o,p,q,r)]++,T[S(o,p,q,r,a,b)]++,T[S(q,r,a,b,c,d)]++;if (T[0]&&T[1]) puts("NO"); else puts("YES");} return 0;}

Measured memory_bytes: 1036
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>
 
#define rep(i,n) for(ll i=0;i<(n);i++)
typedef long long ll;
using namespace std;

int main() {
  int K;
  cin >> K;
  int A, B;
  cin >> A >> B;
  int cnt = 0;
  for( int i = A;i < B + 1; i++) {
    if( i % K != 0) {
      continue;
    }
    cnt++;
  }
  if (cnt == 0) { 
    cout << "NG" << endl;
  }
  else {
    cout << "OK" << endl;
  }
}
  

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#define INF 10000000000000000
#define MOD 1000000007
using namespace std;


int main(){
    string s;
    cin >> s;
    int a[3]={};
    for(int i=0; i<3; i++){
        a[s[i]-'a']++;
    }
    int k=0;
    for(int i=0; i<3; i++){
        if(a[i]==1){k++;}
    }
    
    if(k==3){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}
    return 0;
}


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

int main(void)
{
	int length[4];
	bool use[4] = {false};

	int i,j;

	for (i = 0; i < 4; i++)
	{
		cin >> length[i];
	}

	int check = 0;
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 4 && !use[i] ; j++)
		{
			if (length[i] == length[j] && i != j && !use[j])
			{
				use[i] = use[j] = true;
				check++;
				continue;
			}
		}

	}

	if (check == 2)
	{
		cout << "yes\n";
	}
	else
	{
		cout << "no\n";
	}

	return 0;
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
string to_string(const string& s) {
	return '"' + s + '"';
}
string to_string(const bool b) {
	return (b ? "true" : "false");
}
string to_string(const char* s) {
	return to_string((string)s);
}
string to_string(const char c) {
	string s = "'";
	s += c;
	s += "'";
	return s;
}
template<class T, class U>
string to_string(const pair<T, U>& p) {
	string s = "(";
	s += to_string(p.first);
	s += ", ";
	s += to_string(p.second);
	s += ")";
	return s;
}
template<class T>
string to_string(const T& a) {
	bool first = true;
	string s = "{";
	for (const auto& x : a) {
		if(!first){
			s += ", ";
		}
		first = false;
		s += to_string(x);
	}
	s += "}";
	return s;
}
void debug_out() {cerr << '\n';}
template<class Head, class... Tail>
void debug_out(Head head, Tail... tail) {
	cerr << ' ' << to_string(head);
	debug_out(tail...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
using ll = long long;
using ld = long double;
const int mod = 1e9 + 7;
const int inf = 1e9 + 100;
const ll inf64 = 7e18l;
vector<vector<int>> perm;
int n, m;
void construct(const vector<int> cur) {
	if ((int) cur.size() == n) {
		perm.push_back(cur);
		return;
	}
	int last = cur.empty() ? 1 : cur.back();
	for (int i = last; i <= m; ++i) {
		vector<int> p = cur;
		p.push_back(i);
		construct(p);
	}
}
struct S {
	int a, b, c, d;
};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(20);
	int q;
	cin >> n >> m >> q;
	construct({});
	vector<S> vec(q);
	for (int i = 0; i < q; ++i) {
		cin >> vec[i].a >> vec[i].b >> vec[i].c >> vec[i].d;
		--vec[i].a;
		--vec[i].b;
	}
	int answer = 0;
	for (const vector<int>& p : perm) {
		int cur_ans = 0;
		for (int i = 0; i < q; ++i) {
			if (p[vec[i].b] - p[vec[i].a] == vec[i].c) {
				cur_ans += vec[i].d;
			}
		}
		answer = max(answer, cur_ans);
	}
	cout << answer << '\n';
 	return 0;
}


Measured memory_bytes: 9812
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define vcout(v) rep(i,v.size()) cout << v[i] << " "; cout << endl
#define mcout(m) rep(j,m.size()){vcout(m[j]);}
const ll MOD = 998244353;


struct robo{ll x1; ll x2; ll idx;
	bool operator<(const robo& o) const{
		return x1 < o.x1;
	}
};

void mainsolve(){


	ll n;
	cin >> n;
	vector<robo> aa(n);
	
 	rep(i,n){
		ll x,d;
		cin >> x >> d;
		aa[i] = robo{x,x+d,i};

	}
	sort(aa.rbegin(), aa.rend());

	vector<vector<ll>> to(n);

	set<robo> st;
	rep(i,n){

		while(!st.empty() && aa[i].x2 > st.begin()->x1){
			to[aa[i].idx].push_back(st.begin()->idx);
			st.erase(st.begin());
		}
		st.insert(aa[i]);
	}
	reverse(aa.begin(),aa.end());
	vector<vector<ll>> dp(n,vector<ll>(2,-1));

	vector<bool> checked(n,false);

	function<ll(ll,bool)> dfs = [&](ll v, bool moved) {
		checked[v] = true;
		if(dp[v][moved] != -1) return dp[v][moved];

		ll res = 1;
		for(auto ch : to[v]){
			if(moved){
				( res *= dfs(ch,true) ) %= MOD;
			}
			else{
				(res *= (dfs(ch,false) + dfs(ch,true)) % MOD) %= MOD;
			}

		}
		return dp[v][moved] = res;
	};

	ll res = 1;
	rep(i,n){
		if(!checked[aa[i].idx]){
			ll tmp = ( dfs(aa[i].idx,false) + dfs(aa[i].idx,true) ) % MOD;
			(res *= tmp) %= MOD;
		}
	}

	cout << res << endl;
	return;
}

int main(){
	
//	ll TC;cin>>TC;rep(I,TC){cout<<"case:"<<I+1<<"---"<<endl; // comment out!
		mainsolve();
//	} // comment out!
	return 0;
}


Measured memory_bytes: 51840
import sys
readline = sys.stdin.readline

S = readline().rstrip()
DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[i + 1][0] : i文字目まで見たとき、ABCの部分文字列がまだ始まっていない場合の数
# dp[i + 1][1] : i文字目まで見たとき、ABCのAまで一致した場合の数
# dp[i + 1][2] : i文字目まで見たとき、ABCのBまで一致した場合の数
# dp[i + 1][3] : i文字目まで見たとき、ABCのCまで一致した場合の数

dp[0][0] = 1

for i in range(len(S)):
  if S[i] == "A" or S[i] == "?":
    dp[i + 1][0] += dp[i][0] # まだ始まっていない状態をそのまま
    dp[i + 1][1] += dp[i][1] # まだ始まっていない状態をそのまま
    dp[i + 1][2] += dp[i][2] # まだ始まっていない状態をそのまま
    dp[i + 1][3] += dp[i][3] # まだ始まっていない状態をそのまま
    dp[i + 1][1] += dp[i][0] # 開始状態に遷移することが出来る
    
  if S[i] == "B" or S[i] == "?":
    dp[i + 1][0] += dp[i][0] # その文字を選ばない場合
    dp[i + 1][1] += dp[i][1] # その文字を選ばない場合
    dp[i + 1][2] += dp[i][2] # その文字を選ばない場合
    dp[i + 1][3] += dp[i][3] # その文字を選ばない場合
    dp[i + 1][2] += dp[i][1] # Bを使用した状態に遷移
  
  if S[i] == "C" or S[i] == "?":
    dp[i + 1][0] += dp[i][0] # その文字を選ばない場合
    dp[i + 1][1] += dp[i][1] # その文字を選ばない場合
    dp[i + 1][2] += dp[i][2] # その文字を選ばない場合
    dp[i + 1][3] += dp[i][3] # その文字を選ばない場合
    dp[i + 1][3] += dp[i][2] # Cを使用した状態に遷移
    
  for j in range(4):
    dp[i + 1][j] %= DIV
    
# 最後の文字まで見たとき、Cまで一致した場合の数が答え
print(dp[len(S)][3])


Measured memory_bytes: 32064
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();


        if (n < 105){
            System.out.println(0);
        } else {
            if (n < 135){
                System.out.println(1);
            } else {
                if (n < 165){
                    System.out.println(2);
                } else {
                    if (n < 189){
                        System.out.println(3);
                    } else {
                        if (n < 195){
                            System.out.println(4);
                        } else {
                            System.out.println(5);
                        }
                    }
                }
            }
        }
    }
}





Measured memory_bytes: 22868
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = (int)1e9;
const long long mod = (long long)1e9 + 7;
const double pi = acos(-1.0);

int main() {
	LL n; cin >> n;
	VL a(n); rep(i, n)cin >> a[i];
	VL b(n); rep(i, n)b[i] = a[i] - i - 1;
	sort(all(b));

	LL B1 = b[(n - 1) / 2], B2 = b[n / 2];
	LL c1 = 0, c2 = 0;
	rep(i, n) {
		c1 += abs(a[i] - (B1 + i + 1));
		c2 += abs(a[i] - (B2 + i + 1));
	}
	Cout(min(c1, c2));
}

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


#define  SZ(items) (int)items.size()
#define  CLR(a)  memset(a,0,sizeof(a))
#define  SET(a)  memset(a,-1,sizeof(a))
#define  nl "\n";

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



template <class T> inline T biton(T n, T pos)
{
    return n | ((T)1 << pos);
}
template <class T> inline T bitoff(T n, T pos)
{
    return n & ~((T)1 << pos);
}
template <class T> inline T ison(T n, T pos)
{
    return (bool)(n & ((T)1 << pos));
}
template <class T> inline T gcd(T a, T b)
{
    while (b)
    {
        a = a % b;
        swap(a, b);
    }
    return a;
}
template <class T> inline T bigmod(T p, T e, T m)
{
    T ret = 1;
    for (; e > 0; e >>= 1)
    {
        if (e & 1)
            ret = (ret * p) % m;
        p = (p * p) % m;
    }
    return (T)ret;
};

#ifdef DEBUG
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template < typename Arg1 >
void __f(const char* name, Arg1&& arg1)
{
    cerr << name << " is " << arg1 << std::endl;
}
template < typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args)
{
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " is " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define debug(...)
#endif

int k;
string str;
vector<int> bits;

long long dp[105][2][105];

long long Recur(int pos,int isSmall,long long cnt)
{

    if ((int)bits.size() == pos)
    {
        return cnt==k;
    }

    if (dp[pos][isSmall][cnt]!= -1)
    {
        return dp[pos][isSmall][cnt];
    }

    long long sum = 0;
    int to = isSmall ? 9 : bits[pos];

    for (int i = 0; i <= to; i++)
    {
        if(cnt==k && i==0)
        {
            sum += Recur( pos + 1, isSmall || i < bits[pos], (i!=0) ? cnt + 1 : cnt);
        }
        else if(cnt<k)
        {
            sum += Recur( pos + 1, isSmall || i < bits[pos], (i!=0) ? cnt + 1 : cnt);
        }

    }

    return dp[pos][isSmall][cnt]= sum;
}

void solve()
{

    SET(dp);
    cin>>str>>k;

    for(auto t:str)
    {
        bits.push_back(t-'0');
    }


    long long a=Recur(0ll,0ll,0ll);
    cout<<a<<endl;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    cout.tie(nullptr);
    cin.tie(nullptr);

    int t = 1;

    while (t--)
    {
        solve();
    }

    return 0;
}


Measured memory_bytes: 384
K = int(input())

print((1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51)[K - 1])

Measured memory_bytes: 3060
/*1.4*/
#include "bits/stdc++.h"
using namespace std;


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

    int h[n];
    for(int i = 0; i < n; ++i) cin >> h[i];

    int dp[n];
    dp[0] = 0;

    dp[1] = abs(h[1] - h[0]);
    for(int i = 2; i < n; ++i) {
        dp[i] = min(dp[i-2] + abs(h[i-2] - h[i]), dp[i-1] + abs(h[i-1] - h[i]));

    }
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <set>
#include <algorithm>
#include <numeric>

using namespace std;


int main() {
  int N, A, B;
  cin >> N >> A >> B;
  cout << min(N * A, B) << endl;
  return 0;
}


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

int main(){
  int i,j,b,r,g,c,s,t,ans;
  while(1){
    cin >> b >> r >> g >> c >> s >> t;
    if(!b && !r && !g && !c && !s && !t) break;

    ans = 100;
    ans += 15 * b + r * 15 + 7 * g + 2 * c;
    ans += 15 * (b * 5 + r * 3);
    ans -= 3 * (t - s - b*5 - r*3) + 2 * (b * 5 + r * 3);

    cout << ans << endl;

  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,n) for(i=a;i<n;i++)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define sortrev(x) sort(all(x),greater<int>())
#define pi 3.1415926535897932384626

typedef pair<int,int> pii;
typedef pair<ll, ll> pl;
typedef vector<int>	vi;
typedef vector<bool> vb;
typedef vector<ll>	vl;
typedef vector<pii>	vpii;
typedef vector<pl>	vpl;
typedef vector<vi>	vvi;
typedef vector<vl>	vvl;
typedef vector<double> vd;


const int mod = 100000007;
const int inf = 100000005;
const int N = 200007, M = N;
int i,j,idx,cnt,par;

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

    ll ans = 1;

    if(n == 1) {
        cout<<"0\n";
        return;
    }

    fo(i,3,n+1) {
        ans+=(i-1);
    }
    cout<<ans<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    //cin >> t;
    while(t--) {
      solve();
    }

    return 0;
}




Measured memory_bytes: 3632
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt(); 
		int m = stdIn.nextInt();
		int c = stdIn.nextInt();
		
		int[] b = new int[m];
		
		for(int i = 0; i < m; i++) {
			b[i] = stdIn.nextInt();
		}
		
		int ans = 0;
		
		for(int i = 0; i <n; i++) {
			int[] a = new int[m];
			int cnt = 0;
			for(int j = 0; j < m; j++) {
				a[j] = stdIn.nextInt();
				cnt += a[j]*b[j];
			}
			if(cnt+c>0) {
				ans++;
			}
		}
		System.out.println(ans);
		
		
	}

}


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

int main(void)
{
    string s;
    cin >> s;
    int i = s.find('A');
    int f;
    for(int j = 0; j < s.size(); j++)
    {
        if(s[j] == 'Z') f = j;
    }
    cout << f - i + 1 << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    if(n >= 1200) cout << "ARC" << endl;
    else cout << "ABC" << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define lcm xyz
using namespace std;

const int N=1e4+20,MAX=1e6+20, MOD=1e9+7;

int n,x,lp[MAX],a[N],mx[MAX],ans;
map <int,int> lcm;

int power(int a, int b)
{
	if(b==0) return 1;
	int ans = power(a, b / 2);
	ans = (1ll * ans * ans) % MOD;
	if(b%2 == 1) ans = (1ll * ans * a) % MOD;
	return ans;
}

int inverse_euler(int n)
{
	return power(n,MOD-2);
}

int main()
{
	for(int i = 2; i < MAX; i++)
		for(int j = i; j < MAX; j+=i)
			if(lp[j] == 0) lp[j] = i;

	scanf("%d",&n);
	for(int i = 0; i < n;i++)
	{
		scanf("%d",&a[i]);

		map <int,int> m;
		int x = a[i];
		while(x != 1) {
			m[lp[x]]++;
			x /= lp[x];
		}

		for(auto i:m) {
			mx[i.first] = max(mx[i.first], i.second);
		}
	}

	for(int i = 0; i < MAX; i++)
	{
		if(mx[i]==0) continue;
		lcm[i] = mx[i];
	}

	int lans = 1;
	for(auto i: lcm) {
		lans = (1ll * lans * power(i.first, i.second)) % MOD;
	}

	for(int i = 0;i < n; i++)
	{
		map <int,int> m;
		int x = a[i];
		while(x != 1) {
			m[lp[x]]++;
			x /= lp[x];
		}

		int v=1;
		for(auto i: m) {
			v = (1ll * v * power(i.first, i.second)) % MOD;
		}

		ans = (ans + (1ll * lans * inverse_euler(v)) % MOD) % MOD;
	}

	printf("%d",ans);
}

// 2 3 4
// 2^1
// 3^1
// 2^2

// lcm - 2^2 * 3^1


// 2^1 * 3^1 - 6
// 2^2 - 4
// 3^1 - 3









// 2, 10, 24
// 2^1
// 2^1 * 5^1
// 2^3 * 3^1

// 2^3 * 3^1 * 5^1


// 2^2 * 3^1 - 12
// 2^2 * 3^1
// 5^1

Measured memory_bytes: 10384
#include<iostream>
#include<queue>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

class place{
public:
	int x;
	int y;
};

int main(){
	int W,H;
	while(1){
		cin>>W>>H;
		if(W==0 && H==0)break;
		bool dt[H][W];
		int startx,starty;
		rep(i,H){
			rep(j,W){
				char c;
				cin>>c;
				if(c=='.'){
					dt[i][j]=false;
				}else if(c=='#'){
					dt[i][j]=true;
				}else{
					startx=j;
					starty=i;
					dt[i][j]=false;
				}
			}
		}
		queue<place> que;
		place p;
		p.x=startx;
		p.y=starty;
		que.push(p);
		int cnt=0;
		int dirx[4]={1,0,-1,0};
		int diry[4]={0,1,0,-1};
		while(!que.empty()){
			p=que.front();
			que.pop();
			if(!dt[p.y][p.x])cnt++;
			dt[p.y][p.x]=true;
			rep(k,4){
				int nx=p.x+dirx[k];
				int ny=p.y+diry[k];
				if(nx>=0 && ny>=0 && nx<W && ny<H && !dt[ny][nx]){
					place pp;
					pp.x=nx;
					pp.y=ny;
					que.push(pp);
				}
			}
		}
		cout<<cnt<<endl;
	}
	return 0;
}

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

using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;

ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll g = a; x = 1; y = 0;
    if(b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}

int main() {
    ll a, b;
    cin >> a >> b;
    ll x, y;
    extgcd(a, b, x, y);
    cout << x << ' ' << y << endl;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e8+10;
char ch[maxn];
int len;
ll sum;
int main(){
	cin>>ch+1;
	len=strlen(ch+1);
	for(int i=1;i<=len;i++)sum+=ch[i]-'0';
	if(sum%9==0)puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 3708
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] a;
    if(N % 2 == 0){
      a = new int[N/2];
    }else{
      a = new int[N/2 + 1];
    }
    Arrays.fill(a, 0);
    for(int i = 0; i < N; i++){
      int tmp = sc.nextInt();
      if(tmp % 2 == N % 2){
        System.out.println(0);
        System.exit(0);
      }
      if(tmp > N - 1){
        System.out.println(0);
        System.exit(0);
      }
      a[tmp/2]++;
      if(a[tmp/2] > 2){
        System.out.println(0);
        System.exit(0);
      }
    }
    if(N % 2 == 0){
      for(int i = 0; i < a.length; i++){
        if(a[i] != 2){
          System.out.println(0);
          System.exit(0);
        }
      }
    }else{
      if(a[0] != 1){
        System.out.println(0);
        System.exit(0);
      }
      for(int i = 1; i < a.length; i++){
        if(a[i] != 2){
          System.out.println(0);
          System.exit(0);
        }
      }
    }
    long ans = 1L;
    for(int i = 0; i < N/2; i++){
      ans = (ans * 2) % 1000000007L;
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 48520
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,a,b) for(int i = (a); i >= (b); i--)
#define mst(a,b) memset(a,b,sizeof(a));
#define clr(a) mst(a,0);
#define pb  push_back
#define mp  make_pair
#define first fi
#define second se
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const double PI = acos(-1);
//head

int x,y,x2,y2,x3,y3,x4,y4;

int main(int argc, char const *argv[]){

	cin >> x >> y >> x2 >> y2;
	y3 = y2+x2-x;
	x3 = x2-y2+y;
	y4 = y3-y2+y;
	x4 = x3-x2+x;
	cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
	
	

	
	return 0;
}












Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int oto[10100000];
long long L[500];
char p[10100000];
map<long long, long long>Map[500];
int Do(int n) {
	int i;
	p[n] = 0;
	oto[0] = -1;
	for (i = 1; i <= n; i++) {
		int t = oto[i - 1];
		while (t != -1 && p[i - 1] != p[t])t = oto[t];
		oto[i] = t + 1;
	}
	for (int TT = 0; TT < 3; TT++) {
		int t = n;
		while (t * 2 >= n)t = oto[t];
		L[TT] = n;
		int tn = n * 2 - t * 2;
		for (i = n + 1; i <= tn; i++) {
			p[i - 1] = p[t - 1 + i - n];
			int tt = oto[i - 1];
			while (tt != -1 && p[i - 1] != p[tt])tt = oto[tt];
			oto[i] = tt + 1;
		}
		n = tn;
		L[TT + 1] = n;
	}
	if (L[3] - L[2] == L[2] - L[1]) return 1;
	return 2;
}
long long C[26], C2[26], T[26];
void Get1(long long n) {
	int i;
	for (i = 0; i < 26; i++)T[i] = C[i] = 0;
	for (i = 0; i < min(L[1], n); i++)C[p[i] - 'a']++;
	for (i = L[1]; i < L[2]; i++)T[p[i] - 'a']++;
	if (n <= L[1])return;
	for (i = 0; i < 26; i++)C[i] += ((n - L[1]) / (L[2] - L[1])) * T[i] ;
	for (i = 0; i < (n - L[1]) % (L[2] - L[1]); i++)C[p[L[1] + i] - 'a']++;
}
int main() {
	int i;
	long long b, e;
	scanf("%s", p);
	scanf("%lld%lld", &b, &e);
	for (i = 0; p[i]; i++);
	int n = i;
	if (Do(n) == 1) {
		Get1(b-1);
		for (i = 0; i < 26; i++)C2[i] = C[i];
		Get1(e);
		for (i = 0; i < 26; i++)printf("%lld ", C[i] - C2[i]);
		return 0;
	}
	else {
		int i;
		for (i = 4;; i++) {
			L[i] = L[i - 1] + L[i - 2];
			if (L[i] >= e)break;
		}
		int pv = i;
		Map[pv][e]++;
		Map[pv][b - 1]--;
		for (i = pv; i >= 2; i--) {
			for (auto &tp : Map[i]) {
				if (tp.first <= L[i - 1])Map[i - 1][tp.first] += tp.second;
				else {
					Map[i - 1][L[i - 1]]+=tp.second;
					Map[i - 1][tp.first - L[i] / 2]+=tp.second;
					Map[i - 1][L[i - 1] - L[i] / 2]-=tp.second;
				}
			}
		}
		long long s = 0;
		for (i = L[1]; i >= 1; i--) {
			s += Map[1][i];
			C[(p[i - 1] - 'a')] += s;
		}
		for (i = 0; i < 26; i++)printf("%lld ", C[i]);
	}
}

Measured memory_bytes: 32384
package main

import (
	"fmt"
	"regexp"
	"strings"
)

func main() {
	var s, t string

	r := regexp.MustCompile(`[a-z]*`)

	fmt.Scanf("%s", &s)
	fmt.Scanf("%s", &t)

	slen := len(s)
	tlen := len(t)

	if (r.MatchString(s)) && (r.MatchString(t)) &&
		(slen >= 1) && (slen <= 10) && (slen+1 == tlen) && (strings.HasPrefix(t, s)) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 2048
# -*- coding: utf-8 -*-
import bisect
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


ans = [-1] * (2*10**5+1)


@mt
def slv(N, A, UV):
    A.insert(0, -1)
    g = [list() for _ in range(0, N+1)]
    for u, v in UV:
        g[u].append(v)
        g[v].append(u)

    def dfs(u, p, dp):
        global ans

        for v in g[u]:
            if v == p:
                continue

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF)
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+1)
    dp[0] = A[1]
    dfs(1, 0, dp)

    ans[1] = 1
    for i in range(1, N+1):
        print(ans[i])


def main():
    N = read_int()
    A = read_int_n()
    UV = [read_int_n() for _ in range(N-1)]
    slv(N, A, UV)


if __name__ == '__main__':
    main()


Measured memory_bytes: 383380
#include<stdio.h>

int main(){
	char line[64];
	unsigned int sp_1, sp_2;

	fgets(line, 64, stdin);

	for(sp_1 = 0; line[sp_1] != ' '; sp_1++) ;
	for(sp_2 = sp_1+1; line[sp_2] != ' '; sp_2++) ;
	
	if((line[sp_1-1] == line[sp_1+1]) && (line[sp_2-1] ==line[sp_2+1])){
		printf("YES\n");
	} else{
		printf("NO\n");
	}
	
	return 0;
}

Measured memory_bytes: 128
#include <queue>
#include <cstdio>
#include <iostream>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <stack>
using namespace std;
typedef long long int ll;

#define EPS (1e-9)
#define INF (1e9)
#define PI (acos(-1))
#define REP(i,n) for(int i=0;i<n;i++)

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

ll beki(ll a, ll b) {
	ll tmp = 1;
	REP(i, b) tmp *= a;
	return tmp;
}

int N, D;

int main() {
	cin >> N >> D;
	int a = 2 * D + 1;
	int ans = 0;
	while (true) {
		ans++;
		N -= a;
		if (N <= 0) break;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool com(char a,char b){
    return a<b;
}
int main(){
    int a,b,c,i,n;
    cin>>n;
    char arr[100][100];
    for(i = 0;i < n;i++){
        scanf("%s",arr[i]);
    }
    b = 0x3f3f3f3f;
    c = 0;
    for(i = 0;i < n;i++){
        a = strlen(arr[i]);
        if(a < b){
            b = a;
            c = i;
        }
    }

    char dp[100];
    int j = 0,k=0,m;
    char s;
    for(i = 0;i < strlen(arr[c]);i++){
        for(a = 0;a < n;a++){
            for(b = 0;b < strlen(arr[a]);b++){
                if(arr[a][b]==arr[c][i]&&a!=c){
                    j++;
                    s = arr[a][b];
                    arr[a][b] = arr[a][0];
                    arr[a][0] = s;
                    break;
                }
            }
        }
        if(j==n-1){
            dp[k] = arr[c][i];
            k++;
            for(m = 0;m < n;m++){
                if(m!=c){
                    arr[m][0] = '0';
                }
            }
        }
        j = 0;
    }
    sort(dp,dp+k,com);
    for(i = 0;i < k;i++){
        cout<<dp[i];
    }
    if(strlen(dp)==0){
        cout<<"The answer is an empty string.";
    }
}



Measured memory_bytes: 256
//AUTHOR: RAVAN_2070
//PUNE INSTITUTE OF COMPUTER TECHNOLOGY
/*
        PEOPLE'S LIVES DON'T END WHEN THEY DIE.
        IT ENDS WHEN THEY LOSE FAITH
                                     -ITACHI UCHIHA
        EXPLAINATION BELOW->
        
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pair<ll,ll>> vii;
typedef pair<ll,ll> pii;
typedef map<ll,ll> mii;
#define MOD7 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define Test_cases ll TC;cin>>TC;while(TC--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed<<setprecision(x)
#define sz(x) (ll)(x.size())
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
ll modularExponentiation(ll x,ll n,ll M)
{   
    ll result=1;
    while(n>0)
    {
        if(n % 2 ==1)
        result=(result * x)%M;
        x=(x*x)%M;
        n=n/2;
    }
        return result;
}
ll nCr(ll n,ll r)
{
    ll N,D,i;
    N=1;
    D=1;
    fo(i,0,r)
    {
       N=N*(n-i);N%=MOD7;
       D=D*(i+1);D%=MOD7;
    }
   D=modularExponentiation(D,MOD7-2,MOD7);
   ll ans=(N*D)%MOD7;
   if(ans<0)ans+=MOD7;
   ans%=MOD7;
   return ans;
    
}
void solve()
{
  ll n,a,b;cin>>n>>a>>b;
  ll ans=(modularExponentiation(2LL,n,MOD7)-1+MOD7)%MOD7;
  ans=(ans-nCr(n,a))%MOD7;if(ans<0){ans+=MOD7;ans%=MOD7;}
  ans=(ans-nCr(n,b))%MOD7;if(ans<0){ans+=MOD7;ans%=MOD7;}
  cout<<ans<<"\n";
}
int main()
{
   fastio
   solve();
    
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iterator>
#include <iomanip>
#include <cmath>
#include <vector>
#include <numeric>
#include <cstdio>
#include <bitset>
#include <map>
#include <string>
#include <valarray>
#include <queue>
#include <utility>

using namespace std;

int main() 
{
    int N, W;
    cin >> N >> W;

    vector<int> values(N+1);
    vector<int> weights(N+1);

    for (int i = 1; i <= N; i++)
        cin >> values[i] >> weights[i];

    vector< vector<int> > F(N+1, vector<int>(W+1));

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= W; j++)
            if (weights[i] > j)
                F[i][j] = F[i-1][j];
            else
                F[i][j] = max(F[i-1][j-weights[i]]+values[i], F[i-1][j]);

    cout << F[N][W] << endl;

    // for (int i = 0; i < N; i++)
    //     cout << values[i] << ' ' << weights[i] << endl;

    
}


Measured memory_bytes: 6760
#include<stdio.h>
     
 int main(){
 int h,w;
 scanf("%d%d",&h,&w);
 int qes[h][w],j,i,ans[h*w][4],cnt=0; 
 for(i=0;i<h;i++){
  for(j=0;j<w;j++){
   scanf("%d",&qes[i][j]);
  }
 }
 for(i=h-1;i>0;i--){
  for(j=0;j<w;j++){
   if(qes[i][j]!=0){
    while(qes[i][j]%2==1){
     qes[i][j] -= 1;
     qes[i-1][j]+=1;
     ans[cnt] [0] =i+1;
     ans[cnt] [1] =j+1;
     ans[cnt] [2] =i;
     ans[cnt] [3] =j+1;
     cnt++;
   	}
   }
  }
 }
 for(i=w-1;i>0;i--){
  while(qes[0][i]%2==1){
   qes[0][i]-= 1;
   qes[0][i-1]+=1;
   ans[cnt] [0] =1;
   ans[cnt] [1] =i+1;
   ans[cnt] [2] =1;
   ans[cnt] [3] =i;
   cnt++;
  }
 }
 printf("%d\n",cnt);
 for(i=0;i<cnt;i++){
  printf("%d %d %d %d\n",ans[i][0],ans[i][1],ans[i][2],ans[i][3]);
 } 
 return 0;
}

Measured memory_bytes: 6912
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Contest.A
{
	class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			Scanner cin = new Scanner();
			int a = cin.nextInt();
			int b = cin.nextInt();
			int c = cin.nextInt();
			int d = cin.nextInt();

			if (a + b == c + d) Console.WriteLine("Balanced");
			else if (a + b > c + d) Console.WriteLine("Left");
			else Console.WriteLine("Right");

			Console.Out.Flush();
		}
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return next();
			i = 0;
			return s[i++];
		}

		public int nextInt()
		{
			return int.Parse(next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextInt() + add;
			}
			return Array;
		}

		public long nextLong()
		{
			return long.Parse(next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextLong() + add;
			}
			return Array;
		}

		public double nextDouble()
		{
			return double.Parse(next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextDouble() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
int C[5][5],rowb[5],cola[5];
bool f1()
{

    for(int a1=0;a1<=100;a1++){
        for(int a2=0;a2<=100;a2++){
            for(int a3=0;a3<=100;a3++){
                if(rowb[1]-3*a1==rowb[2]-3*a2&&rowb[2]-3*a2==rowb[3]-3*a3){
                    return 1;
                }
            }
        }
    }
    return 0;
}
bool f2()
{

    for(int b1=0;b1<=100;b1++){
        for(int b2=0;b2<=100;b2++){
            for(int b3=0;b3<=100;b3++){
                if(cola[1]-3*b1==cola[2]-3*b2&&cola[2]-3*b2==cola[3]-3*b3){
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main ()
{
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cin >> C[i][j];
            rowb[i]+=C[i][j];
        }
    }
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            //cin >> C[i][j];
            cola[i]+=C[j][i];
        }
    }
    if(f1()&&f2())cout<<"Yes\n";
    else cout<<"No\n";
}


Measured memory_bytes: 256
N = int(input())
Alist = list(map(int, input().split()))
Blist = list(map(int, input().split()))
Clist = list(map(int, input().split()))

ans = 0
for i in range(N):
    ans += Blist[i]
for i in range(N-1):
    if Alist[i]+1 == Alist[i+1]:
        # AlistとBlist,Clistの対応する並び方をあわせる　わかりづらい
        ans += Clist[Alist[i]-1]

print(ans)

Measured memory_bytes: 3064
# B

n = int(input())

ans = 0

if n >= 10000:
    ans += min(n,99999) - 10000 + 1
if n >= 100:
    ans += min(n,999) - 100 + 1
if n >= 1:
    ans += min(n,9) - 1 + 1

print(ans)

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

string replace(string S, char a, char b){
  string ret = S;
  for(int i = 0; i < S.length(); ++i){
    if(S[i] == a) ret[i] = b;
  }
  return ret;
}

class Parser{
public:
  string s;
  size_t i;
  int parse(){
    i = 0;
    return formula();
  }
  int formula(){
    if(i >= s.length()) return 0;
    if(s[i] >= '0' && s[i] <= '2'){
      ++i;
      return s[i-1] - '0';
    }
    if(s[i] == '-'){
      ++i;
      return 2 - formula();
    }
    if(s[i] == '('){
      ++i;
      int x = formula();
      char o = s[i];
      ++i;
      int y = formula();
      ++i;
      if(o == '*') return min(x,y);
      if(o == '+') return max(x,y);
    }
    return -1;
  }
};


int solve(string S){
  int ret = 0;
  for(int i = 0; i < 3; ++i){
    for(int j = 0; j < 3; ++j){
      for(int k = 0; k < 3; ++k){
        string S_ = S;
        S_ = replace(S_,'P','0'+i);
        S_ = replace(S_,'Q','0'+j);
        S_ = replace(S_,'R','0'+k);
        Parser P;
        P.s = S_;
        if(P.parse() == 2) ++ret;
      }
    }
  }
  return ret;
}

int main(){
  string S;
  while(cin >> S, S != "."){
    cout << solve(S) << endl;
  }
  return 0;
}



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

int main()
{
    long long x;
    long long a=100;
    cin>>x;
    for(long long i=0;;i++){
        if(a>=x){
            cout<<i;
            return 0;
        }
        a+=a/100;

    }
    return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

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

    int out;
    out = a - b * 2;

    if (out > 0) {
        cout << out << endl;
    }
    else {
        cout << 0 << endl;
    }
}


Measured memory_bytes: 256
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
A = list(map(int, input().split()))

def solve(N,A):
    if all(x == 0 for x in A):
        return True
    q,r = divmod(N,3)
    if r:
        return False
    counter = Counter(A)
    n = len(counter)
    if n == 1:
        return False
    if n == 2:
        a,b = counter.keys()
        if a > b:
            a,b = b,a
        if a != 0:
            return False
        # 0,b
        if counter[0] != N//3:
            return False
        return True
    if n == 3:
        a,b,c = counter.keys()
        for x in [a,b,c]:
            if counter[x] != q:
                return False
        return a^b^c == 0
    return False
print('Yes' if solve(N, A) else 'No')

Measured memory_bytes: 20732
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define clr(a, b) memset(a, b, sizeof(a))
#define Error(x) cout << #x << " = " << x << endl
#define iDEBUG freopen("in.txt", "r", stdin)
#define oDEBUG freopen("output.txt","w",stdout)
#define pb push_back
#define x first
#define y second
#define all(x) x.begin(),x.end()
typedef long long ll;

using namespace std;
int gcd(int m, int n) { if((0 == m) || (0 == n)){return 0;} while(m != n){ if(m > n){m -= n;}else{n -= m;} } return m; }
int lcm(int m, int n) { if((0 == m) || (0 == n)){return 0;} return (m / gcd(m, n)) * n; }

int main()
{_
    int a, b;
    cin >> a >> b;
    cout << ((a*b)%2==0 ? "Even" : "Odd");

    return 0;
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, R = LI()
    if N >= 10:
        print(R)
    else:
        ans = R + 100 * (10 - N)
        print(ans)

main()



Measured memory_bytes: 67052
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int h,a,sum=0;
    cin>>h>>a;
    int arr[a];
    for(int i=0;i<a;i++)
    {
        cin>>arr[i];
        sum+=arr[i];
    }
    if(sum>=h)
    cout<<"Yes";
    else
    cout<<"No";
    return 0;
}
    
    
    
    
    

Measured memory_bytes: 640