akhauriyash/Code-Regression huggingface dataset:
//submitted by HimJ
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define fr(i,s,e) for(i=s;i<e;i++)
#define ms(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
const int mxn=1e5;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  int t=1;
  //cin>>t;
    while(t--){
            int n,i;
    cin>>n;
    ll arr[n],ans[n],sum=0;
    fr(i,0,n)
    cin>>arr[i];
    fr(i,1,n)
    sum+=abs(arr[i]-arr[i-1]);
    sum+=abs(arr[0]);
    sum+=abs(arr[n-1]);
    fr(i,1,n-1)
    {
        ll temp=sum;
        if(i-1>=0)
            temp-=abs(arr[i]-arr[i-1]);
        if(i+1<n)
            temp-=abs(arr[i]-arr[i+1]);
        temp+=abs(arr[i-1]-arr[i+1]);
        ans[i]=temp;
    }
    i=n-1;
    ll temp=sum;
    temp-=abs(arr[i-1]-arr[i]);
    temp-=abs(arr[i]);
    temp+=abs(arr[i-1]);
    ans[i]=temp;
    temp=sum;
    i=0;
    temp-=abs(arr[i]-arr[i+1]);
    temp-=abs(arr[i]);
    temp+=abs(arr[i+1]);
    ans[i]=temp;
    fr(i,0,n)
    cout<<ans[i]<<"\n";

  }
  return 0;
  }



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

int N, M, X;
vector<int> C, E;
vector<vector<int>> A;

int main()
{
  cin >> N >> M >> X;
  C.resize(N);
  E.resize(M, 0);
  A.resize(N, vector<int>(M));
  for (int i = 0; i < N; i++)
  {
    for (int j = -1; j < M; j++)
    {
      int n;
      cin >> n;
      if (j == -1)
      {
        C.at(i) = n;
      }
      else
      {
        A.at(i).at(j) = n;
      }
    }
  }
  int min_cost = 10000000, tmp;
  for (int bit = 0; bit < (1 << N); bit++)
  {
    for (int j = 0; j < M; j++)
    {
      E.at(j) = 0;
    }
    tmp = 0;
    for (int i = 0; i < N; i++)
    {
      if (bit & (1 << i))
      {
        tmp += C.at(i);
        for (int j = 0; j < M; j++)
        {
          E.at(j) += A.at(i).at(j);
        }
      }
    }
    bool flag = true;
    for (int j = 0; j < M; j++)
    {
      if (E.at(j) < X)
      {
        flag = false;
        break;
      }
    }
    if (flag)
    {
      min_cost = min(min_cost, tmp);
    }
  }
  if (min_cost == 10000000)
  {
    min_cost = -1;
  }
  cout << min_cost << endl;
}

Measured memory_bytes: 3640
#include<iostream>
#include<vector>
#define MAX 1046527
using namespace std;

vector<string> dictionaly(MAX);
int cnt = 0;

int h1(int key){
  return key % MAX;
}

int h2(int key){
  return 1 + (key % (MAX-1));
}

int toInt(char c){
    if(c == 'A') return 1;
    else if(c == 'C') return 2;
    else if(c == 'G') return 3;
    else return 4;
}

long long int Key(string s){
  long long int ans = 0;
  long long int p = 1;

  for(long long int i = 0; i < s.size(); i++){
    ans += p*(toInt(s[i]));
    p *= 5;
  }

  return ans;
  
}

void insert(string s){
  long long int key, h;
  key = Key(s);
  
  for(long long int i = 0; ;  i++){
    h = (h1(key) + i*h2(key)) % MAX;

    if(dictionaly[h] == s) break;

    else if(dictionaly[h].size() == 0){
      dictionaly[h] = s;
      break;
    }
  }
}

int find(string s){
  long long int key, h;

  key = Key(s);
  
  for(long long int i = 0; ; i++){
    h = (h1(key) + i*h2(key)) % MAX;

    if(dictionaly[h] == s) return 1;

    else if(dictionaly[h].size() == 0) return 0;
  }

  return 0;
    
}

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

  dictionaly.resize(n);

  string check;
  string s;

  for(int i = 0; i < n; i++){
    cin >> check >> s;

    if(check == "insert") insert(s);

    else{
      if(find(s)) cout << "yes" << endl;
	 else cout << "no" << endl;
    }    
  }

  return 0;

}



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

int main(){
    string s[3], S;
    cin >> s[0] >> s[1] >> s[2];
    
    S.push_back(s[0][0]);
    S.push_back(s[1][0]);
    S.push_back(s[2][0]);
    
    S[0] = S[0] - 32;
    S[1] = S[1] - 32;
    S[2] = S[2] - 32;
    cout << S << endl;
}


Measured memory_bytes: 256
#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;
main(){
    int N,M;
    cin >> N >> M;
    set<int> st[M];
    vector<int> V[M];
    rep(i,0,M){
        int num;
        cin >> num;
        rep(j,0,num){
            int n;
            cin >> n;
            //V[i].push_back(n-1);
            st[i].insert(n-1);
        }
    }
    vector<int> P(M);
    rep(i,0,M){
        cin >> P[i];
    }
    int ans = 0;
    rep(i,0,1 << N){
        vector<int> cnt(M);
        rep(j,0,N){
            if(!(i & (1 << j)))continue;
            rep(k,0,M){
                if(st[k].count(j))cnt[k]++;
            }
        }
        bool flag = 1;
        rep(j,0,M){
            if(cnt[j] % 2 != P[j]){
                flag = 0;
                break;
            }
        }
        if(flag)ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 2147483600
#define long long long // for codeforces

int main(){
  int n,m;
  cin>>n>>m;
  vector<string> vec(n);
  vector<string> mat(m);
  rep(i,n) cin>>vec[i];
  rep(i,m) cin>>mat[i];

  auto solve = [&](int x, int y){
    rep(i,m)rep(j,m){
      if(vec[x+i][y+j]!=mat[i][j]) return false;
    }
    return true;
  };

  for(int i=0; i+m<=n; i++){
    for(int j=0; j+m<=n; j++){
      if(solve(i,j)){
        cout<<"Yes"<<endl;
        return 0;
      }
    }
  }
  cout<<"No"<<endl;
  return 0;
}


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

using namespace std;
using card = pair<char, int>;
using card_list = vector<card>;
using Iterator = card_list::iterator;


Iterator partition(Iterator begin, Iterator end, card x) {
    for (auto it = begin; it != end; ++it) {
        if (it->second <= x.second) {
            swap(*begin++, *it);
        }
    }
    return begin-1;
}

void quick_sort(Iterator begin, Iterator end) {
    auto mid = partition(begin, end, *(end-1));
    if (begin < end-1) {
        auto last = end - 1;
        auto mid = partition(begin, end, *last);
        quick_sort(begin, mid);
        quick_sort(mid+1, end);
    }
}

void merge(card_list& v, card_list& left, card_list& right) {
    auto it = v.begin();
    auto l = left.begin();
    auto r = right.begin();
    while (l != left.end() && r != right.end()) {
        if (l->second <= r->second) {
            *it++ = *l++;
        } else {
            *it++ = *r++;
        }
    }
    if (l != left.end()) {
        copy(l, left.end(), it);
        distance(l, left.end());
    } else {
        copy(r, right.end(), it);
        distance(r, right.end());
    }
}

void merge_sort(card_list& v) {
    if (v.size() <= 1) {
        return;
    }

    auto mid = v.begin() + distance(v.begin(), v.end()) / 2;
    auto left = card_list(v.begin(), mid);
    auto right = card_list(mid, v.end());
    merge_sort(left);
    merge_sort(right);
    merge(v, left, right);
}

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

    card_list v;
    for (auto i = 0; i < n; ++i) {
        char c;
        int n;
        cin >> c >> n;
        v.push_back(card(c, n));
    }
    card_list v2 = v;

    quick_sort(v.begin(), v.end());
    merge_sort(v2);
    if (equal(v.begin(), v.end(), v2.begin())) {
        cout << "Stable" << endl;
    } else {
        cout << "Not stable" << endl;
    }
    for (auto& card: v) {
        cout << card.first << " " << card.second << endl;
    }

    return 0;
}

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

using namespace std;

#define MOD 1000000007

using lli = long long int;
using ulli = unsigned long long int;

//#define EVEL 1

#ifndef EVEL
#define dbug(X) std::cout << #X << ":" <<X<<" " ;
#define dbugf(s) std::cout << s << " ";
#define dbugln std::cout<<"\n";
#else
#define dbug(X) {}
#define dbugf(s) {}
#define dbugln {}
#endif

int main(){
  string A, B, C;
  cin >> A >> B >> C;
  if( A[A.size()-1] == B[0] && B[B.size()-1] == C[0] ){
    cout << "YES";
  }else{
    cout << "NO";
  }
  return 0;
}


Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
const int N = 109;
int n, k, A[N];
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &A[i]);
    int Mx = INT_MIN;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j + i <= n; j++)
        {
            if (i + j > k)
                continue;
            vector < int > vec;
            for (int h = 0; h < i; h++)
                vec.push_back(A[h]);
            for (int h = 0; h < j; h++)
                vec.push_back(A[n - 1 - h]);
            sort(vec.begin(), vec.end());
            int sum = 0;
            for (int a : vec)
                sum += a;
            for (int h = 0; h < min(k - i - j, (int)vec.size()); h++)
                if (vec[h] < 0) sum -= vec[h];
            Mx = max(Mx, sum);
        }
    return !printf("%d\n", Mx);
}

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

typedef long long int ll;
#define pb push_back
#define mp make_pair
#define N 300005

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	int a[N],sum=0;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		sum+=a[i];
	}
	cout<<max(-1,n-sum)<<endl;
	return 0;
}


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

#define ENDL '\n'
#define io ios_base::sync_with_stdio(false);cin.tie(0);
#define sayy cout<<"YES"<<ENDL;
#define sayn cout<<"NO"<<ENDL;

int main(){
    io

    string s,t;
    cin >> s >> t;

    int ans(0);
    for(int i(0); i<s.length(); i++){
        if(s[i] != t[i]){
            ans++;
        }
    }
    cout << ans << ENDL;

    return 0;
}


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

vector<int> v;
void dfs(string s){
	if(s.size()>10)return;
	bool three=false,five=false,seven=false;

	for (int i = 0; i < s.size(); ++i){
		if(s[i]=='3')three=true;
		if(s[i]=='5')five=true;
		if(s[i]=='7')seven=true;
	}

	if(three&&five&&seven)
		v.push_back(stoi(s));

	dfs(s+'3');
	dfs(s+'5');
	dfs(s+'7');

}


int main(){
	dfs("0");

	int n;
	cin>>n;

	int ans=0;
	for (int i = 0; i < v.size(); ++i){
		if(n>=v[i])
			ans++;
	}
	
	cout<<ans<<endl;

}


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


void solve(long long N, std::vector<long long> A){
    long long ans = A[0];
    for(int i=1;i<N;i++){
        ans = __gcd(ans, A[i]);
    }
    cout << ans << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


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

int main(){
  int n,i,j,count;

  cin>>n;
  vector<int> a(n);
  for(i=0;i<n;i++)
  cin>>a.at(i);

  sort(a.begin(),a.end());
  count=1;

  for(i=0;i<n-1;i++){
    if(a.at(i)==a.at(i+1))
    continue;
    else
    count++;
  }

  cout<<count<<endl;


}


Measured memory_bytes: 256
S = input()
answer = 0
for bit in range(2 ** (len(S) - 1)):
    formula = S[0]
    for i in range(len(S) - 1):
        if bit & (1 << i):
            formula += '+'
        formula += S[i + 1]
    answer += sum(map(int, formula.split('+')))
print(answer)


Measured memory_bytes: 9080
#include<bits/stdc++.h>
#define int long long
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    return f*x;
}
char s[1000];
int n,Ans;
int c[1001],b[1001];
void dfs(int x,int ans){
	if(x==n){
		int res=0,js=0;
		for(int i=1;i<=ans;i++){
			js=0;
			for(int j=c[i-1]+1;j<=c[i];j++)
				js=js*10+s[j]-'0';
			res+=js;
		}
		Ans+=res;
		return ;
	}
	for(int i=x+1;i<=n;i++)
		c[ans]=i,dfs(i,ans+1);
}
main(){
    //file("");
	scanf("%s",s+1);
	n=strlen(s+1);
	dfs(0,1);
	printf("%lld",Ans);
    return 0;
}

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

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define MOD 1000000007
#define mm(arr) memset(arr, 0, sizeof(arr))

int main(){
    FAST
    int n; cin >> n;
    int dp[n][3];
    int a[n]; int b[n]; int c[n];
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    dp[0][0] = a[0];
    dp[0][1] = b[0];
    dp[0][2] = c[0];
    for(int i = 1; i < n; i++){
        dp[i][0] = a[i] + max(dp[i - 1][1], dp[i - 1][2]);
        dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][2]);
        dp[i][2] = c[i] + max(dp[i - 1][0], dp[i - 1][1]);
    }
    cout << max(max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]) << endl;
    return 0;
}


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


int main()
{
	long long int table[21][120] = {0};
	int number[120];
	int n;


	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		cin >> number[i];
	}


	table[number[0]][0] = 1;


	for (int now = 0; now < n - 2; ++now)
	{
		for (int sum = 0; sum < 21; ++sum)
		{
				if (sum + number[now + 1] <= 20) table[sum + number[now + 1]][now + 1] += table[sum][now];
				if (sum - number[now + 1] >= 0)  table[sum - number[now + 1]][now + 1] += table[sum][now];
		}
	}


	cout << table[number[n - 1]][n - 2] << endl;


	return 0;
}

Measured memory_bytes: 1184
package main

import (
	"fmt"
	"os"
	"strconv"
	"bufio"
	"strings"
)

// define
var (
	sc = bufio.NewScanner(os.Stdin)
)

func scanIntLine(len int) []int{
	arr := make([]int, len)
	for i:=0; i<len; i++{
		sc.Scan()
		tmp, err := strconv.Atoi(sc.Text())
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func scanStringLine(len int) []string{
	arr := make([]string, len)
	for i:=0; i<len; i++{
		sc.Scan()
		arr[i] = sc.Text()
	}
	return arr
}

func scanIntSplit(len int) []int{
	arr := make([]int, len)
	sc.Scan()
	for i, v := range strings.Split(sc.Text(), " "){
		tmp, err := strconv.Atoi(v)
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func main(){
	arr := scanIntLine(4)
	A, B, C, X := arr[0], arr[1], arr[2], arr[3]
	ans := 0
	for a:=0; a<=A; a++{
		if X < 500*a {
			break
		}
		for b:=0; b<=B; b++{
			if X < 100*b {
				break
			}
			for c:=0; c<=C; c++{
				if X == 500*a+100*b+50*c {
					ans++
					break
				}
			}
		}
	}
	fmt.Println(ans)
}

Measured memory_bytes: 640
//\\                            ||                     ||
            ////          //  \\                           ||                     ||
                         //    \\          //\\    //\\    ||                     ||
            ////        //      \\       //   \\  //  \\   ||                     ||
            ////       ____________     ||     \\//    ||  ||_______      ________||
            ////      //          \\    ||             ||  ||______\\    //_______||
            ////     //            \\   ||             ||  ||       ||   ||       ||
            ////    //              \\  ||             ||  ||_______||   ||_______||
            ////   //                \\ ||             ||  ||______//     \\______||







                     /*WHO CARES IF ONE MORE LIGHT GOES OUT ?
                           IN A SKY OF A MILLION STARS
                               IT FLICKERS,FLICKERS
                       WHO CARES WHEN SOMEONE'S TIME RUNS OUT ?
                            IF A MOMENT IS ALL WE ARE.
                       WHO CARES IF ONE MORE LIGHT GOES OUT ?
                                WELL I DO...*/
#include<bits/stdc++.h>
using namespace std;
long long int fa[1022];

long long int powe(long long int d,long long int s)
{
    if(s==1) return d;
    else if(s==0) return 1;
    else
    {
        long long int u,v=d;
        for(u=1;u<s;u++)
        {
            d=d*v;
        }
        return d;
    }
}
long long int phi(long long int n)
{
    double result=n;
    for (long long int p=2;p*p<=n;++p){
        if (n%p==0){
            while(n%p==0)
                n/=p;
            result*=(1.0-(1.0/(double)p));
        }
    }
    if(n>1)
        result*=(1.0-(1.0/(double)n));

    return (long long int)result;
}
long long int bigmod(long long int a, long long int b,long long int m)
{
    long long int r;
    if(b==0) return 1;
    if(b%2==0) { r=(r*r)%m;
        return  r;
    }
        return ((a%m)*bigmod(a,b-1,m)%m)%m;
}
int main()
{
    map<string,long long int>mp;
    long long int t,x=0;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        mp[s]++;
        if(mp[s]<=1)
        {
            x++;
        }
    }
    cout<<x;




    return 0;
}

Measured memory_bytes: 19232
#include<stdio.h>
int main(){
	int s,r,g,b;
	scanf("%d %d %d",&r,&g,&b);
	s=r*100+g*10+b;
	if(s%4==0){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
	return 0;
}

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

#define int long long
#define ff first
#define ss second
#define loop(i,k,n) for(int i=k;i<n;++i)
#define rloop(i,n,k) for(int i=n;i>=k;i--)
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpii vector<pair<int,int> >
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define mci map<char,int>  
#define pii pair<int,int>
#define pdd pair<double,double>
#define deb(x) cout<<#x<<" "<<x<<endl;
#define mp make_pair
#define pb push_back
#define mod 1000000007  
#define endl "\n"
#define inf 1e18
#define sp(x,y) fixed<<setprecision(y)<<x

void get_it_done(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
int gcd(int a, int b){ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
void swap(int &a,int &b){
	a^=b;b^=a;a^=b;
}
const int N = 3e3+5;
int dp[N][N];
string s1,s2;
string s="";
int solve(int i,int j){
    int m = s1.size();
    int n = s2.size();
    if(i>=m || j>=n)
        return 0;
    if(dp[i][j]!=-1) return dp[i][j];
    int ans = 0;
    if(s1[i]==s2[j]){
        ans = 1+solve(i+1,j+1);
    }
    ans = max(ans,max(solve(i+1,j),solve(i,j+1)));
    return dp[i][j] = ans;

}

int32_t main(){
	get_it_done();
    int t=1;
    // cin >> t;
    while (t--){
        cin>>s1>>s2;
        memset(dp,-1,sizeof(dp));
        // solve(0,0);
        int m = s1.size();
        int n = s2.size();
        loop(i,0,n+1)
            dp[0][i] = 0;
        loop(i,0,m+1)
            dp[i][0] = 0;

        loop(i,1,m+1){
            loop(j,1,n+1){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j] = 1+dp[i-1][j-1];
                }else 
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                // cout<<dp[i][j]<<" ";
            }
            // cout<<endl;
        }
        // cout<<dp[m][n]<<endl;
    int index = dp[m][n]; 
  
   // Create a character array to store the lcs string 
   char lcs[index+1]; 
   lcs[index] = '\0'; // Set the terminating character 
  
   // Start from the right-most-bottom-most corner and 
   // one by one store characters in lcs[] 
   int i = m, j = n; 
   while (i > 0 && j > 0) 
   { 
      // If current character in X[] and Y are same, then 
      // current character is part of LCS 
      if (s1[i-1] == s2[j-1]) 
      { 
          lcs[index-1] = s1[i-1]; // Put current character in result 
          i--; j--; index--;     // reduce values of i, j and index 
      } 
  
      // If not same, then find the larger of two and 
      // go in the direction of larger value 
      else if (dp[i-1][j] > dp[i][j-1]) 
         i--; 
      else
         j--; 
   }
   cout<<lcs<<endl;

    }
}


Measured memory_bytes: 70784
class Array
  def fq
    return self.map do |e|
      self.count e
    end
  end
end

while 0 != n = gets.to_i
  a = gets.split.map(&:to_i)
  c, _a = 0, nil
  loop do
    _a = a.fq
    break if _a == a
    a = _a
    c += 1
  end
  puts c
  puts _a.join(" ")
end

Measured memory_bytes: 6112
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			var firstLine = Console.ReadLine().Split(' ').Select(value => long.Parse(value)).ToList();
			var n = firstLine[0];
			var a = firstLine[1];
			var b = firstLine[2];

			var values = Console.ReadLine().Split(' ').Select(value => long.Parse(value)).ToList();

			var valueDp = new decimal[n + 1, b + 1];
			var combinationDp = new long[n + 1, b + 1];

			for(var i = 0; i <= n; i++)
			{
				for(var j = 0; j <= b; j++)
				{
					valueDp[i, j] = 0;
					combinationDp[i, j] = 0;
				}
			}

			for (var i = 0; i <= n; i++)
			{
				combinationDp[i, 0] = 1;
			}

			for (var i = 1; i <= n; i++)
			{
				for (var j = 1; j <= b; j++)
				{
					if(i < j)
					{
						continue;
					}

					var notSelectedValue = valueDp[i - 1, j];
					var selectedValue = valueDp[i - 1, j - 1] + values[i - 1];

					if(notSelectedValue < selectedValue)
					{
						valueDp[i, j] = selectedValue;
						combinationDp[i, j] = combinationDp[i - 1, j - 1];
					}
					else if(notSelectedValue == selectedValue)
					{
						valueDp[i, j] = selectedValue;
						combinationDp[i, j] = combinationDp[i - 1, j] + combinationDp[i - 1, j - 1];
					}
					else
					{
						valueDp[i, j] = notSelectedValue;
						combinationDp[i, j] = combinationDp[i - 1, j];
					}
				}
			}

			var maxValue = decimal.MinValue;
			long maxCombination = 0;

			for(var i = a; i <= b; i++)
			{
				valueDp[n, i] /= i;

				if(valueDp[n, i] > maxValue)
				{
					maxValue = valueDp[n, i];
				}
			}

			for (var i = a; i <= b; i++)
			{
				if (valueDp[n, i] == maxValue)
				{
					maxCombination += combinationDp[n, i];
				}
			}

			Console.WriteLine("{0:f6}", maxValue);
			Console.WriteLine(maxCombination);
		}
	}
}


Measured memory_bytes: 13780
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>

#define rep(i, n)     for (int (i) = 0; (i) < (n); (i)++)
#define rep1(i, n)    for (int i = 1; i <= (int)(n); i++)

using namespace std;
typedef long long ll;

const int MAX = 100000;
int w[MAX];

int mv(int p, int k, int n) {
   int ans = 0, curw = 0, cnt = 0;

   rep(i, n) {
      curw += w[i];
      if (curw > p) {
         cnt++;
         if (cnt == k) return(ans);

         curw = w[i];
         if (curw > p) return(ans);

         ans++;
      }
      else
         ans++;
   }
   return(n);
}

int solve(int k, int n) {
   int head = 1, tail = n * 10000;
   int mid;

   while (head != tail) {
      mid = (head + tail) / 2;
      if (mv(mid, k, n) == n)
         tail = mid;
      else
         head = mid + 1;
   }
   return(head);
}

int main() {
   int n, k, sum = 0;

   cin >> n >> k;
   rep(i, n) {
      scanf("%d", &w[i]);
      sum += w[i];
   }
   cout << solve(k, n) << endl;
   return(0);
}



Measured memory_bytes: 3528
using System;

namespace ABC085_C_Otosidama
{
	internal class Program
	{
		public static void Main(string[] args)
		{
			string[] input = Console.ReadLine().Split(' ');
			int n = int.Parse(input[0]);
			int y = int.Parse(input[1]);

			int tenThousand = -1;
			int fiveThousand = -1;
			int thousand = -1;

			for (int i = 0; i <= n; i++) {
				for (int j = 0; j <= n - i; j++)
				{
					int thousandInLoop = n - i - j;
					int money = 10000 * i + 5000 * j + 1000 * thousandInLoop;

					if (money == y && (i + j + thousandInLoop) == n)
					{
						tenThousand = i;
						fiveThousand = j;
						thousand = thousandInLoop;
						break;
					}
				}
			}
			
			Console.WriteLine(tenThousand + " " + fiveThousand + " " + thousand);
		}
	}
}


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

using namespace std;

int n, m;

char lab[1003][1003];
int DP[1003][1003];

constexpr int mod=1000000007;

int main(void)
{
	
	ios_base::sync_with_stdio(0);
	
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	
	for(int i=0;i<n;i++)
	{
		
		for(int j=0;j<m;j++)
		{
			
			cin >> lab[i][j];
			
		}
		
	}
	
	DP[1][1]=1;
	
	for(int i=1;i<=n;i++)
	{
		
		for(int j=1;j<=m;j++)
		{
			
			if( i==1 && j==1 )
			{
			
				continue;
			
			}
			
			if( lab[i-1][j-1]=='.' )
			{
				
				DP[i][j]=DP[i-1][j]+DP[i][j-1];
				DP[i][j]%=mod;
				
			}
			
		}
		
	}
	
	cout << DP[n][m];
	
	return(0);
	
}

Measured memory_bytes: 5120
const val P = 1000000007L

fun modPlus(x1: Long, x2: Long) = (x1 + x2) % P
fun modMinus(x1: Long, x2: Long) = (x1 + P - x2) % P
fun modTimes(x1: Long, x2: Long) = x1 * x2 % P

fun main(args: Array<String>) {
    val (n, h, d) = readLine()!!.split(" ").map { it.toInt() }
    val factorials = LongArray(n + 1)
    factorials[0] = 1L
    for (i in 1..n) {
        factorials[i] = modTimes(i.toLong(), factorials[i - 1])
    }
    var x = 0L
    for (i in 1..n) {
        x = modPlus(x, factorials[i])
    }

    val dp = LongArray(h + 1)
    val dpSum = LongArray(h + 1)
    dp[1] = factorials[n]
    dpSum[1] = dp[1]
    for (i in 2..h) {
        val factor = modMinus(dpSum[i - 1], dpSum[Math.max(i - d - 1, 0)])
        dp[i] = modPlus(modTimes(factor, x), if (i <= d) factorials[n] else 0L)
        dpSum[i] = modPlus(dpSum[i - 1], dp[i])
    }
    println(dp[h])
}

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

#define ll long long
#define d long double

#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define dscf(n) scanf("%Lf",&n)
#define pri(n) printf("%d ",(int)n)
#define lpri(n) printf("%lld ",n)
#define dpri(n) printf("%Lf ",n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define dprin(n) printf("%Lf\n",n)

#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,ini,n) for(ll i=ini;i<(int)n;i++)
#define all(x) x.begin(),x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define bitcount(n) __builtin_popcount(n)
#define tc   int tt; scf(tt); while(tt--)
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define PI 3.14159265358979323846264

const ll M =1e9+7;
const int N = 1e6+7;



int main()
{
    d dis,t,s;
    dscf(dis);dscf(t);dscf(s);
    if(dis/s<=t)
    printf("Yes");
    else
    {
        printf("No");
    }
    
return 0;
}

Measured memory_bytes: 3796
n,m = map(int,input().split())
l = [0] * m
for i in range(n):
    a = list(map(int,input().split()))
    for j in a[1:]:
        l[j-1] += 1
ans = 0
for i in l:
    if i == n:
        ans += 1
print(ans)


Measured memory_bytes: 9144
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

func main() {
	fmt.Printf("%d\n", resolve(parseProblem(os.Stdin)))
}

func parseProblem(r io.Reader) (int, int, string) {
	const (
		initialBufSize = 100000
		maxBufSize     = 1000000
	)
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords) // bufio.ScanLines
	n := scanInt(sc)
	p := scanInt(sc)
	s := scanString(sc)

	return n, p, s
}

func resolve(n, p int, s string) int {
	upper = map[int]int{0: 1}
	if p == 2 || p == 5 {
		return countLastNumberIs(n, p, s)
	}
	count := 0
	nums := map[int]int{0: 1}
	l := len(s)
	before := 0
	for i := l; i > 0; i-- {
		current := toInt(s, i-1)

		upper[l-i+1] = (upper[l-i] * 10) % p
		current = (upper[l-i+1] * current) % p

		current = (before + current) % p
		count += nums[current]
		nums[current]++
		before = current
	}
	xc := 0
	for _, v := range nums {
		xc += v * (v + 1) / 2
	}
	return count
}

var upper map[int]int

func countLastNumberIs(n, p int, s string) int {
	num := 0
	for i := 0; i < n; i++ {
		v := toInt(s, i)
		if v%p == 0 {
			num += i + 1
		}
	}
	return num
}

func toInt(s string, i int) int {
	d, _ := strconv.Atoi(s[i : i+1])
	return d
}

// snip-scan-funcs
func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return int(i)
}
func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 12672
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;

#define FOR(i,a,b) for(long long int i=(a);i<(b);i++)
#define REP(i,n) for(long long int i=0;i<(n);i++)
#define ALL(s) (s).begin(),(s).end()

#define PI 3.14159265358479

typedef long long int ll;
typedef vector<long long int> vi;

int main(){
	ll a, b, da, db, c, GCD, LCM = 0, k = 0;
	bool f;
	while (cin >> a >> b){
		da = a;
		db = b;
		if (a > b){
			k = a;
			a = b;
			b = k;
		}
		while (1){
			c = b%a;
			if (c == 0){
				GCD = a;
				break;
			}
			b = a;
			a = c;
		}
		LCM = da*db / GCD;
		cout << GCD <<" "<< LCM << "\n";
	}
}

Measured memory_bytes: 1152
#include <climits>
#include <iostream>

using namespace std;

template <typename Type>
long long Maximum_Sum_Sequence(Type N[], int size)
{
	long long max = LLONG_MIN;

	for (int i = 0; i < size; i++)
	{
		long long sum = 0;

		for (int j = i; j < size; j++)
		{
			sum += N[j];

			if (sum > max) { max = sum; }
		}
	}

	return max;
}

int main()
{
	const int DATASETS = 100;

	int n[DATASETS], a[DATASETS][5000], c = 0;

	while (true)
	{
		cin >> n[c];

		if (n[c] == 0) { break; }

		for (int i = 0; i < n[c]; i++) { cin >> a[c][i]; }

		c++;
	}

	for (int i = 0; i < c; i++)
	{
		cout << Maximum_Sum_Sequence(a[i], n[i]) << endl;
	}

	return 0;
}

Measured memory_bytes: 1220
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <map>
#include <set>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define sz(x) int(x.size())

typedef long long ll;

using namespace std;

static const int MAX = 100001;

/******* c++14 don't include *******/

template<typename T>
T gcd(T a, T b){if( b == 0)return a; return gcd(b, a%b); }
template<typename T>
T lcm(T a, T b){return a*b/gcd(a,b); }

/*******                      *******/

int n, m;
vector<int> s[11];
int p[11];

void solve(int &res, int now_num, int *arr){
    if(now_num>n)return;
    else if(now_num<n){
        arr[now_num]=0;
        solve(res, now_num+1, arr);
        arr[now_num] = 1;
        solve(res, now_num+1, arr);
    }
    else{
        bool ok = true;
        rep(i, m){
            int sum = 0;
            rep(j, s[i].size()){
                sum += arr[s[i][j]];
            }
            sum%=2;
            if(sum != p[i]){
                ok = false;
                break;
            }
        }
        
        if(ok)res++;
        else return;
    }
    
    
}

int main(int argc, const char * argv[]) {
    // input from txt
    
    /////////
    //write//
    /////////
    
    cin >> n >> m;
    rep(i, m){
        int k;
        cin >> k;
        rep(j, k){
            int foo;
            cin >> foo;
            foo--;
            s[i].push_back(foo);
        }
    }
    rep(i, m){
        cin >> p[i];
    }
    
    int res = 0;
    
    solve(res, 0, new int[12]);
    
    cout << res << endl;
    
    
    return 0;
}


Measured memory_bytes: 256
n, T = map(int, input().split())
t = list(map(int, input().split()))

ans = 0
tmp = 0
for i in range(n):
    start, end = t[i], t[i]+T
    if start<tmp:
        ans += end-tmp
    else:
        ans += end-start
    tmp = end

print(ans)

Measured memory_bytes: 25196
#pragma region Macros
#include <bits/stdc++.h>
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll;
#pragma endregion

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

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

	ll K, ans = 0;
	cin >> K;

	rep2 (i, 1, K + 1)
	{
		rep2 (j, 1, K + 1)
		{
			rep2 (h, 1, K + 1)
			{
				ans += gcd(i, gcd(j, h));
			}
		}
	}

	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 3640
public class Main {
    public static void main(String[] args) {

        // ??????????????????????????????.
        java.util.Scanner sc = new java.util.Scanner(System.in);

        // ??¢??????????????????????????°????¨??????????????????????????????????????????????.
        int[] num = new int[26];
        for (int i = 0; i < 26; i ++) { num[i] = 0; }

        // ???????????????????????§????????????????????? 1 ?????\???????????????????????????.
        // ???????????? 1 ???????????????????????¢??????????????????????????°?????????????????????.
        while (sc.hasNext()) {
            String s = sc.nextLine();
            for (int i = 0; i < s.length(); i ++) {
                if (s.charAt(i) <= 'Z' && 'A' <= s.charAt(i)) { num[s.charAt(i) - 'A'] ++; }
                else if (s.charAt(i) <= 'z' && 'a' <= s.charAt(i)) { num[s.charAt(i) - 'a'] ++; }
            }
        }
        char c = 'a';
        for (int i = 0; i < 26; i ++) {
            System.out.println(c + " : " + num[i]);
            c ++;
        }
    }
}

Measured memory_bytes: 26268
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#define ios ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
int a[maxn];
int main()
{
	ios;
	int n; cin>>n;
	int minn=1,sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]<a[minn]) minn=i;
		if(a[i]==0) sum++;
	}
	while(sum!=n-1){
		for(int i=1;i<=n;i++){
			if(a[i]==0) continue;
			if(i==minn) continue;
			a[i]%=a[minn];
			if(a[i]==0) sum++;
			if(a[i]!=0) minn=a[i]<a[minn]?i:minn;
		}
		if(a[minn]==1) break;
//		cout<<a[minn]<<endl;
	}
	cout<<a[minn]<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main(){
  int n;
  cin >>n;
  int x[n];
  for(int i =0; i<n; i++){
    cin >>x[i];
  }
  int sum=10000000;
  for(int i =0; i<100; i++){
    int a=0;
    for(int j = 0; j<n; j++){
      a += (x[j]-i)*(x[j]-i);
    }
    if(sum>a)sum=a;
  }
  cout <<sum;
  return 0;
}



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

int main(void){
    int a,b,c,x,y;
    cin >> a >> b >> c >> x >> y;
    long long int ans = a*x+b*y;
    
    for(int i = 0;i <= max(x,y);i++){
        long long int sum = (i*2)*c;
        if((x-i) > 0)sum += (x-i)*a;
        if((y-i) > 0)sum += (y-i)*b;
        ans = min(ans,sum);
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 256
N,K = map(int, input().split())

h = []
for _ in range(N):
    h.append(int(input()))
h.sort()

min = float("inf")
for i in range(N-K+1):
    temp = h[K+i-1]-h[i]
    if min > temp:
        min = temp

print(min)


Measured memory_bytes: 7384
#include <bits/stdc++.h>
#define F(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define f(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;

template<typename T>bool chkmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool chkmin(T &a,T b){return (a>b)?a=b,1:0;}

inline int read() {
 int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}
int n;
int X,Y;
int p[200005][2];
int fa[400005],dfn[400005],low[400005];
int he[400005],ne[800005],to[800005],cost[800005],e;
void add(int x,int y,int z){
    to[++e]=y;
	ne[e]=he[x];
	he[x]=e;
	cost[e]=z;
}
int vis[400005];
int tot;
int dep[400005];
void dfs(int x,int ff){
     fa[x]=ff;
	 dfn[x]=++tot;
	 for(int i=he[x];i;i=ne[i]){
	   int v=to[i];
	   if(!cost[i])continue;
	   if(v==ff)continue;
	   dep[v]=dep[x]+1;
	   dfs(v,x);
	 }
	 low[x]=++tot;
}
bool check(int x,int y){
    if(dfn[x]>dfn[y])swap(x,y);
    if(dfn[x]<=dfn[y]&&low[x]>=low[y])return dep[y]-dep[x]>2;
    if(fa[x]==fa[y])return 0;
	else return 1;
}
int ans[200005];
int dis[200005];
queue<int>q;
void bfs(){
     vis[X]=1;
	 q.push(X);
	 while(!q.empty()){
	    int x=q.front();
		q.pop();
		for(int i=he[x];i;i=ne[i]){
			int v=to[i];
		   if(!cost[i]&&!vis[v]){
		      dis[v]=dis[x]+1;
			  if(dis[v]<dep[v]){
			      q.push(v);
				  vis[v]=1;
			  }
		   }
		}
	 }
}
int main () {
#ifndef ONLINE_JUDGE
//file("agc005e");
#endif
    n=read();
	X=read();
	Y=read();
	F(i,1,n-1){
	    p[i][0]=read();
		p[i][1]=read();
	}
	F(i,1,n-1){
	   int x=read(),y=read();
	   add(x,y,1);
	   add(y,x,1);
	}
	dfs(Y,0);
    F(i,1,n-1){
	   int x=p[i][0],y=p[i][1];
	   if(check(x,y))ans[x]=ans[y]=1;
	   else add(x,y,0),add(y,x,0);
	}
	bfs();
	int Ans=0;
	F(i,1,n){
	   if(vis[i]&&ans[i]){
	       puts("-1");
		   return 0;
	   }
	   else if(vis[i])chkmax(Ans,dep[i]*2);
	}
	printf("%d\n",Ans);
    return 0;
}

Measured memory_bytes: 30592
#include<iostream>
using namespace std;
int qw(int n) {
	return n / 10;
}
int er(int n){
	return n - qw(n) * 10;

}
int main() {
	int m; cin >> m;
	int d; cin >> d;
	
	int sum = 0;
	for (int i = 2; i <= m; i++) {
		for (int x = 22; x <= d; x++) {
			if (qw(x) * er(x) == i&&2<=qw(x)&&2<=er(x)) {
				
				sum += 1;
			}
		}
		
	}
	cout << sum;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
//#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};
 

int H, W, D;

P get_idx(int x) {
    return P((x - 1) % D, (x - 1) / D);
}

signed main()
{
    cin >> H >> W >> D;

    // cout << H << endl;

    mat tbl;
    tbl.resize(D);
    REP(i,D) tbl[i].resize((H * W + D - 1) / D);

    P pos[90001];
    REP(i,H) REP(j,W) {
        int A;
        cin >> A;
        pos[A] = P(i, j);
    }

    //tblの構成
    vector<P> now_pos(D);
    vector<int> sum(D, 0);
    for (int i=1; i<=H*W; i++) {
        if (i <= D) {
            tbl[get_idx(i).first][get_idx(i).second] = 0;
            now_pos[i-1] = pos[i];
            sum[i-1] = 0;
        } else {
            sum[get_idx(i).first] += abs(now_pos[get_idx(i).first].first - pos[i].first) + abs(now_pos[get_idx(i).first].second - pos[i].second);
            now_pos[get_idx(i).first] = pos[i];
            tbl[get_idx(i).first][get_idx(i).second] = sum[get_idx(i).first];
        }
    }

    int Q;
    cin >> Q;
    REP(i,Q) {
        int L, R;
        cin >> L >> R;
        cout << tbl[get_idx(R).first][get_idx(R).second] - tbl[get_idx(L).first][get_idx(L).second] << endl;
    }
}

Measured memory_bytes: 7168
#include<bits/stdc++.h>
using namespace std;
int main(){
    double n,k;
    cin>>n>>k;
    double x=0.0;
    for(int i=1;i<=n;i++){
        int p=1.0;
        for(int j=i;j<k;j*=2)p*=2;
        x+=1.0/p;
    }
    printf("%.10lf\n",x/n);
    return 0;
}

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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) (int)((a).size())
#define all(c) (c).begin(), (c).end()
#define debug(v) {for (auto z : v) {cerr << z << ' ';} cerr << endl;}

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

const ll MOD = 1e9 + 7;

ll powmod(ll a, ll b) {
	ll r = 1;
	while (b > 0) {
		if (b&1) r = (r * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return r;
}

ll inverse(ll x) {
	return powmod(x, MOD - 2);
}

ll combine(ll n, ll k) {
	ll x = 1, y = 1;
	for (ll i = 0; i < k; i++) {
		x = (x * (n - i)) % MOD;
		y = (y * (i + 1)) % MOD;
	}
	return (x * inverse(y)) % MOD;
}

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	ll n, a, b;
	scanf("%lld%lld%lld", &n, &a, &b);
	ll ans = powmod(2, n);
	ll x = (1 + combine(n, a) + combine(n, b)) % MOD;
	ans = (ans + MOD - x) % MOD;
	printf("%lld\n", ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ___                      \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(0);
#define endl '\n'
#define pii pair<int, int>
#define MAX INT_MAX
#pragma GCC optimize("Ofast")
#define int long long
const int MOD = (1e9 + 7);
using namespace std;
#define vvi vector<vector<int>>
signed main()
{
	___ 
	int a,b;
	cin >> a >>b;
	if(a>=13) cout<<b;
	else if(a>=6)cout<<b/2;
	else cout<<0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


MOD = 10**9 + 7
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N, X, Y = read_ints()
X -= 1
Y -= 1

# 一箇所だけ短絡している
# もし短絡していなかったら簡単
# O(NN)でも間に合いそう

# 愚直にダイクストラしてもええか？
from scipy.sparse import csr_matrix, lil_matrix  # 自分で配列を作ってからcsrに入れよう(lilに打ち込んでいくのは非常に遅い)

# ダイクストラ法 (正の単一始点最短経路) (全点間最短経路)
from scipy.sparse.csgraph import dijkstra
graph = lil_matrix((N,N))
for i in range(N - 1):
    graph[i,i + 1] = 1
    graph[i + 1,i] = 1
graph[X,Y] = 1
graph[Y,X] = 1
adj_mat = csr_matrix(graph)
D = dijkstra(adj_mat, directed=False)
cnt = Counter(D.reshape(-1))
for i in range(1, N):
    print(int(cnt[i]) // 2)


# D[i,j]でi→jに向かう最短経路
# indicesで始点を指定している場合は、D[j]でok


Measured memory_bytes: 46344
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long A, B;
    cin >> A >> B;
    for(long long i = 1; i <= B; i++){
        if(A*i%B == 0){
            printf("%lld\n", A*i);
            break;
        }
    }
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

type Matrix [4100][4100]int32

var b Matrix
var w Matrix

func sum(g *Matrix) {
	n := len(g)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if i > 0 {
				g[i][j] += g[i-1][j]
			}
			if j > 0 {
				g[i][j] += g[i][j-1]
			}
			if i > 0 && j > 0 {
				g[i][j] -= g[i-1][j-1]
			}
		}
	}
}

func check(g *Matrix, sx, sy int, k int) int32 {
	k2 := k * 2

	k -= 1
	k2 -= 1
	a := g[sx+k2][sy+k2] - g[sx+k2][sy+k] - g[sx+k][sy+k2] + g[sx+k][sy+k]
	b := g[sx+k][sy+k]
	if sx > 0 {
		b -= g[sx-1][sy+k]
	}
	if sy > 0 {
		b -= g[sx+k][sy-1]
	}
	if sx > 0 && sy > 0 {
		b += g[sx-1][sy-1]
	}
	return a + b
}

func main() {
	var N, K int
	fmt.Scanf("%d %d", &N, &K)
	K2 := K * 2

	for i := 0; i < N; i++ {
		x, y, s := 0, 0, ""
		fmt.Scanf("%d %d %s", &y, &x, &s)
		c := s[0]

		if c == 'B' {
			b[x%K2][y%K2] += 1
			b[x%K2+K2][y%K2] += 1
			b[x%K2+K2][y%K2+K2] += 1
			b[x%K2][y%K2+K2] += 1
		} else {
			w[x%K2][y%K2] += 1
			w[x%K2+K2][y%K2] += 1
			w[x%K2+K2][y%K2+K2] += 1
			w[x%K2][y%K2+K2] += 1
		}
	}

	//for _, t := range w {
	//	fmt.Println(t)
	//}

	sum(&b)
	sum(&w)

	//fmt.Println("----")
	//for _, t := range w {
	//	fmt.Println(t)
	//}

	ans := 0
	for i := 0; i < K; i++ {
		for j := 0; j < K; j++ {
			nw := check(&w, i, j, K)
			nb := check(&b, i+K, j, K)
			if int(nw+nb) > ans {
				ans = int(nw + nb)
			}
		}
	}

	for i := 0; i < K; i++ {
		for j := 0; j < K; j++ {
			nb := check(&b, i, j, K)
			nw := check(&w, i+K, j, K)
			if int(nw+nb) > ans {
				ans = int(nw + nb)
			}
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 136832
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
int A[200011];

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%d", A+i);

    LL ans = 0;
    int right = 0;
    for (int i=N; i--;) {
	if (A[i] < right-1) {
	    puts("-1");
	    return;
	}
	if (A[i] >= right) {
	    ans += A[i];
	}
	right = max(A[i], right-1);
    }

    if (right == 0) {
	printf("%lld\n", ans);
    } else {
	puts("-1");
    }
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 1024
def insert(cnt, data):
    T[str(data)] = cnt


cnt = 0
T = {}
n = int(input())
for i in range(n):
    Order, data_S = input().split()
    if Order[0] =="i":
        insert(cnt, data_S)
        cnt +=1

    else:
        if str(data_S) in T:
            print("yes")
        else:
            print("no")


Measured memory_bytes: 41812
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  int a,b,c,k,i,j;
  
  cin>>a>>b>>c>>k;
  
  if(a==b&&b==c){
    j=a;
    for(i=0;i<k;i++)
      j=j*2;
    cout<<j+a+a<<endl;
    return 0;}
  else{
    j=1;
    for(i=0;i<k;i++)
      j=j*2;
    cout<<j*max({a,b,c})+a+b+c-max({a,b,c})<<endl;
    return 0;
  }
  
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define of(i,l,r) for(int i=l;i>=r;i--)
#define fe(i,u) for(int i=head[u];i;i=e[i].next)
using namespace std;
typedef long long ll;
inline void open(const char *s)
{
	#ifndef ONLINE_JUDGE
	char str[20];
	sprintf(str,"in%s.txt",s);
	freopen(str,"r",stdin);
//	sprintf(str,"out%s.txt",s);
//	freopen(str,"w",stdout);
	#endif
}
inline int rd()
{
	static int x,f;
	x=0;f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return f>0?x:-x;
}
int bin[21],L;

int main()
{
	bin[0]=1;fo(i,1,20)bin[i]=bin[i-1]<<1;
	L=rd();
	int t=upper_bound(bin,bin+21,L)-bin-1;
	int n,m,d;
	n=t+1;m=t<<1;
	int p=L-bin[t];
	fo(i,0,t)if(bin[i]&p)m++;
	cout<<n<<' '<<m<<endl;
	fo(i,1,n-1){
		cout<<i<<' '<<i+1<<' '<<bin[i-1]<<endl;
		cout<<i<<' '<<i+1<<" 0\n";
	}
	int K=L-bin[t];d=L;p=0;
	fo(i,0,t-1){
		if(bin[i]&K){
			cout<<i+1<<' '<<n<<' '<<(d-=bin[i])<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 256
S = input()
K = int(input())
if (K <= len(S)) :
    if (S[:K] == '1'*K) :
        print('1')
    else:
        for ch in list(S):
            if (ch != '1'):
                print(ch)
                break
else :
    for ch in list(S):
        if (ch != '1'):
            print(ch)
            break

Measured memory_bytes: 38384