akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define eee(a) (cerr << (#a) << ": " << (a) << endl);
#define ppp(a) (cout << (a) << endl);
#define cop(a) for(auto x:(a)){cout << x << endl;}


using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using mint = map<int, int>;

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

constexpr char sp = ' ';
constexpr char cmm = ',';
constexpr int MOD = 1e9+7;
constexpr int INF = 1e9;
constexpr ll LINF = 1e18;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powmod(ll b, ll e){ll r=1;while(e>0){if(e&1)r=(r%MOD)*(b%MOD)%MOD;b=(b%MOD)*(b%MOD)%MOD;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    s << '[';
    for (int i = 0; i < len; ++i) {
        s << v[i]; if (i < len-1) s << ", ";
    }
    s << ']';
    return s;
}

struct aaa{
    aaa(){
        // comment this out when you use scanf or printf
        // cin.tie(0); ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(15);
    };
}fastio;

int main(){

    double n;
    cin >> n;

    if((int)n%2){
        cout << ((n+1)/2)/n << endl;
    }
    else{
        cout << (n/2)/n << endl;
    }


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define mp make_pair
#define ff first
#define ss second
#define MAXN  1000005
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll k;
    cin>>k;
    ll e=k/50;
    ll f=k%50;
    ll rr=50+e-1;
    ll zz=rr+(f*50);
    ll xx=rr+1;
    cout<<50<<endl;
    for(ll i=0;i<=49;i++){
        xx--;
        xx=max(0LL,xx);
        if(i<f)
        cout<<(xx+50-f)<<" ";
        else cout<<xx<<" ";
    }





    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using o_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define M 1000010
ll f(ll a,ll b){
	ll ans=1;a%=md;
	while(b){
		if(b&1)ans=(ans*a)%md;
		a=(a*a)%md;b/=2;
	}
	return ans;
}
int main(){
	IOS;
	ll n;cin>>n;
	ll a[n];
	rep(i,0,n)cin>>a[i];
	ll ans=0;
	rep(i,0,62){
		ll a1=0,b=0,s=0;
		rep(j,0,n){
			if(a[j]%2)a1++;
			else b++;
			a[j]/=2;
		}
		s=((a1*b)%md*f(2,i))%md;
		ans=(ans+s)%md;
	}
	cout<<ans;
	return 0;
}



Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n , d , rem;
  cin >> n >> d >> rem;
  for(int i=0; i<n; i++)
  {
      int v ;
      cin >> v;
      for(int j=0;   ; j++)
      {
          if(v*j+1<=d)rem++;
          else break;
      }
  }
  cout << rem << endl;
}


Measured memory_bytes: 3592
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime> 
#include <memory.h>
#include <assert.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18 + 1;

int main() {
    int N;
    cin >> N;
    vector<pair<pair<string, int>, int>> v(N);
    for(int i = 0; i < N; i++) {
        string s;
        int p;
        cin >> s >> p;
        v[i].first.first = s;
        v[i].first.second = -p;
        v[i].second = i+1; 
    }

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

    for(int i = 0; i < N; i++) {
        cout << v[i].second << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#define N 1005
using namespace std;
typedef long long ll;
int main()
{
    int a,b;
    char s[N];
    while(scanf("%d%d",&a,&b)==2)
    {
        int flag=0;
        scanf("%s",s);
        for(int i=0; i<=a+b; i++)
        {
            if(i!=a)
            {
                if('0'>s[i]||s[i]>'9')
                {
                    flag=1;
                    break;
                }
            }
            else
            {
                if(s[i]!='-')
                {
                    flag=1;
                    break;
                }
            }
        }
   if(flag)
    printf("No\n");
   else
    printf("Yes\n");
    }
}


Measured memory_bytes: 256
n,m = input().split(" ")
n=int(n)
m=int(m)
arr = list(map(int,input().split(" ")))

x = sum(arr)

frac = x/(m*4)

ans=0
for i in range(len(arr)):
    if(arr[i]>=frac):
        ans+=1
if(ans>=m):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MAXN = 100005;

vector<int> G[MAXN];

int cnt[MAXN];

int A[MAXN], B[MAXN], C[MAXN];

ll Ans;
int N;

void f(int i) {
	cnt[i] = 1;
	for(int e : G[i]) {
		int v = A[e] + B[e] - i;
		if(cnt[v]) continue;
		f(v);
		cnt[i] += cnt[v];
	}
}

void g(int &ridx) {
	const int N = cnt[ridx];
	for(int hi, hc;;) {
		hi = hc = -1;
		for(int e : G[ridx]) {
			int v = A[e] + B[e] - ridx;
			if(cnt[ridx] <= cnt[v]) continue;
			if(cnt[v] <= hc) continue;
			hc = cnt[v]; hi = v;
		}
		if(hc <= N/2) break;

		cnt[ridx] = N - hc;
		cnt[hi] = N;
		ridx = hi;
	}
}

void dfs(int i) {
	for(int e : G[i]) {
		int v = A[e] + B[e] - i;
		if(cnt[i] <= cnt[v]) continue;
		Ans += ll(cnt[v]) * C[e] * 2;
		dfs(v);
	}
}

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

	cin >> N;
	for(int i = 1; i < N; i++) {
		cin >> A[i] >> B[i] >> C[i];
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}

	f(1);

	{
		int ridx = 1;
		g(ridx);

		dfs(ridx);

		vector<int> mxc;
		int mne = INF;

		for(int e : G[ridx]) {
			mxc.eb(cnt[A[e] + B[e] - ridx]);
			sorv(mxc); revv(mxc);
			if(2 < sz(mxc)) mxc.pop_back();
		}

		for(int e : G[ridx]) {
			int c = cnt[A[e] + B[e] - ridx];

			if(mxc[0] != c) {
				if(mxc[0] <= N-mxc[0]-1)
					upmin(mne, C[e]);
			} else {
				upmin(mne, C[e]);
			}
		}

		Ans -= mne;
	}

	cout << Ans << endl;
	return 0;
}

Measured memory_bytes: 11264
var s:string;
    c,i:longint;

begin
 readln(s);
 c:=0;
 for i:=1 to length(s) do 
  if S[i]<'a' then 
  if S[i]='C' then inc(c);
 if c>1 then 
  begin
   write('WA');exit;
  end;
 if c<1 then 
  begin
   write('WA');exit;
  end;
 if (s[1]<>'A') or (c<>1) or (s[2]<'a') or (s[length(S)]<'a') then writeln('WA')
 else writeln('AC');
end.

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


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

    if(abs(a-c) <= d){
        cout << "Yes" << endl;
    }else if(abs(b-c) <= d && abs(a - b) <= d){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
	
	
	return 0;
}


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

int main() {
    /* Input */
    int n, m;
    cin >> n >> m;

    vector<int> a(m);
    rep (i, m) {
        cin >> a.at(i);
    }

    /* Main Logic */
    int ans = 0;
    int total_time = 0;
    rep (i, m) {
        total_time += a.at(i);
        ans = n - total_time;
        if (ans < 0) {
            ans = -1;
            break;
        }
    }

    /* Output */
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3640
# Author: cr4zjh0bp
# Created: Sat Mar 28 15:38:17 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()

flag = False
ans = n
for i in range(0, n + 1):
    if int(i * 1.08) == n:
        flag = True
        ans = i
        break

print(ans if flag else ":(")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    string s;
    cin>>s;
    int num=int(s.back()-'0');
    if(num==3) cout<<"bon"<<endl;
    else if(num==0 || num==1 || num==6 || num==8) cout<<"pon"<<endl;
    else cout<<"hon"<<endl;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define pb  push_back
#define mxn 100005
#define fst first
#define snd second
typedef long long ll;
using namespace std;
// Debuging
template<class Debug>
Debug debug (string x,Debug y){
	cout <<"[" << x <<" : "<< y <<"] ";
}
int main()
{
	int n;
	cin >> n;
	if (n>=30)
		cout << "Yes\n";
	else
		cout << "No\n";
	


 return 0;
}



Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
 <url:https://arc083.contest.atcoder.jp/tasks/arc083_a>
 問題文============================================================
 すぬけ君はビーカーに砂糖水を作ろうとしています。
 最初ビーカーは空です。すぬけ君は以下の 4 種類の操作をそれぞれ何回でも行うことができます。
 一度も行わない操作があっても構いません。
 
 操作 1: ビーカーに水を 100A [g] 入れる。
 操作 2: ビーカーに水を 100B [g] 入れる。
 操作 3: ビーカーに砂糖を C [g] 入れる。
 操作 4: ビーカーに砂糖を D [g] 入れる。
 すぬけ君の実験環境下では、水 100 [g] あたり砂糖は E [g] 溶けます。
 
 すぬけ君はできるだけ濃度の高い砂糖水を作りたいと考えています。
 
 ビーカーに入れられる物質の質量 (水の質量と砂糖の質量の合計) が F [g] 以下であり、
 ビーカーの中に砂糖を溶け残らせてはいけないとき、 すぬけ君が作る砂糖水の質量と、
 それに溶けている砂糖の質量を求めてください。 答えが複数ある場合はどれを答えても構いません。
 
 水 a [g] と砂糖 b [g] を混ぜた砂糖水の濃度は  100b/a+b  [%]です。
 また、この問題では、砂糖が全く溶けていない水も濃度 0 [%] の砂糖水と考えることにします。
 
 
 =================================================================
 
 解説=============================================================
 
 ================================================================
 */

ll A,B,C,D,E,F;
int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> A >> B >> C >> D >> E >> F;
    vector<ll> x,y;
    for(int i = 0; i <= F; i++){
        for(int j = 0; j <=F;j++){
            if(100*A*i + 100*B*j > F)continue;
            x.push_back(100*A*i+100*B*j);
        }
    }
    for(int i = 0; i <= F; i++){
        for(int j = 0; j <=F;j++){
            if(C*i + D*j > F)continue;
            y.push_back(C*i+D*j);
        }
    }
    sort(x.begin(),x.end()); sort(y.begin(),y.end());
    x.erase(unique(x.begin(),x.end()),x.end());
    y.erase(unique(y.begin(),y.end()),y.end());
    
    double max_noudo = -1;
    ll ans = 0, ans2 = 0;
    for(int i = 0; i < (int)x.size();i++){
        for(int j = 0; j < (int)y.size();j++){
            if(x[i] + y[j] <= F){
                if(100*y[j] <= E*x[i]){
                    double noudo = 100*(double)y[j]/(double)(x[i]+y[j]);
                    if(noudo > max_noudo){
                        max_noudo = noudo;
                        ans = x[i] + y[j];
                        ans2 = y[j];
                    }
                }
            }
        }
    }
    cout << ans << " " << ans2 << endl;
    return 0;
}


Measured memory_bytes: 2420
n = int(input())
info = [list(map(int, input().split())) for _ in range(n)]
for Cx in range(101):
    for Cy in range(101):
        flag = False
        check = []
        for x, y, h in info:
            if h == 0:
                continue
            check.append(h+abs(x-Cx)+abs(y-Cy))
        if len(set(check)) == 1:
            flag = True
            ans_h = check[0]
            for x, y, h in info:
                if h != max(ans_h-abs(x-Cx)-abs(y-Cy), 0):
                    flag = False
        if flag:
            print(Cx, Cy, ans_h)
            exit()


Measured memory_bytes: 3064
// https://atcoder.jp/contests/apc001/tasks/apc001_b
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define EPS (1e-9)
#define INF (1e9)
#define INFL (1e18)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = (n - 1); i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define BIT(n) (1LL << (n))
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
// ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    REP(i, n) cin >> a[i];
    REP(i, n) cin >> b[i];
    ll cnt = 0;
    REP(i, n) {
        if (a[i] < b[i]) {
            // aを差分/2だけ増加させて、差分が奇数ならbを1増加
            // つまり、差分/2で切り捨てればいい
            cnt += (b[i] - a[i]) / 2;
        } else {
            cnt -= a[i] - b[i];
        }
    }
    if (cnt >= 0) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int scmp(const void *a, const void *b){
    return *(char *)a - *(char *)b;
}
int tcmp(const void *a, const void *b){
    return *(char *)b - *(char *)a;
}
int main(void)
{
    char s[110], t[110];
    scanf("%s%s",s,t);
    qsort(s, strlen(s), sizeof(char), scmp);
    qsort(t, strlen(t), sizeof(char), tcmp);
    puts(strcmp(s,t)<0?"Yes":"No");
    return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)

const int MAX = 15;
const ll INF = 1e10;

int H, W, K;
string S[MAX];

ll sub(int flag) {
    flag += (1<<(H-1));
    ll pop = __builtin_popcount(flag);
    ll ret = pop - 1;
    vi count = vi(pop+1);
    vi next;
    REP (w, W) {
        next = vi(pop+1);
        int k = 0;
        REP (h, H) {
            if (S[h][w] == '1') next[k]++;
            if ((flag >> h)&1) {
                if (next[k] > K) return INF;
                k++;
            }
        }

        bool f = true;
        REP (p, pop) if (count[p] + next[p] > K) {
            count = next;
            ret++;
            f = false;
            break;
        }
        if (f) {
            REP (p, pop) count[p] += next[p];
        }
    }
    return ret;
}

ll solve() {
    ll ans = INF;
    REP (i, 1<<(H-1)) CHMIN(ans, sub(i));
    return ans;
}

int main() {
    cin >> H >> W >> K;
    REP (h, H) cin >> S[h];
    cout << solve() << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int main() {
  int P, Q, R;
  cin >> P >> Q >> R;
  int sum = P + Q + R;
  cout << min(sum - P, min(sum - Q, sum - R)) << endl;
  return 0;
}


Measured memory_bytes: 256
//Let's join Kaede Takagaki Fan Club !!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
template<class T>
void dmp(T a){
	rep(i,a.size()) cout << a[i] << " ";
	cout << endl;
}
template<class T>
bool chmax(T&a, T b){
	if(a < b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
bool chmin(T&a, T b){
	if(a > b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
void g(T &a){
	cin >> a;
}
template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 1000000007;//998244353
template<class T>
void add(T&a,T b){
	a+=b;
	if(a >= mod) a-=mod;
}
int n;
ll a[100005];
ll b[100005];
int main(){
	//ios::sync_with_stdio(false);
	cin >> n;
	rep(i, n+1) cin >> a[i];
	
	if(n == 0){
		if(a[0] == 1) puts("1");
		else puts("-1");
	}
	else{
		if(a[0] != 0) puts("-1");
		else{
			for(int i=n-1;i>=0;i--) a[i] += a[i+1];
			b[0] = 1;
			for(int i=1;i<=n;i++){
				b[i] = b[i-1] * 2LL;
				if(b[i] < a[i]-a[i+1]){
					puts("-1");
					return 0;
				}
				else if(b[i] > a[i]) b[i] = a[i];
				b[i] -= (a[i]-a[i+1]);
			}
			ll ans = a[0];
			//rep(i, n+1) cout << a[i] << " " << b[i] << endl;
			rep(i, n+1) ans += b[i];
			cout << ans << endl;
		}
	}
}

Measured memory_bytes: 5148
#include <iostream>
#include <numeric>
#include <math.h>
#include <algorithm>
#include <float.h>
#include <limits>
#include <vector> 
#include <string.h>
#include <iomanip>

#define rep(i,a,n) for(ll int (i) = (a);(i) < (n);(i)++)
#define urep(i,a,n) for(ll int (i) = (a);(i) > (n);(i)--)
#define MOD 1000000007
#define Imax 2147483647
#define ll long long
#define asort(a) sort(a.begin(),a.end());

using namespace::std;

int jo(ll int jxo, ll int jyo){//累乗
	ll int jhogeo = 1;
	rep(jinto,0,jyo) jhogeo=jhogeo*jxo;
	return jhogeo;
}
char tobig(char toxbig){//char大文字化
  return (toxbig-0x20);
}
char tolow(char toxlow){//char小文字化
  return (toxlow+0x20);
}
int ctoi(char cctoi){//char->int
  if('0' <= cctoi && cctoi <= '9') return (cctoi-'0');
  return -1;
}
int gcd(int gcad, int gcbd) {//最大公約数
  if(gcad < gcbd) return gcd(gcbd, gcad);
  int gcrd;
  while ((gcrd=gcad%gcbd)) {
    gcad = gcbd;
    gcbd = gcrd;
  }
  return gcbd;
}
int lcm(int lcam, int lcbm){//最小公倍数
 return (lcam*lcbm)/gcd(lcam,lcbm);
}


int main(){
  double N,K;
  cin>>N>>K;
  vector<double> a(N);
  cout<<fixed<<setprecision(10);
  rep(i,1,N+1){
    int j=0;
    while(1){
     // cout<<i*(jo(2,j))<<" "<<K<<"/";
      if(i*(jo(2,j))>=K){
        break;
      }
      j++;
    }
  //  cout<<j<<" ";
    a[i-1]=1.0/(double(jo(2,j)));

  //  cout<<"<<"<<a[i-1];
  }
  rep(i,1,N) a[i]=a[i]+a[i-1];
  
  //cout<<a[N-1];
  
  cout<<a[N-1]/double(N);
    
      
    

  
}
// int *p = new int[N];

//  vector<int> 変数名(要素数);
//  sort(変数名.begin(),変数名.end());//昇順ソート

// vector<vector<int>> 変数名(左の個数, vector<int>(右の個数));

//


Measured memory_bytes: 1024
#include<cstdio>
#include<cmath>
#pragma warning(disable:4996);
using namespace std;

int main(void)
{
	int a, b, hour, min;
	scanf("%d %d %d %d", &a, &b, &hour, &min);
	double shi, fen;
	shi = 30 * hour + 0.5 * min;
	fen = 6 * min;
	double jiajiao = shi - fen;
	if (jiajiao < 0)
		jiajiao *= -1;
	if (jiajiao > 180)
	{
		jiajiao = 360 - jiajiao;

	}
	jiajiao *= 3.14159265358979323846264338328 / 180;
	double ans = a * a + b * b - 2 * a * b * cos(jiajiao);
	ans = sqrt(ans);
	printf("%.12lf", ans);
	return 0;
}

Measured memory_bytes: 2576
K, N = map(int, raw_input().split())
A = map(int, raw_input().split())

max_dis = 0
for i in range(N-1):
    max_dis = max(max_dis, A[i+1]-A[i])
    sum_dis = A[i+1] - A[i]

max_dis = max(max_dis, (K-A[N-1]+A[0]))

print K-max_dis


Measured memory_bytes: 20032
#include<iostream>
#include<stdio.h>
using namespace std;

int main(){
	double r;
	cin>>r;

	//cout<<r*r*3.141592653589<<" "<<2.0*r*3.141592653589<<endl;
	printf("%f %f\n",r*r*3.141592653589,2.0*r*3.141592653589);
	return 0;

}



Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);
    ll N,M;cin>>N>>M;
    vl a(N);
    rep(i,N)cin>>a[i];
    set<int> ch;
    rep(i,N){
        int p=a[i],cnt=0;
        while(p%2==0){
            cnt++;
            p/=2;
        }
        ch.insert(cnt);
    }
    if(ch.size()!=1){
        cout<<0<<endl;
        return 0;
    }
    ll now=1;
    rep(i,N){
        a[i]/=2;
        now=now/__gcd(now,a[i])*a[i];
        if(now>M)break;
    }
    if(now>M)cout<<0<<endl;
    else cout<<(M-now)/now/2+1<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S, T;
  cin >> S >> T;
  if (S.at(0) == T.at(0) && S.at(1) == T.at(1) && S.at(2) == T.at(2)) {
    cout << 3 << endl;
  }
  else if (S.at(0) != T.at(0) && S.at(1) != T.at(1) && S.at(2) != T.at(2)) {
    cout << 0 << endl;
  }
  else if ((S.at(0) != T.at(0) && S.at(1) == T.at(1) && S.at(2) == T.at(2)) || 
           (S.at(0) == T.at(0) && S.at(1) != T.at(1) && S.at(2) == T.at(2)) ||
            (S.at(0) == T.at(0) && S.at(1) == T.at(1) && S.at(2) != T.at(2))) {
    cout << 2 << endl;
  }
  else {
    cout << 1 << endl;
  }
}

Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array;


void main() {
    int n;
    scan(n);

    auto a = new int[](n);
    auto b = new int[](n);

    iota(n).each!(i => scan(a[i], b[i]));

    if (a == b) {
        writeln(0);
        return;
    }

    long ans;
    auto c = new long[](0);

    foreach (i ; 0 .. n) {
        if (a[i] <= b[i]) {
            ans += b[i];
        }
        else {
            c ~= b[i];
        }
    }

    c.sort();
    c.popFront();

    ans += c.sum(0L);

    writeln(ans);
}



void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const int nmax = 8;
bool graph[nmax][nmax];
const int INF = 1e9;
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

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

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

void solve(std::string X)
{
    stack<char> s;
    for (int i = 0; i < X.size(); i++)
    {
        if (X[i] == 'S')
        {
            s.push(X[i]);
        }
        else
        {
            if (s.empty())
            {
                s.push(X[i]);
            }
            else if (s.top() == 'T')
            {
                s.push(X[i]);
            }
            else if (s.top() == 'S')
            {
                s.pop();
            }
        }
    }
    cout << s.size() << endl;
}

int main()
{
    std::string X;
    std::cin >> X;
    solve(X);
    return 0;
}


Measured memory_bytes: 896
n=int(input())
ans='Yes'
ab=input()
l=[ab]
for i in range(n-1):
    a=input()
    l.append(a)
    if l[i][-1]!=a[0]:
        ans='No'
        break
    if len(set(l))!=len(l):
        ans='No'
        break
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
	int n;
	cin >> n;
	int nn = (1 << n);
	map<int, int> m;
	for (int i = 0; i < nn; i++) {
		int t;
		cin >> t;
		m[t]++;
	}
	vector<int> v;
	v.push_back(m.rbegin()->first);
	m[v.back()]--;
	if (m[v.back()] == 0) m.erase(v.back());
	while (m.size() > 0) {

		nn = v.size();
		for (int i = 0; i < nn; i++) {
			auto it = m.lower_bound(v[i]);
			if (it == m.begin()) {
				cout << "No" << endl;
				return 0;
			}
			it--;
			v.push_back(it->first);
			m[v.back()]--;
			if (m[v.back()] == 0) m.erase(v.back());
		}
	}
	cout << "Yes" << endl;
}


Measured memory_bytes: 16608
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N];
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		long ans = 0;
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
			if(map.containsKey(i-A[i])) {
			    ans += map.get(i-A[i]);
			}
			int c = A[i] + i;
			map.put(c, map.getOrDefault(c, 0) + 1);
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 70152
#include <iostream>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

int main()
{
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a + b == c + d)
    cout << "Balanced" << endl;
  else if (a + b > c + d)
    cout << "Left" << endl;
  else
    cout << "Right" << endl;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.StringJoiner;
import java.util.stream.Collectors;

public class Main {
	Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}
	
	void run() {
		int n = sc.nextInt();
		int q = sc.nextInt();
		
		Map<Integer,List<Integer>> child = new HashMap<Integer,List<Integer>>();
		for(int i = 0 ;i < n-1; i++) {
			int k = sc.nextInt();
			int v = sc.nextInt();
			
			child.computeIfAbsent(k, c -> new ArrayList<Integer>()).add(v);
		}
		
		int root = 1;
		
		
		int s[] = new int[n+1];
		for(int i = 0; i < q; i++) {
			s[sc.nextInt()] += sc.nextInt();
		}
		int res[] = new int[n+1];
		dfs(root,s,child,res, 0);
		StringJoiner sj = new StringJoiner(" ");
		for(int x= 1; x <= n; x++) {
			sj.add(res[x]+"");
		}
		System.out.println(sj.toString());
	}
	
	void dfs(int addr, int s[], Map<Integer,List<Integer>> child, int res[], int sum) {
		sum += s[addr];
		res[addr] = sum;
		if(child.containsKey(addr)) {
			for(int next: child.get(addr)) {
				dfs(next, s,child, res, sum);
			}
		}
	}
	
}


Measured memory_bytes: 269396
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const int MAXN = 120000;
int ans = 0;
int dp[MAXN][5];
int n;
vector<int> eds[MAXN];
int was[MAXN];

void dfs1(int v) {
	was[v] = 1;
	int mxd1 = 0;
	int mxd2 = 0;
	int mx1 = 0;
	int mx2 = 0;
	int sum = 0;
	int mxd = 0;
	int mx = 0;
	for (int u: eds[v]) {
		if (was[u])
			continue;
		dfs1(u);
		mxd2 = max(mxd2, dp[u][0] - dp[u][1]);
		if (mxd2 > mxd1)
			swap(mxd1, mxd2);
		mx2 = max(mx2, dp[u][0]);
		if (mx2 > mx1)
			swap(mx1, mx2);
		mxd = max(mxd, dp[u][2] - dp[u][1]);
		sum += dp[u][1];
		mx = max(mx, dp[u][2]);
	}
	ans = max(ans, sum + mxd1 + mxd2);
	ans = max(ans, 1 + mx1 + mx2);
	ans = max(ans, sum + mxd);
	ans = max(ans, mx + 1);
	dp[v][0] = max(1 + mx1, sum + mxd1);
	dp[v][1] = max(1, sum);
	dp[v][2] = max(mxd + sum, sum + mxd1 + mxd2);
}


int main() {
	scanf("%d", &n);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	dfs1(0);
	cout << ans << "\n";
	return 0;
}




Measured memory_bytes: 8704
x1, y1, x2, y2 = map(int, input().split())

x = x2 - x1
y = y2 - y1
x3 = x2 - y
y3 = y2 + x
x4 = x3 - x
y4 = y3 - y

print('{} {} {} {}'.format(x3, y3, x4, y4))


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+10;
int n,m,H[M];
vector<int>g[M];
bool cv[M],mark[M];
int dfs(int v,int par,int h)
{
  int up=h,cnt=0;
  mark[v]=true;
  H[v]=h;
  for(auto u:g[v])
    if(!mark[u])
      {
	cnt++;
	int d=dfs(u,v,h+1);
	up=min(up,d);
	if(d>=h)cv[v]=true;
      }
    else if(u!=par)
      up=min(up,H[u]);
  if(v==1)
    if(cnt>1) cv[v]=true;
    else cv[v]=false;
  return up;
}
int main()
{
  cin>>n>>m;
  for(int i=0;i<m;i++)
    {
      int u,v;
      cin>>u>>v;u++;v++;
      g[u].push_back(v);
      g[v].push_back(u);
    }
  dfs(1,1,0);
  for(int i=1;i<=n;i++)
    if(cv[i])cout<<i-1<<endl;
  return 0;
}

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

int main () {
  int n, m, x, y;
  cin >> n >> m >> x >> y;
  vector<int> xx(n);
  vector<int> yy(m);
  for (int i = 0; i < n; i++) {
    cin >> xx[i];    
  }
  for (int i = 0; i < m; i++) {
    cin >> yy[i];  
  }
  sort(xx.begin(), xx.end());
  sort(yy.begin(), yy.end());
  if (xx[n - 1] >= yy[0]) {
    cout << "War" << endl;  
  }
  else {
    for (int i =(xx[n - 1] + 1); i <= yy[0]; i++) {
      if (i > x && i <= y) {
        cout << "No War" << endl;  
        break;
      }  
      if (i == yy[0]){
        cout << "War" << endl;  
      }
    }  
  }
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc131/tasks/abc131_c

#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for (int(i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for (int(i) = (m); (i) < (n); i++)
#define FORR(i, m, n) for (int(i) = (n); (i) >= (m); i--)
#define rep(...) _overload3(__VA_ARGS__, FOR, REP, )(__VA_ARGS__)
#define repr(...) _overload3(__VA_ARGS__, FORR, REPR, )(__VA_ARGS__)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

// 最大公約数
ll gcd(ll a, ll b)
{
  return b == 0 ? a : gcd(b, a % b);
}

// 最小公倍数
ll lcm(ll a, ll b)
{
  return a / gcd(a, b) * b;
}

int main()
{
  ll A, B, C, D, CD;
  cin >> A >> B >> C >> D;

  CD = lcm(C, D);
  ll cntC = B / C - (A + C - 1) / C + 1,
     cntD = B / D - (A + D - 1) / D + 1,
     cntCD = B / CD - (A + CD - 1) / CD + 1;

  cout << (B - A + 1) - (cntC + cntD - cntCD) << '\n';

  return 0;
}


Measured memory_bytes: 256
N = int(input())
ab = [[int(_) for _ in input().split()] for n in range(N - 1)]

from collections import defaultdict

ns = defaultdict(list)

for a, b in ab:
    ns[a].append(b)
    ns[b].append(a)

from heapq import *

queue = []
heappush(queue, (0, 1))
heappush(queue, (1, N))

colors = defaultdict(lambda:None)
black_count, white_count = 0, 0

while queue:
    i, index = heappop(queue)
    color = i % 2
    if colors[index] is None:
        colors[index] = color
        if color:
            white_count += 1
        else:
            black_count += 1
        for t in ns[index]:
            if ns[t]:
                heappush(queue, (i + 2, t))

if black_count > white_count:
    print("Fennec")
else:
    print("Snuke")


Measured memory_bytes: 52648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793

int main(){
    char s[100010];
    scanf("%s", s);

    vector<bool> alp(26, false);
    for(int i = 0; i < (int)strlen(s); i++)
        alp[s[i]-'a'] = true;
    for(int i = 0; i < 26; i++){
        if(!alp[i]){
            cout << (char)(i + 'a') << endl;
            return 0;
        }
    }
    cout << "None" << endl;
}


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

#define MAXSIZE 100000
#define ll long long

int main(){
  ll N, K, Q;
  ll* A;
  cin >> N >> K >> Q;
  A = new ll[N];
  for(ll x = 0; x < N; x++)
  {
    A[x] = 0;
  }
  
  ll thre = 1 - K + Q;
  
  for(ll x = 0; x < Q; x++)
  {
    ll tmp;
    cin >> tmp;
    A[tmp-1]++;
  }
  
  for(ll x = 0; x < N; x++)
  {
    if(thre <= A[x])
    {
      	cout << "Yes" << endl;
    }
    else
    {
      	cout << "No" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1408
const int LG = 21;
const int FN = 400005;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long INFLL = 1e18;

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <unordered_set>
#include <bitset>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vi;

#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define fi first
#define se second
#define re return
#define uniq(x) sort(all(x)); (x).resize(unique(all(x)) - (x).begin())

#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
#define ln cerr << __LINE__ << endl
#else
#define dbg(x) void(0)
#define ln void(0)
#endif // LOCAL

int cx[4] = {-1, 0, 1, 0};
int cy[4] = {0, -1, 0, 1};

ll inq(ll x, ll y)
{
    if (!y) re 1 % MOD;
    ll l = inq(x, y / 2);
    if (y % 2) re l * l % MOD * x % MOD;
    re l * l % MOD;
}

ll rev(ll x)
{
    return inq(x, MOD - 2);
}

bool __precomputed_combinatorics = 0;
vector<ll> __fact, __ufact, __rev;

void __precompute_combinatorics()
{
    __precomputed_combinatorics = 1;
    __fact.resize(FN);
    __ufact.resize(FN);
    __rev.resize(FN);
    __rev[1] = 1;
    for (int i = 2; i < FN; i++) __rev[i] = MOD - __rev[MOD % i] * (MOD / i) % MOD;
    __fact[0] = 1, __ufact[0] = 1;
    for (int i = 1; i < FN; i++) __fact[i] = __fact[i - 1] * i % MOD, __ufact[i] = __ufact[i - 1] * __rev[i] % MOD;
}

ll fact(int x)
{
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[x];
}

ll cnk(int n, int k)
{
    if (!__precomputed_combinatorics) __precompute_combinatorics();
    return __fact[n] * __ufact[n - k] % MOD * __ufact[k] % MOD;
}

const int N = 100500;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, t;
    cin >> n >> t;
    vi a(n);
    forn(i, n) cin >> a[i];
    int ans = 0;
    ll mx = 0;
    ll dif = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        mx = max(mx, a[i]);
        dif = max(dif, mx - a[i]);
    }
    mx = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        mx = max(mx, a[i]);
        if (mx - a[i] == dif) ans++;
    }
    cout << ans;
}

/* Note:
Check constants at the beginning of the code.
    N is set to 4e5 but be careful in problems with large constant factor.
    Setting N in every problem is more effective.
Check corner cases.
    N = 1
No def int long long for now.
Add something here.
*/


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define MAX (ll)(5e3 + 4)
#define MOD (ll)(1e9 + 7)
#define PI (double)(3.14159265)
#define IO ios_base :: sync_with_stdio (false), cin.tie (nullptr);

using namespace std;
using ll = long long;
using ld = long double;

int mult (int a, int b) {
	return (a * 1LL * b) % MOD;
}

int add (int a, int b) {
	return (a + b) % MOD;
}

int pw (int a, int b) {
	if (b < 0) {
		return 0;
	}
	int res = 1;
	while (b) {
		if (b & 1) {
			res = mult (res, a);
		}
		b >>= 1;
		a = mult (a, a);
	}
	return res;
}

int main () {
	int n;
	cin >> n;
	int ar[n];
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
	}
	sort (ar, ar + n);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int x = n - i - 1;
		ans = add (ans, mult (ar[i], mult (pw (2, i), add (pw (2, x), mult (x, pw (2, x - 1))))));
	}
	cout << mult (pw (2, n), ans) << "\n";
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <climits>
using namespace std;

#define MOD1097 1000000007

#define ll long long
#define pint pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mpair make_pair
#define pm(first, second) pb(mpair(first, second))
#define SPACE " "
#define fpf first.first
#define fps first.second
#define spf second.first
#define sps second.second

#define all(X) (X).begin(), (X).end()
#define reall(X) (X).rbegin(), (X).rend()
#define divcel(a, b) (((a) + ((b) - 1)) / (b))

int main(){

    ll N, A, B;
    cin >> N >> A >> B;
    N %= 12;
    for(int i = 1; i <= N; i++){
        if(i%2 == 0LL){
            B = A + B;
        }
        else{
            A = A - B;
        }
    }
    cout << A << SPACE << B << endl;

    return 0;
}



Measured memory_bytes: 3112
n, k = map(int, input().split())
s = input()

sc = 0
lr = 0
rl = 0

for i in range(n-1):
    c = s[i]
    nc = s[i+1]

    if c == nc:
        sc += 1
    elif c == 'L' and nc == 'R':
        lr += 1
    elif c == 'R' and nc == 'L':
        rl += 1

if rl > 1 or lr > 1:
    dc = min(lr, rl)
    oc = abs(lr-rl)
elif rl == 1 or lr == 1:
    dc = 0
    oc = 1
else:
    dc = 0
    oc = 0

dnum = min(k, dc)
onum = 0
if k - dc > 0 and oc == 1:
    onum += 1
print(onum + sc + dnum*2)


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

int main(){
    ll n;
    ld m;
    cin>>n>>m;
    ld a[n];
    ld ans=0;
    ld sum=0;
    for(ll i=0;i<n;++i){
        cin>>a[i];
        sum+=a[i];
    }
    ld flag=sum/(4*m);
    for(ll i=0;i<n;++i){
        if(flag<=a[i]){
            ans++;
        }
    }
    if(ans>=m){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    //cout<<sum<<endl;
    //cout<<flag<<endl;
}

Measured memory_bytes: 256
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
      int R = nextInt();
      int G = nextInt();
      myout(2 * G - R);
	}
	//Method addition frame start



	//Method addition frame end
}


Measured memory_bytes: 32948
#include<stdio.h>
int main()
{
	int k;
	scanf("%d", &k);
	char s[102];
	scanf("%s", s);
	int i = 0;
	while (s[i] != '\0')
		i++;
	if (i <= k)
		printf("%s\n", s);
	else
	{
		for (i = 0; i < k; i++)
			printf("%c", s[i]);
		printf("...\n");
	}
	return 0;
}

Measured memory_bytes: 1656
def dist(a, b):
	res = 0
	for i in range(D):
		res += (a[i] - b[i]) ** 2
	res = res ** 0.5
	return res


N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		if dist(X[i], X[j]).is_integer():
			ans += 1
print(ans)

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

int main(){
  long long int x,y;
  cin >> x >> y;
  
  long long int now=x;
  int answer;
  
  for (int i=0;;i++){
    if (now*2 <= y ) now *= 2;
    else{ answer = i+1; break;}
  }
    
    cout << answer;
    
    
  }

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

const int mxN = 3e3 + 2;
long long n, nums[mxN], dp[mxN][mxN];

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

    for (int len = 0; len <= n; len++)
    {
        for (int i = 0; i <= n - len; i++)
        {
            if (len == 0)
            {
                continue;
            }

            long long t1 = nums[i] + dp[i + 1][len - 1];
            long long t2 = nums[i + len - 1] + dp[i][len - 1];
            if ((len - n) % 2)
            {
                t1 -= 2 * nums[i];
                t2 -= 2 * nums[i + len - 1];
            }

            if ((len - n) % 2 == 0)
            {
                dp[i][len] = max(t1, t2);
            }
            else
            {
                dp[i][len] = min(t1, t2);
            }
        }
    }

    cout << dp[0][n] << endl;
}

Measured memory_bytes: 49736