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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

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

A.reverse()
max_list = [A[0]]
before_top = A[0]
for i in range(1, len(A)):
    max_list.append(before_top + A[i])
    before_top = max_list[i]
    
A.reverse()
max_list.reverse()
ans = 1
before_top = 1
for i in range(1, len(A)):
    if A[i] <= before_top*2:
        ans += min(before_top*2, max_list[i])
        before_top = min(before_top*2, max_list[i]) - A[i]
    else:
        print(-1)
        exit()
        
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

if N == 0 and A[0] == 1:
    print(1)
    exit()

if A[0] != 0:
    print(-1)
    exit()
    
sum_leaf = sum(A)
ans = 1
before_top = 1
for i in range(1, len(A)):
    if A[i] <= before_top*2:
        ans += min(sum_leaf, before_top*2)
        before_top = min(sum_leaf, before_top*2) - A[i]
        sum_leaf -= A[i]
    else:
        print(-1)
        exit()

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N = INT()
A = LIST()

LR = [[A[-1], A[-1]]]
for i, b in enumerate(A[::-1][1:], 1):
	if N-i+1 < 30:
		LR.append([-(-LR[-1][0]//2)+b, min(LR[-1][1]+b, pow(2, N-i+1))])
	else:
		LR.append([-(-LR[-1][0]//2)+b, LR[-1][1]+b])


LR = LR[::-1]
if LR[0][0] <= 1 <= LR[0][1]:
	pass
else:
	print(-1)
	exit()

ans = 1
tmp = 1
for i, (L, R) in enumerate(LR[1:], 1):
	tmp = min(2*tmp-A[i], R-A[i])
	ans += tmp+A[i]

print(ans)

Solution (Python):

import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

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

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

rcA = [0] * (N)
rcA[-1] = A[-1]
for i in range(1, N):
    rcA[-i - 1] = rcA[-i] + A[-i - 1]


cnt = 1
node = 1
for a, rca in zip(A, rcA):
    min_node = node - a
    max_node = 2 * (node - a)
    if rca < min_node or min_node < 0:
        print(-1)
        exit()
    node = min(max_node, rca)
    
    cnt += node
if node != A[-1]:
    print(-1)
    exit()
print(cnt)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop, heapify
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N = INT()
A = LIST()

LR = [[A[-1], A[-1]]]
for b in A[::-1][1:]:
	LR.append([-(-LR[-1][0]//2)+b, LR[-1][1]+b])

LR = LR[::-1]
if LR[0][0] <= 1 <= LR[0][1]:
	pass
else:
	print(-1)
	exit()

ans = 1
tmp = 1
for i, (L, R) in enumerate(LR[1:], 1):
	tmp = min(2*tmp-A[i], R-A[i])
	ans += tmp+A[i]

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
d=1
mx=[]
for i in range(n+1):
  d-=a[i]
  mx.append(d)
  d*=2

mx.append(1)
f=mx[n]>=0
d=0
c=0
for i in range(n,-1,-1):
  d+=a[i]
  c+=d
  t=(d+1)//2
  if t>mx[i-1]:
    f=False
    break
  d=min(d,mx[i-1])
print(c if f else -1)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    A = list(map(int,input().split())) 
    B = [0] * (n + 1)   
    sum_A = sum(A[1:]) 

    B[0] = 1 - A[0]
    if sum_A == 0:
        if B[0] == 0:
            print(1)
        else:
            print(-1)
        sys.exit()
    ans = 1
    for i in range(1, n + 1):
        sum_A -= A[i]
        max_b = min(2*B[i-1] - A[i], sum_A)
        if max_b + A[i] < B[i-1] or max_b < 0:
            print(-1)
            sys.exit()
        else:
            B[i] = max_b
        ans += A[i] + max_b

    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    A = list(map(int,input().split())) 
    B = [0] * (n + 1)   
    sum_A = sum(A[1:]) 

    B[0] = 1 - A[0]
    if sum_A == 0:
        if B[0] == 0:
            print(1)
        else:
            print(-1)
        sys.exit()
    ans = 1
    for i in range(1, n + 1):
        sum_A -= A[i]
        max_b = min(2*B[i-1] - A[i], sum_A)
        if max_b + A[i] < B[i-1] or max_b < 0:
            print(-1)
            sys.exit()
        else:
            B[i] = max_b
        ans += A[i] + max_b

    print(ans)

if __name__=='__main__':
    main()

Solution (Python):
def solve():
    if N == 0:
        if A[0] == 1:
            return 1
        else:
            return -1

    if A[0] != 0:
        return -1

    tot = sum(A)
    cur = 1
    ans = 1
    for i in range(1, N + 1):
        cur *= 2
        if cur < A[i]:
            return -1
        tmp = min(cur, tot)
        ans += tmp
        cur = tmp - A[i]
        tot -= A[i]
    return ans


N, *A = map(int, open(0).read().split())
print(solve())

Solution (Python):


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int();
    A = read_ints();
    B = [0]*(N+1)
    B[N] = A[N]
    for i in range(N-1, -1, -1):
        B[i] = B[i+1]+A[i]
    nodes, answer = 1, 0
    for i in range(N+1):
        if nodes < A[i]:
            return -1
        answer += nodes
        nodes -= A[i]
        if i<N:
            nodes = min(2*nodes, B[i+1])
    return answer


if __name__ == '__main__':
    print(solve())

Solution (Python):
N = int(input())
As = list(map(int,input().split()))

if(N == 0):
    if(As[0] == 1):
        print(1)
    else:
        print(-1)
else:
    flag = True
    if(As[0] != 0):
        flag = False
    if(flag):
        D = [[0]*3 for i in range(N+1)]
        D[0] = [1,1,0] 
        for i in range(1,N+1):
            if(As[i] > 2*D[i-1][1]):
                flag = False
                break
            else:
                D[i][0] = max(0,D[i-1][0] - As[i])
                D[i][1] = min(2*D[i-1][1] - As[i],1 << i)
                D[i][2] = As[i]
    if(flag):
        D[N][1] = 0
        maxcnt = 0
        for i in range(N,-1,-1):
            depthmax = D[i][1] + D[i][2]
            maxcnt += depthmax
            if(i > 0):
                D[i-1][1] = min(D[i-1][1],depthmax)
        print(maxcnt)
    else:
        print(-1)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = []
    now = 1
    ans = 0
    for i in range(n+1):
        if a[i] > now:
            print(-1)
            return
        else:
            dp.append(now)
            now -= a[i]
            now *= 2
    now = 0
    for i in range(n, -1, -1):
        now += a[i]
        ans += min(now, dp[i])
    print(ans)


main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
if a[0] >= 1 or n == 0:
    print(1 if a[0] == 1 and n == 0 else -1)
    exit()
b = [0] * (n + 1)
for i in range(1, n + 1):
    b[i] = a[i] + b[i - 1]
v = 1
ans = 1
for i in range(n):
    v = min(b[n] - b[i], 2 * (v - a[i]))
    if v < a[i + 1]:
        print(-1)
        exit()
    ans += v
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

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

X = [0] * (N+1)
X[-1] = A[-1]
for i in range(N,0,-1):
  X[i-1] = X[i] + A[i-1]
  


wk = 2
ans = 1
for i in range(1,N+1):
  
  
  if 0 <= A[i] <= wk:
    ans += min(wk,X[i])
    wk -= A[i]
    wk *= 2
  else:
    print(-1)
    exit(0)
  
print(ans)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int,input().split()))
    ki = [0 for i in range(n+1)]
    ki[0] = 1   
    for i in range(1,n+1):
        ki[i] = 2*(ki[i-1] - a[i-1])
        if ki[i]<=0:
            print(-1)
            return
    if ki[-1]<a[-1]:
        print(-1)
        return
    ki[-1] = a[-1]
    for i in range(n):
        ki[n-1-i] = min(ki[n-1-i],ki[n-i]+a[n-1-i])
    print(sum(ki))

if __name__ == "__main__":
    main()

Solution (Python):


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

if A[0]==1:
    if N==0:
        pass
    else:
        print(-1)
        exit()
elif A[0]>1:
    print(-1)
    exit()

limit=[1]

for a in A[1:]:
    limit.append(limit[-1]*2-a)

A=A[::-1]
limit=limit[::-1]

ans=A[0]
temp=A[0]


for i in range(len(limit)-1):
    a=limit[i+1]
    b=temp
    x=b-a
    y=a-x
    
    if x<0:
        x=0
        y=temp
    elif y<0:
        print(-1)
        exit()
    
    temp=x+y+A[i+1]
    ans+=temp
        

print(ans)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    all_v = sum(a)
    ans = 0
    if n == 0:
        if a[0] == 1:
            ans = 1
        else:
            ans = -1
    elif a[0] != 0:
        ans = -1
    else:
        ans = 1
        max_vertex = 1
        for i in range(1, n + 1):
            max_vertex *= 2
            if max_vertex < a[i]:
                ans = -1
                break
            ans += min(max_vertex, all_v)
            max_vertex = min(max_vertex, all_v) - a[i]
            all_v -= a[i]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if n==0 and a[0]!=1:
  print(-1)
  exit()
b=[a[0]==0]
for i in a[1:]:
  b+=[2*b[-1]-i]
  if b[-1]<0:
    print(-1)
    exit()
b.pop()
ans=root=a[-1]
a=a[::-1]
b=b[::-1]
for i,j in zip(a[1:],b):
  root=min(root,j)+i
  ans+=root
print(ans)

Solution (Python):
n=int(input()) ; n+=1
A=list(map(int,input().split()))
if n==1:
    if A[0]==1: print(1);exit()
    print(-1);exit()
if A[0]!=0:print(-1);exit()
ANS=[0]*n ;ANS[0]=1
R=[0]*n
for i in range(n-2,-1,-1):
    R[i]=R[i+1]+A[i+1]

for i in range(1,n):
    ANS[i]=min(ANS[i-1]*2-A[i], R[i])
    if ANS[i]<0:print(-1);exit()
print(sum(A)+sum(ANS))

Solution (Python):
import sys
import operator
from typing import Iterable, Tuple, Union

Shape = Union[int, Tuple[int, ...], Iterable[int]]
RangeShape = Union[slice, Tuple[slice, ...]]
Indices = Union[int, Tuple[int, ...]]

class nd (object):
    getter = (
        lambda a, i: a,
        lambda a, i: a[i[0]],
        lambda a, i: a[i[0]][i[1]],
        lambda a, i: a[i[0]][i[1]][i[2]],
        lambda a, i: a[i[0]][i[1]][i[2]][i[3]],
        lambda a, i: a[i[0]][i[1]][i[2]][i[3]][i[4]],
        lambda a, i: a[i[0]][i[1]][i[2]][i[3]][i[4]][i[5]],
    )

    class _setter (object):
        def __getitem__(self, n: int):
            setter_getter = nd.getter[n - 1]

            def setter(a, i, v):
                setter_getter(a, i[:-1])[i[-1]] = v
            return setter
    setter = _setter()
    initializer = (
        lambda s, v: [v] * s,
        lambda s, v: [v] * s[0],
        lambda s, v: [[v] * s[1] for _ in range(s[0])],
        lambda s, v: [[[v] * s[2] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, v: [[[[v] * s[3] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, v: [[[[[v] * s[4] for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, v: [[[[[[v] * s[5] for _ in range(s[4])] for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
    )
    func_initializer = (
        lambda s, f: [f() for _ in range(s)],
        lambda s, f: [f() for _ in range(s[0])],
        lambda s, f: [[f() for _ in range(s[1])] for _ in range(s[0])],
        lambda s, f: [[[f() for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, f: [[[[f() for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, f: [[[[[f() for _ in range(s[4])] for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
        lambda s, f: [[[[[[f() for _ in range(s[5])] for _ in range(s[4])] for _ in range(s[3])] for _ in range(s[2])] for _ in range(s[1])] for _ in range(s[0])],
    )
    shape_getter = (
        lambda a: len(a),
        lambda a: (len(a),),
        lambda a: (len(a), len(a[0])),
        lambda a: (len(a), len(a[0]), len(a[0][0])),
        lambda a: (len(a), len(a[0]), len(a[0][0]), len(a[0][0][0])),
        lambda a: (len(a), len(a[0]), len(a[0][0]), len(a[0][0][0]), len(a[0][0][0][0])),
        lambda a: (len(a), len(a[0]), len(a[0][0]), len(a[0][0][0]), len(a[0][0][0][0]), len(a[0][0][0][0][0])),
    )
    indices_iterator = (
        lambda s: iter(range(s)),
        lambda s: ((i,) for i in range(s[0])),
        lambda s: ((i, j) for j in range(s[1]) for i in range(s[0])),
        lambda s: ((i, j, k) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
        lambda s: ((i, j, k, l) for l in range(s[3]) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
        lambda s: ((i, j, k, l, m) for m in range(s[4]) for l in range(s[3]) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
        lambda s: ((i, j, k, l, m, n) for n in range(s[5]) for m in range(s[4]) for l in range(s[3]) for k in range(s[2]) for j in range(s[1]) for i in range(s[0])),
    )
    iterable_product = (
        lambda s: iter(s),
        lambda s: ((i,) for i in s[0]),
        lambda s: ((i, j) for j in s[1] for i in s[0]),
        lambda s: ((i, j, k) for k in s[2] for j in s[1] for i in s[0]),
        lambda s: ((i, j, k, l) for l in s[3] for k in s[2] for j in s[1] for i in s[0]),
        lambda s: ((i, j, k, l, m) for m in s[4] for l in s[3] for k in s[2] for j in s[1] for i in s[0]),
        lambda s: ((i, j, k, l, m, n) for n in s[5] for m in s[4] for l in s[3] for k in s[2] for j in s[1] for i in s[0]),
    )
    flattener = (
        lambda a: iter(a),
        lambda a: iter(a),
        lambda a: (y for z in a for y in z),
        lambda a: (x for z in a for y in z for x in y),
        lambda a: (w for z in a for y in z for x in y for w in x),
        lambda a: (v for z in a for y in z for x in y for w in x for v in w),
        lambda a: (u for z in a for y in z for x in y for w in x for v in w for u in v),
    )

    @classmethod
    def full(cls, fill_value, shape: Shape):
        if isinstance(shape, int):
            return cls.initializer[0](shape, fill_value)
        elif not isinstance(shape, tuple):
            shape = tuple(shape)
        return cls.initializer[len(shape)](shape, fill_value)

    @classmethod
    def nones(cls, shape: Shape):
        return cls.full(None, shape)

    @classmethod
    def zeros(cls, shape: Shape, type=int):
        return cls.full(type(0), shape)

    @classmethod
    def ones(cls, shape: Shape, type=int):
        return cls.full(type(1), shape)

    @classmethod
    def fromiter(cls, iterable: Iterable, ndim=1):
        if ndim == 1:
            return list(iterable)
        else:
            return list(map(cls.fromiter, iterable))

    class _range (object):
        def __getitem__(self, shape: RangeShape):
            if isinstance(shape, slice):
                return iter(range(shape.stop)[shape.start:][::shape.step])
            else:
                shape = tuple(range(s.stop)[s.start:][::s.step] for s in shape)
                return nd.iterable_product[len(shape)](shape)
    range = _range()

    @classmethod
    def ensure_shape_tuple(cls, shape: Shape):
        if isinstance(shape, int):
            return shape,
        elif not isinstance(shape, tuple):
            return tuple(shape)
        else:
            return shape

    @classmethod
    def ensure_indices_tuple(cls, indices: Indices):
        if isinstance(indices, int):
            return indices,
        else:
            return indices

    @classmethod
    def join_shapes(cls, *shapes: Shape):
        return tuple(map(cls.ensure_shape_tuple, shapes))

def bytes_to_str(x: bytes):
    return x.decode('utf-8')

def inputs(func=bytes_to_str, sep=None, maxsplit=-1):
    return map(func, sys.stdin.buffer.readline().split(sep=sep, maxsplit=maxsplit))

def inputs_1d(func=bytes_to_str, **kwargs):
    return nd.fromiter(inputs(func, **kwargs))

def inputs_2d(nrows: int, func=bytes_to_str, **kwargs):
    return nd.fromiter(
        (inputs(func, **kwargs) for _ in range(nrows)),
        ndim=2
    )

def inputs_2d_T(nrows: int, func=bytes_to_str, **kwargs):
    return nd.fromiter(
        zip(*(inputs(func, **kwargs) for _ in range(nrows))),
        ndim=2
    )

N, = inputs(int)
A = inputs_1d(int)
cum_A = nd.zeros(N + 1, int)
cum_A[0] = A[0]
for i in nd.range[1:N + 1]:
    cum_A[i] = cum_A[i - 1] + A[i]

B = nd.zeros(N + 1, int)
B[0] = 1

constructable = True

for d in nd.range[:N]:
    if B[d] < A[d]:
        constructable = False
        break
    B[d] = B[d] - A[d]
    B[d + 1] = min(B[d] * 2, cum_A[N] - cum_A[d])

if constructable:
    if A[N] != B[N]:
        constructable = False
        print(-1)
    else:
        B[N] = 0
        print(sum(A) + sum(B))
else:
    print(-1)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

cons = []
cur = 0
mn, mx = 0, 0
for i in range(N, -1, -1):
    mn = ((mn + 1) // 2) + A[i]
    mx = mx + A[i]
    if mn > 2 ** i:
        print(-1)
        exit()
    cons.append((mn, mx))
cons = list(reversed(cons))
ans = 0
cnt_node = 1
for i in range(N + 1):
    mn, mx = cons[i]
    now = min(mx, cnt_node)
    ans += now
    cnt_node = (now - A[i]) * 2
print(ans)

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

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


non_leaf_node = []
tmp = 1
for i in range(0,N+1):
    tmp = tmp -A[i]
    if tmp < 0:
        print(-1)
        exit()
    non_leaf_node.append(tmp)
    tmp *= 2
non_leaf_node[-1]=0




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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

ans = 0
nonleaf_nodes = []
current = 1


for depth in range(0, n+1):
    c = current-a[depth]
    
    if c < 0:
        print(-1)
        exit()
    nonleaf_nodes.append(c)
    current = c*2
nonleaf_nodes[-1]=0



ans = a[-1]
for depth in range(n-1, -1, -1):
    nonleaf_nodes[depth] = min(nonleaf_nodes[depth], nonleaf_nodes[depth+1]+a[depth+1])
    ans += nonleaf_nodes[depth] + a[depth]
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

ans = 0
nonleaf_nodes = []
current = 1

for depth in range(0, n+1):
    c = current-a[depth]
    if c < 0: 
        print(-1)
        exit()
    nonleaf_nodes.append(c)
    current = c*2
nonleaf_nodes[-1]=0

ans = a[-1]
for depth in range(n-1, -1, -1):
    nonleaf_nodes[depth] = min(nonleaf_nodes[depth], nonleaf_nodes[depth+1]+a[depth+1])
    ans += nonleaf_nodes[depth] + a[depth]
print(ans)

Solution (Python):

N = int(input())
X = list(map(int, input().split()))

cnt = [0] * (N + 1)
cnt[0] = 1
for i in range(N):
    cnt[i + 1] = (cnt[i] - X[i]) * 2

ans = 0
cur = 0
for i in reversed(range(N + 1)):
    cur += X[i]
    ans += min(cnt[i], cur)

if all(cnt[i] >= X[i] for i in range(N + 1)):
    print(ans)
else:
    print(-1)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))+[0]
b=[0]*(n+1)
b[0]=1-a[0]
r=sum(a)-a[0]-a[1]
for i in range(1,n+1):
    b[i]=min(r,b[i-1]*2-a[i])
    r-=a[i+1]
if any(i<0 for i in b):print(-1)
else:print(sum(a)+sum(b))

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]

L, R = [A[-1]], [A[-1]]
for i in range(1, N+1):
    L.append((L[-1]+1)//2+A[-1-i])
    R.append((R[-1]+A[-1-i]))
L = L[::-1]
R = R[::-1]

if L[0] >= 2:
    print(-1)
    exit()

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

Solution (Python):
def main():
    import sys

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

    n = int(input())
    a = list(map(int, input().split()))
    s = [0]
    for i in range(n+1):
        s.append(s[-1]+a[~i])
    s.reverse()
    max_nodes = 1
    ans = 0
    for i in range(n+1):
        if a[i] > max_nodes:
            print(-1)
            return
        ans += min(max_nodes, s[i])
        max_nodes -= a[i]
        max_nodes *= 2

    print(ans)
        
    
    
if __name__ == '__main__':
    main()

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue


Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
def pow_k(x, n):

    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x
def main():  
    n = int(input())
    a = list(map(int, input().split()))
    accum = sum(a)
    ans = 1
    b = [0] * (n + 1)
    b[0] = 1
    for i in range(1, n + 1):
        accum -= a[i]
        b[i] = min(2 * b[i - 1] - a[i], accum)
        if b[i] < 0:
            ans = -1
            break
        ans += b[i] + a[i]
    if a[0] == 1:
        ans = -1
    if n == 0:
        if a[0] == 1:
            ans = 1
        else:
            ans = -1
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):



def main():
    N = int(input())
    A = list(map(int, input().split()))
    leaf = sum(A)
    M = [0]*(N+1)
    if N==0:
        if A[0]==1:
            print(1)
            exit()
        else:
            print(-1)
            exit()
    if A[0]==1:
        print(-1)
        exit()
    M[0] = 1
    for i in range(1,N+1):
        M[i] = 2*M[i-1] - A[i]
        leaf -= A[i]
        M[i] = min(M[i],leaf)
        if M[i] < 0:
            print(-1)
            exit()
    print(sum(M)+sum(A))
    
if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
leaf = sum(a) - 1
now = 1
ans = 0
for i, num in enumerate(a):
    ans += now
    now -= num
    if leaf >= now:
        leaf -= now
        now *= 2
    elif leaf > 0:
        now += leaf
        leaf = 0
    if now < 0:
        print(-1)
        exit()
print(ans)

Solution (Python):
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''　標準入力
1行のint=====================================
N, K = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
A = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''


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

B = A.copy()
B.reverse()

upper = [0] * (N+1)
upper[0] = B[0]
for i in range(N):
    upper[i + 1] = upper[i] + B[i+1]
upper.reverse()

V = [0] * (N+1)
if A[0] == 1:
    if N >= 1:
        print(-1)
        sys.exit()
    elif N == 0:
        print(1)
        sys.exit()

if A[0] > 1:
    print(-1)
    sys.exit()

V[0] = 1
for d in range(1, N + 1):
    can = min((V[d-1] - A[d-1]) * 2, upper[d])
    least = V[d-1] - A[d-1]

    if A[d] > can or least > can:
        print(-1)
        sys.exit()

    V[d] = can

V[N] = A[N]

ans = 0
for v in V:
    ans += v

print(ans)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



import bisect
n=int(input())
a=list(map(int,input().split()))
b_d=[[0,0] for _ in range(n+1)]
b_u=[[0,0] for _ in range(n+1)]
b_d[n]=[a[n],a[n]]
b_u[0]=[1,1]
for i in range(1,n+1):
    l=(1+b_d[n+1-i][0])//2+a[n-i]
    r=(b_d[n+1-i][1])+a[n-i]
    if l>r:
        print(-1)
        exit()
        break
    b_d[n-i]=[l,r]
    l=max(0,b_u[i-1][0]-a[i-1])
    r=2*(b_u[i-1][1]-a[i-1])
    if l>r:
        print(-1)
        exit()
        break
    b_u[i]=[l,r]
ans=0

for i in range(n+1):
    if b_d[i][0]>b_u[i][1] or b_u[i][0]>b_d[i][1]:
        print(-1)
        exit()
    else:
        ans+=min(b_u[i][1],b_d[i][1])
print(ans)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



import bisect
n=int(input())
a=list(map(int,input().split()))
b_d=[[0,0] for _ in range(n+1)]
b_u=[[0,0] for _ in range(n+1)]
b_d[n]=[a[n],a[n]]
b_u[0]=[1,1]
for i in range(1,n+1):
    l=(1+b_d[n+1-i][0])//2+a[n-i]
    r=(b_d[n+1-i][1])+a[n-i]
    if l>r:
        print(-1)
        exit()
        break
    b_d[n-i]=[l,r]
    l=max(0,b_u[i-1][0]-a[i-1])
    r=2*(b_u[i-1][1]-a[i-1])
    if l>r:
        print(-1)
        exit()
        break
    b_u[i]=[l,r]
ans=0

for i in range(n+1):
    if b_d[i][0]>b_u[i][1] or b_u[i][0]>b_d[i][1]:
        print(-1)
        exit()
    else:
        ans+=min(b_u[i][1],b_d[i][1])
print(ans)

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

L = [0]*(n+2)
R = [0]*(n+2)
L[n] = A[n]
R[n] = A[n]

for i in range(n,-1,-1):
  L[i] = A[i] + (L[i+1]+1)//2
  R[i] = A[i] + R[i+1]
  
if L[0]>1:
  print(-1)
else:
  tmp = 1
  ans = 0
  for i in range(n+1):
    ans += tmp
    tmp -= A[i]
    tmp = min(tmp*2,R[i+1])    
  print(ans)

Solution (Python):
from itertools import accumulate

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


cA = list(accumulate(A[::-1]))[::-1]

if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
if A[0]:
    print(-1)
    exit()


B = [1]
P = 1

for i in range(N):
    
    if B[i] * 2 < A[i + 1]:
        print(-1)
        exit()
    P += min(2 * B[i], cA[i + 1])
    
    B.append(min(2 * B[i], cA[i + 1]) - A[i + 1])
    if B[-1] < 0:
        print(-1)
        exit()

print(P)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
flg = True
n_node = 0.5
ans = 0
As = [0]*(N+2)
for i in range(N, -1, -1):
    As[i] = As[i+1] + A[i]
for i in range(N+1):
    if A[i] > n_node*2:
        flg = False
        break
    n_node = min(int(n_node*2)-A[i], As[i+1])
    ans += n_node + A[i]
print(ans if flg else -1)

Solution (Python):
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
if A[0] != 0:
    if N == 0 and A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
ans = 1
n = 1
if A[0] > 1:
    print(-1)
    exit()
cumr = list(itertools.accumulate(A[::-1]))[::-1]
for i in range(1, N + 1):
    minn = n - A[i - 1]
    n = min(2 * minn, cumr[i])
    if n>=minn and n>=A[i]:
        ans += n
    else:
        print(-1)
        exit()
print(ans)