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):
from itertools import accumulate

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

if n == 0:
    print(1 if a[0] == 1 else - 1)
    exit()

if a[0] != 0:
    print(-1)
    exit()

b = list(accumulate(a))
v = 1
cnt = 1
for i in range(n):
    if (v - a[i]) * 2 - a[i + 1] < 0:
        print(-1)
        exit()
    v = min((v - a[i]) * 2, b[-1] - b[i])
    cnt += v
print(cnt)

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    a = list(map(int, input().split()))
    maxnum = [0] * (n + 1)
    num = [0] * (n + 1)
    maxnum[0] = 1
    num[0] = 1
    if n > 0:
        num[-1] = a[-1]

    if n == 0 and a[0] == 1:
        print(1)
    elif n == 0 and a[0] == 0:
        print(-1)
    elif n == 0 and a[0] > 1:
        print(-1)
    elif n >= 1 and a[0] > 0:
        print(-1)
    elif n == 1 and a[1] == 1:
        print(2)
    elif n == 1 and a[1] == 2:
        print(3)
    else:
        for i1 in range(1, n + 1):
            if maxnum[i1-1] * 2 < a[i1]:
                print(-1)
                sys.exit()
            else:
                maxnum[i1] = maxnum[i1-1] * 2 - a[i1]

        for j1 in range(n-1, 0, -1):
            numt = a[j1] + min(num[j1 + 1], maxnum[j1-1]*2 - a[j1])
            num[j1] = numt
        r = sum(num)
        print(r)

if __name__ == '__main__':
    main()

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

s=0
cap=[]
flag=False
for i,a in enumerate(A):
    s*=2
    s+=a
    cap.append(min(2**i-s,(n+1-i)*10**8))
    if s>2**i:
        flag=True
        break

if flag:
    print(-1)
else:
    remain=2**n-s
    ans=0
    node=0
    for i in range(n,-1,-1):
        a=A[i]
        c=cap[i]
        node=min(c,node)+a
        ans+=node
    print(ans)

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

rng = [[A[N], A[N]]]

for i in range(N - 1, -1, -1):
    merged = (rng[-1][0] + 1) // 2 + A[i]
    nonmerged = rng[-1][1] + A[i]
    rng.append([merged, nonmerged])
if rng[-1][0] > 1:
    print(-1)
    exit()
rng.reverse()
prev_non_leaf = 1
ans = 1
for i in range(1, N + 1):
    l, u = rng[i]
    ans += min(prev_non_leaf * 2, u)
    prev_non_leaf = prev_non_leaf * 2 - A[i]
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
sa = sum(A)
last = A[-1]
count = last
root = 1
for i in range(N):
  sa -= A[i]
  if root <= A[i]:
    print(-1)
    break
  elif root-A[i] > sa:
    root = sa + A[i]
  count+=root
  root = (root-A[i])*2
else:
  if count == 0 or root < last:
    count = -1
  print(count)

Solution (Python):

import sys
readline = sys.stdin.readline

N = int(readline())
A = list(int(x) for x in readline().split())

leaf = sum(A)
tmp = 1
ans = 0
for a in A:
    if tmp < a:
        ans = -1
        break
    ans += min(tmp, leaf)
    leaf -= a
    tmp -= a
    tmp *= 2

print(int(ans))

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

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1
laS = [0 for i in range(N+1)]
laS[-1] = A[-1]

for i in range(N):
    laS[-2-i] = A[-2-i] + laS[-1-i]
    nodeS[i+1] = (nodeS[i]-A[i])*2

for i in range(N+1):
    if nodeS[i] <= 0:
        print(-1)
        exit()

for i in range(N+1):
    if nodeS[i] >= laS[i]:
        break
    if i == N:
        print(-1)
        exit()

print(sum(nodeS[:i]) + sum(laS[i:]))

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

b = [1]
f = True
for i in range(n+1):
    sa -= a[i]
    d = min(sa, (b[i] - a[i]) * 2)
    if d < 0:
        f = False
        break
    b.append(d)

print(sum(b) if f else -1)

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

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1
laS = [0 for i in range(N+1)]
laS[-1] = A[-1]

for i in range(N):
    laS[-2-i] = A[-2-i] + laS[-1-i]
    nodeS[i+1] = min(10**18,(nodeS[i]-A[i])*2)

for i in range(N+1):
    if nodeS[i] <= 0:
        print(-1)
        exit()

for i in range(N+1):
    if nodeS[i] >= laS[i]:
        break
    if i == N:
        print(-1)
        exit()

print(sum(nodeS[:i]) + sum(laS[i:]))

Solution (Python):
import sys

input = sys.stdin.buffer.readline

n = int(input())

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

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

ans = 0
max2 = 0
kouho = [0] * (n + 1)
for i in range(n, 0, -1):
    max1 = pow(2, i)
    max2 += A[i]
    max2 = min(max1, max2)
    kouho[i] = max2
kouho[0] = 1
not_leave = 1
for i in range(1, n + 1):
    cnt = 0
    not_leave *= 2
    temp = min(kouho[i], not_leave)
    ans += temp
    not_leave -= A[i]
    if not_leave <= 0 and i != n:
        print(-1)
        exit()
    if i == n:
        if not_leave == 0:
            continue
        elif not_leave < 0:
            print(-1)
            exit()
ans += 1
print(ans)

Solution (Python):
import sys
n=int(input())
a=input()
a=[int(s)for s in a.split()]
M=1
Q=1
m=sum(a)
if a[0]>=1:
    if a[0]==1 and n==0:
        print(1)
        sys.exit()
    else:    
        print(-1)
        sys.exit()
for i in range(n):
    M=2*M-a[i+1]
    if M<0:
        print(-1)
        sys.exit()
    M1=M+a[i+1]
    m=m-a[i]
    Q=Q+min(M1,m)
print(Q)

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
if n == 0:
  if A[0] == 1:
    print(1)
  else:
    print(-1)
  exit()
C = list(accumulate(A[::-1]))[::-1] + [0]
B = [-1]*(n+1)
B[0] = 1 - A[0]
for i in range(1, n+1):
  B[i] = min(C[i+1], 2*B[i-1]-A[i])
  if B[i] < 0 or B[i] < B[i-1] - A[i]:
    print(-1)
    exit()
ans = sum(A) + sum(B)
print(ans)

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

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


sumA = sum(A_list)
node = 1
count = 1
for i in range(len(A_list) - 1):
    temp = min([node * 2, sumA])
    count += temp
    node = temp - A_list[i + 1]

    if node < 0:
        print(-1)
        exit()

    sumA -= A_list[i + 1]

print(count)

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

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


MAX = 10 ** 18
lst = [1] * (10 ** 5 + 10)


for i in range(N + 1):
    lst[i + 1] = min(MAX, lst[i] * 2)


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



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


ans = 1
tmp = 0
for i in range(N, 0, -1):
    ans += lst[i]
    lst[i - 1] = min(lst[i] + A[i - 1], lst[i - 1])


print (ans)

Solution (Python):

N=int(input())
A=list(map(int,input().split()))
sum_value = sum(A)
chiled_value = 1
top_value = 1
if(N==0 and A[0]==1):
    print(1)
    exit()
if(A[0]!=0):
    print(-1)
    exit()
for i in range(1,N):
    if(sum_value >= chiled_value*2):
        top_value += chiled_value*2
        chiled_value = chiled_value*2-A[i]
        sum_value=sum_value-A[i]
        if(A[i+1]>chiled_value*2):
            print(-1)
            exit()
    elif(sum_value < chiled_value*2):
        chiled_value=sum_value
        top_value += chiled_value
        sum_value=sum_value-A[i]
    if(A[i]>=2**i):
        print(-1)
        exit()
if((sum_value-A[N])!=0):
    print(-1)
    exit()
print(top_value+A[N])

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
node = [0 for i in range(n+1)]
if n == 0:
    if a[0] != 1:
        print(-1)
        exit()
    else:
        print(1)
        exit()
if a[0] != 0:
    print(-1)
    exit()
node[0] = 1
count = 1
for i in range(1,n+1):
    count = min(count * 2, 10**18)
    if a[i] > count:
        print(-1)
        exit()
    node[i] = node[i-1] - a[i-1]
    node[i] *= 2
if node[-1] < a[-1]:
    print(-1)
    exit()
node[-1] = a[-1]
for i in range(n-1, -1, -1):
    if a[i] > node[i]:
        print(-1)
        exit()
    node[i] = min(node[i], node[i+1] + a[i])
print(sum(node))

Solution (Python):


def main():
    N = int(input())
    *A, = map(int, input().split())

    mis = [0]
    mas = [0]
    for x in reversed(A):
        mis.append((mis[-1] + 1) // 2 + x)
        mas.append(mas[-1] + x)

    if not (mis[-1] <= 1 <= mas[-1]):
        print(-1)
        return

    mas.reverse()

    ans = [1]
    for i, x in enumerate(A, start=1):
        ans.append(min(mas[i], (ans[-1] - x) * 2))

    print(sum(ans))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]





N = ii()
A = li()

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

max_a = [0] * (N+1)
max_a[0] = 1 - A[0]

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

cnt_list = [0]*(N)
cnt_list[-1] = min(A[-1], max_a[N-1])

for i in reversed(range(N-1)):
    if cnt_list[i+1] + A[i+1] <= max_a[i]:
        cnt_list[i] = cnt_list[i+1] + A[i+1]
    else:
        cnt_list[i] = max_a[i]

cnt = sum(cnt_list[:N+1]) + sum(A)

print(cnt)

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

SUM = sum(A)
ans = 0

for i in range(N+1):
    SUM -= A[i]
    if i == 0:
        res = min(1 - A[0], SUM)
    else:
        res = min(2*B-A[i], SUM)
    if res < 0:
        ans = -1
        break
    ans = ans + res + A[i] 
    B = res
    
print(ans)

Solution (Python):
import math

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

end_flag = False
count = sum(leaf)
ans = 0
node = 1

for i in range(N+1):
    if end_flag:
        break
    ans += node
    count -= leaf[i]
    node = min(count, (node-leaf[i])*2)

    if node < 0:
        end_flag = True

if end_flag:
    print('-1')
else:
    print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
 
P=[0]*(N+1)
P[N]=A[N]
Q=[0]*(N+1)
Q[N]=A[N]
 
for i in range(N,0,-1):
    mxp=P[i]+A[i-1]
    mnp=(P[i]//2) + (P[i]%2) +A[i-1]
    mxq=Q[i]+A[i-1]
    mnq=(Q[i]//2) + (Q[i]%2) +A[i-1]
    P[i-1]=mnp
    Q[i-1]=min(mxq,2**i)
 
if P[0]!=1:
    print(-1)
    exit()
 
Q[0]=1
 
for i in range(1,N):
    if Q[i]>2**i:
        Q[i]=2**i
    if Q[i]>(Q[i-1]-A[i-1])*2:
        Q[i]=(Q[i-1]-A[i-1])*2
 
print(sum(Q))

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

pm = sum(a)
e = 1
te = 1
for i in a:
    pm -= i
    e = min((e-i)*2, pm)
    if e < 0:
        break
    te += e
if e < 0:
    print(-1)
else:
    print(te)

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

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

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N  = I()
A = LI()
sum = [0]*(N+2)
sum[N] = A[N]
for i in range(N-1,-1,-1):
    sum[i] = sum[i+1]+A[i]

if N==0:
    if A[0]==1:
        print(1)
    else:
        print(-1)
else:
    if A[0]!=0:
        print(-1)
    else:
        ans = 1
        b = 1
        for i in range(1,N+1):
            a = A[i]
            b_ = sum[i+1]
            if b_<b-a or 2*b-a<0:
                print(-1)
                break
            b_ = min(b_, 2*b-a)
            ans += a+b_
            b = b_
        else:
            print(ans)

Solution (Python):
n = int(input())
 
a = list(map(int,input().split()))
 
cumsum_a = a.copy()
 
for i in range(n-1, -1, -1):
    cumsum_a[i] += cumsum_a[i+1]
 
ans = 0
node = 1
 
for i in range(n + 1):
    if a[i] > node:
        ans = -1
        break
 
    ans += node
 
    if i < n:
        node = min(2 * (node - a[i]), cumsum_a[i + 1])
 
print(ans)

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

A_sum = sum(A)
cnt = 1
tmp = 1

for a in A:
    A_sum -= a
    tmp = min((tmp - a) * 2, A_sum)
    cnt += tmp
    if tmp < 0:
        break

if tmp < 0:
    print(-1)
else:
    print(cnt)

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

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

    bound = [0] * (N+1)
    bound[0] = 1
    flag = True

    for i in range(1, N+1):
        bound[i] = (bound[i-1] - A[i-1]) * 2
        if bound[i] < A[i]:
            flag = False

    if not flag:
        print(-1)
        exit()

    B = [0] * (N+2)
    for i in range(N, -1, -1):
        tmp = min(bound[i], B[i+1] + A[i])
        B[i] = tmp

    print(sum(B))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    res = 0
    not_leaf = 1
    s = sum(A)
    count = 1
    for d in range(n + 1):
        res += not_leaf
        if not_leaf < A[d]:
            print(-1)
            return
        not_leaf -= A[d]
        add = min(s - count, not_leaf)
        count += add
        not_leaf += add

    print(res if not_leaf == 0 else -1)
resolve()

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

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

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


corr_flag = 1
if A[-1] > capacity[-1]:
    corr_flag = 0
curr = A[-1]
ans = A[-1]
for i in range(N-1, -1, -1):
    curr = min(capacity[i], A[i] + curr)
    ans += curr
if corr_flag:
    print(ans)
else:
    print(-1)

Solution (Python):

N = int(input())

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


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


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


ans = [A[-1]]
now_leaf = A[-1]  
for i in range(N-1, -1, -1):
    
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]

for i in range(N):
    
    if (ans[N-i]-A[i])*2 < A[i+1]:  
        print(-1)
        exit()
print(sum(ans))

Solution (Python):
n= int(input())

a = list(map(int, input().split()))

if n == 0 and a[0]==1:
    print(1)
    exit(0)

if a[0] != 0:
    print(-1)
    exit(0)

b=1
count=1
asum =sum(a)
alim = asum

for i in range(n):
    if a[i+1] > 2*b:
        print(-1)
        exit(0)
    else:
        alim = alim - a[i+1]
        b= min(2*b-a[i+1], alim)

        count += b

print(count+ asum)

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

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    suma = sum(a)
    ans = 0
    can = 1
    for i,ai in enumerate(a):
        if ai > can:
            print(-1)
            exit()
        suma -= ai
        ans += can
        if (can-ai)*2 >= suma:
            can = suma
        else:
            can = (can-ai)*2

    print(ans)




    return

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate

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

S = list(accumulate(A))

ans = 1
cur = 1
for a, s in zip(A, S):
    if (cur := min(2 * (cur - a), S[-1] - s)) < 0:
        print(-1)
        quit()

    ans += cur

print(ans)

Solution (Python):
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n = ni()
    a = na()

    whole = sum(a)

    
    
    

    ans = 0
    base = 1
    for i in range(n + 1):
        ans += base
        base -= a[i]
        whole -= a[i]
        base = min(base * 2, whole)
        if (base <= 0 and i != n) or (i == n and base != 0):
            print(-1)
            exit(0)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
k=l[n]
count=1
sumleaf=1
flag=True
i0=0
suml=[]
for i in l:
    i0+=i
    suml.append(i0)
if l[0]>2 or l[0]==1 and n>=1:
    print(-1)
    flag=False
elif n==0 and l[0]!=1:
    print(-1)
    flag=False
    
else:
    for i in range(1,n+1):
        sumleaf*=2
        if i==n and sumleaf<k:
            flag=False
            print(-1)
            break
        elif i==n:
            count+=k
        else:
            if sumleaf<=l[i]:
                flag=False
                print(-1)
                break
            else:
                sumlnew=suml[n]-suml[i-1]
                count+=min(sumlnew,sumleaf)
                sumleaf=min(sumlnew,sumleaf)-l[i]
    
                    
                    
                    
                    
                
if flag==True:
    print(count)

Solution (Python):
n = int(input())

a = list(map(int,input().split()))

cumsum_a = a.copy()

for i in range(n-1, -1, -1):
    cumsum_a[i] += cumsum_a[i+1]

ans = 0
childable_node = 1

for i in range(n + 1):
    if a[i] > childable_node:
        ans = -1
        break

    ans += childable_node

    if i < n:
        b_max1 = 2 * (childable_node - a[i])
        b_max2 = cumsum_a[i + 1]
        childable_node = min(b_max1, b_max2)

print(ans)

Solution (Python):
n,*a=map(int,open(0).read().split())
tot=sum(a)
v=[1]
for q in a:
  tot-=q
  vt=min(2*(v[-1]-q),tot)
  if vt<0:
    print(-1)
    exit()
  v.append(vt)
print(sum(v))

Solution (Python):
n,*l=map(int,open(0).read().split())
e=[1]
for i in range(n): e+=[(e[-1]-l[i])*2]
a=t=0
for i in range(n,-1,-1):
  if l[i]>e[i]: print(-1); break
  t=min(l[i]+t,e[i]); a+=t
else: print(a)

Solution (Python):
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n = ni()
    a = na()

    whole = sum(a)

    if n == 0 and a[0] == 0:
        print(-1)
        exit(0)

    ans = 0
    base = 1
    for i in range(n + 1):
        ans += base
        base -= a[i]
        whole -= a[i]
        base = min(base * 2, whole)
        if (base <= 0 and i != n) or (i == n and base != 0):
            print(-1)
            exit(0)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,*l=map(int,open(0).read().split())
e=[1]
for i in range(n):
  e+=[(e[-1]-l[i])*2]
a=t=0
for i in range(n,-1,-1):
  if l[i]>e[i]:
    print(-1)
    break
  t=min(l[i]+t,e[i])
  a+=t
else:
  print(a)

Solution (Python):
N, *A = map(int, open(0).read().split())

s = sum(A)

ans = 1
cur = 1
for a in A:
    s -= a

    if (cur := min(2 * (cur - a), s)) < 0:
        print(-1)
        quit()

    ans += cur

print(ans)

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

Solution (Python):
N, *A = map(int, open(0).read().split())

s = sum(A)

ans = 1
cur = 1
for a in A:
    s -= a

    cur = min(2 * (cur - a), s)
    if cur < 0:
        print(-1)
        quit()

    ans += cur

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)
 
if N == 0:
  if A[0] != 1:
    print(-1)
  else:
    print(1)
  exit()
 
ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
cir = 1
bsum = 1
hantei=0
asum = [0 for i in range(n+1)]
asum[0] = sum(a)
for i in range(1,n+1):
    asum[i] = asum[i-1]-a[i]

swi = 0
for i in range(n):
    if swi == 1:
        
        cir = cir-a[i]
    if swi==0:
        if (cir-a[i])*2 < asum[i]:
            cir = (cir-a[i])*2
        else:
            cir = asum[i]
            swi = 1

    bsum += cir
    if cir<=0:
        hantei=1
        break





if hantei==1 or cir!=a[-1]:
    print(-1)
else:
    print(bsum)

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

ans, cnt, node = 0, sum(A), 1
for i in range(N + 1):
    ans += node
    cnt -= A[i]
    node = min(cnt, (node - A[i]) * 2)
    if node < 0:
        print(-1)
        break
else:
    print(ans)

Solution (Python):
N = int(input())

A = [int(i) for i in input().split()]

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

nodes = [0] * (N+1)
nodes[0] = 1
for i in range(1, N+1):
    node = (nodes[i-1]-A[i-1])*2
    if node < A[i]:
        print(-1)
        exit()
    nodes[i] = node



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



print(sum(nodes))

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

ans = 0
cnt = sum(a)
node = 1

for i in range(n + 1):
    ans += node
    cnt -= a[i]
    node = min(cnt, (node - a[i]) * 2)

    if node < 0:
        print(-1)
        sys.exit()

print(ans)

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

v=[1]
for q in a:
    tot-=q
    v.append(min(2*(v[-1]-q),tot))
    
if all([u>=0 for u in v]):
    print(sum(v))
else:
    print(-1)

Solution (Python):
from itertools import accumulate
n, *A = map(int, open(0).read().split())
if A[0] != 0:
    if A[0] == 1 and n == 0:
        print(1)
    else:
        print(-1)
else:
    B = list(accumulate(A[::-1]))[::-1]
    C = [1] * (n+1)
    D = [1] * (n+1)

    for i in range(1, n+1):
        C[i] = min(B[i], 2*D[i-1])
        D[i] = C[i] - A[i]
        if D[i] < 0:
            print(-1)
            break
    else:
        print(sum(C))

Solution (Python):
def main():
  input()
  in_a = list(map(int, input().split()))
  leaves = [0] * len(in_a)
  leaves[-1] = in_a[-1]

  if in_a[0] > 1:
    print(-1)
    return

  
  

  for i in range(len(in_a) - 1, 1, -1):
    leaves[i-1] = leaves[i] + in_a[i-1]
    
  node = 1
  total = 1
  
  for i in range(1, len(in_a)):
    n = (node - in_a[i-1]) * 2

    if n < in_a[i]:
        print(-1)
        return

    node = min(n, leaves[i])
    total += node

  print(total)

if __name__ == '__main__':
  main()

Solution (Python):
def main():
  n = int(input()) + 1
  a = [int(x) for x in input().split()]
  q = [0] * n
  for i in range(n):
    q[i] = (q[i - 1] - a[i - 1]) * 2 if i != 0 else 1
    
    if q[i] <= 0:
      print(-1)
      return
  
  if q[n - 1] < a[n - 1]:
    print(-1)
    return
  q[n - 1] = a[n - 1]
  s = q[n - 1]
  
  
  for i in range(n - 2, -1, -1):
    q[i] = min(q[i], q[i + 1] + a[i])
    if q[i] == 0:
      print(-1)
      return
    
    s += q[i]
  print(s)

main()

Solution (Python):
import sys

input = lambda: sys.stdin.readline().rstrip()


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

    v = [tuple() for _ in range(N + 1)]
    v[N] = (A[N], A[N])

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

    for i in range(N - 1, -1, -1):
        low, up = v[i + 1][0], v[i + 1][1]
        up = min(2 ** i, up + A[i])
        if low % 2 == 0:
            low = low // 2 + A[i]
        else:
            low = low // 2 + A[i] + 1
        v[i] = (low, up)

    
    for i in range(N):
        low, up = v[i][0], v[i][1]
        low = max(v[i + 1][0], low - A[i])
        up = min(v[i + 1][1], (up - A[i]) * 2)
        v[i + 1] = (low, up)

    ans = 0
    for i in range(N + 1):
        if v[i][0] > v[i][1]:
            print('-1')
            exit()
        ans += v[i][1]

    
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    if N == 0 and A[0] > 1:
        print(-1)
        return 0
    low, high = A[N], A[N]
    maxN = [0] * (N + 1)
    maxN[N] = A[N]
    Limit = [2 ** 50] * (N + 1)
    Limit[N] = A[N]

    for i in reversed(range(N)):
        leaf = A[i]
        Limit[i] = min(Limit[i], Limit[i+1] + leaf)
        if i <= 50: Limit[i] = min(pow(2, i), Limit[i])
        low = (low + 1) // 2 + leaf
        high += leaf
        if low > Limit[i]:
            print(-1)
            break
        else: 
            maxN[i] = min(high, Limit[i])
    else:
        for i in range(N):
            if (maxN[i] - A[i]) * 2 <= maxN[i+1]: maxN[i + 1] = (maxN[i] - A[i]) * 2
        print(sum(maxN))

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from itertools import accumulate
n = int(input())
As = list(map(int, input().split()))

if n == 0:
    if As[0] == 1:print(1)
    else:print(-1)
    exit()


if As[0] != 0:
    print(-1)
    exit()

b = 1
ans = 1
acc = list(accumulate(As))
s = acc[-1]
for ac,a in zip(acc[1:], As[1:]):
    
    b = min(2*b-a, s-ac)
    if b < 0:
        print(-1)
        exit()
    ans += b+a
print(ans)

Solution (Python):
def main():
  input()
  in_a = list(map(int, input().split()))
  leaves = [0] * len(in_a)
  leaves[-1] = in_a[-1]

  if in_a[0] > 1:
    print(-1)
    return

  for i in range(len(in_a)-2, -1, -1):
    leaves[i] = leaves[i+1] + in_a[i]

  node = 1
  total = 1
  
  for i in range(1, len(in_a)):
    n = (node - in_a[i-1]) * 2

    if n < in_a[i]:
        print(-1)
        return

    node = min(n, leaves[i])
    total += node

  print(total)

if __name__ == '__main__':
  main()

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

ans = 0

leaves = sum(A)
node_num = 1

for i in range(N+1):
    if A[i] > node_num:
        print(-1)
        exit()
    ans += min(node_num, leaves)

    leaves -= A[i]
    node_num -= A[i]
    node_num *= 2
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = a[::-1]

if n == 0 and a[0] == 1:
    print(1)
    exit()

if a[0] >= 1:
    print(-1)
    exit()
    
ans = [0] * (n + 1)
for i in range(n):
    ans[i + 1] = ans[i] + b[i]

ans = ans[::-1]

ans = ans[1::]
a = a[1::]

res = 1
prev_cnt = 1

for i in range(n):
    cnt = min(prev_cnt * 2, ans[i] + a[i])
    if cnt < a[i]:
        print(-1)
        exit()
    res += cnt
    prev_cnt = cnt - a[i]
print(res)

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

max_node = [0 for _ in range(n+1)]
for i in range(n-1, -1, -1):
    max_node[i] = max_node[i+1] + a[i+1]

ans = 1
node = 1
for i in range(n+1):
    node -= a[i]
    if (i < n and node <= 0) or node < 0:
        print(-1)
        exit(0)
    node = min(node * 2, max_node[i])
    ans += node
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if a[0]>=2:
    print(-1)

else:
    pN=1
    s=1
    l=[]
    S=sum(a)
    b=0
    z=1
    for k in range(len(a)):
        b+=a[k]
        l.append(b)

    for i in range(1,n+1):
        if a[i]>2*pN:
            print(-1)
            z=0
            break
        else:
            pN=min(2*pN-a[i],S-l[i])
            s+=pN
    s+=S
    if n==0:
        s=1
    if a[0]==1 and n>=1:
            print(-1)
            z=0

    if z:
        print(s)

Solution (Python):
def main():
  input()
  A = list(map(int, input().split()))
  cusum = [0] * len(A)
  cusum[-1] = A[-1]

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

  for i in range(len(A)-2, -1, -1):
    cusum[i] = cusum[i+1] + A[i]

  pre_node = 1
  ans = 1
  for i in range(1, len(A)):
    node = (pre_node - A[i-1]) * 2

    if node < A[i]:
        print(-1)
        return

    pre_node = min(node, cusum[i])
    ans += pre_node

  print(ans)

if __name__ == '__main__':
  main()