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

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

A.reverse()
MAX.reverse()
MIN.reverse()

ans = 0
s = 0
for i,a in enumerate(A):
    s += a
    s = min(MAX[i],s)
    
    ans+= max(MIN[i],s)

print(ans)

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]
max_node_num = {i: min(2**i, A[i] + max_parent_num[i]) for i in range(0, N+1)}

ans = 0
for i in range(N, 0, -1):
    if node_num[i] > max_node_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] > max_node_num[i-1]:
            ans = -1
            break

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * (N + 1)
    if A[0] >= 2:
        print(-1)
        exit()
    if A[0] == 1:
        if len(A) == 1:
            print(1)
            exit()



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

        B[i] = tmp - A[i]
    ans += A[N]
    C = [0] * (N+1)

    C[N] += A[N]
    for i in range(N-1,0,-1):
        
        if C[i+1] <= B[i] + A[i]:
            ans += A[i] + C[i+1]
            C[i] = A[i] + C[i+1]
        else:
            ans += B[i] + A[i]
            C[i] = B[i] 
    print(ans)
        







if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())                                                                    
line_data = input()                                                                 
data = list(map(lambda x: int(x), line_data.split(' ')))                            
                                                                                    
num = 1                                                                             
prev_leave = 1                                                                      
for i, d in enumerate(data[:-1]):                                                   
    tmp = (prev_leave - d) * 2                                                      
    top = sum(data[1+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()))

MAX = []
MIN = []
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 = [-1] * (N+1)
s = 0
for i,a in enumerate(A):
    s += a
    s = min(MAX[i],s)
    ans[i] = s
print(sum(ans))

Submission status: Wrong Answer

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

if N == 0:
    print(-1 if A[0] == 0 else 1)
else:
    Pmax = [0 for _ in range(N+1)]
    Pmax[0] = 1-A[0]
    for i in range(1, N+1):
        Pmax[i] = 2*Pmax[i-1] - A[i]

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

    print(ans)

Submission status: Wrong Answer

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

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

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

if ans == 0:
    ans = -1
print(ans)

Submission status: Wrong Answer

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

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

A.reverse()
MAX.reverse()

ans = [-1] * (N+1)
s = 0
for i,a in enumerate(A):
    s += a
    s = max(MIN[i],s)
    s = min(MAX[i],s)
    ans[i] = s
print(sum(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 and i != N-1 :
        flug = 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()))
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
    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()))
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
#    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, = map(int, input().split())

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

capacity = [0]
cap = 1
for i, a in enumerate(A):
    n = 2 ** i
    cap = cap - a
    if cap <= 0:
        print(-1)
        sys.exit(0)
    capacity.append(cap)
    cap *= 2

total = 0
carry = 0
for d in range(N, -1, -1):
    cap = capacity[d]
    a = A[d]
    check = carry + a
    if check <= cap:
        total += check
        carry += a
    else:
        total += check
        carry = cap

print(total)

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
    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()))
# 結局うえからとしたからでサンドイッチすれば良いのか？
# なんか一瞬だけ頭にひらめいたアイディアなんだけどなぁ．．．
# 上からの範囲と下からの範囲でたかだかの最大値を計算していき，それぞれの最小値を計算することにより
MA = [0] * (N+1)
MI = [0] * (N+1)
# まずうえから
MA[0] = 1
ind = 0
for a in A[:-1]:
    if MA[ind]-a<0:
        print(-1)
        exit()
    MA[ind+1] = (MA[ind]-a) * 2
    ind += 1

if MA[N]<A[N]:
    print(-1)
    exit()
# つぎに下からなるべく多くとっていく
# 足の数をそのまま上に足し上げていく
MA[N] = A[N]
ind = N
for a in A[1:][::-1]:
    MA[ind-1] = min(MA[ind]+A[ind-1], MA[ind-1])

if MA[0]<0:
    print(-1)
    exit()

print(sum(MA))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))
sums = [0]
branch1 = [0] * (N+1)
branch2 = [0] * (N+1)
branch1[0] = 1
branch2[-1] = A[-1]

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

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

ans = 0
for i in range(N+1):
    ans += min(branch1[i], branch2[i])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    a = list(map(int, input().split()))
    maxnum = [0] * (n + 1)
    num = [0] * (n + 1)
    maxnum[0] = 1
    num[0] = 1
    if n > 0:
        num[-1] = a[-1]

    if n == 0 and a[0] == 1:
        print(1)
    elif n == 0 and a[0] == 0:
        print(-1)
    elif n == 0 and a[0] > 1:
        print(-1)
    elif n == 1 and a[1] == 0:
        print(-1)
    elif n == 1 and a[1] == 1:
        print(2)
    elif n == 1 and a[1] == 2:
        print(3)
    elif n >= 1 and a[0] > 0:
        print(-1)
    else:
        for i1 in range(1, n + 1):
            if maxnum[i1-1] * 2 < a[i1]:
                print(-1)
                sys.exit()
            else:
                maxnum[i1] = maxnum[i1-1] * 2 - a[i1]

        for j1 in range(n-1, 0, -1):
            numt = a[j1] + min(num[j1 + 1], maxnum[j1-1]*2 - a[j1])
            num[j1] = numt
        r = sum(num)
        print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
# 結局うえからとしたからでサンドイッチすれば良いのか？
# なんか一瞬だけ頭にひらめいたアイディアなんだけどなぁ．．．
# 上からの範囲と下からの範囲でたかだかの最大値を計算していき，それぞれの最小値を計算することにより
MA = [0] * (N+1)
MI = [0] * (N+1)
# まずうえから
MA[0] = 1
ind = 0
for a in A[:-1]:
    if MA[ind]-a<0:
        print(-1)
        exit()
    MA[ind+1] = (MA[ind]-a) * 2
    ind += 1

# つぎに下からなるべく多くとっていく
# 足の数をそのまま上に足し上げていく
MA[N] = A[N]
ind = N
for a in A[1:][::-1]:
    MA[ind-1] = min(MA[ind]+A[ind-1], MA[ind-1])

print(sum(MA))

Submission status: Wrong Answer

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

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

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

up_down = [1] * (n+1)
for i in range(1, n+1):
    if a[i] >= pow(2, i):
        print(-1)
        exit()
    up_down[i] = up_down[i-1] * 2 - a[i-1] * 2

ans = 0
for i in range(n+1):
    ans += min(bottom_up[i], up_down[i])

#print(bottom_up)
#print(up_down)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 子供を持たないノードの合計数が深さと同じになるような木を作れるか
    ans = 0
    node = 1
    for i in range(N+1):
        # node全てを葉にしても足りない
        if node<A[i]:
            print(-1)
            return
        else:
            ans += node
            node -= A[i]
            node *= 2

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline

n = int(input())
# n+1個
A = list(map(int, input().split()))

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

ans = 0
max2 = 0
kouho = [0] * (n + 1)
for i in range(n, 0, -1):
    max1 = pow(2, i)
    max2 += A[i]
    max2 = min(max1, max2)
    kouho[i] = max2
kouho[0] = 1
not_leave = 1
for i in range(1, n + 1):
    cnt = 0
    not_leave *= 2
    temp = min(kouho[i], not_leave)
    ans += temp
    not_leave -= A[i]
    if not_leave <= 0 and i != n:
        print(-1)
        exit()
    if i == n:
        if not_leave == 0:
            continue
        elif not_leave < 0:
            print(-1)
            exit()
ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

N = INT()
A = LIST()

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

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

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

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

ans = sum(cond1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline

n = int(input())
# n+1個
A = list(map(int, input().split()))

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

ans = 0
max2 = 0
kouho = [0] * (n + 1)
for i in range(n, 0, -1):
    max1 = pow(2, i)
    max2 += A[i]
    max2 = min(max1, max2)
    kouho[i] = max2
kouho[0] = 1
not_leave = 1
for i in range(1, n + 1):
    cnt = 0
    not_leave *= 2
    temp = min(kouho[i], not_leave)
    ans += temp
    not_leave -= A[i]
    if not_leave < 0 and i != n:
        print(-1)
        exit()
    if i == n:
        if not_leave == 0:
            continue
        else:
            print(-1)
            exit()
ans += 1
print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=input()
a=[int(s)for s in a.split()]
M=1
Q=1
m=sum(a)
if a[0]>=1:
    print(-1)
    sys.exit()
for i in range(n):
    M=2*M-a[i+1]
    if M<0:
        print(-1)
        sys.exit()
    M1=M+a[i+1]
    m=m-a[i]
    Q=Q+min(M1,m)
print(Q)

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
    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:
    ans = -1
if flug == 1:
   ans = -1
if N == 0:
    ans = -1

print(ans)

Submission status: Wrong Answer

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

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

ans = 0
max2 = 0
kouho = [0] * (n + 1)
for i in range(n, 0, -1):
    max1 = pow(2, i)
    max2 += A[i]
    max2 = min(max1, max2)
    kouho[i] = max2
kouho[0] = 1
not_leave = 1
for i in range(1, n + 1):
    cnt = 0
    not_leave *= 2
    temp = min(kouho[i], not_leave)
    ans += temp
    not_leave -= A[i]
    if not_leave < 0 and i != n:
        print(-1)
        exit()
ans += 1
print(ans)

Submission status: Wrong Answer

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

if n > 1 and A[0] > 0:
    print(-1)
    exit()
ans = 0
max2 = 0
kouho = [0] * (n + 1)
for i in range(n, 0, -1):
    max1 = pow(2, i)
    max2 += A[i]
    max2 = min(max1, max2)
    kouho[i] = max2
kouho[0] = 1
not_leave = 1
for i in range(1, n + 1):
    cnt = 0
    not_leave *= 2
    temp = min(kouho[i], not_leave)
    ans += temp
    not_leave -= A[i]
    if not_leave < 0 and i != n:
        print(-1)
        exit()
ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
C = list(accumulate(A[::-1]))[::-1] + [0]
B = [-1]*(n+1)
B[0] = 1 - A[0]
for i in range(1, n+1):
  B[i] = min(C[i+1], 2*B[i-1]-A[i])
  if B[i] < 0 or B[i] < B[i-1] - A[i]:
    print(-1)
    exit()
ans = sum(A) + sum(B)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

N = INT()
A = LIST()

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

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

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

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

ans = 0
for i in range(N+1):
    ans += min(cond1[i], cond2[i])
print(ans)

Submission status: Wrong Answer

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

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


MAX = 10 ** 9
lst = [1] * (10 ** 5 + 10)
for i in range(N + 1):
    lst[i + 1] = min(MAX, lst[i] * 2)

# print (lst[:10])
for i in range(N + 1):
    tmp = lst[i] - A[i]
    if tmp < 0:
        print (-1)
        exit()
    lst[i + 1] = min(lst[i + 1], tmp * 2)

# print (lst[:10])

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

# print (lst[:10])
ans = 1
tmp = 0
for i in range(N, 0, -1):
    ans += lst[i]
    lst[i - 1] = min(lst[i] + A[i - 1], lst[i - 1])

# print (lst[:10])
print (ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
node = [0 for i in range(n+1)]
if n == 0:
    if a[0] != 1:
        print(-1)
        exit()
    else:
        print(1)
        exit()
if a[0] != 0:
    print(-1)
    exit()
node[0] = 1
count = 1
for i in range(1,n+1):
    count = min(count * 2, 10**18)
    if a[i] > count:
        print(-1)
        exit()
    node[i] = node[i-1] - a[i-1]
    node[i] *= 2
if node[-1] < a[-1]:
    print(-1)
    exit()
for i in range(n-1, -1, -1):
    if a[i] > node[i]:
        print(-1)
        exit()
    node[i] = min(node[i], node[i+1] + a[i])
print(sum(node))

Submission status: Wrong Answer

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

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1
laS = [0 for i in range(N+1)]
laS[-1] = A[-1]

for i in range(N):
    laS[-2-i] = A[-2-i] + laS[-1-i]
    nodeS[i+1] = min(10**18,(nodeS[i]-A[i])*2)

for i in range(N+1):
    if nodeS[i] <= 0:
        print(-1)
        exit()

for i in range(N+1):
    if nodeS[i] >= laS[i]:
        break

print(sum(nodeS[:i]) + sum(laS[i:]))

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:
    ans = -1
if flug == 1:
   ans = -1
if N == 0:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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
    
    nodes = 0
    bound = list(accumulate(A[::-1]))
    bound.reverse()
    # print('bound: ', bound)

    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 (i == n and 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(map(int,input().split()))

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1
laS = [0 for i in range(N+1)]
laS[-1] = A[-1]

for i in range(N):
    laS[-2-i] = A[-2-i] + laS[-1-i]
    nodeS[i+1] = min(10**18,(nodeS[i]-A[i])*2)

for i in range(N+1):
    if nodeS[i] <= 0:
        print(-1)
        exit()
    if nodeS[i] >= laS[i]:
        break

print(sum(nodeS[:i]) + sum(laS[i:]))

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=input()
a=a.split()
a=[int(s)for s in a]
M=1
Q=1
m=sum(a)
if a[0]>=2:
    print(-1)
    sys.exit()
for i in range(n):
    M=2*M-a[i+1]
    if M<0:
        print(-1)
        sys.exit()
    M1=M+a[i+1]
    m=m-a[i]
    Q=Q+min(M1,m)
print(Q)

Submission status: Wrong Answer

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

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1
laS = [0 for i in range(N+1)]
laS[-1] = A[-1]

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

for i in range(N+1):
    if nodeS[i] <= 0:
        print(-1)
        exit()
    if nodeS[i] >= laS[i]:
        break

print(sum(nodeS[:i]) + sum(laS[i:]))

Submission status: Wrong Answer

Solution code:
import math

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

end_flag = False
count = sum(leaf)
ans = 0
node = 1

for i in range(N+1):
    if end_flag:
        break
    ans += node
    count -= leaf[i]
    node = min(count, (node-leaf[i])*2)

    if node < 0:
        end_flag = True

if end_flag:
    print('-1')
else:
    print(1+sum(leaf)-leaf[N]+N*2)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
node = [0 for i in range(n+1)]
if n == 0:
    if a[0] != 1:
        print(-1)
        exit()
    else:
        print(1)
        exit()
if a[0] != 0:
    print(-1)
    exit()
node[0] = 1
count = 1
for i in range(1,n+1):
    count = min(count * 2, 10**18)
    if a[i] > count:
        print(-1)
        exit()
    node[i] = node[i-1] - a[i-1]
    node[i] *= 2
node[-1] = a[-1]
for i in range(n-1, -1, -1):
    if a[i] > node[i]:
        print(-1)
        exit()
    node[i] = min(node[i], node[i+1] + a[i])
print(sum(node))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li()

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

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

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

cnt_list = [0]*(N)
cnt_list[-1] = min(A[-1], max_a[N-1])

for i in reversed(range(N-1)):
    if cnt_list[i+1] + A[i+1] <= max_a[i]:
        cnt_list[i] = cnt_list[i+1] + A[i+1]
    else:
        cnt_list[i] = max_a[i]

cnt = sum(cnt_list[:N+1]) + sum(A)

print(cnt)

Submission status: Wrong Answer

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

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1
laS = [0 for i in range(N+1)]
laS[-1] = A[-1]

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

for i in range(N+1):
    if nodeS[i] < 0:
        print(-1)
        exit()
    if nodeS[i] >= laS[i]:
        break

print(sum(nodeS[:i]) + sum(laS[i:]))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 子供を持たないノードの合計数が深さと同じになるような木を作れるか
    ans = 0
    node = 1
    for i in range(N+1):
        print(node)
        # node全てを葉にしても足りない
        if node<A[i]:
            print(-1)
            return
        else:
            ans += node
            node -= A[i]
            node *= 2

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy
n=int(input())
a=input()
a=a.split()
a=[int(s)for s in a]
M=1
Q=1
if a[0]>=2:
    print(-1)
    sys.exit()
for i in range(n):
    M=2*M-a[i+1]
    if M<0:
        print(-1)
        sys.exit()
    M1=M+a[i+1]
    Q=Q+min(M1,sum(a[i+1:]))
print(Q)

Submission status: Wrong Answer

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

SUM = sum(A) - A[0]
B = 1 - A[0]
ans = 1

if N == 0 and A[0] == 0:
    ans = -1

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

Submission status: Wrong Answer

Solution code:
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()

MAX = 10 ** 9
lst = [1] * (10 ** 5 + 10)
for i in range(N + 1):
    lst[i + 1] = min(MAX, lst[i] * 2)

# print (lst[:10])
for i in range(N + 1):
    tmp = lst[i] - A[i]
    if tmp < 0:
        print (-1)
        exit()
    lst[i + 1] = min(lst[i + 1], tmp * 2)

# print (lst[:10])

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

# print (lst[:10])
ans = 1
tmp = 0
for i in range(N, 0, -1):
    ans += lst[i]
    lst[i - 1] = min(lst[i] + A[i - 1], lst[i - 1])

# print (lst[:10])
print (ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    flag = True
    kuki = []
    kuki.append(1)
    if A[0] != 0:
        flag = False
    for i in range(1,N+1):
        if A[i] < kuki[i-1]*2:
            kuki.append(kuki[i-1]*2 - A[i])
        elif A[i] <= kuki[i-1]*2 and i == N:
            kuki.append(kuki[i-1]*2 - A[i])
        else:
            flag = False
            break
    
    if flag:
        ne = A[N]
        for i in range(0,N+1):
            j = N-i
            if kuki[j] > ne:
                kuki[j] = ne
            else:
                break
        
    if flag:
        count = sum(A) + sum(kuki[:N])
    else:
        count = -1
    print(count)
 
if __name__ == '__main__':
    main()

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
V[N]=0
 
ans = sum(V)+sum(A)
if A[0] != 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()))

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1
laS = [0 for i in range(N+1)]
laS[-1] = A[-1]

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

for i in range(N+1):
    if nodeS[i] < 0:
        print(-1)
        exit()
        break
    if nodeS[i] >= laS[i]:
        j = i

print(sum(nodeS[:i]) + sum(laS[i:]))

Submission status: Wrong Answer

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

total = sum(A)
node = 1
ans = 0
for i in range(N+1):
  ans += node
  total -= A[i]
  #print(node, total)
  node = min(total, (node - A[i]) * 2)
  
  if node < 0:
    print(-1)
      
print(ans)

Submission status: Wrong Answer

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

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] <= 0:
        flug = 1
    Lsum = Lsum - A[i+1]
    if V[i+1] > Lsum :
        V[i+1] = Lsum
V[N]=0
 
ans = sum(V)+sum(A)
if A[0] != 0:
    ans = -1
if flug == 1:
   ans = -1
if N == 0:
    ans = -1

print(ans)