akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const long double EPS = 0.0000000001;

long double f(long double a, long double b,long double t){
    if(t > M_PI / 2.0 - EPS)return 0.0;
    if(a * tan(t) <= b)return a * a * b - a * a * a * tan(t) / 2.0;
    else return b * b / tan(t) * a / 2.0;
}

//ミョ(-ω- ?)
int main() {
    long double a,b,x;
    cin >> a >> b >> x;
    long double ok = M_PI/2.0;
    long double ng = 0.0;
    rep(_,100000){
        long double mid = (ok + ng)/2.0;
        if(f(a,b,mid) < x)ok = mid;
        else ng = mid;
    }
    cout << fixed << setprecision(10) << ok / M_PI * 180 << "\n";
    return 0;
}

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

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

    const ll LIM = 1e14;

    ll n; cin >> n;
    ll a[n+1]; rep(i,n+1) cin >> a[i];


    bool flag = true;
    rep(i,n){
        if(a[i+1] != 0){
            flag = false;
            break;
        }
    }
    if(a[0] == 1 && flag){
        cout << 1 << endl;
        return 0;
    }else if(a[0] != 0 && (!flag)){
        cout << -1 << endl;
        return 0;
    }

    ll nleaf = 1LL;
    ll ans = 0LL;
    ll v[n+1];
    rep(i,n){
        if(nleaf <= a[i]){
            cout << -1 << endl;
            return 0;
        }
        nleaf -= a[i];
        v[i] = nleaf;
        nleaf <<= 1LL;
        if(nleaf > LIM) nleaf = LIM;
    }

    if(nleaf < a[n]){
        cout << -1 << endl;
        return 0;
    }

    nleaf = a[n];
    ans += a[n];
    for(ll i = n-1; i >= 0; --i){
        if(v[i]*2 < nleaf){
            cout << -1 << endl;
            return 0;
        }
        if(v[i] > nleaf) v[i] = nleaf;
        nleaf = v[i] + a[i];
        ans += nleaf;
    }
    cout << ans << endl;
}

Measured memory_bytes: 5256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <complex>
#include <math.h>

using namespace std;

//conversion
//------------------------------------------
inline long toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline long toLong(string s) {long v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(long i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

const long double EPS = 1e-12;
const int INF = 10000;


int main(){
	long sum[1002];
	int cnt[1002];CLR(cnt);
	
	sum[0]=0;
	REP(i,1000)sum[i+1]=sum[i]+i+1;
	REP(i,1001)FOR(j,i+2,1001){
		if(sum[j]-sum[i]<=1000)cnt[sum[j]-sum[i]]++;
	}
	int T;
	while(cin>>T){
		if(T==0)break;
		cout<<cnt[T]<<endl;
	}
	return 0;
}

Measured memory_bytes: 1168
# AOJ0520

import sys

def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return y
    
class frac:
    def __init__(self, n, d):
        self.num = n
        self.den = d
    
    def mul(self, yn, yd):
        xn, xd = self.num, self.den
        xn *= yn
        xd *= yd
        if xn != 0 and xd != 0:
            g = gcd(xn, xd)
            xn /= g
            xd /= g
        return frac(xn, xd)
    
    def is_zero(self):
        return self.num == 0
    
    def output(self):
        return "{}/{}".format(self.num, self.den)      
            
class LightestMobile:
    def __init__(self, n):
        self.n = n + 1
        self.mobile = [[0,0,0,0]]
        self.weight = [[frac(0,1), frac(0,1)]]
        self.denom = []

    def read(self, p, q, r, b):
        self.mobile.append([p, q, r, b])
        self.weight.append([frac(0,1), frac(0,1)])
    
    
    def root(self):
        for i in range(1, self.n):
            m = self.mobile[i]
            if m[2] == 0 and m[3] == 0:
                return self.parent(i)
    
    def parent(self, c):
        for i in range(1, self.n):
            m = self.mobile[i]
            if i != c and (m[2] == c or m[3] == c):
                return self.parent(i)
        return c
    
    def solve(self, i):
        self.solve2(i, frac(0,1))
        lcm = 1
        for d in self.denom:
            lcm = lcm * d / gcd(lcm, d)
        answer = self.weight[i][0].mul(lcm, 1).num + self.weight[i][1].mul(lcm, 1).num
        return int(answer)
    
    def solve2(self, i, wlr):
        p, q, r, b = self.mobile[i]
#        print("p,q,r,b=", self.mobile[i])
#        print("i, wlr=", i, wlr.output())
        if wlr.is_zero():
            g = gcd(p, q)
            p /= g
            q /= g
            self.weight[i] = [frac(q, 1), frac(p, 1)]
        else:
            self.weight[i] = [wlr.mul(q, p + q), wlr.mul(p, p + q)]
        if r != 0:
            self.solve2(r, self.weight[i][0])
        if b != 0:
            self.solve2(b, self.weight[i][1])
        if r == 0 and b == 0:
            if not self.weight[i][0].is_zero() and not self.weight[i][1].is_zero():
                self.denom.append(self.weight[i][0].den)
                self.denom.append(self.weight[i][1].den)
        return

if __name__ == '__main__':
    while True:
        line = input()
        n = int(line)
        if n == 0:
            break
        lm = LightestMobile(n)
        for _ in range(0, n):
            p, q, r, b = map(int, list(input().split()))
            lm.read(p, q, r, b)
        rt = lm.root()
        print(lm.solve(rt))
        del lm


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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())

signed main(){

	lli n;
	cin>>n;

	map<lli,lli> m;
	REP(i,0,n){
		lli a;
		cin>>a;
		m[-a]++;
	}
	lli sum=0;

	for(lli i=0;i<n && !m.empty();i++){
		lli now = -m.begin()->first;
		if(DEBUG)cout<<"now="<<now<<endl;
		m[-now]--;
		if(m[-now]==0)m.erase(-now);

		lli bi=1;
		while(bi<=now)bi*=2;
		lli target = bi-now;
		if(DEBUG)cout<<"target="<<target<<endl;
		if(m.count(-target)){
			sum++;
			m[-target]--;
			if(m[-target]==0)m.erase(-target);
		}
	}

	cout<<sum<<endl;

	return 0;
}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	string S;
	int N;
	cin >> S >> N;
	int L =S.length();
	vector<int> D(L+1,0);
	for(int i =0; i <= L; i++) {
		char nxt =(i == L)?'a':S[i], prev =(i == 0)?'a':S[i-1];
		if(i < L-i) D[i] =((int)nxt-(int)prev+2600)%26;
		else D[i] =((int)prev-(int)nxt+2600)%26;
	}

	vector< vector<int> > G1(L+1); // +- edges
	vector< pair<int,int> > E; // ++ edges

	for(int i =0; i < N; i++) {
		int l,r;
		cin >> l >> r;
		l--;
		int sgn_l =1, sgn_r =-1;
		if(l >= (L+1)/2) sgn_l *=-1;
		if(r >= (L+1)/2) sgn_r *=-1;
		if(sgn_l != sgn_r) {
			G1[l].push_back(r);
			G1[r].push_back(l);
		}
		else E.push_back(make_pair(l,r));
	}
	for(int i =0; i < L; i++)
		if(i <= L-i) E.push_back(make_pair(i,L-i));

	vector<int> comp(L+1,-1),comp_sum(L+1,0);
	queue<int> q;
	for(int i =0; i <= L; i++) if(comp[i] == -1) {
		q.push(i);
		comp[i] =i;
		while(!q.empty()) {
			comp_sum[i] +=D[q.front()];
			ALL_THE(G1[q.front()],it) if(comp[*it] == -1) {
				comp[*it] =i;
				q.push(*it);
			}
			q.pop();
		}
		comp_sum[i] %=26;
	}

	vector< vector<int> > G2(L+1);
	ALL_THE(E,it) {
		G2[comp[it->ff]].push_back(comp[it->ss]);
		G2[comp[it->ss]].push_back(comp[it->ff]);
	}

	vector<int> comp2(L+1,-1), comp2_sum(2*(L+1),0), part(L+1);
	for(int i =0; i <= L; i++) if(comp2[i] == -1 && comp[i] == i) {
		q.push(i);
		comp2[i] =i;
		part[i] =0;
		bool is_bip =true;
		vector<int> v;
		while(!q.empty()) {
			v.push_back(q.front());
			comp2_sum[2*i+part[q.front()]] +=comp_sum[q.front()];
			ALL_THE(G2[q.front()],it) if(comp2[*it] != -1)
				if(part[q.front()] == part[*it]) is_bip =false;
			ALL_THE(G2[q.front()],it) if(*it == q.front()) is_bip =false;
			ALL_THE(G2[q.front()],it) if(comp2[*it] == -1) {
				comp2[*it] =i;
				part[*it] =1-part[q.front()];
				q.push(*it);
			}
			q.pop();
		}
		if(!is_bip) {
			if((comp2_sum[2*i]+comp2_sum[2*i+1])%2 != 0) {
				cout << "NO\n";
				return 0;
			}
		}
		else {
			if((comp2_sum[2*i]-comp2_sum[2*i+1])%26 != 0) {
				cout << "NO\n";
				return 0;
			}
		}
	}

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

// look at my code
// my code is amazing


Measured memory_bytes: 13124
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <utility> 

#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const int MOD = 1e9 + 7;



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

	vector<int> vbef(n);
	vector<int> vaft(n);
	rep(i, 0, n) {
		int x;
		cin >> x;
		vbef[i] = x;
		vaft[i] = x;
	}
	sort(vaft.begin(),vaft.end());
	int m = vaft[n / 2];


	rep(i, 0, n) {
		if (vbef[i] < m) {
			cout << vaft[n / 2] << endl;
		}
		else {
			cout << vaft[(n-2) / 2] << endl;
		}
	}


	return 0;

}


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

int main()
{
	string s, t;cin>>s>>t;
	int start=-1;
	for(int i=s.size()-t.size();i>=0;i--)
	{
		bool match=true;
		rep(j,t.size())
		{
			//cout<<s[j+i];
			if(s[j+i]!=t[j]&&s[j+i]!='?')
			{
				match=false;
				break;
			}
		}
		if(match)
		{
			start = i;
			//cout<<i<<endl;
			break;
		}
		//cout<<endl;
	}

	if(start==-1)
	{
		cout<<"UNRESTORABLE"<<endl;
		return 0;
	}
	for(int i=0;i<s.size();++i)
	{
		if(i<start)
		{
			if(s[i]=='?')
			{
				cout<<'a';
			}
			else
			{
				cout<<s[i];
			}
		}
		else if((i-start)<t.size())
		{
			cout<<t[i-start];
		}
		else
		{
			if(s[i]=='?')
			{
				cout<<'a';
			}
			else
			{
				cout<<s[i];
			}
		}
		
	}
	cout<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int N, j = 1, cnt = 0; string S; cin >> N >> S;
    for (int i = 0; i < N; ++i) {
        if (S[i] == S[j]) j++;
        else {
            cnt++; j = i;
        }
    }
    printf("%d\n", cnt);
}


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

#define REP(i,n) for(int i=0;i<n;i++)
int a[3][3];
template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}
signed main(){
  REP(i,3)REP(j,3)cin>>a[i][j];
  int n;cin>>n;
  while(n--){
    int s;cin>>s;
    REP(i,3)REP(j,3)if(a[i][j]==s)a[i][j]=0;
  }
  REP(i,3){
    int c=0;
    REP(j,3)c+=a[i][j];
    if(!c)fin("Yes");
  }
  //コピペを3回していい感じにする
  REP(i,3){
    int c=0;
    REP(j,3)c+=a[j][i];
    if(!c)fin("Yes");
  }
  REP(i,3){
    int c=0;
    REP(j,3)c+=a[j][j];
    if(!c)fin("Yes");
  }
  REP(i,3){
    int c=0;
    REP(j,3)c+=a[2-j][j];
    if(!c)fin("Yes");
  }
  fin("No");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PREP(i, s, x) for(ll i = (s); i < (x); i++)
#define MREP(i, s, x) for(ll i = (s); i >= (x); i--)
#define REP(i, x) PREP(i, 0, x)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// variable -------------------------------------------

constexpr ll INF = (1ll << 59);
constexpr ll MOD = 1000000007ll;

// structure ------------------------------------------

// function -------------------------------------------
ll f(ll a, ll b){
    return a / b;
}

// 最大公約数を計算 GCD
// 最小公倍数を計算 LCM
ll llgcd(ll a, ll b){
    if(b == 0){
        return a;
    }
    return llgcd(b, a % b);
}
ll lllcm(ll a, ll b){
    if(a == 0 || b == 0){
        return 1;
    }
    return a / llgcd(a, b) * b;
}

// main -----------------------------------------------

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll a_ans = a-1 - f(a-1, c) - f(a-1, d) + f(a-1, lllcm(c, d));
    ll b_ans = b - f(b, c) - f(b, d) + f(b, lllcm(c, d));
    cout << b_ans - a_ans << endl;
    return 0;
}

Measured memory_bytes: 3584
import java.util.*;
	import java.util.Map.Entry;
	 
	 
	 class Main {
		 static int mod =  (int) (Math.pow(10,9)+7);
//		 static int mod =  (int) 998244353;
		 public static void main(String[] args) {
	    	
	        Scanner sc = new Scanner(System.in);
 
	        int N = sc.nextInt();
	        System.out.println(N-1);
        	String NS = sc.next();
	        System.out.println(0);
	        String RS=sc.next();
        	if(NS.equals("Vacant"))return;
        	if(RS.equals("Vacant"))return;
	        int R=0;
	        N=N-1;
	        for(int i=0;i<25;i++) {
	        	int mid = (N+R)/2;
	        	System.out.println(mid);
	        	String tmp = sc.next();
	        	if(tmp.equals("Vacant"))return;
	        	if(((mid-R)%2==1&&!RS.equals(tmp)) || ((mid-R)%2==0&&RS.equals(tmp))) {
	        		R=mid;
	        		RS=tmp;
	        	} else {
	        		N=mid;
	        		NS=tmp;
	        	}
	        }
	        
	       
	    }
 
	}

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, a, b;
	cin >> n >> a >> b;
	vi v(n);
	REP(i, n)cin >> v[i];
	int x = 0, y = 0, z = 0;
	REP(i, n) {
		if (v[i] <= a)x++;
		else if (v[i] <= b)y++;
		else z++;
	}
	cout << min(x, min(y, z)) << endl;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(){
  string s;cin>>s;
  rep(i,16){
    string t="AKIHABARA";  
    if(i&(1<<0))t[0]='#';
    if(i&(1<<1))t[4]='#';
    if(i&(1<<2))t[6]='#';
    if(i&(1<<3))t[8]='#';
    string ans="";
    rep(j,t.size()){
      if(t[j]!='#')ans+=t[j];
    }
    //cout<<ans<<endl;
    if(ans==s){
      cout<<"YES"<<endl;
      return 0;
    }
  }
  cout<<"NO"<<endl;
  return 0;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define debugArray(x, n)                           \
  cerr << __LINE__ << ": " << #x << " = {";        \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];        \
  cerr << "}" << endl
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  long double ans = 0;
  for (int i = 0; i < N; i++) {
    long double x;
    string u;
    cin >> x >> u;
    if (u == "JPY")
      ans += x;
    else
      ans += x * 380000;
  }
  cout << fixed << setprecision(12) << ans << '\n';
  return 0;
}


Measured memory_bytes: 3796
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int a,b,c;
	cin >> a >> b >> c;
	cout << c << " " <<  a << " " << b << endl;




}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll ac(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
int D;
vector<int> c(26);
vector<int> last(26, 0);
vector<vector<int>> s(365, vector<int>(26));
void input();
int score;
int next_num;
const int Way = 6;
const int Nest = 4;
/*void dfs(int nest, int d) {
	int M = 0, temp = score;
	int prev, n;
	vector<pair<int, int>> kouho(26);
	rep(j, 0, 26) {
		score = temp;
		score += s[d - 1][j];
		prev = last[j];
		last[j] = d;
		rep(k, 0, 26)score -= c[k] * (d - last[k]);
		kouho[j].first = score;
		kouho[j].second = j;
		last[j] = prev;
	}
	//sort(all(kouho), greater<pair<int, int>>());
	rep(j, 0, Way) {
		//prev = last[kouho[j].second];
		//last[kouho[j].second] = d;
		score = kouho[j].first;
		if (nest && d < D)dfs(nest - 1, d + 1);
		if (M < score)M = score, n = kouho[j].second;
		printf("j:%2d score:%d\n", j, score);
		//last[kouho[j].second] = prev;
	}
	score = M;
	next_num = n;
}*/
int dfs(int nest, int i) {
	ll M = -1 << 30, temp = score;
	int prev, p;
	vector<pair<int, int>> kouho(26);
	rep(j, 0, 26) {
		score = temp + s[i - 1][j];
		rep(k, 0, 26)if (j != k)score -= c[k] * (i - last[k]);
		kouho[j].first = score;
		kouho[j].second = j;
	}
	sort(all(kouho), greater<pair<int, int>>());
	rep(j, 0, Way + nest){
		score = kouho[j].first;
		prev = last[kouho[j].second];
		last[kouho[j].second] = i;
		if (nest && i < D)dfs(nest - 1, i + 1);
		last[kouho[j].second] = prev;
		if (M < score)M = score, p = kouho[j].second;
	}
	score = M;
	return p;
}
int main()
{
	input();
	/*rep(i, 1, D + 1) {
		//score = 0;
		dfs(Nest, i);
		printf("%d\n", next_num + 1);
		last[next_num] = i;
		printf("%d\n", score);
	}*/
	rep(i, 1, D + 1) {
		score = 0;
		int p = dfs(Nest, i);
		last[p] = i;
		printf("%d\n", p + 1);
		//printf("%d\n", score);
	}
	return 0;
}
void input() {
	cin >> D;
	rep(i, 0, 26)cin >> c[i];
	rep(i, 0, D) {
		rep(i2, 0, 26)cin >> s[i][i2];
	}
}

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

int main() {
  int N, D;
  cin >> N >> D;
  vector<vector<int>> X(N, vector<int>(D));
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < D; ++j)
      cin >> X[i][j];

  int ans = 0;
  for (int i = 0; i < N; ++i) {
    for (int j = i + 1; j < N; ++j) {
      int d2 = 0;
      for (int k = 0; k < D; ++k)
        d2 += abs(X[i][k] - X[j][k]) * abs(X[i][k] - X[j][k]);
      for (int k = 0; k * k <= d2; ++k)
        if (k * k == d2)
          ++ans;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <numeric>
#include <cmath>
#include <iomanip> //cout << fixed << setprecision(15) << << endl;
#include <cassert>
//#include "atcoder/all"

using namespace std;
//using namespace atcoder;

typedef long long ll;

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define P pair<int,int>

int mx8[] = {0,0,1,-1,-1,1,-1,1};
int my8[] = {-1,1,0,0,-1,-1,1,1};
int mx4[] = {1,-1,0,0};
int my4[] = {0,0,-1,1};


const int MAX = 510000;
const int MOD = 1000000007;

class UnionFind {
public:
    std::vector<int> RANK;
    std::vector<int> par;

public:
    UnionFind(int n)
    {
        RANK.resize(n);
        par.resize(n);
        for(int i = 0; i < n; ++i) par[i] = i;
    }

    int FindRoot(int x)
    {
        if (par[x] == x) return x;
        par[x] = FindRoot(par[x]);
        return par[x];
    }

    bool IsSame(int x, int y)
    {
        return FindRoot(x) == FindRoot(y);
    }

    void Union(int x, int y)
    {
        x = FindRoot(x);
        y = FindRoot(y);
        if (x == y) return;
        else{
            if(RANK[x] > RANK[y]){
                par[y] = x;
            }
            else{
                par[x] = y;
                if(RANK[x] == RANK[y]){
                    RANK[x]++;
                }
            }
        }
    }
};

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

    int n,m; cin >> n >> m;
    vector<int> p(n);
    rep(i,n) cin >> p[i];

    UnionFind uf(n);
    while(m--)
    {
        int x, y; cin >> x >> y;
        x--; y--;
        uf.Union(x,y);
    }

    int ans = 0;
    rep(i,n)
    {
        if(i+1 == p[i])
        {
            ans++;
            continue;
        }
        if(uf.IsSame(i,p[i]-1)) ans++;
    }

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

Measured memory_bytes: 4560
#include <stdio.h>
#include <stdlib.h>

long long int compare(const void *a,const void *b){
  return *(long long int*)a-*(long long int*)b;
}

int main(void){
  long N,K;
  scanf("%ld%ld",&N,&K);
  long long int data[N];
  long long int min;

  for(int i = 0;i < N;i++){
    scanf("%lld",&data[i]);
  }

  qsort(data,N,sizeof(long long int),compare);
  K--;

  for(int i = 0;i < N-K;i++){
    if(i == 0){
      min = data[i+K]-data[i];
    }else{
      if(min > data[i+K]-data[i]){
        min = data[i+K]-data[i];
      }
    }
  }

  printf("%lld\n",min);
  return 0;
}

Measured memory_bytes: 1788
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int n, a, b;
    int[] hs;

    public static void main(String args[]) {
        new Main().run();
    }

    void run() {
        FastReader sc = new FastReader();
        n = sc.nextInt();
        a = sc.nextInt();
        b = sc.nextInt();
        hs = new int[n];
        for (int i = 0; i < n; i++) {
            hs[i] = sc.nextInt();
        }
        solve();
    }

    void solve() {
        long low = 0;
        long high = 1000000001;
        while (low < high) {
            long mid = (low + high) >> 1;
            long count = mid;
            boolean flag = true;
            for (int i = 0; i < n; i++) {
                long temp = hs[i] - b * mid;
                if (temp > 0) {
                    count -= temp / (a - b);
                    if (temp % (a - b) > 0) {
                        count--;
                    }
                    if (count < 0) {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        System.out.println(low);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}


Measured memory_bytes: 38084
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
bool isAns = false;
char c = 0;
template<class F>
auto  maximize(int imin,int imax,F &f){
    while(imax - imin > 1){
        int mid = imin + (imax - imin)/2;
        if(f(mid)) imin = mid;
        else imax = mid;
        if(isAns) return 0;
    }
    return imin;
}

signed main(){
    cin >> N; printf("0\n");
    cout.flush();
    string s; cin >> s;
    c = s.front();
    if(c == 'V'){
        return 0;
    } else {
        auto f = [&](int mid){
            printf("%d\n",mid);cout.flush();
            string s; cin >> s;
            char temp = s.front();
            if(temp == 'V'){ isAns = true ;return true;}
            if(mid % 2 == 0 and c == temp) return true;
            if(mid % 2 == 1 and c != temp) return true;
            return false;
        };
        int val = maximize(1,N,f);
        cout << val << endl; cout.flush();
        cin >> s;
        assert(s.front() == 'V');
    }
}


Measured memory_bytes: 852
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define loop(i ,a,b) for(int i = a;i<b;i++)
#define rloop(i,a,b) for(int i = a ; i>b;i--)
#define loopll(i,a,b) for( long long int i = a; i<b;i++)
#define rloopll(i,a,b) for(long long int i = a; i>b;i--)
#define eb emplace_back
#define pii pair<int ,int>
#define pll pair<ll ,ll>
#define mk make_pair
#define intmin INT_MIN
#define intmax INT_MAX
#define cout(x) cout<<x<<" ";
using namespace std;
void vec(vector<int> & v){

    for(int i = 0;i<v.size() ; i++){
        cout<<v[i]<< " ";
    }
    cout<<endl;
}
void vec_ll(vector<long long int> & v){

    for(int i = 0;i<v.size() ; i++){
        cout<<v[i]<< " ";
    }
    cout<<endl;
}
int parsestring(string temp){
    int num= 0;
    int digs = temp.size() - 1;
    for(int i = 0 ;i<=digs;i++){
        num += pow(10 , digs -i)*(temp[i] - '0');
    }
    return num;
}
int main(){
    int x;
    cin>>x;
    if(x  >=30){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}
}


Measured memory_bytes: 3680
#include <cstdio>
#include <vector>
#include <algorithm>
#define STR_MAX 100000
using namespace std;

vector<int> pos[26];
long long int cycl=0,p=0,N;

int main(){
  char str[STR_MAX+1];
  scanf("%s",str);
  for(int i=0;str[i] != '\0';i++){
    pos[str[i]-'a'].push_back(i+1);
    N++;
  }
  
  scanf("%s",str);
  
  for(int i=0;str[i] != '\0';i++){
    int ch=str[i]-'a';
    if(pos[ch].size()==0){
      printf("-1\n");return 0;
    }
    
    auto  chp=upper_bound(pos[ch].begin(),pos[ch].end(),p);
    if(chp==pos[ch].end()){
      cycl++;chp=pos[ch].begin();
    }
    p=*chp;
  }
  
  printf("%ld",cycl*N+p);

  return 0;
}

Measured memory_bytes: 1020
#include<iostream>
#include<cstring>
using namespace std;
#define LL long long
char str[15];
LL ans;
void dfs(LL sum,LL pos,LL len){
	if(pos==len){
		ans+=sum;
		return;
	}
	for(LL i=pos;i<len;++i){
		LL tmp=0;
		for(LL j=pos;j<=i;++j)
			tmp=tmp*10+(str[j]-'0');
		dfs(sum+tmp,i+1,len);
	}
	return;
}
int main(){
	cin>>str;
	int len=strlen(str);
	dfs(0,0,len);
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import deepcopy, copy

import queue
from collections import deque



def divisor(n): #nの約数を全て求める
    i = 1
    table = set()
    while i * i <= n:
        if n%i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    return table

ans = 10 ** 10

def check(box_num, kagi_num, kagi_data, ind, now_data_kari, money, data):
    now_data = copy(now_data_kari)

    if ind == box_num:
        for i in range(box_num):
            if now_data[i] == 0:
                break
        else:
            global ans
            ans = min(ans, money)
        return


    if now_data[ind]:
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money, data)
        return

    check_set = set()
    for i in range(len(kagi_data[ind + 1])):
        aaa = kagi_data[ind + 1][i]
        now_data = copy(now_data_kari)

        bbb = ['0' for i in range(box_num)]
        flg = 1
        for ele in data[aaa][2]:
            if now_data[ele - 1] == 0:
                now_data[ele - 1] = 1
                flg = 0
            if ele >= ind + 1:
                bbb[ele - 1] = '1'
        if flg:
            continue
        bbb = ''.join(bbb)
        if bbb in check_set:
            continue
        check_set.add(bbb)
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money + data[aaa][0], data)



def main():
    box_num, kagi_num = map(int, input().split())

    data = [0 for i in range(kagi_num)]
    kari = set()

    for i in range(kagi_num):
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        kari |= set(b)
        data[i] = [a[0], a[1], b]


    kagi_data = defaultdict(int)
    for i in range(kagi_num):
        a = data[i]
        aaa = 0
        for ele in a[2]:
            aaa += 2 ** (ele - 1)
        bin_data = bin(aaa)[2:]
        bin_data = bin_data.zfill(box_num)

        if bin_data in kagi_data:
            kagi_data[bin_data] = min(a[0], kagi_data[bin_data])
        else:
            kagi_data[bin_data] = a[0]

        aaaaaa = kagi_data.items()

        for key, value in list(aaaaaa):
            aaa = ['0' for i in range(box_num)]
            for i in range(box_num):
                if key[i] == '1' or bin_data[i] == '1':
                    aaa[i] = '1'
            aaa = ''.join(aaa)
            if aaa in kagi_data:
                kagi_data[aaa] = min(value + a[0], kagi_data[aaa])
            else:
                kagi_data[aaa] = value + a[0]


    # print(kagi_data)
    aaa = ['1' for i in range(box_num)]
    aaa = ''.join(aaa)
    if aaa in kagi_data:
        print(kagi_data[aaa])
    else:
        print(-1)



# def test():
#     for i in :
#         print(i)

if __name__ == '__main__':
    main()
    # test()


Measured memory_bytes: 112088
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
bool b(char x) {
	if (x == 'a' || x == 'i' || x == 'u' || x == 'e' || x == 'o')return true;
	return false;
}
int main() {
	int n;
	while (cin >> n, n) {
		vector<string> v;
		string s;
		for (int i = 0; i < n; i++) {
			cin >> s;
			string t = "";
			t += s[0];
			int len = s.length();
			for (int j = 0; j < len-1; j++) {
				if (b(s[j]))t += s[j + 1];
			}
			v.push_back(t);
		}
		int chk=1;
		for (int i = 50; i > 0; i--) {
			bool f = true;
			for (int j = 0; j < n; j++) {
				for (int k = j+1; k < n; k++) {
					if (v[j] == v[k])f = false;
				}
			}
			if (!f) {
				chk = i + 1; break;
			}
			for (int j = 0; j < n; j++) {
				if (v[j].size() == i) {
					v[j].erase(v[j].begin() + i - 1);
				}
			}
		}
		if (chk == 51) {
			cout << -1 << endl;
		}
		else {
			cout << chk << endl;
		}
	}
	return 0;
}


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

vector<vector<pair<int,int> > >vec;
int n,c,m=0;
int C[1000]={0};

int dfs(int pre, int cur){
    int las=0;
    for(int i=0;i<vec[cur].size();i++){
        if(vec[cur][i].first==pre){
            las=vec[cur][i].second;
            break;
        }
    }
    if(C[cur]>0)
        return las;
    int tot=0;
    for(int i=0;i<vec[cur].size();i++){
        if(vec[cur][i].first!=pre){
            tot+=dfs(cur,vec[cur][i].first);
        }
    }
    return min(tot,las);
}

int main(){
    
    cin>>n;
    vec.resize(n);
    for(int i=1;i<n;i++){
        cin>>c;
        C[i]=c;
    }
    for(int i=0;i<n-1;i++){
        int u,v,p;
        cin>>u>>v>>p;
        vec[u].push_back((make_pair(v, p)));
        vec[v].push_back((make_pair(u, p)));
    }
    for(int i=0;i<vec[0].size();i++){
        m+=dfs(0,vec[0][i].first);
    }
    cout<<m<<endl;
}

Measured memory_bytes: 1260
#include<iostream>

using namespace std;

int MAX_N = 100;

int main()
{
    // スペース区切りの整数の入力
    string s;
    cin >> s;

    int N = s.size();

    for (int i = 0; i < (N-1)/2; i++)
    {
        if (s[i] != s[N-1-i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    for (int i = 0; i < (N-1)/4; i++)
    {
        if (s[i] != s[(N-1)/2-1-i])
        {
            cout << "No" << endl;
            return 0;
        }
    }

    for (int i = 0; i < (N-1)/4; i++)
    {
        if (s[(N-1)/2+1+i] != s[N-1-i])
        {
            cout << "No" << endl;
            return 0;
        }
    }


    cout << "Yes" << endl;


    return 0;
}

Measured memory_bytes: 256
n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]

p = [k-q]*(n)
for i in a:
    p[i-1] +=1

for i in range(n):
    if p[i]>0:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 10472
import itertools
import math

n = int(input())
xy = [list(map(int,input().split())) for _ in range(n)]
dist = 0

route = list(itertools.permutations([i for i in range(n)]))
for num in route:
    for i in range(1,n):
        dist += math.sqrt((xy[num[i]][0]-xy[num[i-1]][0])**2+ (xy[num[i]][1]-xy[num[i-1]][1])**2)
    
print(dist/len(route))

Measured memory_bytes: 13848
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG 
#define rep(i, n) for (int i = 0; i < n; i++)
#define reps(i, s, n) for (int i = s; i < n; i++)
#define all(v) v.begin(), v.end() // sort(all(array))
#define INF 1000000000
#define LINF 1LL << 60
#define mod 1000000007
#define EPS 0.0001
using namespace std;
using ll = long long;
using vi = vector<int>; //vi array(要素数, 初期値)
using vll = vector<ll>; 
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using vc = vector<char>;
using vs = vector<string>;
using vb = vector<bool>;
using vvi = vector<vi>; //vvi table(行数, vi(列数, 初期値))
using vvc = vector<vc>;
using vvs = vector<vs>;
using vvb = vector<vb>;

int main(){
    int k;
    cin >> k;
    string ans;
    rep(i, k) {  
        ans += "ACL";
    }
    cout << ans << endl;
}

Measured memory_bytes: 3544
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
string solve(bool a) { return ((a) ? "Yes" : "No"); }
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
template <class T, class U>ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}
template <class T>ostream& operator<<(ostream& os, const vector<T>& v) {
	os << "{";
	rep(i, v.size()) {
		if (i) os << ",";
		os << v[i];
	}
	os << "}";
	return os;
}
template <class T, class U>istream& operator>>(istream& is, pair<T, U>& p) {
	is >> p.first >>p.second ;
	return is;
}
template <class T>istream& operator>>(istream& is,  vector<T>& v) {
	rep(i, v.size()) {
		is >> v[i];
	}
	return is;
}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int n;
	int ans=-INF;
	cin >>n;
	Vi h(n);
	cin >> h;
	int last = INF;
	int len  = -1;
	rep(i,n){
		if(chmin(last,h[i]) or last==h[i]){
			len++;
		}else{
			chmax(ans, len);
			len  = 0;
			last = h[i];
		}
	}
	chmax(ans, len);
	cout<<ans<<endl;
}


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

const int maxn = 100010, P = 1000000007;
int n, a[maxn], fact[maxn], s[maxn];

int qp(int x, int y) {
    int z = 1;
    for (; y; y >>= 1, x = 1LL * x * x % P) {
        if (y & 1) z = 1LL * z * x % P;
    }
    return z;
}

int main() {
    scanf("%d", &n);
    for (int i = fact[0] = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        fact[i] = 1LL * i * fact[i - 1] % P;
        s[i] = (s[i - 1] + qp(i, P - 2)) % P;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + 1LL * a[i] * (s[i] + s[n - i + 1] - 1)) % P;
    }
    printf("%d\n", 1LL * fact[n] * ans % P);
    return 0;
}

Measured memory_bytes: 1408
#include <cstdio>
#include <cstdlib>

int main()
{
	int n;
	scanf("%d", &n);

	int* a = (int*)calloc(n, sizeof(int));
	int m = 0, p;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", a + i);
		if (a[i] >= m)
		{
			p = m;
			m = a[i];
		}
		else if (a[i] > p)
			p = a[i];
	}

	for (int i = 0; i < n; i++)
		printf("%d\n", a[i] == m ? p : m);

	return 0;
}

Measured memory_bytes: 2304
import java.util.*;
import java.util.function.*;
import java.math.*;
public class Main {
    public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();
		long[] leaf = new long[N + 1];
		for(int i = 0; i < N + 1; i++) {
			leaf[i] = s.nextInt();
		}
		long[] MAX = new long[N+2];
		long[] MIN = new long[N+2];
		MAX[N] = MIN[N] = leaf[N];
		
		for(int i = N - 1; i >= 0; i--) {
			MAX[i] = MAX[i+1] + leaf[i];
			MIN[i] = (MIN[i+1]+1) / 2 + leaf[i]; 
		}
		
		if(MIN[0] != 1) {
			System.out.println("-1");
			return;
		}
		
		long cur = 1;
		long ret = 0;
		for(int i = 0; i <= N; i++) {
			ret += cur;
			cur -= leaf[i];
			cur = Long.min(cur*2, MAX[i+1]);
		}
		System.out.println(ret);
	}
}

Measured memory_bytes: 60276
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;i++)
#define Rep(i,a,b) for(ll i=a;i<b;i++)
#define pb emplace_back
#define allv v.begin(),v.end()
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
#define FASTio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define deb(x) cout<<(#x)<<" "<<x<<endl
ll mod=1e9+7;
template<typename t>
ll Max(ll a,ll b)
{
    return (a>b)?a:b;
    
}
ll Min(ll a,ll b)
{
    return (a>b)?b:a;
}
ll Power(ll a,ll b)
{
    ll p=1;
    a=a;
    b=b;
    while(b)
    {
        if(b&1)
        {
            p=((p)*(a));
        }
        a=((a)*(a));
        b=(b/2);
    }
    return p;
}
ll power(ll a,ll b)
{
    if(b==0)
    return 1;
    ll p=power(a,b/2)%mod;
    p=(p*p)%mod;
    if(b&1)
    p=(p*a)%mod;
    return p;
}
ll gcd(ll a,ll b)
{
    if(a==0)
    return b;
    return gcd(b%a,a);
}
/*void dfs(ll i)
{
    visited[i]=true;
   // provinces.pb(i);
    for(auto it:adj[i])
    {
        if(!visited[it] && choices[it])
        dfs(it);
    }
}*/
ll prod(ll a,ll b)
{
    return ((a%mod)*(b%mod))%mod;
}
ll add(ll a,ll b)
{
    return ((a%mod)+(b%mod))%mod;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    ll dp[n+1]={0};
    dp[0]=1;
    for(ll i=3;i<=n;i++)
    {
        for(ll j=3;j<=i;j++)
        {
            (dp[i]+=dp[i-j])%=mod;
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 29)
using namespace std;

bool check(int alp[30], int k){
    rep(i,30){
        if(alp[i] > 0){
            alp[i]--;
            k--;
        }
        if(k == 0) return 1;
    }
    return 0;
}

int main(){
    int n, k;
    int alp[30] = {0};
    cin >> n >> k;
    rep(i,n){
        string str;
        cin >> str;
        alp[ str[0] - 'A' ]++;
    }

    int ans = 0;
    while(true){
        sort(alp, alp + 30, greater<int>());
        if(check(alp, k)){
            ans++;
        }else{
            break;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
/* Properties of modulo:
	(a/b)%m ,where m is prime  = (a%m) * (b^(m-2))%m
*/
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define ll long long
#define pb push_back
#define gcd __gcd
#define nl cout<<"\n"
#define endl "\n"
#define all(c) (c).begin(),(c).end()
#define trav(a,x) for(auto a = x.begin() ; a != x.end() ; a++)
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
template<typename T>
#define o_set(T) tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>
// o_set(ll) name ; -- defining ordered set
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set - returns iterator
bool compare(ll a, ll b){
    return a > b;
}
ll power(ll x, ll ex , ll md) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x) % md;
        ex >>= 1ll;
        x = (x * x) % md;
    }
    return ans;
}
void solve(){
    ll a, b , c ,d ;
    cin >> a>> b >> c >>d ;
    ll m1 , m2 =0;
    if(c%b ==0 ) m1 = c/b;
    else m1 = c/b + 1;
    if(a%d == 0) m2 = a/d;
    else m2 = a/d + 1;
    if(m1 <= m2) cout<<"Yes\n";
    else cout<<"No\n";
}
int main(){
    IOS;
    ll T=1;
    //cin>>T;
    ll t=0;
    while(t++<T){
        //cout<<"Case #"<<t<<":"<<' ';
        solve();
        //cout<<'\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}


Measured memory_bytes: 3804
#include<stdio.h>

int main(void){
   int X,i;
   int y,z;
   int count=0;
   
   scanf("%d",&X);
   y=(X/500)*1000;
      z=((X%500)/5)*5;
      
      count=y+z;
      printf("%d\n",count);
      return 0;
      }


Measured memory_bytes: 1728
#include "bits/stdc++.h"
using namespace std;
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define MOD         1000000007
#define hell        1000000007
#define N	    400001
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define rev(i,a,b)  for(int i=a;i>=b;i--)
#define ll          long long
#define bg(i)       i.begin()
#define fset(it,s)   for(auto it = s.begin(); it != s.end(); it++)


#define track(x)                cerr<<#x<<": "<<x<<endl
#define track2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define track3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define track4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl

#define ed(i)       i.end()
#define mem(a)	    memset(a, 0, sizeof(a))
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
ll fpow(ll n, ll k, ll p = MOD) {ll r = 1; for (; k; k >>= 1LL) {if (k & 1LL) r = mult(r,n,p); n = mult(n,n,p);} return r;}
ll inv(ll a, ll p = MOD) {return fpow(a, p - 2, p);}
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

ll dp[N];
const int INF = 1e9 + 5;
void solve(){
	int n, w;
	cin>>n>>w;
	vector<ll> dp(w+1, 0);
	dp[0] = 0;
	rep(i,0,n) {
		ll weight, value;
		cin>>weight>>value;
		rev(j,w,0) {
			if(j - weight < 0) break;
			dp[j] = max(dp[j], dp[j-weight] + value);
		}
	}
	cout<<dp[w]<<endl;
}
int main() {
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(20);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//	cin>>t;
	while(t--){
		solve();
	}
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,s,n) for (int i = s; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  string s;
  cin >> s;
  int a = stoi(s.substr(0,2)), b = stoi(s.substr(2,2));
  if (a > 12 || a == 0) {
    if (b > 12 || b == 0) cout << "NA" << endl;
    else cout << "YYMM" << endl;
  } else {
    if (b > 12 || b == 0) cout << "MMYY" << endl;
    else cout << "AMBIGUOUS" << endl;
  }
  return 0;
}

Measured memory_bytes: 3620