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):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    lim = [None]*(n+1)
    f = True
    lim[0] = 1 - a[0]
    for i in range(1, n+1):
        lim[i] = lim[i-1]*2
        lim[i] -= a[i]
    ans = 0
    pre = 0
    for i in reversed(range(n+1)):
        if (pre+1)//2 > lim[i]:
            f = False
            break
        x = a[i] + min(lim[i], pre)
        ans += x
        pre = x
    if f:
        print(ans)
    else:
        print(-1)

if __name__ == "__main__":
    main()

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

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

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

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

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

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

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

INF=10**18

pr=[0]*(n+2)

pr[0]=1

for i in xrange(n+1):
	pr[i+1]=min(INF,(pr[i]-a[i])*2)

if pr[n+1]<0:
	print "-1"
	exit(0)

s=0
ans=0

for i in xrange(n,-1,-1):
	s=min(s+a[i],pr[i])
	ans+=s

print ans

Solution (Python):
import math
N = int(input())
A = list(map(int, input().split()))
section = [[A[-1], A[-1]]]
for i in range(1, N+1):
    min_section = math.ceil(section[i-1][0] / 2) + A[-i-1]
    max_section = section[i-1][1] + A[-i-1]
    section.append([min_section, max_section])
section = section[::-1]

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

node = [1]

for i in range(1, N+1):
    node.append(min((node[i-1] - A[i-1]) * 2, section[i][1]))

print(sum(node))

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

L = [0] * N + [A[N]]    
U = [0] * N + [A[N]]    
for i in range(N - 1, -1, -1):
    L[i] = (L[i + 1] + 1) // 2 + A[i]
    U[i] = U[i + 1] + A[i]

if 1 < L[0]:
    print(-1)
    sys.exit()

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

print(sum(U))

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

N = INT()
A = LIST()


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


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


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

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


print(ans)

Solution (Python):
import math

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

    max_node = [0 for i in range(n+1)]
    min_node = [0 for i in range(n+1)]
    res = 0

    for i in range(n, -1, -1):
        if i == n:
            max_node[i] = A[i]
            min_node[i] = A[i]
        elif i == 0:
            max_node[i] = 1
            min_node[i] = 1
        elif i == 1 and n != 1:
            max_node[i] = 2
            min_node[i] = math.ceil(min_node[i+1] /2) + A[i]
        else:
            max_node[i] = max_node[i+1] + A[i]
            min_node[i] = math.ceil(min_node[i+1] / 2) + A[i]

    for i in range(n):
        if i == 0:
            if n != 0 and A[i] != 0:
                res = -1
                break
        else:
            if max_node[i] > 2 * (max_node[i-1] - A[i-1]):
                max_node[i] = 2 * (max_node[i-1] - A[i-1])
            if max_node[i] < min_node[i]:
                res = -1
                break
    
    if res == -1:
        print(res)
    else:
        if n == 0 and A[i] != 1:
            print(-1)
        else:
            print(sum(max_node))

if __name__ == '__main__':
    main()

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

def solve():
    cur = 1
    res = 0
    for i in range(n+1):
        if cur < a[i]: return -1
        res += cur
        cur -= a[i]
        if cur > s[i+1]: return -1
        cur = min(cur*2, s[i+1])
    return res

print(solve())

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

INF = 10 ** 13 + 100

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

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

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

print(sum(B))

Solution (Python):

from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"
n = int(input())
a= list(map(int , input().split()))
s = sum(a)
f = 1
if n == 0:
  if a[0] != 1:
    print(-1)
    exit()
  else:
    print(1)
    exit()
elif a[0]!=0:
  print(-1)
  exit()
ans = 1
node = 1
for i in range(1,n+1):
  node=min(2*node, s)
  ans+=node
  node-=a[i]
  s-=a[i]
  if node < 0:
    print(-1)	
    exit()
if f: print(ans)

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

ar = list(reversed(a))

com = [ar[0]]
for i in range(n):
    com.append(com[i] + ar[i+1])

com.reverse()
ans = 0
val = 1
for i in range(n+1):

    ans += min(val,com[i])
    val -= a[i]
    if (i < n and val <= 0) or (i == n and val < 0) or (i == n and a[i] == 0):
        print(-1)
        exit()
    val *= 2
print(ans)

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

com = [ar[0]]
for i in range(n):
    com.append(com[i] + ar[i+1])

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

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

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

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

if min(cond1) <= 0:
    print(-1)
    exit()

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

if min(cond2) <= 0:
    print(-1)
    exit()

if cond2[N] < A[N]:
    print(-1)
    exit()

ans = sum(cond2)
print(ans)

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):
n = int(input())
a = list(map(int,input().split()))
b = [0]*(n+1)
if n == 0:  
    x = a[0]
    if x == 1:
        print(1)
    else:
        print(-1)
    exit()
nows = sum(a)
s = nows
for i in range(n+1):
    if i == 0:
        b[i] = 1 - a[i]
    else:
        nows -= a[i]
        b[i] = min(nows, 2*b[i-1]-a[i])
        if b[i] < 0:  
            print(-1)
            exit()

print(sum(b)+s)

Solution (Python):
N = int(input())
A = tuple(map(int, input().split()))
S = [0]
for a in reversed(A):
    S.append(S[-1] + a)
S.reverse()

lst = [0] * (N + 2)
lst[0] = 1
for i, a in enumerate(A):
    if lst[i] < a:
        print(-1)
        break
    lst[i + 1] = min((lst[i] - a) * 2, S[i + 1])
else:
    print(sum(lst))

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




now, max = 1, [None] * (n + 1)
for i in range(n + 1):
  if a[i] > now:
    print(-1)
    exit(0)
  max[i] = now
  now = min((now - a[i]) * 2, 2000000000000000000)






ans, up = 0, 0
for i in range(n, -1, -1):
  count = min(max[i], up + a[i])
  ans += count
  up = count
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
res=0
m=1

for i in a:
    b=m-i
    if b<0:
        print(-1)
        exit(0)
    res+=i
    res+=b
    s-=i
    m=min(b*2,s)
print(res)

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

now, max = 1, [None] * (n + 1)
for i in range(n + 1):
  if a[i] > now:
    print(-1)
    exit(0)
  max[i] = now
  now = min((now - a[i]) * 2, 2000000000000000000)

ans, up = 0, 0
for i in range(n, -1, -1):
  count = min(max[i], up + a[i])
  ans += count
  up = count
print(ans)

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

node_max = [1]
for i in range(1, n+1):
    node_max.append(min(10**18, node_max[i-1]*2-a[i]))

a.reverse()
node_max.reverse()

node_max2 = [a[0]]
node_min2 = [a[0]]

for i in range(n):
    node_max2.append(node_max2[-1]+a[i+1])
    node_min2.append((node_min2[-1]+1)//2+a[i+1])

if node_min2[-1] != 1:
    print(-1)
else:
    ans = 0
    for i in range(n+1):
        ans += min(node_max[i]+a[i], node_max2[i])

    print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.reverse()
min_max = [[] for _ in range(N+1)]

def main():
    min_max[0] = [A[0], A[0]]
    for i in range(1, N+1):
        a = A[i]
        pre_min, pre_max = min_max[i-1]
        min_max[i] = [(1+pre_min)//2 +a, pre_max +a]
    min_max.reverse()
    if min_max[0][0] != 1:
        print(-1)
        return
    A.reverse()
    ans = 1
    pre = 1
    for i in range(1, N+1):
        a = A[i-1]
        pre = min(2*(pre -a), min_max[i][1])
        ans += pre
    print(ans)

main()

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

N = int(input())
A = list(map(int, input().split()))
low = [0]*(N+1)
high = [0]*(N+1)
low[N] = A[N]
high[N] = A[N]

for i in range(N-1, -1, -1):
    low[i] = (low[i+1]+1)//2+A[i]
    high[i] = high[i+1]+A[i]

if not low[0]<=1<=high[0]:
    print(-1)
    exit()

ans = 1
now = 1

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

print(ans)

Solution (Python):
import sys

n = int(input())
a = [int(x) for x in input().split()[::-1]]

if 0 < n and a[-1] != 0:
    print(-1)
    sys.exit()

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

limit = [[a[0], a[0]]]
for i in range(0, n):
    low = -(-limit[i][0] // 2) + a[i + 1]
    high = limit[i][1] + a[i + 1]
    
    limit.append([low, high])
    
limit = limit[::-1]
a = a[::-1]

if 1 < limit[0][0]:
    print(-1)
    sys.exit()

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

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

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

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

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

print(ans)

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

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



en = [0]
en[0] = 1

for a in A_list:
    tmp = en[-1] - a
    if tmp < 0:
        print(-1)
        exit()
    en.append(tmp * 2)

en = en[:-1]

branch = A_list[-1]
res = A_list[-1]
nodes = en[-1]
for a, ena in zip(A_list[-2::-1], en[-2::-1]):
    branch = min(branch+a, ena)
    res += branch

print(res)

Solution (Python):
DEBUG = False

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

ranges_num_nodes = [[0 for _ in range(2)] for _ in range(N + 1)]
ranges_num_nodes[N][0] = LEAVES[N]
ranges_num_nodes[N][1] = LEAVES[N]

if DEBUG:
    print("ranges_num_nodes: {}".format(ranges_num_nodes))

for depth in range(N, 0, -1):
    ranges_num_nodes[depth-1][0] = LEAVES[depth-1] + (ranges_num_nodes[depth][0] + 1) // 2
    ranges_num_nodes[depth-1][1] = LEAVES[depth-1] + ranges_num_nodes[depth][1]

if DEBUG:
    print("ranges_num_nodes: {}".format(ranges_num_nodes))

num_nodes = [0] * (N + 1)
num_nodes[0] = 1

if DEBUG:
    print("num_nodes: {}".format(num_nodes))

for depth in range(N):
    num_nodes[depth+1] = min((num_nodes[depth] - LEAVES[depth]) * 2, ranges_num_nodes[depth+1][1])

if DEBUG:
    print("num_nodes: {}".format(num_nodes))

for depth in range(N+1):
    if num_nodes[depth] < ranges_num_nodes[depth][0]:
        print(-1)
        break
else:
    print(sum(num_nodes))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
b = [0]*(n+1)
if n == 0:  
    x = a[0]
    if x == 1:
        print(1)
    else:
        print(-1)
    exit()

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
cap = [[0, 0] for _ in range(N+1)]
cap[-1] = [A[-1], A[-1]]
for i in range(N-1,-1,-1):
    cap[i][0] = (cap[i+1][0] + 2 - 1)//2
    cap[i][1] = cap[i+1][1] + A[i]
ans = 1
nodes = 1
failed = nodes < cap[0][0]
for i in range(N):
    nodes = min((nodes - A[i])*2, cap[i+1][1])
    if nodes < cap[i+1][0]:
        failed = True
        break
    ans += nodes
print(-1 if failed else ans)

Solution (Python):
from math import log2

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

def solve() :
  m, M = A[-1], A[-1]
  max1 = [0] * (N + 1)
  max1[-1] = M
  for i in range(N - 1, -1, -1) :
    m = (m + 1) // 2 + A[i]
    M = M + A[i]
    max1[i] = M
  if not m <= 1 <= M :
    return -1
  
  ne = 1 - A[0]
  max2 = [0] * (N + 1)
  max2[0] = 1
  for i in range(1, N + 1) :
    ne = ne * 2 - A[i]
    max2[i] = ne + A[i]
    
  return sum(min(max1[i], max2[i])for i in range(N + 1))
  
print(solve())

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = list(map(int, input().split()))
    node_count = [0] * (N+1)
    for i, a in enumerate(A[::-1]):
        if i == 0:
            node_count[N] = a
            continue
        node_count[N-i] = node_count[N-i+1] + a
    can_build = True
    for i, a in enumerate(A):
        if i == 0:
            if N > 0 and a > 0:
                can_build = False
                break
            if N == 0 and a > 1:
                can_build = False
                break
            node_count[0] = min(node_count[0], 1)
            continue
        if (i < N and a >= node_count[i-1]*2) or (i == N and a > node_count[i-1]*2):
            can_build = False
            break
        node_count[i] = min(node_count[i], node_count[i-1]*2-A[i-1]*2)
    if can_build:
        ans = sum(node_count)
    else:
        ans = -1
    print(ans)
if __name__ == "__main__":
    main()

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

sum_leaves = [0]*(n+1)
sum_leaves[0] = leaves[0]
for depth in range(n):
    sum_leaves[depth+1] = sum_leaves[depth] + leaves[depth+1]

ans = 0

root = [None] * (n + 1)
if n == 0:
    root[0] = 0
else:
    root[0] = 1
if root[0] + leaves[0] != 1:
    print(-1)
else:
    for depth in range(n):
        root[depth+1] = min(2*root[depth]-leaves[depth+1],
                            sum_leaves[n]-sum_leaves[depth+1])
        if root[depth + 1] < root[depth] - leaves[depth + 1] or root[depth+1] < 0:
            print(-1)
            break
    else:
        print(sum(root)+sum(leaves))

Solution (Python):
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    N = iRaw()
    As = isRaw()
    Vs = [1]
    sumA = sum(As)
    for d in range(N+1):
        if As[d] > Vs[d]:
            print(-1)
            return -1
        sumA-=As[d]
        Vs+=[min((Vs[d]-As[d])*2,sumA)]
    print(sum(Vs[:N+1]))

main()

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

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

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

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

ans = 1
if l[0][0] == 1:
    num = [1]
    for i in range(n):
        num.append(
            min(
                l[i+1][-1], 
                (num[i]-a[i])*2
                
                )
            )
        ans += num[i+1]

    print(ans)
else:
    print(-1)

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

from_deeper_bind = [[0,0] for i in range(N+1)]
from_deeper_bind[N][0] = from_deeper_bind[N][1] = A[N]
node_num = [1]*(N+1)
node_num[N] = A[N]
from_shallower_bind = [1]*(N+1)

for i in range(N-1,-1,-1):
    from_deeper_bind[i][0],from_deeper_bind[i][1] = (from_deeper_bind[i+1][0]+1)//2+A[i],from_deeper_bind[i+1][1]+A[i]


if not from_deeper_bind[0][0] <= 1 <= from_deeper_bind[0][1]:
    print(-1)
    exit()


for i in range(1,N):
    from_shallower_bind[i] = (node_num[i-1]-A[i-1])*2
    node_num[i] = min(from_shallower_bind[i],from_deeper_bind[i][1])

print(sum(node_num))

Solution (Python):
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
if N==0:
    if H[0]!=1:
        print(-1)
        exit()
    else:
        print(1)
        exit()
else:
    if H[0]!=0:
        print(-1)
        exit()
    for i in range(1,N+1):
        depth[i]=(depth[i-1]-H[i-1])*2
        if depth[i]<0:
            print(-1)
            exit()
    if depth[N-1]*2<H[N]:
        print(-1)
        exit()
    else:
        depth[N]=min(depth[N],H[N])
    for i in range(N - 1, -1, -1):
        if depth[i + 1] == 0:
            if H[i] != 0:
                depth[i] = H[i]
            else:
                depth[i] = 0
            if i == 0:
                depth[i] = 1
        else:
            depth[i] = min(depth[i + 1] + H[i], depth[i])
    print(sum(depth))

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

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

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

Solution (Python):
def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * (n+1)
    if n == 0:
        x = A[0]
        if x == 1:
            print(1)
        else:
            print(-1)
        exit()
    
    
    
    

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

    print(sum(B) + s)


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if a[0]!=0:
    if n==0 and a[0]==1:
        print(1)
    else:
        print(-1)
    exit()
l=[[] for _ in range(n+1)]
l[0]=[1,1]
l[n]=[a[n],a[n]]
for i in reversed(range(1,n)):
    if l[i+1][0]%2==1:
        l[i]=[l[i+1][0]//2+a[i]+1,l[i+1][1]+a[i]]
    else:
        l[i]=[l[i+1][0]//2+a[i],l[i+1][1]+a[i]]
ans=[0]*(n+1)
ans[0]=1
for i in range(1,n+1):
    if ans[i-1]*2>=l[i][0]:
        ans[i]=min((ans[i-1]-a[i-1])*2,l[i][1])
    else:
        print(-1)
        exit()
print(sum(ans))

Solution (Python):

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
child =[0]*(N+1)
child[0] =2


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


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

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

print(sum(child) +1)

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

node = [[] for i in range(N + 1)]
idx = list(range(N+1))  
idx = idx[1:]  


node[0].append(A[N])
node[0].append(A[N])

for i in idx:
    
    node[i].append(- (- node[i - 1][0] // 2) + A[- i - 1])
    
    node[i].append(node[i - 1][1] + A[- i - 1])

if 1 not in node[-1]:
    print(-1)
    exit()

node.reverse()
idx = list(range(N + 1))
idx = idx[1:]
maximum = []
maximum.append(1)

for i in idx:
    val = min(node[i][1], (maximum[i - 1] - A[i - 1]) * 2)
    maximum.append(val)

print(sum(maximum))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
  
def solve(N, A):
  
  if N == 0 and A[0] > 1 or N > 0 and A[0] > 0:
    print(-1)
    return

  total = sum(A[1:])
  
  par = 1 - A[0]
  rt = 1
  for i, a in enumerate(A[1:]):
    total -= a
    max_node = par * 2
    cur = max_node - a
    if cur < 0:
      print(-1)
      return
    cur = min(total, cur)
    
    rt += a
    if i + 1 < N:
      rt += cur
    par = cur  
   
  print(rt)
  
solve(N, A)

Solution (Python):
from math import ceil

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

a.reverse()

max_tree = [0] * (n+1)
min_tree = [0] * (n+1)

max_tree[0] = a[0]
min_tree[0] = a[0]
for i in range(1, n+1):
    max_tree[i] = max_tree[i-1] + a[i]
    min_tree[i] = ceil(min_tree[i-1]/2) + a[i]

max_tree.reverse()
min_tree.reverse()

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

a.reverse()
possible = [0] * (n+1)
possible[0] = 1

for i in range(1, n+1):
    possible[i] = min((possible[i-1]-a[i-1])*2, max_tree[i])

print(sum(possible))

Solution (Python):
n = int(input())
ai = [int(i) for i in input().split()]

tmp = 0
ans = 0
old = 0

a_mnmx = [[0 for i in range(2)] for j in range(n+1)]

old = ai[n]

a_mnmx[n][0] = old
a_mnmx[n][1] = old

for i in range(n):
    a_mnmx[n-i-1][0] = (a_mnmx[n-i][0]+1)//2 + ai[n-i-1]
    a_mnmx[n-i-1][1] = a_mnmx[n-i][1] + ai[n-i-1]
    


if a_mnmx[0][1] < 1 or a_mnmx[0][0] > 1:
    print(-1)
    exit()

old = 1
ans = 1

for i in range(n):
    old = min(a_mnmx[i+1][1],old*2)
    ans += old
    old -= ai[i+1]
    
    
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
ans=0
tree=1
node=sum(A)
flag=0
for i in A:
    ans+=i
    node-=i
    if i>tree:
        ans=-1
        break
    tree-=i
    if tree<node:
        ans+=tree
    else:
        ans+=node
    tree=2*tree
print(ans)

Solution (Python):
from sys import stdin
from sys import setrecursionlimit
from itertools import accumulate
setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
b = list(accumulate(a[::-1]))
b = b[::-1]


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

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

ne = [0]*(n+1)

ne[0] = 1
point = 1

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

if ne[n-1]*2 < a[n]:
    print(-1)
    exit()

point += a[n]
ne[n] = 0

print(point)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res


N=II()
AS=LI()
SM=sum(AS)
B=1
res=0
M = 1
m = 1

for a in AS:
    B = M-a
    if B < 0:
        print(-1)
        exit(0)
    res += a
    res += B
    SM -= a
    M = min(B*2, SM)
    m = B
print(res)

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

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

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

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

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

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

Solution (Python):
import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

n = int(rl())

li = list(map(int, rl().split()))
if n == 0 and li[0] == 1:
    print(1)
    exit()

can = [1-li[0]]

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

ans = 0
can.reverse()
li.reverse()
temp = 0
for i in range(n+1):
    temp += li[i]
    ans += min(can[i], temp)
print(ans)

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


'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n=int(input())
a = list(map(int, input().split()))
if (a[0]==1 and n+1>1) or a[0]>1:
    print(-1)
    sys.exit()
if n==0 and a[0]==1:
    print(1)
    sys.exit()

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

yo_next=min(2-a[0],su[0])
cnt=yo_next+1

for i in range(1,n):
    if yo_next-a[i]<1:
        print(-1)
        sys.exit()
    
    yo_next=min(su[i],(yo_next-a[i])*2)
    cnt+=yo_next
    
if yo_next<a[-1]:
    print(-1)
    sys.exit()
else:
    print(cnt)

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

from itertools import accumulate

copy = values[:]
copy.reverse()
acc = list(accumulate(copy))
acc.reverse()

b = 1
total = 1
for i in range(n+1):
    a = values[i]
    bCandidate = b - a
    if bCandidate < 0:
        print(-1)
        exit()
    b = min(2*bCandidate, acc[i] - a)
    total += b
print(total)