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:
import math
n = int(input())
li = list(map(int,input().split()))

tmp = 1
for i,l in enumerate(li):
    if i == 0:
        continue
    tmp *= 2
    if l > tmp:
        print(-1)
        exit()
    else:
        tmp -= l

max_li = [1]
for i,l in enumerate(li):
    if i == 0:
        continue
    la = (max_li[-1]-li[i-1])*2
    max_li.append(la)


li.reverse()
ans = 0
codomo = li[0]
for i,l in enumerate(li):
    if i == 0:
        if l > 2**(n-i):
            print(-1)
            exit()
        else:
            ans += codomo
    else:
        tmp = codomo + l
        fin = min(min(2**(n-i),tmp),max_li[n-i])
        #print(min(2**(n-i),tmp),max_li[i],i,'i')
        ans += fin
        codomo = fin
    #print(ans,'ans')
print(ans)

Submission status: Wrong Answer

Solution code:
n = input()
alist = [int(s) for s in input().split(" ")]

def check(alist):
  r = alist[-1]
  n = r
  l = len(alist)
  for i, a in enumerate(reversed(alist[:-1])):
    if r // 2 < a:
      return -1
    d = l - 1 - i
    r = min(r + a, 2 ** (d - 1) - a)
    n += r 
  return n

print(check(alist))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.reverse()
B = []
ans = 0
num = 0
num2 = 0
for i in range(N+1):
    lim = 2**(N-i)
    num = min(num+A[i],lim)
    B.append(num)
A.reverse()
B.reverse()
for i in range(N):
    num2 = B[i]-A[i]
    if num2*2 < B[i+1]:
        B[i+1] = num2*2
print(sum(B))

Submission status: Wrong Answer

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

cnt = 0
max_reaf = 2
can = True
for i in range(N+1):
    if i==0:
        cnt += 1

    elif A[i]>2**i:
        can = False
        break
    else:
        if A[i]>max_reaf:
            can = False
            break
            
        if i==N:
            cnt += A[i]
        else:
            cnt += max_reaf
            max_reaf -= A[i]
            max_reaf *= 2




if can:
    print(cnt)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
if a[0] > 0:
    print(-1)
    exit()
if n == 0:
    print(1)
    exit()
if n < 30 and a[-1] > (1 << n):
    print(-1)
    exit()
for i in range(min(n, 30)):
    if a[i] > (1 << i) - 1:
        print(-1)
        exit()
s = sum(a)
ans = 1
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n):
    dp[i + 1] = min(s, 2 * dp[i])
    ans += dp[i + 1]
    dp[i + 1] -= a[i + 1]
    s -= a[i + 1]
    if dp[i] <= 0:
        print(-1)
        exit()
print(ans)

Submission status: Wrong Answer

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

max_v=[0 for _ in range(n+1)]
max_v[0]=1-a[0]
if(max_v[0]<=0):
    print(-1)
    sys.exit()
#print(0,max_v[0])

for i in range(1,n+1):
    max_v[i]=2*max_v[i-1] - a[i]
#    print(i,max_v[i])
    if(max_v[i]<=0 and i<n):
        print(-1)
        sys.exit()
#print(max_v)
ans=a[-1]
v=a[-1]
for i in range(n-1,-1,-1):
    if(v>2*max_v[i]):
        print(-1)
        sys.exit()
    v=min(v,max_v[i])
    v+=a[i]
    ans+=v
#    print(i,v,ans)
print(ans)

Submission status: Wrong Answer

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

def floor_div(x,d):
    if x%d != 0:
        return int(x/d)+1
    else:
        return int(x/d)

N = int(input())

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

n_not_leaf = 0
sum_node = 0

num_node = [0 for d in range(N+1)]
max_node = [0 for d in range(N+1)]

# 各層のnodeのmax個を計算
for d in range(N+1):
    if d == 0:
        max_node[0] = 1-A[0]
    else:
        max_node[d] = (max_node[d-1]-A[d-1])*2
    
    if d != N and max_node[d]-A[d] <= 0:
        print(-1)
        exit()
if max_node[N]-A[N] < 0:
    print(-1)
    exit()


for d in reversed(range(N+1)):
    if d == N:
        num_node[N] = min(A[N], max_node[N])
    else:        
        if floor_div(num_node[d+1],2)+A[d] > max_node[d]:
            print(-1)
            exit()
        else:
            num_node[d] = min(num_node[d+1]+A[d], max_node[d])

print(sum(num_node))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
su = sum(a)
# print(su)
l = [su]*(n+1)
for i in range(1,n+1):
    l[i]=l[i-1]-a[i-1]
# print(l)
count=0
x = 0
m=[1]*(n+1)
for j in range(1,n+1):
    m[j] = m[j-1]*2
    if m[j]>l[j]:
        m[j]=l[j]
    if (m[j]<a[j])or(m[j]==a[j] and j!=n):
        # print(m[j],a[j])
        x = 1
        break
    # print(m[j])
    count += m[j]
    m[j] -= a[j]
count+=1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
# = map(int, input().split())
A = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
r = [1]
for i in range(N):
    r.append(r[i]*2)
if N == 0 and A[0] == 0:
    print(0)
    exit()
if A[N] == 0:
    print(-1)
    exit()


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


for i in range(N):
    r[i] -= A[i]


q = A[N]
ans = q

for i in range(N):
    q = min(q,r[N-1-i]) + A[N-1-i]
    ans += q
print(ans)

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

result = 0
branch_num = 0

candidates = [1]
possible = 1
for a in As:
    possible -= a
    possible *= 2
    candidates.append(possible)

candidates.pop(-1)

for i in range(1, N+1):
    index = -i
    a = As[index]
    c = candidates[index]
    if c < a:
        result = -1
        break
    branch_num += a
    result += min(branch_num, c)
    if branch_num//2 >= c:
        branch_num = branch_num//2

    N -= 1

if result != -1:
    result += 1

print(result)

Submission status: Wrong Answer

Solution code:
n=int(input())
flag=0
a=list(map(int,input().split()))
for i in range(n+1):
    if a[i]>i**2:
        flag=-1
if flag!=0:
    print(flag)
else:
    ans=0
    n+=1
    for i in range(a[-1]):
        ans+=n
        n-=1
    print(ans)

Submission status: Wrong Answer

Solution code:
# C
 
N = int(input())
A_N = list(map(int, input().split()))
if N == 0:
    print(1 if A_N[0] == 1 else -1)
    exit()

reversed_A_N = list(reversed(A_N))
for i in range(1, N + 1):
    reversed_A_N[i] += reversed_A_N[i - 1]
r_reversed_A_N = list(reversed(reversed_A_N))
 
 
r_reversed_A_N[0] = 1
for i in range(N):
    max_next_nodes = (r_reversed_A_N[i] - A_N[i]) * 2 - A_N[i+1]
    if max_next_nodes < 0:
      print(-1)
      exit()
    elif max_next_nodes >= r_reversed_A_N[i+1]:
        break
    else:
        r_reversed_A_N[i+1] = max_next_nodes + A_N[i+1]
 
r_reversed_A_N[-1] = A_N[-1]
print(sum(r_reversed_A_N))

Submission status: Wrong Answer

Solution code:

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

ch = [1]

cH = [1]
if A[0]>0:
    print(-1)
    exit()
for e,i in enumerate(A[1:]):
    cH.append(cH[-1]*2-i)
    # ch.append((cH[-1]*2)//(2**i))
# print(ch)
# print(cH)
# ch = ch[:-1]
# ch = ch[::-1]
# ch[0]*=2
# print(ch)
cH = cH[:-1]
cH.append(cH[-1]*2)
cH = cH[::-1]
# print(cH)
if 0 in cH:
    print(-1)
    exit()
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:-1]):
    # print(n,ch[e],-1)
    if n//2>cH[e]:
        print(-1)
        exit()
    if n  <= cH[e]:
        # print('ans:',ans,'n:',n)
        ans += n+i
        n+=i
    else:
        # print('ans:',ans,'ch:',cH[e],'i:',i)
        ans +=cH[e]+i
        n = cH[e]+i

    # print('ans:',ans,'n:',n)
print(ans+1)

Submission status: Wrong Answer

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

MAX = []
e = 1
for a in A:
    if e > 0:
        MAX.append(e)
        e -= a
        e *= 2
    else:
        print(-1)
        exit()

A.reverse()
MAX.reverse()
ans = 0
s = 0
for i,a in enumerate(A):
    s += a
    s = min(MAX[i],s)
    ans += s
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    d = list(map(int,input().split()))
    mx_next_gen_nodes_num = 1
    total_nodes_num = 0
    for i in range(n+1):
        #print(total_nodes_num)
        leaves_num = d[i]
        temp_node_num = mx_next_gen_nodes_num - leaves_num
        if temp_node_num >= 0:
            total_nodes_num += temp_node_num + leaves_num
        else:
            total_nodes_num = -1
            break
        mx_next_gen_nodes_num = temp_node_num * 2
    print(total_nodes_num)





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
asc = [0] * (n + 1)
desc = [0] * (n + 1)
asc[0] = 1
desc[-1] = a_list[-1]
sum = 0

for i in range(n):
    asc[i + 1] = (asc[i] -a_list[i]) * 2
    desc[n - 1 - i] = desc[n - i] + a_list[n - 1 - i]

    if asc[i + 1] <= 0:
        print(-1)
        exit()

for i in range(n + 1):
    sum += min(asc[i], desc[i])

print(sum)

Submission status: Wrong Answer

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

n = int(input())
a = list(mapi())
res =a[n]
mp = [min(2**(i),int(1e8)) for i in range(n+1)]
#print(*mp)
lst = 1
pst = [0]*(n+1)
for i in range(n+1):
    #print(lst,a[i])
    #res+=lst
    pst[i] = lst
    if pst[i]<=0:
        print(-1)
        exit()
    lst-=a[i]
    lst*=2
#print(*pst,"c")
#print(*mp,"d")
mx = a[n]
for i in range(n-1,-1,-1):
    if a[i]>=mp[i] or a[i]>=pst[i]:
        res = -1
        break
    mx = min(mx+a[i],mp[i])
    res+=min(mx,pst[i])
    #print(res,mx,mp[i],a[i])
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
a = np.array(list(map(int, input().split())))
l = 0
n = 1
b = 0
g = np.zeros(N+1)
g[0] = 1-a[0]
for i in range(1, N+1):
    g[i] = (g[i-1]-a[i-1])*2
    if g[i] <= 0:
        l = -1
g[N] = a[N]
for i in range(1, N+1):
    if l<0:
        break
    b = N-i
    if g[b] > g[b+1]+a[b]:
        g[b] = g[b+1]+a[b]
if a[0] != 0 or l == -1:
    print(-1)
else:
    print(int(sum(g)))

Submission status: Wrong Answer

Solution code:
n=int(input())
cnt=0
B1=list(map(int,input().split()))
if B1[0]!=0 and n>1:
    print(-1)
    exit()
if B1[0]>=1 and n==1:
    print(-1)
    exit()
if B1[0]==0 and n==1:
    print(-1)
    exit()
if B1[0]==1 and n==1:
    print(1)
    exit()
D=B1.copy()
A=[0]*(n+1)
A[0]==1 

C=[0]*(n+1)
C[-1]=B1[-1]
upper=[0]*(n+1)
upper[-1]=0
for i in range(n,-1,-1):
    if B1[0]>1:
        print(-1)
        exit()
    if i:
        B1[i-1]+=B1[i]//2
        C[i-1]=B1[i-1]
        upper[i-1]=(upper[i]+D[i])
lower=[0]*(n+1)
lower[0]=1
for i in range(1,n+1):
    lower[i]=2*lower[i-1]-D[i]
    A[i]=min(lower[i],upper[i])

print(sum(A)+sum(D)+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [1]
if a[0] != 0:
    print(-1)
    exit()
cnt = 2
ans = 1
for i in range(1, n+1):
    if i != n:
        if a[i] >= cnt:
            ans = -1
            break
        l.append(a[i]+(cnt-a[i])//2)
        ans += cnt
        cnt -= a[i]
        cnt *= 2
    if i == n:
        if cnt < a[i]:
            ans = -1
        else:
            ans += cnt
            l.append(cnt//2)
if ans == -1:
    print(ans)
else:
    ind = -1
    while cnt > a[n]:
        if cnt - l[ind] <= a[n]:
            ans += (cnt - a[n]) * ind
            cnt = a[n]
        else:
            cnt -= l[ind]
            ans += l[ind] * ind
            ind -= 1
    print(ans)

Submission status: Wrong Answer

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

flag=True
top_list=[1]
bot_list=[a[-1]]

for i in range(n):
    top_list.append((top_list[i]-a[i])*2)
# print(top_list)

for i in range(1,n+1):
    bot_list.append(bot_list[i-1]+a[n-i])
bot_list.reverse()
# print(bot_list)

total=0
for i in range(n+1):
    if top_list[i]<=0 or bot_list[i]<=0:
        flag=False
    total+=min(top_list[i],bot_list[i])

if a[0]!=0:
    if n==0 and a[0]==1:
        total=1
    else:
        flag=False

if flag:
    # if n==0:
    #     if a[0]==1:
    #         print(1)
    #     else:
    #         print(-1)
    # else:
    print(total)
else:
    print(-1)
# print(total if flag else -1)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

for i in range(n+1):
    d += (1+i)*a[i]
    
k = sum(a)-1
d = d - 1/2*k*(k+1)

if d < 2:
    print('-1')
else:
    print(d)

Submission status: Wrong Answer

Solution code:

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

ch = [1]

cH = [1]
if A[0]>0:
    print(-1)
    exit()
for e,i in enumerate(A[1:]):
    cH.append(cH[-1]*2-i)
if 0 in cH:
    print(-1)
    exit()
    # ch.append((cH[-1]*2)//(2**i))
# print(ch)
# print(cH)
# ch = ch[:-1]
# ch = ch[::-1]
# ch[0]*=2
# print(ch)
cH = cH[:-1]
cH.append(cH[-1]*2)
cH = cH[::-1]
# print(cH)
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:-1]):
    # print(n,ch[e],-1)
    if n//2>cH[e]:
        print(-1)
        exit()
    if n  <= cH[e]:
        # print('ans:',ans,'n:',n)
        ans += n+i
        n+=i
    else:
        # print('ans:',ans,'ch:',cH[e],'i:',i)
        ans +=cH[e]+i
        n = cH[e]+i

    # print('ans:',ans,'n:',n)
print(ans+1)

Submission status: Wrong Answer

Solution code:

from math import ceil
N = int(input())
A = list(map(int, input().split()))
if(A[0] > 0):
    print(-1)
    exit(0)
# curは作り出せる最大ノード数
cur = 0
S = [0] * (N + 1)
for i in range(N, 0, -1):
    cur += A[i]
    S[i - 1] = cur
# print(S)

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

    if(node[i] >= S[i]): node[i] = S[i]
    a[i] = node[i - 1] + cur
    #print("i={}, cur={}".format(i, cur))
print(node)
print(a)
# 最初の頂点
print(sum(node) + 1)
'''
cur = 0
for i in range(N, 0, -1):
    cur += A[i]
    if(cur >= 2**(i - 1)): cur = 2**(i - 1)
    #if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
    ans += cur
    print(cur, ans)
print(ans)

'''

Submission status: Wrong Answer

Solution code:
n=int(input())
As = list(map(int, input().split()))
import sys
kosu=0
if As[len(As)-1]==0:
    print(-1)
    sys.exit()

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

for i in range(len(As)):
    if As[i]==0:
        kosu+=1
        maekosu=1
    else:
        maekosu=maekosu*2-As[i]
        kosu+=As[i]+maekosu

print(kosu)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = [0]*(n+1)
y = 1
p = 0
for i in range(n+1):
    if(y-a[i] > 0):
        s[i] = y
        y -= a[i]
        y *= 2
    else:
        if(i != n):
            print(i,n)
            p = -1
            break
        elif(y == a[i]):
            s[i] = y
if(p == -1):
    print(-1)
elif(n == 0):
    if(a[0] == 1):
        print(1)
    else:
        print(-1)
else:
    q = 0
    for i in range(n+1):
        q += a[-1-i]
        if(q <= s[-1-i]):
            p += q
        else:
            p += s[-1-i]
    print(p)

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()
for i in range(n):
    if a[i] > 2**i - 1:
        print(-1)
        quit()
if a[-1] > 2**n:
    print(-1)
    quit()

if n == 0:
    if a[0] == 1:
        print(1)
        quit()
    else:
        print(-1)
        quit()
lst = [1]
for i in range(1, n):
    l = lst[-1] - a[i-1]
    if l <= 0:
        print(-1)
        quit()
    lst.append(2*l)
if lst[-1] - a[-2] <= 0:
    print(-1)
    quit()
lst.append(a[-1])
i = n-1
tmp = a[-1]
ans = 0
lst2 = [a[-1]]
while i >= 0:
    tmp += a[i]
    tmp = min(tmp, 2**i)
    lst2.append(tmp)
    i -= 1
lst2 = lst2[::-1]
for i in range(n+1):
    ans += min(lst[i], lst2[i])
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

revA = reversed(A)
ans = 0

l = list(accumulate(revA))
for i in range(N+1):
    if l[i] > 2**(N-i):
        if i == 0:
            ans = -1
            break
        l[i] = 2**(N-i)

for i in range(N):
    if 2*(l[N-i]-A[i]) < l[N-i-1]:
        l[N-i-1] = 2*(l[N-i]-A[i])

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

Submission status: Wrong Answer

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

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

for index, a in enumerate(A[1:], start=1):
    nodes[index] = nodes[index - 1] * 2 - a
    if nodes[index] < 0:
        print(-1)
        break
else:
    fixed_nodes = [0] * (N + 1)
    fixed_nodes[-1] = A[-1]
    for i in reversed(range(N)):
        if nodes[i] * 2 < fixed_nodes[i + 1]:
            print(-1)
            break
        fixed_nodes[i] = min(nodes[i], fixed_nodes[i + 1])
        fixed_nodes[i] += A[i]
    else:
        print(sum(fixed_nodes))

Submission status: Wrong Answer

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

cnt = [0] * (N + 1)
cnt[0] = 1
for i in range(N):
    if i > 45:
        cnt[i + 1] = cnt[i] - A[i]
    else:
        cnt[i + 1] = (cnt[i] - A[i]) * 2

ans = A[-1]
cur = A[-1]
for i in reversed(range(N)):
    cur += A[i]
    ans += min(cnt[i], cur)
        
if all(v > 0 for v in cnt):
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int( input() )
p = [ int( pi ) for pi in input().split() ]

sump = int( 0 )
for pi in p:
    sump += pi

ans = int( 0 )
for i in range( n+1 ):
    if i == 0:
        ans += 1
        px = 1
        if p[ i ] != 0:
            ans = -1
            break
    else:
        if px*2 <= sump:
            ans += px*2
            px = px*2 - p[ i ]
            sump = sump - p[ i ]
        else:
            ans += sump
            px = sump - p[ i ]
            sump = sump - p[ i ]
#        print( px, sump )
        if i != n and px <= 0:
            ans = -1
            break
        elif i == n and sump != 0:
            ans = -1
            break
        elif i == n and px != 0:
            ans = -1
            break

print( ans )

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
flag=True
ans=0
B=[0 for i in range(N+1)]
for i in range(N+1):
  if(i==0):
    if(A[i]==0):
      B[i]=1
    if(A[i]==1 and N>0):
      flag=False
  else:
    B[i]=B[i-1]*2-A[i]
  if(B[i]<0):
    flag=False
#print(B)
x=B[-1]#層の葉でない頂点数
y=A[-1]#層の頂点数
ans=A[-1]
#print(x,y,ans)
for i in range(N):
  if(x>B[N-1-i]*2):
    flag=False
    break
  else:
    x=min(y,B[N-1-i])
    y=x+A[N-1-i]
    ans+=y
if flag:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

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

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

ans = 1
sm = sum(a)
limit = 1
for i in range(1, n):
    ans += a[i]
    limit = 2*limit - a[i]
    if limit < 0:
        print(-1)
        exit()
    else:
        sm -= a[i]
        if limit <= sm:
            ans += limit
        else:
            ans += sm

ans += a[-1]

print(ans)

Submission status: Wrong Answer

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

ans = 0
isOK = True
for i in range(n,-1,-1):
    limit = 2**i
    if(limit<A[i]):
        isOK = False
        break
    if(i==n):
        ans += A[i]
        pre = A[i]
        continue
    if((pre+A[i]) > limit):
        target = (pre+1)//2 + A[i]
        if(target > limit):
            isOK = False
            break
        else:
            target = limit
    else:
        target = pre+A[i]
        
    ans += target
    pre = target

if(isOK):
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())

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

for i in range(n+1):
    d += (1+i)*a[i]
    
k = sum(a)-1
d = d - 1/2*k*(k+1)

if d < 1:
    print('-1')
else:
    print(d)

Submission status: Wrong Answer

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


if A[0] != 0:
    ans = -1

V = []

for i in range(N):
    if i == 0:
        V.append(1)
        continue
    V.append(V[i-1]*2 - A[i])
V.append(0)

for i in range(N):
    j = N - i -1
    if V[j] > A[j+1] + V[j+1]:
        V[j] = A[j+1] + V[j+1]
 
ans = sum(V)+sum(A)

if A[0] != 0:
    ans = -1

if min(V) < 0:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N = ri()
A = ri_()
# 限界値
B = [1] * (N + 1)
# 葉でない頂点の数
C = [0] * (N + 1)
if N == 0:
    if A[0] == 1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
if A[0] > 0:
    print(-1)
    exit()
for i in range(1, N):
    B[i] = B[i - 1] * 2 - A[i]
    if B[i] <= 0:
        print(-1)
        exit()
for i in reversed(range(0, N)):
    C[i] = min(A[i + 1] + C[i + 1], B[i])
print(sum(A) + sum(C))
# print('A:', A)
# print('C:', C)
# print('B:', B)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 変更
def dfs(i,c,f):
  global ans
  if f==0 and i==1:
    ans=max(ans,c)
  elif f==0:
    ans=-1
  else:
    for k in range(i//2+1):
      if i-k+a[f-1]<=2**(f-1):
        dfs(i-k+a[f-1],c+i-k+a[f-1],f-1)
      else:
        break
      
n=int(input())
a=list(map(int,input().split()))
ans=-1
if a[0]==1:
  print(1)
elif a[0]>=2:
  print(-1)
else:
  dfs(a[n],a[n],n)
  print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
t = 1
c = [1-a[0]]+[1]*(n)
# print(c)
for i in range(1,n+1):
    c[i] = c[i-1]*2-a[i]
    # print(i)
    if c[i] < 0:
        # print(c)
        print(-1)
        exit()
c[n] = 0
m = a[n]
for i in range(n-1,-1,-1):
    c[i] = min(c[i],m)
    m+=a[i]
# print(c)
print(sum(a)+sum(c))
# b = [0]*(n) + [a[-1]]
# for i in range(n-1,-1,-1):
#     b[i] = min(b[i+1]+a[i],2**(i))
# print(b)

Submission status: Wrong Answer

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

flag = True
for i in range(n):
    if a[i+1] != 0:
        flag = False
        break

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

nleaf = 1
ans = 0
v = list()

for i in range(n):
    nleaf -= a[i]
    v.append(nleaf)
    nleaf *= 2

nleaf = a[n]
ans += a[n]
for i in range(n-1, 0, -1):
    if v[i]*2 < nleaf:
        print(-1)
        exit()
    if v[i] > nleaf:
        v[i] = nleaf
    nleaf = v[i] + a[i]
    ans += nleaf
print(ans + 1)

Submission status: Wrong Answer

Solution code:
#木への理解が違うみたい。どう違うのかわからない。
N = int(input())
A = list(map(int, input().split()))

ans = 1
n = 1

for i in range(N+1):
    if A[i] > n :
        print(-1)
        exit()
    elif A[i] == n:
        print(ans)
        exit()
    else:
        ans += 2 * (n - A[i])
        n = 2 * (n - A[i])
        #print("ans:",ans, "n:",n)        

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = sum(a)
if n == 1:
    print(a[1]+1)
    exit()
if a[0] != 0:
    print(-1)
    exit()
for i in range(1,n):
    if a[i] > pow(2,i):
        print(-1)
        exit()
l = 1
ans = 1
for i in range(n):
    x = a[i+1]
    if m >= l*2:
        ans += l * 2
        l *= 2
    else:
        ans += m
        l = m
        #gr = False
    if x > 0:
        m -= x
        l -= x
        if m < 0:
            print(-1)
            exit()
print(ans)

Submission status: Wrong Answer

Solution code:
def main():

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

    z, w = 1, 1
    B1 = [[1-A[0], 1-A[0]]]
    for i in range(1, N+1):
        if 2*B1[-1][1] < A[i]: return -1
        x, y = max(B1[-1][0]-A[i], 0), 2*B1[-1][1] - A[i]
        B1.append([x, y])
        z = x+A[i]
        w = y + A[i]
    if A[N] < z or A[N] > w:
        return -1
    # print(C1)

    v = A[N]
    ans = v
    for i in range(N-1, 0, -1):
        x, y = (v + 1) // 2, v
        z = 0
        if y < B1[i][0] or x > B1[i][1]: return -1
        if B1[i][0] <= y < B1[i][1]:
            z = y
        else:
            z = B1[i][1]
        v = z + A[i]
        ans += v
    # print(C2)

    return ans + 1

    # return ans

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

Submission status: Wrong Answer

Solution code:
# C

N = int(input())
A_N = list(map(int, input().split()))
reversed_A_N = list(reversed(A_N))
if N == 0:
    print(A_N[0])
    exit()

for i in range(1, N + 1):
    reversed_A_N[i] += reversed_A_N[i - 1]
 
r_reversed_A_N = list(reversed(reversed_A_N))
 
 
r_reversed_A_N[0] = 1
for i in range(N):
    max_next_nodes = (r_reversed_A_N[i] - A_N[i]) * 2 - A_N[i+1]
    if max_next_nodes < 0:
      print(-1)
      exit()
    elif max_next_nodes >= r_reversed_A_N[i+1]:
        break
    else:
        r_reversed_A_N[i+1] = max_next_nodes + A_N[i+1]
 
r_reversed_A_N[-1] = A_N[-1]
print(sum(r_reversed_A_N))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A[0] == 1:
            print(1)
        else:
            print(-1)
    ans = 2 ** (N + 1) - 1
    len_list = []
    current_len = 1
    for depth, leafs in enumerate(A):
        ans -= leafs * (2 ** (N - depth + 1) - 2)
        len_list.append(current_len - leafs)
        current_len = (current_len - leafs) * 2
    last_leaf = len_list[-1]
    if last_leaf < 0:
        print(-1)
        return
    must_delete = last_leaf
    # print(must_delete)
    for _depth, x in enumerate(len_list[::-1]):
        depth = N - _depth
        leaf = A[depth]
        if must_delete <= (x + leaf) // 2:
            ans -= must_delete
            if ans > 0:
                print(ans)
            else:
                print(-1)
            return
        ans -= must_delete
        must_delete -= (x + leaf) // 2
    print(-1)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

b[0] = 1
for i in range(n):
    b[i+1] = 2*(b[i] - a[i])
#根から計算した深さごとの要素数の最大値

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]
#葉から計算した最小値

#print(b)
#print(c)

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

print(sum(d) if flag == 0 else -1)

Submission status: Wrong Answer

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

if A[0] == 1:
    if N == 0:
        print("1")
    else:
        print("-1")
    exit()
cnt = 1
roots = 1
for i in range(N):
    roots = roots * 2
    if roots > sum(A[i+1:]):
        roots = sum(A[i+1:])

    if roots - A[i+1] < 0:
        print("-1")
        exit()

    cnt += roots
    roots -= A[i+1]
print(cnt)