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: Wrong Answer

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

ans = 0
if A[0] >= 1:
    ans = -1
if N == 0:
    if A[0] == 0:
        ans = 1
    else:
        ans = -1
else:
    node_num = {N: A[N]}
    max_parent_num = {0: 1}
    for i in range(1, N):
        max_parent_num[i] = max_parent_num[i-1] * 2 - A[i]

    for i in range(N, 0, -1):
        if i < N:
            if node_num[i] > min(2**i, A[i] + max_parent_num[i]):
                ans = -1
                break
        #i-1 no parent wo tukuru
        if node_num[i] <= max_parent_num[i-1]:
            i_1_parent_num = node_num[i]
        else:
            i_1_parent_num = max_parent_num[i-1]
        node_num[i-1] = i_1_parent_num + A[i-1]
        if i == 1:
            if node_num[i-1] > min(2**(i-1), A[i-1] + max_parent_num[i-1]):
                ans = -1
                break

if ans == -1 or ans == 1:
    print(ans)
else:
    ans = sum(node_num.values())
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * N
    sumA = sum(A)

    if N == 0:
        print(1)
        return
    
    B[0] = 1

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A_sum = sum(A)
A_left = A_sum
B_sum = 0
now_d = 0

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

if A_sum == 1:
  print('1')
  exit()

B_sum += 1
B_post = 1
now_d += 1

while now_d <= N:
  node_max = B_post * 2
  if node_max < A[now_d]:
    print(-1)
    exit()
  B_now = node_max - A[now_d]
  A_left -= A[now_d]
  if B_now > A_left:
    B_now = A_left
  B_sum += B_now
  B_post = B_now
  now_d += 1

print(A_sum + B_sum)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n = int(input())
L = list(map(int,input().split()))

a = sum(L)
b = 0
n = 0
j = 1
#print(a,L)

for i in range(len(L)):
    #print(a,b,j,n)
    if i > 0:
        a = a-L[i]
#        print(a,b,j,n)
        if b+L[i] <=j:
            n += b
            n += L[i]
            if b == 0:
                break
            elif b*2 <= a and b*2 <=j-L[i]:
#                print('a')
                b = b*2-L[i]
            elif b*2 <= a:
#                print('b')
                b = j - L[i]
            else:
#                print('c')
                b = a
        else:
            n = -1
            break
    elif i == 0:
        if L[i] == 1:
            n = -1 
            break
        b = 1
        n= L[i]
    
    j = j*2

print(n)

Submission status: Wrong Answer

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

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

max_a = [0]*(n + 1)

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

for i in range(n + 1):
    if i == 0:
        max_a[i] = 1
    else:
        max_a[i] = (max_a[i - 1] - a[i - 1])*2
        if max_a[i] < 0:
            print(-1)
            sys.exit()
# print(max_a)
for i in range(n, -1, -1):
    if i == n:
        max_a[i] = a[i]
    else:
        min_p = max_a[i + 1] // 2 + int(max_a[i + 1] % 2 == 1)
        max_p = max_a[i + 1]
        if max_a[i] < min_p:
            print(-1)
            sys.exit()
        max_a[i] = min(max_p + a[i], max_a[i])
print(sum(max_a))
# print(max_a)

Submission status: Wrong Answer

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

ans = 0
if A[0] >= 1:
    ans = -1
if N == 0:
    if A[0] == 0:
        ans = 1
    else:
        ans = -1
else:
    node_num = {N: A[N]}
    max_parent_num = {0: 1}
    for i in range(1, N+1):
        max_parent_num[i] = max_parent_num[i-1] * 2 - A[i]

    for i in range(N, 0, -1):
        if node_num[i] > min(2**i, A[i] + max_parent_num[i]):
            ans = -1
            break
        #i-1 no parent wo tukuru
        if node_num[i] <= max_parent_num[i-1]:
            i_1_parent_num = node_num[i]
        else:
            i_1_parent_num = max_parent_num[i-1]
        node_num[i-1] = i_1_parent_num + A[i-1]
        if i == 1:
            if node_num[i-1] > min(2**(i-1), A[i-1] + max_parent_num[i-1]):
                ans = -1
                break

if ans == -1 or ans == 1:
    print(ans)
else:
    ans = sum(node_num.values())
    print(ans)

Submission status: Wrong Answer

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

numLeafs = A

# Bound max non-leaves by how many expansions the previous level can do
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]
# Tighten max non-leaves by how many available children are on next level
maxNonLeafs[N] = 0
for i in range(N - 1, -1, -1):
    maxNonLeafs[i] = min(maxNonLeafs[i], maxNonLeafs[i + 1] + numLeafs[i + 1])

# Bound min non-leaves by how many expansions are needed for the next level
minNonLeafs = [None for i in range(N + 1)]
minNonLeafs[N] = 0
for i in range(N - 1, -1, -1):
    # The minimum non-leafs of each level is at least half (round up) of number of nodes on next level
    minNonLeafs[i] = (minNonLeafs[i + 1] + numLeafs[i + 1] + 1) // 2
    # Make sure valid
    if minNonLeafs[i] + numLeafs[i] > 2 ** i:
        print(-1)
        exit()

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

Submission status: Wrong Answer

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

A_sum = sum(A)
A_left = A_sum
B_sum = 0
now_d = 0

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

B_sum += 1
B_post = 1
now_d += 1

while now_d <= N:
  node_max = B_post * 2
  if node_max < A[now_d]:
    print(-1)
    exit()
  B_now = node_max - A[now_d]
  A_left -= A[now_d]
  if B_now > A_left:
    B_now = A_left
  B_sum += B_now
  B_post = B_now
  now_d += 1

print(A_sum + B_sum)

Submission status: Wrong Answer

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * N
    sumA = sum(A)

    if N == 0:
        print(0)
        return
    
    B[0] = 1

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * N

    if N == 0:
        print(0)
        return
    
    B[0] = 1

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys                                                                    
                                                                              
N = int(input())                                                              
line_data = input()                                                           
data = list(map(lambda x: int(x), line_data.split(' ')))                      
                                                                              
tmp_sum = sum(data)                                                           
tmp_data = []                                                                 
for i in data:                                                                
    tmp_sum -= i                                                              
    tmp_data.append(tmp_sum)                                                                                                                
                                                                              
if N == 0:                                                                    
    if data[0] == 1:                                                          
        print(1)                                                              
    else:                                                                     
        print(-1)                                                             
    sys.exit(0)                                                               
                                                                              
num = 1                                                                       
prev_leaf = 1                                                                 
for i, d in enumerate(data[:-1]):                                             
    tmp = (prev_leaf - d) * 2                                                 
    top = tmp_data[i]                                            
    if tmp < 0:                                                               
        num = -1                                                              
        break                                                                 
    if tmp < top:                                                             
        prev_leaf = tmp                                    
    else:                                                                     
        prev_leaf = top                                   
    num += prev_leaf                                                          
                                                                              
print(num)

Submission status: Wrong Answer

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

ans = 0
if N == 0:
    if A[0] == 0:
        ans = 1
    else:
        ans = -1
else:
    node_num = {N: A[N]}
    max_parent_num = {0: 1}
    for i in range(1, N+1):
        max_parent_num[i] = max_parent_num[i-1] * 2 - A[i]

    for i in range(N, 0, -1):
        if node_num[i] > min(2**i, A[i] + max_parent_num[i]):
            ans = -1
            break
        #i-1 no parent wo tukuru
        if node_num[i] <= max_parent_num[i-1]:
            i_1_parent_num = node_num[i]
        else:
            i_1_parent_num = max_parent_num[i-1]
        node_num[i-1] = i_1_parent_num + A[i-1]
        if i == 1:
            if node_num[i-1] > min(2**(i-1), A[i-1] + max_parent_num[i-1]):
                ans = -1
                break

if ans == -1 or ans == 1:
    print(ans)
else:
    ans = sum(node_num.values())
    print(ans)

Submission status: Wrong Answer

Solution code:
#import collections
#tree=collections.deque()
n=int(input())
li=list(map(int,input().split()))
tree=[]
if n==0 and li[0]==1:
    print(1)
    exit()
elif n==0 and li[0]!=1:
    print(-1)
    exit()
elif li[0]>=1:
    print(-1)
    exit()
else:
    tree.append(1)
    for i in range(1,n):
        tree.append(tree[i-1]*2)
    tree.append(li[n])
    for i in range(n-1,-1,-1):
        tree[i]=min(2**i,tree[i+1]+li[i])

    s=tree[1]
    for i in range(0,n):
        if (tree[i] - li[i]) * 2 <=0:
            print(-1)
            exit()
        elif (tree[i]-li[i])*2<tree[i+1]:
            tree[i+1]=(tree[i]-li[i])*2
    print(sum(tree))

Submission status: Wrong Answer

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

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

max_a = [0]*(n + 1)

for i in range(n + 1):
    if i == 0:
        max_a[i] = a[i]^1
    else:
        max_a[i] = (max_a[i - 1] - a[i - 1])*2
        if max_a[i] < 0:
            print(-1)
            sys.exit()
# print(max_a)
for i in range(n, -1, -1):
    if i == n:
        max_a[i] = a[i]
    else:
        min_p = max_a[i + 1] // 2 + int(max_a[i + 1] % 2 == 1)
        max_p = max_a[i + 1]
        if max_a[i] < min_p:
            print(-1)
            sys.exit()
        max_a[i] = min(max_p + a[i], max_a[i])
print(sum(max_a))
# print(max_a)

Submission status: Wrong Answer

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

MAX = [1] * (N+1)
ans = [0] * (N+1)
INF = 10**15

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

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

ans[N] = A[N]

for i in reversed(range(N)):
    ans[i] = min(ans[i+1]+A[i], MAX[i])

print(sum(ans))

Submission status: Wrong Answer

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

MAX = [1] * (N+1)
ans = [0] * (N+1)
INF = 10**15

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

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

ans[N] = A[N]

for i in reversed(range(N)):
    ans[i] = min(ans[i+1]+A[i], MAX[i])

print(sum(ans))

Submission status: Wrong Answer

Solution code:
import sys                                                                         
                                                                                   
N = int(input())                                                                   
line_data = input()                                                                
data = list(map(lambda x: int(x), line_data.split(' ')))                           
                                                                                   
tmp_sum = sum(data)                                                                
tmp_data = []                                                                      
for i in data:                                                                     
    tmp_sum -= i                                                                   
    tmp_data.append(tmp_sum)                                                                                                                        
                                                                                   
if N == 0:                                                                         
    if data[0] == 1:                                                               
        print(1)                                                                   
    else:                                                                          
        print(-1)                                                                  
    sys.exit(0)                                                                    
                                                                                   
num = 1                                                                            
prev_leaf = 1                                                                      
for i, d in enumerate(data[:-1]):                                                  
    tmp = (prev_leaf - d) * 2                                                      
    top = tmp_data[i+1]                                                
    if tmp <= 0:                                                                   
        num = -1                                                                   
        break                                                                      
    if tmp < top:                                                                  
        prev_leaf = tmp                                       
    else:                                                                          
        prev_leaf = top                                      
    num += prev_leaf                                                               
                                                                                   
print(num)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
V = [0]*(N+1)
flug = 0
Lsum= sum(A)
 
V[0] = 1
for i in range(N):
    V[i+1] = (V[i]*2 - A[i+1])
    if V[i+1] < 0 :
        flug = 1
    Lsum = Lsum - A[i+1]
    if V[i+1] > Lsum :
        V[i+1] = Lsum
 
ans = sum(V)+sum(A)
if A[0] != 0 or A[N] == 0:
    ans = -1
if flug == 1:
   ans = -1
if N == 0:
    ans = -1
 
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
p=10**9+7
ok=True
if N==0:
    if A[0]!=1:
        print(-1)
    else:
        print(1)
    exit()

for i in range(N+1):
    if i==0:
        preon=1-A[i]
    else:
        if preon*2<A[i]:
            ok=False
        preon=preon*2-A[i]
if not ok:
    print(-1)
    exit()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
V = [0]*(N+1)
flug = 0
Lsum= sum(A)
 
V[0] = 1
for i in range(N):
    V[i+1] = (V[i]*2 - A[i+1])
    if V[i+1] < 0 and i != N-1 :
        flug = 1
    Lsum = Lsum - A[i+1]
    if V[i+1] > Lsum :
        V[i+1] = Lsum
 
ans = sum(V)+sum(A)
if A[0] != 0 or A[N] == 0:
    ans = -1
if flug == 1:
   ans = -1
if N == 0:
    ans = -1
 
print(ans)

Submission status: Wrong Answer

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

node_num = {N: A[N]}
max_parent_num = {0: 1}

for i in range(1, N+1):
    max_parent_num[i] = max_parent_num[i-1] * 2 - A[i]
ans = 0
if N == 0:
    if A[0] == 0:
        ans = 1
    else:
        ans = -1
else:
    for i in range(N, 0, -1):
        if node_num[i] >  min(2**i, A[i] + max_parent_num[i]):
            ans = -1
            break
        #i-1 no parent wo tukuru
        if node_num[i] <= max_parent_num[i-1]:
            i_1_parent_num = node_num[i]
        else:
            i_1_parent_num = max_parent_num[i-1]
        node_num[i-1] = i_1_parent_num + A[i-1]
        if i == 1:
            if node_num[i-1] > min(2**(i-1), A[i-1] + max_parent_num[i-1]):
                ans = -1
                break

if ans == -1 or ans == 1:
    print(ans)
else:
    ans = sum(node_num.values())
    print(ans)

Submission status: Wrong Answer

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

node_num = {N: A[N]}
max_parent_num = {0: 1}

for i in range(1, N+1):
    max_parent_num[i] = max_parent_num[i-1] * 2 - A[i]
ans = 0
if N == 0:
    if A[0] == 0:
        ans = 1
    else:
        ans = -1
else:
    for i in range(N, 0, -1):
        if node_num[i] >  min(2**i, A[i] + max_parent_num[i]):
            ans = -1
            break
        #i-1 no parent wo tukuru
        if node_num[i] <= max_parent_num[i-1]:
            i_1_parent_num = node_num[i]
        else:
            i_1_parent_num = max_parent_num[i-1]
        node_num[i-1] = i_1_parent_num + A[i-1]
        if i == 1:
            if node_num[i-1] > min(2**(i-1), A[i-1] + max_parent_num[i-1]):
                ans = -1
                break

if ans == -1 or ans == 1:
    print(ans)
else:
    ans = sum(node_num.values())
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
V = [0]*(N+1)
flug = 0
Lsum= sum(A)

V[0] = 1
for i in range(N):
    V[i+1] = (V[i]*2 - A[i+1])
    if V[i+1] < 0 :
        flug = 1
    Lsum = Lsum - A[i+1]
    if V[i+1] > Lsum:
        V[i+1] = Lsum

ans = sum(V)+sum(A)
if N != 0 and A[0] != 0 :
    ans = -1 
if A[N] == 0:
   ans = -1
if flug == 1:
   ans = -1
if N == 0 and A[0] == 1:
    ans = 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys                                                           
                                                                     
N = int(input())                                                     
line_data = input()                                                  
data = list(map(lambda x: int(x), line_data.split(' ')))             
                                                                     
tmp_sum = sum(data)                                                  
tmp_data = []                                                        
for i in data:                                                       
    tmp_sum -= i                                                     
    tmp_data.append(tmp_sum)                                                                                             
                                                                     
if N == 0:                                                           
    if data[0] == 1:                                                 
        print(1)                                                     
    else:                                                            
        print(-1)                                                    
    sys.exit(0)                                                      
                                                                     
num = 1                                                              
prev_leave = 1                                                       
for i, d in enumerate(data[:-1]):                                    
    tmp = (prev_leave - d) * 2                                       
    top = tmp_data[i]                                  
    if tmp <= 0:                                                     
        num = -1                                                     
        break                                                        
    if tmp < top:                                                    
        prev_leave = tmp                          
    else:                                                            
        prev_leave = top                                                                      
    num += prev_leave                                                
                                                                     
print(num)

Submission status: Wrong Answer

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

#layers = {i: list(range(2**i-1, 2**(i+1)-1)) for i in range(0, N+1)}
node_num = {N: A[N]}
max_parent_num = {0: 1}
for i in range(1, N+1):
    max_parent_num[i] = max_parent_num[i-1] * 2 - A[i]

ans = 0
if N == 0:
    if A[0] == 0:
        ans = 1
    else:
        ans = -1
else:
    for i in range(N, 0, -1):
        if node_num[i] >  min(2**i, A[i] + max_parent_num[i]):
            ans = -1
            break
        #i-1 no parent wo tukuru
        if node_num[i] <= max_parent_num[i-1]:
            i_1_parent_num = node_num[i]
        else:
            i_1_parent_num = max_parent_num[i-1]
        node_num[i-1] = i_1_parent_num + A[i-1]
        if i == 1:
            if node_num[i-1] > min(2**(i-1), A[i-1] + max_parent_num[i-1]):
                ans = -1
                break

if ans == -1 or ans == 1:
    print(ans)
else:
    ans = sum(node_num.values())
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())                                                                       
line_data = input()                                                                    
data = list(map(lambda x: int(x), line_data.split(' ')))                               
                                                                                       
tmp_sum = sum(data)                                                                    
tmp_data = []                                                                          
for i in data:                                                                         
    tmp_sum -= i                                                                       
    tmp_data.append(tmp_sum)                                                                                                                               
                                                                                       
num = 1                                                                                
prev_leave = 1                                                                         
for i, d in enumerate(data[:-1]):                                                      
    tmp = (prev_leave - d) * 2                                                         
    top = tmp_data[i]                                                                                                                       
    if tmp <= 0:                                                                       
        num = -1                                                                       
        break                                                                          
    if tmp < top:                                                                      
        prev_leave = tmp                                              
    else:                                                                              
        prev_leave = top                                             
    num += prev_leave                                                                  
                                                                                       
print(num)

Submission status: Wrong Answer

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

#layers = {i: list(range(2**i-1, 2**(i+1)-1)) for i in range(0, N+1)}
node_num = {N: A[N]}
max_parent_num = {0: 1}
for i in range(1, N+1):
    max_parent_num[i] = max_parent_num[i-1] * 2 - A[i]

ans = 0
if N == 0:
    if A[0] == 0:
        ans = 1
    else:
        ans = -1
else:
    for i in range(N, 0, -1):
        if node_num[i] >  min(2**i, A[i] + max_parent_num[i]):
            ans = -1
            break
        #i-1 no parent wo tukuru
        if node_num[i] <= max_parent_num[i-1]:
            i_1_parent_num = node_num[i]
        else:
            i_1_parent_num = max_parent_num[i-1]
        node_num[i-1] = i_1_parent_num + A[i-1]
        if i == 1:
            if node_num[i-1] > min(2**i, A[i] + max_parent_num[i]):
                ans = -1
                break

if ans == -1 or ans == 1:
    print(ans)
else:
    ans = sum(node_num.values())
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
V = [0]*(N+1)
flug = 0
Lsum= sum(A)

V[0] = 1
for i in range(N):
    V[i+1] = (V[i]*2 - A[i+1])
    if V[i+1] < 0 :
        flug = 1
    if V[i] - A[i+1] > V[i+1]:
        flug = 1
    Lsum = Lsum - A[i+1]
    if V[i+1] > Lsum:
        V[i+1] = Lsum

ans = sum(V)+sum(A)
if A[0] != 0 or A[N] == 0:
    ans = -1
if flug == 1:
   ans = -1
if N == 0:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
a = LI()
L = [1]
if a[-1] > 2**n:
    print(-1)
    quit()
if n == 0:
    if a[0] == 0:
        print(-1)
        quit()
L2 = [a[-1]]
for i in range(n)[::-1]:
    L2.append(min(L2[-1] + a[i], 2**i))
L2 = L2[::-1]
ans = 0
for i in range(n+1):
    if i == 0:
        tmp = 1
    else:
        tmp = (L[-1] - a[i-1]) * 2
    if tmp <= 0:
        print(-1)
        quit()
    ans += min(tmp, L2[i])
    L.append(tmp)
print(ans)

Submission status: Wrong Answer

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

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

ans = 1
node = 1
for i in range(n):
    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)

Submission status: Wrong Answer

Solution code:
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):
    print((lst[i-1]-a[i-1])*2, sita_maxi[i])
    lst.append(min((lst[i-1]-a[i-1])*2, sita_maxi[i]))
    if lst[-1] < a[i]:
        print(-1)
        exit()

print(sum(lst))

Submission status: Wrong Answer

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

#layers = {i: list(range(2**i-1, 2**(i+1)-1)) for i in range(0, N+1)}
node_num = {N: A[N]}
max_parent_num = {0: 1}
for i in range(1, N+1):
    max_parent_num[i] = max_parent_num[i-1] * 2 - A[i]

ans = 0
for i in range(N, 0, -1):
    if node_num[i] >  min(2**i, A[i] + max_parent_num[i]):
        ans = -1
        break
    #i-1 no parent wo tukuru
    if node_num[i] <= max_parent_num[i-1]:
        i_1_parent_num = node_num[i]
    else:
        i_1_parent_num = max_parent_num[i-1]
    node_num[i-1] = i_1_parent_num + A[i-1]
    if i == 1:
        if node_num[i-1] > min(2**i, A[i] + max_parent_num[i]):
            ans = -1
            break

if ans == -1:
    print(ans)
else:
    ans = sum(node_num.values())
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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


bound = list(accumulate(A[::-1]))
bound.reverse()

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

print(ans)

Submission status: Wrong Answer

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

    if n  == 0:
        if A[0] == 1:
            return 1
        else:
            return -1
    elif A[0] != 0:
        return -1
    
    bound = [0]*(n+1)
    bound[n] = A[n]
    for i in range(n-1, -1, -1):
        bound[i] = bound[i+1] + A[i]

    B = [0] * (n+1)
    for i in range(n+1):
        if i == 0:
            B[i] = 1
        else:
            above = (B[i-1] - A[i-1]) * 2
            if  (i < n and above <= 0) or above < 0:
                return -1
            B[i] = min(above, bound[i])
    # print('B: ', B)
    return sum(B)

print(main())

Submission status: Wrong Answer

Solution code:
N = int(input())
a_list = [int(a) for a in input().split()]

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

ans = a_list[-1] + 1
temp1 = [""]*(N+1)
temp1[-1] = a_list[-1]
for n in range(N-1, 0, -1):
    temp1[n] = temp1[n+1]+a_list[n]
    
temp2 = 1
for n in range(1, N):
    temp2 = (temp2-a_list[n-1])*2
    ans_temp = min(temp2, temp1[n])
    
    if ans_temp < a_list[n]:
        print(-1)
        exit()
    
    ans += ans_temp
    
print(ans)