Problem:


Score : 600 points

Problem Statement

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

Notes

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

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

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

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

Constraints

0 \leq N \leq 10^5

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

A_N \geq 1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 A_2 \cdots A_N

Output

Print the answer as an integer.

Sample Input 1

3
0 1 1 2

Sample Output 1

7

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

Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

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

Sample Output 5

264



Sample input:
3
0 1 1 2


Sample output:
7

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
a = list(map(int, input().split()))
nmax = [None]*(n+1)
nmax[-1] = 0
for i in range(n-1, -1, -1):
    nmax[i] = nmax[i+1] + a[i+1]
    
k = 1
ans = 0
for i,(num, M) in enumerate(zip(a, nmax)):
    if k<num:
        ans = -1
        break
    k -= num
    k = min(M, k)
    ans += (k+num)
    k *= 2
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def ceil(a,b):
    return a//b + int(a%b != 0)

N = I()
A = LI()

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

mad = [0]*(N+1)
mid = [0]*(N+1)
mad[-1] = A[-1]
mid[-1] = A[-1]
for i in range(N)[::-1]:
    mad[i] = mad[i+1]+A[i]
    mid[i] = ceil(mid[i+1],2)+A[i]


ans = 0
for i in range(N+1):
    if mad[i] < 0 or mau[i] < 0:
        print('-1')
        exit()
    if mid[i] > mau[i]:
        print('-1')
        exit()
    if miu[i] > mad[i]:
        print('-1')
        exit()
    ans += min(mad[i],mau[i])

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
flag = True
if A[0] != 0:
    flag = False

ans = 0
cur = 1

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

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

if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
elif flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
LI = lambda: list(map(int, input().split()))
n = int(input())
a = LI()

maxnodes = [1]
sumnodes = 0

if n == 0:
    if a[0] == 1:
        print(1)
    else:
        print(-1)
else:
    for d in range(1, n+1):
        tmp = (maxnodes[-1]-a[d-1])*2
        if tmp < 0:
            print(-1)
            break
        else:
            maxnodes.append(tmp)
    else:
        if maxnodes[d] < a[d]:
            print(-1)
        else:
            maxnodes[d] = a[d]
            sumnodes += a[d]
            for d in range(n-1, -1, -1):
                maxnodes[d] = min(maxnodes[d+1]+a[d], maxnodes[d])
                sumnodes += maxnodes[d]
            print(sumnodes)

Submission status: Accepted

Solution code:
def examA():
    H1, M1, H2, M2, K = LI()
    T = (H2-H1)*60 + (M2-M1)
    ans = T-K
    print(ans)
    return

def examB():
    T = SI()
    ans = ""
    for t in T:
        if t=="?":
            ans += "D"
        else:
            ans += t
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    check = 1<<N
    for i,a in enumerate(A):
        check -= (1<<(N-i))*a
    if check<0:
        print(-1)
        return
    ans = 0
    cnt = 1
    less = sum(A)
    for i in range(N+1):
        a = A[i]
        if cnt>less:
            cnt = less
        ans += cnt
        less -= a
        cnt = (cnt-a)*2
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

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

if n == 0:
    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)

Submission status: Accepted

Solution code:
import sys
N = int(input())

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

ans = 0
v = 1

maxv = []

for i in range(N+1):

    if v <= 0:
        print (-1)
        sys.exit()
    
    maxv.append(v)

    v -= A[i]
    v *= 2

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

#print (maxv)

now = 0
for i in range(N,-1,-1):

    now = min(now + A[i] , maxv[i])
    #print (now)
    ans += now

print (ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
A = na()

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

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

dp = [1]*(n+1)
pd = [1]*(n+1)

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

m = 0
for i in range(0,n+1)[::-1]:
    m+=A[i]
    pd[i] = m

ans = []
for i in range(n+1):
    ans.append(min(dp[i],pd[i]))
    
print(sum(ans))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[0]*(N+1)
B[N]=A[N]
for i in range(N-1,-1,-1):
    B[i]=B[i+1]+A[i]

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

check=[min(B[i],C[i]) for i in range(N+1)]
for i in range(N+1):
    if check[i]<A[i]:
        print(-1)
        exit()
print(sum(check))

Submission status: Accepted

Solution code:
N = int(input())
A= list(map(int, input().split()))
S = sum(A)
ans = 0
leaf = 1
S_now = 0

if A[0] == 1:
  if N==0:
    print(1)
  else:
    print(-1)
elif A[0] != 0:
  print(-1)
else:
  for i in range(N):
    ans += leaf
    leaf -= A[i]
    S_now += A[i] 
    leaf = min(leaf*2,S-S_now)
  if A[-1] != leaf:
    print(-1)
  else:
    print(ans+A[-1])

Submission status: Accepted

Solution code:
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 = 1
prev = 1
P = []
for a in A[1:]:
    P.append(prev)
    mx = prev * 2

    if mx < a:
        print(-1)
        exit()

    ans += mx
    prev = mx - a

while prev and P:
    ans -= prev
    pr = P.pop()
    prev = max(0, prev - pr)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = [sum(a)] * (n + 1)
now = 0
for i in range(n + 1):
    now += a[i]
    s[i] -= now
ans = 0
now = 1
for ai, si in zip(a, s):
    ans += now
    now -= ai
    if now < 0:
        print(-1)
        exit()
    now = min(now * 2, si)
print(ans)

Submission status: Accepted

Solution code:
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()
if a[0] != 0:
  print(-1)
  exit()
ls = [0]*(n+1)
ls[0] = 1
sm = sum(a)
for i in range(1,n+1):
  if a[i] > (ls[i-1]-a[i-1])*2:
    print(-1)
    exit()
  if sm <= (ls[i-1]-a[i-1])*2:
    ls[i] = sm
    sm -= a[i]
  else:
    ls[i] = (ls[i-1]-a[i-1])*2
    sm -= a[i]
print(sum(ls))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(n) for n in input().split()]

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

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

ans = 0

n_prev = 0
for a, b in zip(A[::-1], B[::-1]):
    B_low = (n_prev + 1) // 2
    B_high = n_prev

    #print('{} {} {}'.format(B_low, B_high, b))

    if B_low > b:
        print(-1)
        exit()

    n_cur = a + min(B_high, b)
    #print(a, n_cur)
    ans += n_cur
    n_prev = n_cur
    
print(ans)

Submission status: Accepted

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

div_count = sum(a)-1
node = 1
ans = 0
for i,ai in enumerate(a):
    ans += node
    
    if ai > node:
        ans = -1
        break
    else:
        div_num = min(node - ai, div_count)
        node = div_num + (node - ai)
        div_count -= div_num

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0]
for i in range(n+1):
  b.append(b[-1]+a[-1-i])
b.reverse()
b.pop()
#print(a)
#print(b)
now = 1
ans = 0
for i in range(n+1):
  if now > b[i]:
    now = b[i]
  ans += now
  now -= a[i]
  if now <= 0 and i != n:
    print(-1)
    exit()
  if now < 0 and i == n:
    print(-1)
    exit()
  if now == 0 and i == n:
    print(ans)
    exit()
  now *= 2
  #print(i,now,ans)

Submission status: Accepted

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

left = sum(A)
n = 1
ans = 1
for a in A:
  left -= a
  if a > n or n - a > left:
    print(-1)
    break
  n = min((n - a) * 2, left)
  ans += n
else:
  if n > 0:
    print(-a)
  else:
    print(ans)

Submission status: Accepted

Solution code:
n = input()
vs = list( map(int,input().split(" ")) )
def cal(vs):
    if len(vs)==1:
        if vs[0]==1:
            return 1
        else:
            return -1
    if vs[0]>0:
        return -1
    x = 1
    rem_sum = sum(vs)
    res = [1]
    for v in vs[1:]:
        x = min(2*x, rem_sum)
        res.append(x)
        x -= v
        rem_sum -= v
        if x<0:return -1
    #print(res)
    return sum(res)
print(cal(vs))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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

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


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

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    n = int(input())
    a = [int(x) for x in input().split()]
    
    if n == 0:
        if a[0] > 1:
            print(-1)
        else:
            print(a[0])
        sys.exit()
    
    if a[0] != 0:
        print(-1)
        sys.exit()
    
    sum_a = sum(a)
    b = [0]*(n+1)
    for i in range(n):
        b[i+1] = b[i]+a[i+1]
    
    ans = 0
    key = 1
    for i in range(n+1):
        if a[i] > key:
            print(-1)
            sys.exit()
        
        ans += a[i]
        key -= a[i]
        ans += min([key, sum_a-b[i]])
        key *= 2
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
aa=list(map(int,input().split()))
le=1
st=0
se=10**24
for i in range(n+1):
    if(aa[i]>le):
        st=1
        break
    le-=aa[i]
    le*=2
if(st):
    print(-1)
else:
    ma=[0 for i in range(n+1)]
    ma[0]=1
    le=1
    for i in range(1,n+1):
        le*=2
        le=min(le,se)
        ma[i]=min((ma[i-1]-aa[i-1])*2,le)
    ma[n]=min(ma[n],aa[n])
    for i in range(n-1,-1,-1):
        ma[i]=min(ma[i],aa[i]+ma[i+1])
    print(sum(ma))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split(' ')]

b = [0 for x in a]

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

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

print(res)

Submission status: Accepted

Solution code:
def solve(n, aaa):
    if n == 0:
        if aaa[0] == 1:
            return 1
        else:
            return -1
    if aaa[0] != 0:
        return -1

    hi = 1
    hi_enable = [1]
    for a in aaa[1:]:
        if hi * 2 < a:
            return -1
        hi = hi * 2 - a
        hi_enable.append(hi)
    # print(hi_enable)
    vn = aaa[n]
    ans = vn
    for i in range(n - 1, -1, -1):
        hi = hi_enable[i]
        a = aaa[i]
        vn = min(vn, hi) + a
        ans += vn
        # print(vn, ans)
    return ans


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

    ans = 1
    b = 0
    L = [[0,0] for i in range(n)]
    # L[-1][0] = A[-1]
    # L[-1][1] = A[-1]
    l = A[-1]
    r = A[-1]
    for i in range(n-1,-1,-1):

        L[i][0] = (l+1)//2 + A[i]
        L[i][1] = r + A[i]
        l = L[i][0]
        r = L[i][1]

    if L[0][0] != 1:
        print(-1)
    else:
        ans = 1
        now = 1
        for i in range(1, n):
            now = min(L[i][1], now*2)
            # print(i,now)
            ans += now
            now -= A[i]
        print(ans + A[-1])

Submission status: Accepted

Solution code:
N = int(input())
A = tuple(map(int, input().split()))
limit = sum(A)
alive = 1
total = 0
for a in A:
    alive -= a
    limit -= a
    if alive < 0:
        print(-1)
        break
    total += alive + a
    alive = min(alive * 2, limit)
else:
    print(total)

Submission status: Accepted

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

nl = sum(a)

tmp = 1
l = 0
ans = 0
for ai in a:
    ans += tmp
    if tmp < ai:
        print(-1)
        sys.exit()
    tmp -= ai
    l += ai
    if l + 2 * tmp <= nl:
        tmp *= 2
    else:
        tmp = nl - l

print(ans)

Submission status: Accepted

Solution code:
N = int(input()) + 1
A = list(map(int, input().split()))

B = [0] * N
for i in reversed(range(N)):
    if i == N - 1:
        B[i] = A[i]
    else:
        B[i] = B[i + 1] + A[i]

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
if A[0] != 0:
    print(-1)
    exit()
cum = [0] * (N+2)
for i in range(N+1)[::-1]:
    cum[i] = cum[i+1] + A[i]
ans = 1
cur = 1
for i in range(1, N+1):
    cur = min(cur * 2, cum[i+1] + A[i])
    ans += cur
    cur -= A[i]
    if cur < 0:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    # import math
    # import random
    input = stdin.readline

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

    left_leaves = sum(aa)
    ans = 0
    now = 1
    for i in range(n):
        ans += now
        num_of_node = now - aa[i]
        if num_of_node <= 0:
            print(-1)
            exit()
        max_next_node = num_of_node*2
        left_leaves -= aa[i]
        if max_next_node > left_leaves:
            now = left_leaves
        else:
            now = max_next_node
    ans += now
    if now-aa[-1] != 0:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

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

def tree(A,N):
  m = [A[i] for i in range(N+1)]
  M = [A[i] for i in range(N+1)]
  for i in range(N-1,-1,-1):
    m[i] += m[i+1]//2+m[i+1]%2
    M[i] += M[i+1]
  if m[0]>1 or M[0]==0:
    return -1
  count = 1
  vertex = 1
  for i in range(1,N+1):
    vertex = min(2*(vertex-A[i-1]), M[i])
    count += vertex
  return count
      
print(tree(A,N))

Submission status: Accepted

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

count = sum(a) - 1
tmp = 1
ans = 1

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

for i in range(1,n+1):
    a1 = a[i]
    if count >= tmp:
        count -= tmp
        tmp *= 2
        ans += tmp
    else:
        tmp += count
        count = 0
        ans += tmp
    if tmp >= a1:
        tmp -= a1
    else:
        print(-1)
        exit()

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))

    section_needed = sum(a)
    ans = 0
    section_count = 1
    total_section = 1
    for i in range(n+1):
        ans += section_count
        section_count -= a[i]
        if section_count <= 0 and i != n:
            print(-1)
            return
        if i == n and total_section != section_needed:
            print(-1)
            return
        next_branch = min(max(0, section_needed - total_section), section_count)
        total_section += next_branch
        section_count += next_branch

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
if n == 0 and a[0] == 1:
    print(1)
    exit()
b = []
i = 0
for j in reversed(a):
    i += j
    b.append(i)
b.reverse()
ans = 1
if a[0] != 0:
    print(-1)
    exit()
i = 1
for j, k in zip(a[1:], b[1:]):
    if j > i*2:
        print(-1)
        exit()
    i = min(k, i * 2) - j
    ans += i + j
    if i < 0:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.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()

    B = [0] * (N+1)
    B[N] = A[N]
    for i in range(N-1, -1, -1):
        B[i] = B[i+1] + A[i]
    C = [0] * (N+1)
    for i in range(N+1):
        if i == 0:
            B[0] = 1
            C[0] = 1
        else:
            if B[i] > C[i-1] * 2:
                B[i] = C[i-1] * 2
            C[i] = B[i] - A[i]
            if C[i] < 0:
                print(-1)
                exit()
    print(sum(B))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
MA = [0] * (N + 2)
MA[0] = 1
ma = 1
for i, a in enumerate(A):
    if a > ma or (a == ma and i < N - 1):
        print(-1)
        exit()
    ma = (ma - a) * 2
    MA[i+1] = ma

ans = 0
s = 0
for i in range(N + 1)[::-1]:
    a = A[i]
    s = min(s + a, MA[i])
    ans += s
print(ans)

Submission status: Accepted

Solution code:
import sys, random, math
from bisect import bisect_left, bisect_right
input = sys.stdin.readline

def main():
    inf = 10 ** 20

#    t = int(input())
#    t, a, b = map(int, input().split())
    t = 1
    
    for _ in range(1, t+1):
    #    print("Case #{}: ".format(_), end = '')
        
        n = int(input())
        a = [int(x) for x in input().split()]
        
        ans = 0
        node = 1
        sua = sum(a)
        for x in a:
            ans += node
            if(x > node):
                ans = -1
                break
            node -= x
            sua -= x
            node = min(node*2, sua)
        
        
        print(ans)
        
        
main()

Submission status: Accepted

Solution code:
N, = map(int, input().split())
X = list(map(int, input().split()))
mx = sum(X)

c = 1
R = 0
for i in range(N+1):
    x = X[i]
    R += c
    c -= x
    mx -= x
    if c < 0:
        print(-1)
        break
    c = min(c*2, mx)
else:
    print(R)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
remain = sum(A)
depth = 0
end = 1  # 現時点の深さの頂点の最大値
answer = 0
for i, a in enumerate(A):
    answer += end
    if end < a:
        print(-1); exit()
    end -= a
    remain -= a
    end *= 2
    end = min(remain, end)

print(answer)

Submission status: Accepted

Solution code:
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 = 1 << 60

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
Can = [0]*n
ans = 0
can = 1
for i,a in enumerate(A):
    if can < a:
        print(-1)
        exit(0)
    elif i < n:
        can -= a
        can *= 2
        Can[i] = can
real = A[-1]
for i in range(n-1,-1,-1):
    ans += real
    real = min(real,Can[i]//2)
    real += A[i]
print(ans + 1)

Submission status: Accepted

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

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

r = 1
ans = 1
for i in range(N+1):
  r -= A[i]
  if i<N and r<=0 or r<0:
    print(-1)
    exit(0)
  r = min(2*r, S[i])
  ans += r
print(ans)

Submission status: Accepted

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

sum_a = sum(al)

potential = 1
ans = 0
for a in al:
    ans += min(sum_a, potential)
    sum_a -= a
    potential = 2 * (potential - a)
    if potential < 0:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

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

if n == 0:
    if a[0] == 1:
        print(1)
    else:
        print(-1)
else:
    if a[0] == 1:
        print(-1)
    else:
        lefts = [sum(a)]
        for i in range(1, len(a)):
            lefts.append(lefts[-1] - a[i])

        b = [0] * (n + 1)
        b[0] = 1

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

        if min(b) < 0:
            print(-1)
        else:
            print(sum(b) + sum(a))

Submission status: Accepted

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

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

ans = 0
v = 1
for i in range(n+1):
	if v < a[i]:
		print(-1)
		exit()
	ans += v
	p = v - a[i]
	if i < n:
		if p > back[i+1]:
			print(-1)
			exit()
		elif p*2 > back[i+1]:
			v = back[i+1]
		else:
			v = 2*p
	else:
		if v != a[i]:
			print(-1)
			exit()
print(ans)

Submission status: Runtime Error

Solution code:
# import numpy as np
import sys, math, heapq
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

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

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

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

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

Submission status: Runtime Error

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

def dfs(n,x,t):
    if n+1==N:
        if x-A[n]<=A[N]<=2*(x-A[n]):
            print(t+A[N])
            exit()
    else:
        for i in range(2*(x-A[n]),x-A[n]-1,-1):
            dfs(n+1,i,t+i)

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

dfs(0,1,1)
print(-1)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)


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

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

def rec(x,y,ans,N):
    if y==N-1:
        n=x-A[y]
        if n>0:
            for i in range(n+1):
                cnt=i+2*(n-i)

                if cnt==A[N]:
                    print(ans+cnt)
                    exit()
    else:
        n=x-A[y]
        if n<=A[N]:
            for i in range(n+1):
                cnt=i+2*(n-i)
                rec(cnt,y+1,ans+cnt,N)

rec(1,0,1,N)
print(-1)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)


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

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

def rec(x,y,ans,N):
    if y==N-1:
        n=x-A[y]
        for i in range(n+1):
            cnt=i+2*(n-i)

            if cnt==A[N]:
                print(ans+cnt)
                exit()
    else:
        n=x-A[y]
        if n>0:
            for i in range(n+1):
                cnt=i+2*(n-i)
                rec(cnt,y+1,ans+cnt,N)

rec(1,0,1,N)
print(-1)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)


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

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

def rec(x,y,ans,N):
    if y==N-1:
        n=x-A[y]
        for i in range(n+1):
            cnt=i+2*(n-i)

            if cnt==A[N]:
                print(ans+cnt)
                exit()
    else:
        n=x-A[y]
        for i in range(n+1):
            cnt=i+2*(n-i)
            rec(cnt,y+1,ans+cnt,N)

rec(1,0,1,N)
print(-1)

Submission status: Runtime Error

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

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

def rec(x,y,ans,N):
    if y==N-1:
        n=x-A[y]
        for i in range(n+1):
            cnt=i+2*(n-i)

            if cnt==A[N]:
                print(ans+cnt)
                exit()
    else:
        n=x-A[y]
        for i in range(n+1):
            cnt=i+2*(n-i)
            rec(cnt,y+1,ans+cnt,N)

rec(1,0,1,N)
print(-1)

Submission status: Runtime Error

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

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

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