Problem:


Score : 600 points

Problem Statement

Given is an integer sequence of length N+1: A_0, A_1, A_2, \ldots, A_N. Is there a binary tree of depth N such that, for each d = 0, 1, \ldots, N, there are exactly A_d leaves at depth d? If such a tree exists, print the maximum possible number of vertices in such a tree; otherwise, print -1.

Notes

A binary tree is a rooted tree such that each vertex has at most two direct children.

A leaf in a binary tree is a vertex with zero children.

The depth of a vertex v in a binary tree is the distance from the tree's root to v. (The root has the depth of 0.)

The depth of a binary tree is the maximum depth of a vertex in the tree.

Constraints

0 \leq N \leq 10^5

0 \leq A_i \leq 10^{8} (0 \leq i \leq N)

A_N \geq 1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 A_2 \cdots A_N

Output

Print the answer as an integer.

Sample Input 1

3
0 1 1 2

Sample Output 1

7

Below is the tree with the maximum possible number of vertices. It has seven vertices, so we should print 7.

Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

10
0 0 1 1 2 3 5 8 13 21 34

Sample Output 5

264



Sample input:
3
0 1 1 2


Sample output:
7

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>


using namespace std;

// マクロ&定数&関数 ================================================
typedef unsigned int uint;
typedef long long ll;

typedef pair<ll, ll> pll;

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;

typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vpint> vvpint;
typedef vector<vpll> vvpll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<string>> vvstring;
typedef vector<vector<bool>> vvbool;

typedef vector<vector<vector<ll>>> vvvll;

const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,  0, 1, -1, 1,  1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1, -1, 0,  0, 1, -1,  1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const double PI = 3.14159265358979323846264338327950288;

//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV

const ll MOD = 1000000007; //10^9 + 7

//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV


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

//---------------------------------------------------------------
//  オーバーフローチェック
//---------------------------------------------------------------
void is_overflow(ll a, ll b) { if ((a * b) / b != a)	cout << "OVERFLOW!!!!!" << endl; }

//---------------------------------------------------------------
//  約数列挙
//---------------------------------------------------------------
vll divisor(ll n) {
	vll ret;
	for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i);	if (i * i != n) ret.push_back(n / i); } }
	sort(begin(ret), end(ret));	return (ret);
}

//---------------------------------------------------------------
// N以下のすべての素数を列挙する(エラトステネスの篩)
//---------------------------------------------------------------
vbool searchSosuu(ll N) {
	vbool sosuu;
	for (ll i = 0; i < N; i++) { sosuu.emplace_back(true); }
	sosuu[0] = false;	sosuu[1] = false;
	for (ll i = 2; i < N; i++) { if (sosuu[i]) { for (ll j = 2; i * j < N; j++) { sosuu[i * j] = false; } } }
	return sosuu;
}

//---------------------------------------------------------------
// 素因数分解　O(√N)
//---------------------------------------------------------------
vpll div_prime(ll n) {
	vpll prime_factor;
	for (ll i = 2; i * i <= n; i++) {
		ll count = 0; while (n % i == 0) { count++; n /= i; }
		if (count) { pair<ll, ll> temp = { i, count };	prime_factor.emplace_back(temp); }
	}
	if (n != 1) { pair<ll, ll> temp = { n, 1 }; prime_factor.emplace_back(temp); }
	return prime_factor;
}

//---------------------------------------------------------------
// 素数判定
//---------------------------------------------------------------
bool is_sosuu(ll N) {
	if (N < 2)			 return false;
	else if (N == 2)	 return true;
	else if (N % 2 == 0) return false;
	for (ll i = 3; i <= sqrt(N); i += 2) { if (N % i == 0)	return false; }
	return true;
}

//---------------------------------------------------------------
// 最大公約数（ユークリッドの互除法）
//---------------------------------------------------------------
ll gcd(ll a, ll b) {
	if (a < b) { ll tmp = a;	a = b; b = tmp; }
	ll r = a % b;
	while (r != 0) { a = b; b = r; r = a % b; }
	return b;
}

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

//---------------------------------------------------------------
// 階乗
//---------------------------------------------------------------
ll factorial(ll n) { if (n <= 1) { return 1; }return (n * (factorial(n - 1))) % MOD; }

//---------------------------------------------------------------
// 高速コンビネーション計算(前処理:O(N) 計算:O(1))
//---------------------------------------------------------------
// テーブルを作る前処理
ll comb_const = 300005;
vll fac(comb_const), finv(comb_const), inv(comb_const);
bool COMineted = false;
void COMinit() {
	fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1;
	for (ll i = 2; i < comb_const; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
	COMineted = true;
}
// 二項係数計算
ll COM(ll n, ll k) {
	if (COMineted == false) COMinit();
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;
}

//---------------------------------------------------------------
// 繰り返し２乗法 base^sisuu
//---------------------------------------------------------------
ll RepeatSquaring(ll base, ll sisuu, ll MOD) {
	if (sisuu < 0) { cout << "RepeatSquaring: 指数が負です!" << endl; return 0; }
	if (sisuu == 0) return 1;
	if (sisuu % 2 == 0) { ll t = RepeatSquaring(base, sisuu / 2, MOD) % MOD;	return (t * t) % MOD; }
	return (base * RepeatSquaring(base, sisuu - 1, MOD)) % MOD;
}

//---------------------------------------------------------------
// 高速単発コンビネーション計算(O(logN))
//---------------------------------------------------------------
ll fast_com(ll a, ll b) {
	ll bunshi = 1;	ll bunbo = 1;
	for (ll i = 1; i <= b; i++) { bunbo *= i;	bunbo %= MOD; bunshi *= (a - i + 1); bunshi %= MOD; }
	ll ret = bunshi * RepeatSquaring(bunbo, MOD - 2, MOD); ret %= MOD;
	while (ret < 0) { ret += MOD; }
	return ret;
}

//---------------------------------------------------------------
// 整数をビットのリストに変換する ll->vbool
//---------------------------------------------------------------
vbool to_bitlist(ll bit, ll fixed_size = 1) {
	if (bit == 0) return vbool(fixed_size, 0);
	vbool list;
	while (bit > 0) { list.emplace_back(bit & 1);	bit /= 2; }
	while (list.size() < fixed_size) { list.emplace_back(0); }
	return list;
}

//---------------------------------------------------------------
// 座標圧縮(O(NlogN))   0スタートであることに注意！
//---------------------------------------------------------------
class PosPress
{
	/*
	配列Pを座圧→instance = PosPress(P);

	座圧済み配列→instance.arr
	fooの圧縮後→instance.func[foo]
	fooの圧縮前→instance.rev[foo]
	*/
public:
	vll arr;
	map<ll, ll> func;
	map<ll, ll> rev;

	PosPress(vll P) {
		arr = P; sort(P.begin(), P.end()); func[P[0]] = 0;	rev[0] = P[0]; ll next = 1;
		for (int i = 1; i < P.size(); i++) { if (P[i] != P[i - 1]) { func[P[i]] = next; rev[next] = P[i]; next++; } }
		for (int i = 0; i < P.size(); i++) { arr[i] = func[arr[i]]; }
	}
};

//---------------------------------------------------------------
// 行列累乗(O(N^3))
//---------------------------------------------------------------
vvll mat_cross(vvll A, vvll B) {
	ll N = A.size(); ll K = B.size(); ll M = B[0].size();
	vvll C(N, vll(M));
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			for (int k = 0; k < K; k++)
				C[i][j] += A[i][k] * B[k][j];
	return C;
}

//---------------------------------------------------------------
// 2直線の交差判定(直線(x1, y1)->(x2, y2) と 直線(X1, Y1)->(X2, Y2))
//---------------------------------------------------------------
bool is_cross(ll x1, ll y1, ll x2, ll y2, ll X1, ll Y1, ll X2, ll Y2) {
	ll dx_ai = X1 - x1;	ll dy_ai = Y1 - y1;
	ll dx_bi = X1 - x2;	ll dy_bi = Y1 - y2;
	ll dx_ai2 = X2 - x1; ll dy_ai2 = Y2 - y1;
	ll dx_bi2 = X2 - x2; ll dy_bi2 = Y2 - y2;
	ll si = dx_ai * dy_bi - dy_ai * dx_bi;
	ll si2 = dx_ai2 * dy_bi2 - dy_ai2 * dx_bi2;
	ll si3 = dx_ai * dy_ai2 - dy_ai * dx_ai2;
	ll si4 = dx_bi * dy_bi2 - dy_bi * dx_bi2;
	return (si * si2 < 0 && si3 * si4 < 0);
}

//---------------------------------------------------------------
// 最長増加部分列の長さ(O(NlogN))
//---------------------------------------------------------------
ll LSI(vll vec)
{
	ll size = vec.size();
	vll lsi(size + 1); // 長さjを作った時の右端の最小値
	for (ll i = 0; i <= size; i++) { lsi[i] = LLINF; }
	lsi[0] = 0;	lsi[1] = vec[0];
	for (ll i = 1; i < size; i++)
	{
		// 初めてvec[i]の方が小さくなるところを探す
		auto Iter = lower_bound(lsi.begin(), lsi.end(), vec[i]);
		ll idx = Iter - lsi.begin();
		if (idx > 0 && lsi[idx - 1] < vec[i]) { lsi[idx] = vec[i]; }
	}
	for (ll i = size; i >= 0; i--) { if (lsi[i] < LLINF) { return i; } }
}

//---------------------------------------------------------------
// 木の根からの深さ
//---------------------------------------------------------------
vll tree_depth(vvll edge, ll start_node, ll n_node)
{
	vll dist(n_node, LLINF);
	dist[start_node] = 0;

	stack<pll> S;
	S.push({ start_node, 0 });

	while (!S.empty())
	{
		ll node = S.top().first;
		ll d = S.top().second;
		dist[node] = d;

		S.pop();

		for (int i = 0; i < edge[node].size(); i++)
		{
			if (dist[edge[node][i]] == LLINF)
			{
				S.push({ edge[node][i], d + 1 });
			}
		}
	}

	return dist;
}

//---------------------------------------------------------------
// ワーシャルフロイド法(O(N^3)) d: 正方行列(N*N)
//---------------------------------------------------------------
vvll warshall_floyd(vvll d) {
	ll n = d.size();
	for (int k = 0; k < n; k++) {       // 経由する頂点
		for (int i = 0; i < n; i++) {    // 始点
			for (int j = 0; j < n; j++) {  // 終点
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	return d;
}

//---------------------------------------------------------------
// Union Find
//---------------------------------------------------------------
class UnionFind {
public:
	/*
	UnionFind uf(要素の個数);
	for(int i = 0;i < 関係の個数; i++)
	{
		uf.merge(A[i], B[i]);
	}

	nを含む集合の大きさ = uf.size(n)
	nを含む集合の代表者 = uf.root(n)
	集合の個数 = uf.n_group
	*/
	vector <ll> par; // 各元の親を表す配列
	vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
	ll n_group; //集合の数

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
		n_group = sz_;
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;
		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		n_group--;
		return true;
	}

	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}
};

//---------------------------------------------------------------
// ダイクストラ(O(ElogV))   edge: 隣接リスト from->pair{to, cost}
//---------------------------------------------------------------
class Dijkstra
{
public:

	vll dist; // iまでの最短距離
	vll past; // (iまで最短で行くときの一つ前)

	// edge[i] -> {to, cost}
	Dijkstra(vvpll edge, ll start) : dist(edge.size(), LLINF), past(edge.size(), -1)
	{
		using Pi = pll;
		priority_queue< Pi, vector< Pi >, greater< Pi > > que;
		dist[start] = 0;
		que.emplace(dist[start], start);
		while (!que.empty()) {
			ll cost;
			int idx;
			tie(cost, idx) = que.top();
			que.pop();
			if (dist[idx] < cost) continue;
			for (int i = 0; i < edge[idx].size(); i++)
			{
				ll next_cost = cost + edge[idx][i].second;
				if (dist[edge[idx][i].first] <= next_cost) continue;
				dist[edge[idx][i].first] = next_cost;
				past[edge[idx][i].first] = idx;
				que.emplace(dist[edge[idx][i].first], edge[idx][i].first);
			}
		}
	}

	// goalまでの最短経路
	vll shortest(ll goal)
	{
		vll ret;
		while (goal != -1)
		{
			ret.emplace_back(goal);
			goal = past[goal];
		}
		reverse(ret.begin(), ret.end());
		return ret;
	}
};

//---------------------------------------------------------------
// LCA: 最近共通祖先 (O())
//---------------------------------------------------------------
class Lca
{
public:

	vll depth; // 根0からiまでの最短距離
	vvll doubling;
	ll n_bit = 30;

	// edge[i] -> {to, cost}
	Lca(vvll edge) : doubling(50, vll(edge.size(), -1))
	{
		// 深さ
		depth = tree_depth(edge, 0, edge.size());

		// ダブリングで親を辿れるようにする
		// jから2^i回親を辿ったノード
		doubling[0][0] = -1;
		for (int i = 1; i < edge.size(); i++)
			for (int j : edge[i])
				if (depth[i] > depth[j]) { doubling[0][i] = j; break; }
		for (int i = 1; i < n_bit; i++)
			for (int j = 0; j < edge.size(); j++) {
				if (doubling[i - 1][j] != -1) doubling[i][j] = doubling[i - 1][doubling[i - 1][j]];
				else doubling[i][j] = -1;
			}
	}

	// aとbの最近共通祖先
	ll get_lca(ll a, ll b)
	{
		// depth[a] >= depth[b]にする
		if (depth[a] < depth[b]) swap(a, b);
		ll oa = a;
		ll ob = b;
		ll d = depth[a] - depth[b];

		// aをdだけさかのぼる。
		vbool bit = to_bitlist(d, n_bit);
		for (int i = 0; i < n_bit; i++)if (bit[i]) a = doubling[i][a];

		// depth[a] == depth[b]になっている。
		for (int i = n_bit - 1; i >= 0; i--) {
			if (doubling[i][a] == doubling[i][b]) continue;
			a = doubling[i][a];	b = doubling[i][b];
		}
		return a == b ? a : doubling[0][a];
	}


};

//---------------------------------------------------------------
// セグメント木
//---------------------------------------------------------------
class SegmentTree
{
public:

	const ll SEG_LEN = 1 << 20;
	vll seg;

	SegmentTree() : seg(SEG_LEN * 2, 0) { int a = 0; }

	void seg_change(ll pos, ll to)
	{
		pos += SEG_LEN;
		seg[pos] = to;

		while (true)
		{
			pos /= 2;
			if (pos <= 0) break;
			seg[pos] = min(seg[pos * 2], seg[pos * 2 + 1]);
		}
	}

	ll seg_min(ll left, ll right)
	{
		left += SEG_LEN;
		right += SEG_LEN + 1;

		ll ret = LLINF;

		while (left < right)
		{
			while (left % 2 == 1)
			{
				chmin(ret, seg[left]);
				left++;
			}
			while (right % 2 == 1)
			{
				chmin(ret, seg[right - 1]);
				right--;
			}

			left /= 2;
			right /= 2;
		}

		return ret;
	}

};


//========================================================================
//========================================================================
//========================================================================
//========================================================================








int main() {

	//////==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	//////==================================


	/*
	～思いついたことはとりあえず絶対メモする！！～



	*/


	ll N;
	cin >> N;
	vll A(N + 1);
	for (ll i = 0; i < N + 1; i++) cin >> A[i];

	vll B = A;
	reverse(B.begin(), B.end());

	vll upper(N + 1, 0);
	upper[0] = B[0];
	for (ll i = 0; i < N; i++)
	{
		upper[i + 1] = upper[i] + B[i + 1];
	}
	reverse(upper.begin(), upper.end());

	vll V(N + 1, 0);
	if (A[0] == 1)
	{
		if (N >= 1) cout << -1 << endl;
		if (N == 0) cout << 1 << endl;
		return 0;
	}
	if (A[0] > 1)
	{
		cout << -1 << endl;
		return 0;
	}
	upper.emplace_back(LLINF);

	V[0] = 1;
	for (ll d = 1; d <= N; d++)
	{
		// 次に作れるノードの最大値
		ll can = min((V[d - 1] - A[d-1]) * 2, upper[d]);
		
		// 次作らなければならないノード数
		ll least = (V[d - 1] - A[d - 1]);

		if (A[d] > can || least > can)
		{
			cout << -1;
			return 0;
		}

		V[d] = can;
	}
	V[N] = A[N];

	ll ans = 0;
	for (ll v : V)
	{
		ans += v;
	}

	cout << ans;




}

Submission status: Runtime Error

Solution code:
n=int(input())
arr=list(map(int,input().split()))
if n==0:
  if arr[0]==1:
    print(1)
  else:
    print(-1)
acum=[arr[0]]
for i in range(1,n+1):
  acum.append(acum[-1]+arr[i])
b=[0]*n
b[0]=1-arr[0]
b[0]=min(b[0],acum[n]-b[0])
for i in range(1,n):
  b[i]=2*b[i-1]-arr[i]
  b[i]=min(b[i],acum[n]-acum[i])
for i in range(n):
  if b[i]<=0:
    print(-1)
    exit()
ans=sum(arr)+sum(b)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    l = [0]*(n+1)
    l[n] = (A[n], A[n])
    for i in reversed(range(1, n+1)):
        l[i-1] = (max(math.ceil(l[i][0]/2)+A[i-1], 1), l[i][1]+A[i-1])

    if 1 not in range(l[0][0], l[0][1]+1):
        print(-1)
    else:
        ans = [0]*(n+1)
        ans[0] = 1
        cnt = 1
        for i in range(n):
            ans[i+1] = min((ans[i]-A[i])*2, l[i+1][1])
        print(sum(ans))


resolve()

Submission status: Runtime Error

Solution code:
n = int(input())
nums = list(map(int, input().split()))
if n == 0:
  if nums[0] == 1:
    print(1)
  else:
    print(-1)
  exit()
if n >=1 and nums[0] != 0:
  print(-1)
  exit()
n_nods = 1
ans = 1
ret = sum(nums)
for i in range(1,n+1):
  n_nods = min(n_nods*2,ret)
  ans += n_nods
  ret -= nums[i]
  n_nods -= nums[i]
  if n_nods < 0:
    print(-1)
    exxit()
  if n_nods == 0 and i < n:
    print(-1)
    exit()
print(ans)

Submission status: Runtime Error

Solution code:
import math

def main():
    n = int(input())
    A = list(map(int, input().split()))

    if A[0] != 0:
        print(-1)
        return 

    limit_v = [0]*(n+1)
    limit_v[0] = 1
    for i in range(1, n+1):
        curr_limit_v = (limit_v[i-1] - A[i-1])*2
        limit_v[i] = curr_limit_v


    v_cnt = [0]*(n+1)
    v_cnt[n] = min(limit_v[n], A[n])
    ans = 0
    for i in range(n-1,0,-1):
        leaf = A[i]
        max_not_leaf = v_cnt[i+1]
        min_not_leaf = math.ceil(v_cnt[i+1]/2)

        curr_max_v = max_not_leaf + leaf
        curr_min_v = min_not_leaf + leaf

        if limit_v[i] < curr_min_v:
            print(-1)
            return

        v_cnt[i] = min(limit_v[i], curr_max_v)

    v_cnt[0] = 1
    ans = sum(v_cnt)
    if ans == 0: ans = -1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import deque
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
 
def end():
    print(-1)
    exit()
 
def main():
    n = I()
    deq = deque(LI())
    if n==0:
        if deq[0] == 0:
            print(1)
            exit()
    if deq[0]!=0:
        end()
    max = deque()
    for i in range(n,-1,-1):
        if 2**i<deq[i]:
            end()
        if i == n:
            max.appendleft(deq[i])
        else:
            max.appendleft(max[0]+deq[i])
    for i in range(n+1):
        max[i] = min(2**i,max[i])
        if i!=n and i!=0:
            max[i] = min(2*(max[i-1]-deq[i-1]),max[i])
    	if max[i]<deq[i]:
          end()
    print(sum(max))
    return
 
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

N = int(input())
A = list(map(int, input().split()))
Q = deque()
Q.append([0])
cnt = 1
ans = 1
li = []
while Q:
  temp = Q.popleft()
  if len(temp) == cnt and A[cnt]>=0:
    for i in range(2):
      new = temp + [ans]
      Q.append(new)
      li.append(new)
      ans += 1
      A[cnt] -= 1
      if A[cnt]<0:
        break
  else:
    cnt += 1
    if cnt >= N:
      break
  if not Q and cnt<N:
    Q.append(temp)
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
exp=1
l=[1]
for i in range(1,N+1):
    exp*=2
    exp-=A[i-1]*2
    l.append(exp)
if A[N]==exp:
    print(sum(l))
elif exp>A[N]:
    if A[N]>=l[N]/2:
        l[N]=A[N]
        print(sum(l))
    else:
        l[N]=A[N]
        for j in reversed(range(N)):
            if A[N]>=(l[j]-A[j])/2:
                l[j]=A[N]+A[j]
                print(sum(l))
                exit()
            else:
                l[j]=A[N]+A[j]
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
n = int(stdin.readline())
nmleaves = list(map(int, stdin.readline().strip().split()))

if n == 0:
    print(0)
else:
    if nmleaves[0]!= 0:
        print(-1)
        exit()
    
    # pref[i]: sum(nmleaves[i:]), i.e., the number of leaves at or below level i.
    pref = [0]*(n+1)
    totsum = sum(nmleaves)
    pref[0] = totsum
    t = 0
    for i in range(1, n+1):
        t += nmleaves[i-1]
        pref[i]  = totsum - t

    prev_nl = 1
    ans = 1
    for lev in range(1, n+1):
        nodes = min(prev_nl*2, pref[lev])
        ans += nodes
        prev_nl = nodes - nmleaves[lev]
        if prev_nl < 0:
            print(-1)
            exit()
        elif prev_nl == 0 and pref[lev + 1]>0:
            print(-1)
            exit()
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n = int(input())
    n += 1
    a = list(map(int, input().split()))
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i] + a[i]
    ans = [0] * n
    for i in range(n):
        ans[i] = c[n] - c[i]
    if n == 1 and a[0] == 0:
        print(-1)
        return
    if n > 1 and a[o] > 0:
        print(-1)
        return
    ans[0] = min(1, ans[0])
    for i in range(1, n):
        ans[i] = min(ans[i], (ans[i-1]-a[i-1]) * 2)
        if ans[i] < a[i]:
            print(-1)
            return

    print(sum(ans))
main()

Submission status: Runtime Error

Solution code:
N = int(input())
nums = list(map(int, input().split()))
nodes = []
currentLeaf = 1
fail = False
#check from top
for i in range(N + 1):
	nodes.append(currentLeaf)
	currentLeaf = (currentLeaf-nums[i])*2
	if (currentLeaf < 0):
		fail = True
		break 
if (fail):
	print(-1)
#check from bottom
currentLeaf = 0
totalNode = 0
for i in reversed(range(N+1)):
	currentLeaf += nums[i]
	currentLeaf = min(currentLeaf, nodes[i])
	totalNode += currentLeaf

if (fail):
	print(-1) 
else:
	print(totalNode)

Submission status: Runtime Error

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
import math

N = INT()
A = LIST()


if (N == 0 and A[0] != 1) or (N > 0 and A[0] != 0):
    print(-1)
    exit()


node_min, node_max = [0]*(N+1), [0]*(N+1)
node_min[-1] = A[-1]
node_max[-1] = A[-1]
for i in reversed(range(N)):
    node_min[i] = max(math.ceil(node_min[i+1]/2) + A[i]
    node_max[i] = node_max[i+1] + A[i]


if node_min[0] > 1:
    print(-1)
    exit()

ans = 1
node = 1
for i in range(1, N+1):
    node = min(node_max[i], 2*node)
    ans += node
    node = node - A[i]


print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
arr = list(map(int , input().split()))
s = sum(arr)
f = 1
if n == 0:
  if arr[0] != 1:
    print(-1)
    exit()
  else:
    print(1)
    exit()
elif a[0]!=0:
  print(-1)
  exit()
ans = 1
node = 1
for i in range(1,n+1):
  node=min(2*node, s)
  ans+=node
  node-=a[i]
  s-=a[i]
  if node < 0:
    print(-1)
  	f = 0
    exit()
if f: print(ans)

Submission status: Runtime Error

Solution code:
n,*a=map(int,open(0).read().split())
t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0:exit(-1)
  v+=w
print(v)

Submission status: Runtime Error

Solution code:
n,*a,t=map(int,open(0).read().split()),sum(a)
v=w=1
for q in a:
  w=min(2*(w-q),t:=t-q);(v:=v+w)
  if w<0:print(-1);exit()
print(v)

Submission status: Runtime Error

Solution code:
n,*a,t=map(int,open(0).read().split()),sum(a)
v=w=1
for q in a:
  w=min(2*(w-q),t:=t-q);(v:=v+w)
  if w<0:print(-1);exit()
print(v)

Submission status: Runtime Error

Solution code:
n,*a=map(int,open(0).read().split())
t,v,w=sum(a),1,0
for q in a:
  w=min(2*(v[-1]-q),t:=t-q)
  v+=w
  if w<0:print(-1);exit()
print(v)

Submission status: Runtime Error

Solution code:
import math

# 2分木
# The number is the depth of the tree
n = int(input())
#n = 4

# the number is the count of leaves
a = input()
a = [int(s) for s in a.split(' ')]
#a = [0, 0, 1, 0, 2]


# 可能な範囲を下から見ていく（一番深い葉から見てく)
d = list(range(n + 1))
for i in reversed(range(n + 1)):
    tmp = []
    
    if i == n:
        #min
        tmp.append(a[i])
        #max
        tmp.append(a[i])
    
    else:
        # 葉の数の足し忘れに注意
        #min
        tmp.append(math.ceil(d[i+1][0] / 2) + a[i])
        #max
        tmp.append(d[i+1][1] + a[i])
    
    d[i] = tmp

#print(d)

# その後下に下がっていく
ans = []
for i in range(n + 1):
    if i == 0:
        ans.append(1)
    else:
        tmp = ans[i-1] * 2
        if tmp >= d[i][0] and tmp <= d[i][1]:
            ans.append(tmp)
        elif tmp >= d[i][1]:
            ans.append(d[i][1])

#print(ans)
print(sum(ans))

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n=int(input())
a=list(map(int,input().split()))
c=list(accumulate(a))
b=[0]*(n+1)
#大きくしすぎてしまう場合がある
#いや上限を考えろや
def f():
    global n,a,b
    if n==0:
        
    for i in range(n+1):
        if i==0:
            b[0]=min(c[n]-c[0],1)
        else:
            b[i]=min(2*(b[i-1]-a[i-1]),c[n]-c[i-1])

    if n==0:
        if a[0]!=1:
            print(-1)
        else:
            print(1)
    elif b[n]!=a[n]:
        print(-1)
    else:
        print(sum(b))
        #print(b)
f()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
// using Graph = vector<vector<Edge>>;
using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N;
  cin >> N;
  vector<ll> A(N + 1);
  for (auto &it : A)
    cin >> it;
  vector<ll> th(N + 1);
  if (N == 0)
  {
    if (A[0] != 1)
    {
      cout << -1 << endl;
      return 0;
    }
    else
    {
      cout << 1 << endl;
      return 0;
    }
  }
  else
  {
    if (A[0] != 0)
    {
      cout << -1 << endl;
      return 0;
    }
    else
    {
      th[0] = 1;
      for (int i = 1; i < N + 1; i++)
      {
        th[i] = min(INF / 2, (th[i - 1] - A[i - 1]) * 2);
        if (A[i] > th[i] || (A[i] == th[i] && i != N))
        {
          cout << -1 << endl;
          return 0;
        }
      }
      ll ans = 0;
      ans += A[N];
      th[N] = A[N];
      for (int i = N - 1; i >= 0; i--)
      {
        ans += min(th[i], th[i + 1] + A[i]);
        th[i] = min(th[i], th[i + 1] + A[i]);
      }
      cout << ans << endl;
    }
  }
  return 0;
}

// 下から見ていく

Submission status: Runtime Error

Solution code:
n = int(input())
leaves = list(map(int, input().split()))

ans = 0
nodes_min = [0] * (n + 1)
nodes_max = [0] * (n + 1)
nodes_min[n] = leaves[n]
nodes_max[n] = leaves[n]

for depth in range(n, 0, -1):
    root_min = nodes_min[depth] // 2 + nodes_min[depth] % 2
    nodes_min[depth - 1] = leaves[depth - 1] + root_min
    root_max = nodes_max[depth]
    nodes_max[depth - 1] = leaves[depth - 1] + root_max
nodes = [0] * (n + 1)
nodes[0] = 1
for depth in range(n):
    roots = nodes[depth]-leaves[depth]
    if nodes[depth] < nodes_min[depth]:
        print(-1)
        break
    nodes[depth + 1] = min(roots * 2, nodes_max[depth + 1])
else:
    if nodes[n] < nodes_min[depth]:
        print(-1)
    else:
        print(sum(nodes))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(sys.stdin.readline() for _ in range(n)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N = int(sys.stdin.readline())
LEAVES = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
ret = 0
t = 0
com = []
for l in LEAVES[::-1]:
    t = l + t
    com.append(t)
com.reverse()

def dfs(l=0,parentB=0,t=[]):
    global ret
    lo = parentB-LEAVES[l]
    hi = 2*parentB-LEAVES[l]
    if l == 0:
        lo = 0
        hi = 1
    if parentB > com[l] or 2*parentB-LEAVES[l] < 0:
        return False
    if l == N and lo <= 0 and 0 <= hi:
        t.append(LEAVES[l])
        ret = max(ret,sum(t))
        return ret
    elif l == N:
        return False
    for p in range(lo,hi+1)[::-1]:
        if dfs(l+1,p,t+[p+LEAVES[l]]):
            return True
    return False
dfs()
if ret==0:
    print(-1)
    exit()
print(ret)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(sys.stdin.readline() for _ in range(n)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N = int(sys.stdin.readline())
LEAVES = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
ret = 0
t = 0
com = []
for l in LEAVES[::-1]:
    t = l + t
    com.append(t)
com.reverse()

def dfs(l=0,parentB=0,t=[]):
    global ret
    lo = parentB-LEAVES[l]
    hi = 2*parentB-LEAVES[l]
    if l == 0:
        lo = 0
        hi = 1
    if parentB > com[l] or 2*parentB-LEAVES[l] < 0:
        return False
    if l == N and lo <= 0 and 0 <= hi:
        t.append(LEAVES[l])
        ret = max(ret,sum(t))
        #print(t,ret)
        return
    elif l == N:
        return
    for p in range(lo,hi+1)[::-1]:
        dfs(l+1,p,t+[p+LEAVES[l]])
dfs()
if ret==0:
    print(-1)
    exit()
print(ret)

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int,input().split()))

b = 1
B=[0]*(n+1)
count = 0
for i in range(n):
    B[i] = b
    if 2*(b - A[i]) < A[i+1]:
        count += 1
    b = 2*(b - A[i])

B[n] = b

j = 0
while A[n] > B[j]:
    j+=1
    if j == B[len(B)-1]:
        break

total = 0
for i in range(j):
    total += B[i]

s = A[n]
for i in range(n-1,j-1,-1):
    total += min(B[i],s+A[i])
    s+=A[i]

if count==0:
    print(total+A[n])
else:
    print('-1')