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()))

s = 1
if n == 0:
    if a[0] != 1:
        print(-1)
        quit()
    else:
        print(1)
        quit()
elif a[0] > 0:
    print(-1)
    quit()
memo = [[0,0] for _ in range(n+1)]
memo[0] = [0,1]
for i in range(1,n+1):
    if s == 0:
        print(-1)
        quit()
    s = memo[i-1][1]*2
    if s > 10**15:
        s = 10**15
    memo[i][0] = a[i]
    memo[i][1] = s-a[i]
    if s-a[i] < 0:
        print(-1)
        quit()
ans = [[a[i],0] for i in range(n+1)]
for i in range(n-1,-1,-1):
    if (ans[i+1][0]+ans[i+1][1]) > memo[i][1]*2:
        print(-1)
        quit()
    else:
        ans[i][1] = min(memo[i][1],ans[i+1][0]+ans[i+1][1])
s = 0
for i in range(n+1):
    s += sum(ans[i])
print(s)

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

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

v = 1
for i in range(1, N+1):
    v = min(2*v, L[-1]-L[i])
    ans += v
    v -= A[i]
    if v < 0:
        ans = -1
        break
if A[0] > 0:
    ans = -1
    if N == 0 and A[0] == 1:
        ans = 1

print(ans)

Solution (Python):
import sys

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


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

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

    if N == 0:
        print('1')
        exit()

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

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

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

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

    
    print(ans)


if __name__ == '__main__':
    solve()

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

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

ans = 0
v = 1  
for i in range(N+1):
    if v < A[i]:
        ans = -1
        break

    ans += v
    p = v-A[i]
    if i < N:
        v = min(Asum[i+1], 2*p)

print(ans)

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

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

ans = 0
v = 1  
for i in range(N+1):
    if v < A[i]:
        ans = -1
        break

    ans += v
    p = v-A[i]
    if i < N:
        if p > Asum[i+1]:
            ans = -1
            break
        v = min(Asum[i+1], 2*p)

print(ans)

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

if A[0] >= 2:
  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):
def main():
    import sys
    import math
    input = sys.stdin.buffer.readline
    n = int(input())
    A = list(map(int, input().split()))
    ans = 0
    node = 1
    max_node = sum(A)
    for i in range(n+1):
        ans += node
        max_node -= A[i]
        node = min(max_node,(node-A[i])*2)
        if node < 0:
            print(-1)
            exit(0)
    print(ans)


if __name__ == '__main__':
    main()

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

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

    
    node_num = 0
    next_node_w_children = 1
    next_node_num = 1
    
    for i in range(N+1):
        node_in_the_dept = next_node_num
        node_w_children = next_node_w_children      

        if(i == N):
            node_num += node_in_the_dept
            print(node_num)
        else:
            next_leaf_num = A[i+1]
            all_leave_num -=A[i]

            next_node_num = min(2 * node_w_children, all_leave_num)
            next_node_w_children = next_node_num - next_leaf_num
            if(next_node_num > node_w_children * 2 or next_node_num < node_w_children or next_node_w_children < 0):
                print(-1)
                return
            node_num += node_in_the_dept
    

main()

Solution (Python):
def main():
    N = int(input())
    A  = [int(_n) for _n in input().split()]
    if N == 0:
        print(1 if A[0]==1 else -1)
        return

    l = A[-1]
    L = [(1,1)]
    for i in range(1,N):
        L.append((A[i]+1, (L[i-1][1]-A[i-1])*2))
        if (L[i-1][1]-A[i-1])*2 < A[i]:
            print(-1)
            return
    L.append((A[N], (L[N-1][1]-A[N-1])*2))
    
    if (L[N-1][1]-A[N-1])*2 < A[N]:
        print(-1)
        return
    
    R = [(A[-1],A[-1])]
    for i in reversed(range(N)):
        R.append(((R[-1][0]+1)//2+A[i], R[-1][1]+A[i]))
    res = 0
    for i in range(N+1):
        r = R[i]
        l = L[N-i]
        if r[0] > l[1] or r[1] < l[0]:
            print(-1)
            return
        
        res += min(r[1], l[1])
    print(res)

        
main()

Solution (Python):
from itertools import accumulate
import sys

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

revA = reversed(A)
ans = 0

l = list(accumulate(revA))
l.reverse()

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

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

for v in l:
    if v > 0:
        ans += v
    else:
        ans = -1
        break


print(ans)

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

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

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

lst = [1]
for i in range(1, n+1):
    lst.append(min((lst[i-1]-a[i-1])*2, sita_maxi[i]))
    if lst[-1] < a[i]:
        print(-1)
        exit()

print(sum(lst))

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

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

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

lst = [1]
for i in range(1, n+1):
    lst.append(min((lst[i-1]-a[i-1])*2, sita_maxi[i]))
    if lst[-1] < a[i]:
        print(-1)
        exit()

print(sum(lst))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    def min2(x, y): return x if x <= y else y

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

    if N == 0:
        if As[0] == 1:
            return 1
        else:
            return -1

    pow2 = 1
    pow2s = [pow2]
    for d in range(61):
        pow2 *= 2
        pow2s.append(pow2)
    pow2s += [pow2] * N


    maxV = min2(1, 1-As[0])
    maxVs = [maxV]
    for d in range(1, N+1):
        maxV = min2(maxV*2, pow2s[d]) - As[d]
        maxVs.append(maxV)


    numVs = [0] * (N+1)
    numVs[N] = As[N]
    for d in reversed(range(N)):

        numC2 = -(-numVs[d+1] // 2)

        if maxVs[d] < numC2:
            return -1
        num = min2(maxVs[d], numVs[d+1])
        numVs[d] = As[d] + num

        if numVs[d] > pow2s[d]:
            return -1


    return sum(numVs)


ans = solve()
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
ma1 = [1]*n
ma2 = [0]*n
mi2 = [0]*n

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

for i in range(1,n):
    ma1[i]=ma1[i-1]*2-a[i]
    if ma1[i]<0:
        print(-1)
        exit()
if n == 1:
    if a[0]==1:
        print(-1)
        exit()
    if a[0]==0:
        if a[1]==1:
            print(2)
            exit()
        elif a[1]==2:
            print(3)
            exit()
        else:
            print(-1)
            exit()

ma2[n-1]=a[n]
ma2[n-2]=ma2[n-1]
mi2[n-1]=a[n]
mi2[n-2]=mi2[n-1]//2 + mi2[n-1]%2
if n!=2:
    for i in range(2,n):
        ma2[n-1-i]=min(ma2[n-i]+a[n-i+1],2**(n-i)-a[n-i])
        mi2[n-1-i]=(mi2[n-i]+a[n-i+1])//2 + (mi2[n-i]+a[n-i+1])%2
        if mi2[n-1-i]>ma2[n-1-i]:
            print(-1)
            exit()
ma2 = [1]+ma2
ans = 0
for i in range(n):
    ans += min(ma1[i],ma2[i])
ans +=sum(a)

print(ans)

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):
import sys
N = int(input())
A = list(map(int, input().split()))
cusum = [0 for i in range(N+1)]
cusum[N] = A[N]

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

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


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

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 = list(map(int, input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
elif A[0] != 0:
    print(-1)
    exit()

leaf = A
not_leaf = [0] * (N + 1)
not_leaf[0] = 1

for i, a in enumerate(A[1:-1], 1):
    not_leaf[i] = not_leaf[i - 1] * 2 - a

for i in reversed(range(1, N + 1)):
    total = not_leaf[i] + leaf[i]
    prev = not_leaf[i - 1]
    if prev > total:
        not_leaf[i - 1] -= prev - total
    if not_leaf[i - 1] * 2 < total:
        print(-1)
        break
else:
    print(sum(leaf) + sum(not_leaf))

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    sa = [0]
    for a in A:
        sa.append(sa[-1]+a)

    if N == 0:
        if A[0] == 1:
            return 1
        else:
            return -1

    if A[0] != 0:
        return -1
        
    ans = 1
    p = 1
    for i in range(1, N+1):
        m = min(p*2, sa[-1] - sa[i])
        ans += m
        if m - A[i] < 0:
            return -1
        p = m - A[i]
    return ans




def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

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

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

d[-1] = A[-1]
for i in range(N, 0, -1):
    d[i-1] = min(d[i]+A[i-1], d[i-1]+A[i-1])
print(sum(d))

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    sa = [0]
    for a in A:
        sa.append(sa[-1]+a)

    if N == 0:
        if A[0] == 1:
            return 1
        else:
            return -1

    if A[0] != 0:
        return -1
    ans = 1
    p = 1
    for i in range(1, N+1):
        if p * 2 < A[i]:
            return -1
        m = min(p*2, sa[-1] - sa[i])
        ans += m
        if m - A[i] < 0:
            return -1
        p = m - A[i]
    return ans




def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

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

b[0] = 1
for i in range(n):
    b[i+1] = 2*(b[i] - a[i])

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]

d = [0]*(n+1)
flag = 0
for k in range(n+1):
    if b[k] < c[k]:
        d[k] = b[k]
        if d[k] <= 0:
            flag += 1
    else:
        d[k] = c[k]
        if d[k] <= 0:
            flag += 1

ans = sum(d) if flag == 0 else -1
ans = -1 if n == 0 and a[0] > 1 else ans
ans = -1 if a[n] != d[n] else ans
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
B = [0] *(N+1)
B[0] = 1
ans = 0
for i in range(1, N+1):
    B[i] = (B[i-1] - A[i-1])*2
    if B[i] <= 0:
        ans = -1
        break
if B[N] < A[N]:
    ans = -1
if ans == 0:
    check = 0
    for j in range(N, 0, -1):
        check += A[j]
        if check < B[j]:
            ans += check
        else:
            last = j
            for k in range(1, last+1):
                ans += B[k]
            break
    ans += 1
if N == 0 and A[0] == 1:
    ans = 1
print(ans)

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

def solve(A):
    ans = 0
    leaves = sum(A)
    prev_node_capacity = 1

    for ai in A:
        if ai > prev_node_capacity:
            return -1
        ans += min(prev_node_capacity, leaves)

        leaves -= ai
        prev_node_capacity -= ai
        prev_node_capacity *= 2

    return ans
  
print(solve(A))

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

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


start = 1
way = sum(A)

for i in range(1,n+1):
    start *= 2

    if start < A[i]:
        print(-1)
        exit()
    if start > way:
        start = way

    ans += start
    
    start -= A[i]
    way -= A[i]

print(ans+1)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if n==0 and a[0]==1:
	print(1)
elif n==0:
	print(-1)
elif a[0]!=0:
	print(-1)
else:
	ruisekiwa = [0 for _ in range(n+1)]
	ruisekiwa[n] = a[n]
	for i in range(n)[::-1]:
		ruisekiwa[i] = a[i] + ruisekiwa[i+1]
	cnt=1
	ans=1
	for i in range(1,n+1):
		target = a[i]
		if cnt*2 - target <= 0 and i != n:
			print(-1)
			exit()
		elif i == n:
			if cnt * 2 - target < 0:
				print(-1)
				exit()
			else:
				ans += target
		else:
			if cnt*2 < ruisekiwa[i]:
				ans += cnt*2
				cnt = cnt*2-a[i]
			else:
				ans += ruisekiwa[i]
				cnt = ruisekiwa[i]
	print(ans)

Solution (Python):
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n = iinput()
a = iarr()

cum = []; sum = 0
for num in a: sum += num; cum.append(sum)

ans = 1
now = 1
for i in range(n+1):
    next = min(2*(now - a[i]), cum[n]-cum[i])
    now = next
    if n==i and next<0 : ans = -1; break
    if n!=i and next<=0 : ans = -1; break
    ans += next


print(ans)

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

numLeafs = A
minNonLeafs = [None for i in range(N + 1)]
maxNonLeafs = [None for i in range(N + 1)]

maxNonLeafs[0] = 1
for i in range(1, N + 1):
    maxNonLeafs[i] = 2 * maxNonLeafs[i - 1] - numLeafs[i]

minNonLeafs[N] = 0
maxNonLeafs[N] = 0
if minNonLeafs[N] + numLeafs[N] > 2 ** N:
    print(-1)
    exit()

for i in range(N - 1, -1, -1):
    minNonLeafs[i] = (minNonLeafs[i + 1] + numLeafs[i + 1] + 1) // 2
    if minNonLeafs[i] + numLeafs[i] > 2 ** i:
        print(-1)
        exit()
    maxNonLeafs[i] = min(maxNonLeafs[i], maxNonLeafs[i + 1] + numLeafs[i + 1])
    if minNonLeafs[i] > maxNonLeafs[i]:
        print(-1)
        exit()

count = 0
for i in range(N + 1):
    count += maxNonLeafs[i] + numLeafs[i]
print(count)

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

R = A[:]
for i in range(N - 1, -1, -1):
    R[i] = R[i + 1] + A[i]
B = 1
ans = B
for i in range(1, N + 1):
    M = 2 * B - A[i]
    if M < 0:
        ans = -1
        break
    B = min(M, max(0, R[i] - A[i]))
    ans += A[i] + B

print(ans if A[0] == 0 or A[0] == 1 and len(A) == 1 else -1)

Solution (Python):
def mk_tree(A,N):
    B = [None for _ in range(N+1)]
    B[0] = 1
    
    A_sum = [A[i] for i in range(N+1)]
    for i in reversed(range(N)):
        A_sum[i] += A_sum[i+1]

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

    if B[N] == A[N]:
        return sum(B)
    else:
        return -1

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

    print(mk_tree(A,N))

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
else:
    saidaiA =[]
    oya = 1
    flag = True
    for i in range(len(A)):
        if oya >= 5*10**13:
            ko = 10**14
        else:
            ko = oya *2
        if i == 0:
            ko = 1
        oya = ko - A[i]
        saidaiA.append(ko)
        if oya < 0:
            flag = False
    ans = 0
    
    motikosi = 0
    for i in range(len(A)):
        if A[-i] + motikosi >= saidaiA[-i]:
            ans += saidaiA[-i]
            motikosi = saidaiA[-i]
        else:
            ans += A[-i] + motikosi
            motikosi = A[-i] + motikosi
    if flag == True:
        print(ans+1)
    else:
        print(-1)

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = inpl()
l = [0] * (n + 1)
r = [0] * (n + 1)
l[0] = 1 - a[0]
for i in range(1, n + 1):
    l[i] = l[i - 1] * 2 - a[i]
for i in range(n - 1, -1, -1):
    r[i] = r[i + 1] + a[i + 1]
ans = 0
for i in range(n + 1):
    if min(l[i], r[i]) < 0:
        print(-1)
        exit()
    ans += min(l[i], r[i]) + a[i]


print(ans)

Solution (Python):
import sys
N=int(input())
A=list(map(int,input().split()))
if A[0]>=2:
  print(-1)
  sys.exit()
if A[0]==1:
  left=0
else:
  left=1
ans=A[N]
P=[1 for i in range(N+1)]
for i in range(1,N+1):
  point=left*2
  P[i]=point
  if point-A[i]<0:
    print(-1)
    sys.exit()
  left=point-A[i]
root=A[N]
for i in range(N,0,-1):
  root=min(P[i-1],root+A[i-1])
  ans+=root
print(ans)

Solution (Python):

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

P=[0 for i in range(N+1)]
P[N]=[A[N],A[N]]
for i in range(N-1,-1,-1):
    MIN,MAX=P[i+1]
    mi=int(A[i]+(MIN+MIN%2)/2)
    ma=A[i]+MAX
    P[i]=[mi,ma]
    
    
if P[0][0]==1:
    Q=[0 for i in range(N+1)]
    Q[0]=1
    cnt=1
    for i in range(N):
        Q[i+1]=min((Q[i]-A[i])*2,P[i+1][1])
        cnt+=Q[i+1]
    print(cnt)
else:
    print("-1")

Solution (Python):
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy


sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    A = list(map(int,input().split()))
    ans = 1
    befc = 1 - A[0] 
    if A[0] > 1:
        return -1
    tmp = sum(A[1::])
    for i in range(1,N+1):
        curc = min(befc * 2, tmp)
        if curc < A[i]:
            return -1
        ans += curc
        befc = curc - A[i]
        tmp -= A[i]
    return ans

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

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

internal_max = [1]*(n+1)
internal_max[0] = 1-As[0]

for i in range(1,n+1):
    internal_max[i] = 2*internal_max[i-1]-As[i]

depth_sum = [0]*(n+1)
depth_sum[n] = As[n]
judge = False

for i in range(n-1, -1, -1):
    if depth_sum[i+1] > internal_max[i]*2:
        judge = True
        break
    else:
        depth_sum[i] = As[i] + min(internal_max[i], depth_sum[i+1])

if n == 0:
    if As[0] > 1:
        judge = True

if judge:
    print(-1)
else:
    print(sum(depth_sum))

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

l = []

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

temp = 1
for i in range(N+1):
    l.append(temp-A[i])
    temp = (temp-A[i])*2

for i in range(N+1):
    if l[i] < 0:
        print(-1)
        sys.exit()



ans = 1
node = 0
for i in range(N, 0, -1):
    if l[i-1] >= node + A[i]:
        node += A[i]
        ans += node
    else:
        ans += node + A[i]
        node = l[i-1]

print(ans)

Solution (Python):

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

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

inf = 1 << 60

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

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

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

print(sum(nodes))

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
max_node = [0] * (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):


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    A = list(iim())

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

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

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

    A.reverse()
    B.reverse()
    ans = node = 0
    for d, lim in zip(A, B):
        node = min(node, lim)
        node += d
        ans += node

    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n = iinput()
a = iarr()

cum = []; sum = 0
for num in a: sum += num; cum.append(sum)

ans = 1
now = 1
for i in range(n+1):
    next = min(2*(now - a[i]), cum[n]-cum[i])
    now = next
    if n==i and next<0 : ans = -1; break
    if n!=i and next<=0 : ans = -1; break
    ans += next

if a[n] > 2**n: ans = -1
print(ans)

Solution (Python):
n = int(input())
a_list = list(map(int,input().split()))
a_list_r = a_list[::-1]
ruisekiwa = [a_list_r[0]]
for i in range(1,n+1):
  ruisekiwa.append(ruisekiwa[-1] + a_list_r[i])
ruisekiwa = ruisekiwa[::-1]
max_leaf = a_list[-1]
count = 0
check = True
node = 0
for i in range(n):
  if i == 0:
    if  n == 0 and a_list[0] == 1:
      count = 1
      break
    elif a_list[0] != 0:
      check = False
      break
    else:
      count = 1
      node = 1
  else:
    cand = 2 * node
    if cand < a_list[i]:
      check = False
      break
    node = min(ruisekiwa[i+1],2*node - a_list[i])
    count += node + a_list[i]
if check == False:
  print(-1)
elif n == 0 and a_list[0] == 1 and len(a_list) == 1:
  print(1)
elif 2 * node < a_list[-1]:
  print(-1)
elif a_list[-1] == 0:
  print(-1)
else:
  print(count + a_list[-1])

Solution (Python):
def main():
    n = int(input())
    a = [int(v) for v in input().split()]
    b = [a[i] for i in range(n + 1)]
    for i in reversed(range(0, n)):
        b[i] += b[i + 1]
    pow2 = [1 for _ in range(n + 1)]
    for i in range(1, n + 1):
        pow2[i] = 2 * pow2[i - 1]
    result = a[n]
    d = 0
    for i in range(n):
        d = 2 * d + a[i]
        if pow2[i] - d < 0:
            print(-1)
            return
        result += min(pow2[i] - d, b[i + 1]) + a[i]
    d = 2 * d + a[n]
    if pow2[n] - d < 0:
        print(-1)
        return
    print(result)


if __name__ == '__main__':
    main()

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

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

if d[-1] < 0:
    print(-1)
    exit()
else:
    d[-1] = A[-1]
for i in range(N, 0, -1):
    x = d[i]
    x += A[i-1]
    d[i-1] = min(x, d[i-1]+A[i-1])
print(sum(d))

Solution (Python):

def pow_k(x, n):
    """
    O(log 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():
    from math import ceil
    N = int(input())
    A = list(map(int, input().split()))

    if(N == 0):
        if(A[0] == 1):
            print(1)
        else:
            print(-1)
        exit(0)
    if(A[0] != 0 or A[N] == 0):
        print(-1)
        exit(0)
    
    if(N == 1):
        print(A[1] + 1)
        exit(0)
    cur = 0
    S = [0] * (N + 1)
    for i in range(N, 0, -1):
        cur += A[i]
        S[i - 1] = cur
    

    ans, cur = 0, 2
    node = [0] * (N + 1)
    a = [0] * (N + 1)
    node[0] = 2
    for i in range(1, N + 1):
        if(A[i] > cur):
            print(-1)
            exit(0)
        if(A[i] > pow(2, i)):
            print(-1)
            exit(0)
        cur = 2 * (cur - A[i])
        node[i] = cur

        if(node[i] > S[i]): node[i] = S[i]
        a[i] = node[i - 1] + cur
        
    
    
    
    print(sum(node) + 1)
    '''
  cur = 0
  for i in range(N, 0, -1):
      cur += A[i]
      if(cur >= 2**(i - 1)): cur = 2**(i - 1)
      
      ans += cur
      print(cur, ans)
  print(ans)

  '''


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
if a[0] == 1 and n == 0:
    print(1)
    exit()
su = sum(a)

l = [su]*(n+1)
for i in range(1,n+1):
    l[i]=l[i-1]-a[i-1]

count=0
x = 0
m=[1]*(n+1)
for j in range(1,n+1):
    m[j] = m[j-1]*2
    if m[j]>l[j]:
        m[j]=l[j]
    if (m[j]<a[j])or(m[j]==a[j] and j!=n):
        
        x = 1
        break
    
    count += m[j]
    m[j] -= a[j]
count+=1

if x==1 or a[0]!=0 :
    print(-1)
else:
    print(count)

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

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

if d[-1] < 0:
    print(-1)
    exit()
else:
    d[-1] = A[-1]
for i in range(N, 0, -1):
    x = d[i]
    x += A[i-1]
    if d[i-1] * 2 < x:
        y = x - A[i-1]
        if (y+1) // 2 + A[i-1] <= d[i-1] * 2:
            x = d[i-1] * 2
    d[i-1] = min(x, d[i-1]+A[i-1])
print(sum(d))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
if N == 0 and A[0] == 1:
  print(1)
  quit()

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

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

n = [0] * (N+1)
n[0] = 1
for i in range(1, N+1):
  a = A[i]
  m = n[i-1] * 2
  n[i] = m - a
  if n[i] < 0:
    print(-1)
    quit()

n[-1] = 0
for i in range(N-1, 0, -1):
  nn = n[i+1]
  a = A[i+1]
  n[i] = min(n[i], a + nn)

print(sum(n) + sum(A))