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

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

    if N == 0 and A[0] != 1:
        print(-1)
        return
    
    for i in range(1,N):
        sumA -= A[i]
        B[i] = min(2 * B[i-1] - A[i], sumA)

    for i in range(N+1):
        ans += A[i] + B[i]
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

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

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

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

sums = [0]
branch1 = [0] * (N+1)
branch2 = [0] * (N+1)
branch1[0] = 1
branch2[-1] = A[-1]

flag = True

m = 1

for i in range(N):
    branch1[i+1] = (branch1[i] - A[i])*2
    if branch1[i+1] < 1:
        flag = False
    m *= 2

if m < branch2[N]:
    flag = False

for i in range(N, 0, -1):
    branch2[i-1] = branch2[i]+A[i-1]
    m //= 2
    if m < branch2[i-1]:
        flag = False


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

# print(branch1)
# print(branch2)

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

Submission status: Wrong Answer

Solution code:

from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
#n,m=input_list()
a=input_list()
a.reverse()
ruiseki=[a[0]]
for i in a[1:]:
    ruiseki.append(ruiseki[-1]+i)

ruiseki.reverse()
a.reverse()
now=1
max_num=1
ans=0
for i in range(n+1):
    if now<=0:
        print(-1)
        exit()
    tmp=min(now,ruiseki[i])
    ans+=tmp
    now=2*(tmp-a[i])

if now//2>a[-1]>now:
    print("-1")
    exit()
print(ans)

Submission status: Wrong Answer

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

theory_max = [1-a[0]]
n = len(a)
for i in range(1,n):
    theory_max.append(theory_max[i-1]*2-a[i])

for i in range(n):
    if theory_max[i] < 0:
        print('-1')
        exit()

r_a = list(reversed(a))
r_theory_max = list(reversed(theory_max))
out = [r_a[0]]

for i in range(1,n):
    tmp = out[i-1] + r_a[i]
    if tmp > r_theory_max[i]:
        tmp = r_theory_max[i] + r_a[i]
    out.append(tmp)

print(sum(out))

Submission status: Wrong Answer

Solution code:

from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())z
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
#n,m=input_list()
a=input_list()
a.reverse()
ruiseki=[a[0]]
for i in a[1:]:
    ruiseki.append(ruiseki[-1]+i)

ruiseki.reverse()
a.reverse()
now=1
max_num=1
ans=0
for i in range(n+1):
    if now<=0:
        print(-1)
        exit()
    tmp=min(now,ruiseki[i])
    ans+=tmp
    now=2*(tmp-a[i])

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

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

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

sums = [0]
branch1 = [0] * (N+1)
branch2 = [0] * (N+1)
branch1[0] = 1
branch2[-1] = A[-1]

flag = True

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


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

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

# print(branch1)
# print(branch2)

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

Submission status: Wrong Answer

Solution code:
import math

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

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

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

sums = [0]
branch1 = [0] * (N+1)
branch2 = [0] * (N+1)
branch1[0] = 1
branch2[-1] = A[-1]

flag = True

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


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

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

# print(branch1)
# print(branch2)

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

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]

flag = True

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


for i in range(N, 0, -1):
    branch2[i-1] = branch2[i]+A[i-1]
    if branch1[i-1] < 1:
        flag = False

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

# print(branch1)
# print(branch2)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = list(map(int, input().split()))
if N == 0:
    if arr[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
else:
    if arr[0] != 0:
        print(-1)
        exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    tmp = min((ans[i-1]-arr[i-1])*2,sum_arr[i-1])
    ans[i] = tmp
for i in range(min(25,N+1)):
    if ans[i] > 2**i:
        print(-1)
        exit()
print(sum(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = list(map(int, input().split()))
if N == 0:
    if arr[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
else:
    if arr[0] != 0:
        print(-1)
        exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    tmp = min((ans[i-1]-arr[i-1])*2,sum_arr[i-1])
    ans[i] = tmp
for i in range(min(25,N)):
    if ans[i] > 2**i:
        print(-1)
        exit()
print(sum(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = list(map(int, input().split()))
if N == 0:
    if arr[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
else:
    if arr[0] != 0:
        print(-1)
        exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    tmp = min((ans[i-1]-arr[i-1])*2,sum_arr[i-1])
    if i-1 <= 30 and tmp > 2**(i-1):
        print(-1)
        exit()
    ans[i] = tmp
print(sum(ans))

Submission status: Wrong Answer

Solution code:
def aaaa():
    n=int(input())
    a=list(map(int, input().split()))
    ans=0
    if a[0]>0:
        if n==0:
            if a[0]==1:
                return 1
            else:
                return 0
        return -1
    nezen=1
    hazen=0
    line=[]
    liha=[]
    line.append(nezen)
    liha.append(hazen)
    su=0
    su=sum(a[x] for x in range(len(a)))
    for x in range(1,n):
        if nezen<=0:
            return -1
        ha=a[x]
        su-=ha
        ne=min(nezen*2-ha,su)
        nezen=ne
        line.append(ne)
        liha.append(ha)
    if nezen<0:
        return -1
    if nezen>a[n]/2:
        return -1
    liha.append(a[n])
    line.append(0)
    line[n]=0
    for x in range(len(line)):
        ans+=line[x]+liha[x]
    return ans
print(aaaa())

Submission status: Wrong Answer

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

for j in range(1, n):
    now = min(now * 2 - a[j], s[n] - s[j - 1])
    ans += now
print(ans)

Submission status: Wrong Answer

Solution code:
def aaaa():
    n=int(input())
    a=list(map(int, input().split()))
    ans=0
    if a[0]>0:
        if n==0:
            if a[0]==1:
                return 1
            else:
                return 0
        return -1
    nezen=1
    hazen=0
    line=[]
    liha=[]
    line.append(nezen)
    liha.append(hazen)
    su=0
    su=sum(a[x] for x in range(len(a)))
    for x in range(1,n+1):
        if nezen<=0:
            return -1
        ha=a[x]
        su-=ha
        ne=min(nezen*2-ha,su)
        nezen=ne
        line.append(ne)
        liha.append(ha)
    if line[n]<0:
        return -1
    line[n]=0
    for x in range(len(line)):
        ans+=line[x]+liha[x]
    return ans
print(aaaa())

Submission status: Wrong Answer

Solution code:
def aaaa():
    n=int(input())
    a=list(map(int, input().split()))
    ans=0
    if a[0]>0:
        return -1
    nezen=1
    hazen=0
    line=[]
    liha=[]
    line.append(nezen)
    liha.append(hazen)
    su=0
    su=sum(a[x] for x in range(len(a)))
    for x in range(1,n+1):
        if nezen<=0:
            return -1
        ha=a[x]
        su-=ha
        ne=min(nezen*2-ha,su)
        nezen=ne
        line.append(ne)
        liha.append(ha)
    if line[n]<0:
        return -1
    line[n]=0
    for x in range(len(line)):
        ans+=line[x]+liha[x]
    return ans
print(aaaa())

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = list(map(int, input().split()))
for i in range(min(N,25)):
    if arr[i] > 2**i:
        print(-1)
        exit()
if N == 0:
    if arr[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
else:
    if arr[0] != 0:
        print(-1)
        exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] <= 0:
        print(-1)
        exit()
    if (ans[i-1]-arr[i-1])*2 <= sum_arr[i-1]:
        tmp = (ans[i-1]-arr[i-1])*2
    else:
        tmp = sum_arr[i-1]
    ans[i] = tmp
print(sum(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = list(map(int, input().split()))
for i in range(min(N,30)):
    if arr[i] > 2**i:
        print(-1)
        exit()
if N == 0:
    if arr[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
else:
    if arr[0] != 0:
        print(-1)
        exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    if (ans[i-1]-arr[i-1])*2 <= sum_arr[i-1]:
        tmp = (ans[i-1]-arr[i-1])*2
    else:
        tmp = sum_arr[i-1]
    ans[i] = tmp
print(sum(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = list(map(int, input().split()))
for i in range(min(N,25)):
    if arr[i] > 2**i:
        print(-1)
        exit()
if N == 0:
    if arr[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
else:
    if arr[0] != 0:
        print(-1)
        exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    if (ans[i-1]-arr[i-1])*2 <= sum_arr[i-1]:
        tmp = (ans[i-1]-arr[i-1])*2
    else:
        tmp = sum_arr[i-1]
    ans[i] = tmp
print(sum(ans))

Submission status: Wrong Answer

Solution code:
def aaaa():
    n=int(input())
    a=list(map(int, input().split()))
    ans=0
    if a[0]>0:
        return -1
    nezen=1
    hazen=0
    line=[]
    liha=[]
    line.append(nezen)
    liha.append(hazen)
    su=0
    su=sum(a[x] for x in range(len(a)))
    for x in range(1,n+1):
        if nezen<=0:
            return -1
        ha=a[x]
        su-=ha
        ne=min(nezen*2-ha,su)
        nezen=ne
        line.append(ne)
        liha.append(ha)
    line[n]=0
    for x in range(len(line)):
        ans+=line[x]+liha[x]
    return ans
print(aaaa())

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = list(map(int, input().split()))
for i in range(min(N,25)):
    if arr[i] > 2**i:
        print(-1)
        exit()
if N == 0:
    if arr[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    if (ans[i-1]-arr[i-1])*2 <= sum_arr[i-1]:
        tmp = (ans[i-1]-arr[i-1])*2
    else:
        tmp = sum_arr[i-1]
    ans[i] = tmp
print(sum(ans))

Submission status: Wrong Answer

Solution code:
def aaaa():
    n=int(input())
    a=list(map(int, input().split()))
    ans=0
    if a[0]>0:
        return -1
    nezen=1
    hazen=0
    line=[]
    liha=[]
    line.append(nezen)
    liha.append(hazen)
    su=0
    su=sum(a[x] for x in range(len(a)))
    for x in range(1,n+1):
        if nezen<=0:
            return -1
        ha=a[x]
        su-=ha
        ne=min(nezen*2-ha,su)
        nezen=ne
        line.append(ne)
        liha.append(ha)
    line[n]=0
    for x in range(len(line)):
        ans+=line[x]+liha[x]
    print(line)
    print(liha)
    return ans
print(aaaa())

Submission status: Wrong Answer

Solution code:
N = int(input())
arr = list(map(int, input().split()))
for i in range(min(N,25)):
    if arr[i] > 2**i:
        print(-1)
        exit()
if N == 0:
    print(1)
    exit()
sum_arr = [0]*N
sum_arr[0] = arr[-1]
for i in range(1,N):
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
sum_arr = sum_arr[::-1]
ans = [0]*(N+1)
ans[0] = 1
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    if (ans[i-1]-arr[i-1])*2 <= sum_arr[i-1]:
        tmp = (ans[i-1]-arr[i-1])*2
    else:
        tmp = sum_arr[i-1]
    ans[i] = tmp
print(sum(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.append(0)
vermax = [1]
for i in range(N):
  vermax.append((vermax[i]-A[i])*2)
ver = [0]
ans = 0
for i in range(N+1):
  if vermax[N-i] <= 0:
    ans = -1
    break    
  else:
    ver.append(min(vermax[N-i], ver[i]+A[N-i]))
    ans += ver[i+1]
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cap = [0]*(N+1)
cap[-1] = A[-1]
max_nodes = 2**(N-1)
for i in range(N):
    cap[-2-i] = min(cap[-1-i] + A[-2-i], max_nodes)
    max_nodes //=2
cap.append(0)

ans = 0
nodes = 1
failed = False
for i in range(N+1):
    if nodes <= 0:
        failed = True
    ans += nodes
    nodes = min((nodes - A[i])*2, cap[i+1])

print(-1 if failed else ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cap = [0]*(N+1)
cap[-1] = A[-1]
max_nodes = 2**(N-1)
for i in range(N):
    cap[-2-i] = min(cap[-1-i] + A[-2-i], max_nodes)
    max_nodes //=2
cap.append(0)

ans = 0
nodes = 1
failed = False
for i in range(N+1):
    if nodes <= 0:
        failed = True
    ans += nodes
    nodes = min((nodes - A[i])*2, cap[i+1])
    print(ans, nodes)

print(-1 if failed else ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.append(0)
vermax = [1]
for i in range(N):
  vermax.append((vermax[i]-A[i])*2)
ver = [0]
ans = 0
for i in range(N+1):
  if vermax[i] <= 0:
    ans = -1
    break    
  else:
    ver.append(min(vermax[N-i], ver[i]+A[N-i]))
    ans += ver[i+1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    if N == 0:
        if A[0] == 1: return 1
        else: return - 1
    elif A[0] != 0: return - 1
    ans = [0] * (N + 2)
    ans[0] = 1
    ans[N + 1] = 0
    n2 = 1
    for i in range(1, N + 1):
        n2 *= 2
        ans[i] = min(n2, (ans[i - 1] - A[i - 1]) * 2)
    for i in range(N, -1, -1):
        t = ans[i + 1] + A[i]
        ans[i] = min(ans[i], t)
        if ans[i] < 1: return -1
    return sum(ans)

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

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    if N == 0:
        if A[0] == 1: return 1
        else: return - 1
    elif A[0] != 0: return - 1
    ans = [0] * (N + 2)
    ans[0] = 1
    ans[N + 1] = 0
    n2 = 1
    for i in range(1, N + 1):
        n2 *= 2
        if n2 < A[i]: return -1
        ans[i] = min(n2, (ans[i - 1] - A[i - 1]) * 2)
    for i in range(N, -1, -1):
        t = ans[i + 1] + A[i]
        if t < 0: return - 1
        ans[i] = min(ans[i], t)
    return sum(ans)

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

Submission status: Wrong Answer

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

SUM = sum(A)

ans = 0
node = 1
for i,leaf in enumerate(A):
    if i == 0:
        non_leaf = 1 - leaf
        ans += 1
    else:
        left,right = non_leaf,non_leaf*2
        if SUM < left or non_leaf <= 0:
            print(-1)
            exit()
        node = min(right,SUM)
        ans += node
        non_leaf = node - leaf
        SUM -= leaf

print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
sys.setrecursionlimit(2*100000) 

def dfs(i,pre,n,a,ans):
    if (pre < (a[i]+1)//2): return -1
    ans[i] += a[i]
    if (i == n):
        return a[i]

    pre =  pre*2 - a[i]
    u = dfs(i+1,pre,n,a,ans);
    if (u<0 or pre < (u+1)//2): return -1;
    ans[i] += min(pre, u)
    return min(pre, u) + a[i]



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

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

ans = [1] + [0]*n
u = dfs(1,1,n,a,ans)
if (a[0] != 0): u = -1

if (u >= 0):
    print(sum(ans))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import math

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

    if N == 0 and A[0] != 1:
        print(-1)
        return
    
    for i in range(1,N):
        sumA = sumA - A[i]
        B[i] = min(2 * B[i-1] - A[i], sumA)

    print(sum(A) + sum(B))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys 
sys.setrecursionlimit(2*100000) 

def dfs(i,pre,n,a,ans):
    if (pre*2 < a[i]): return -1
    ans[i] += a[i]
    if (i == n):
        return a[i]

    pre = min(int(1e18), pre*2 - a[i])
    u = dfs(i+1,pre,n,a,ans);
    if (u<0 or pre*2 < u): return -1;
    ans[i] += min(pre, u)
    return min(pre, u) + a[i]



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

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

ans = [1] + [0]*n
u = dfs(1,1,n,a,ans)
if (a[0] != 0): u = -1

if (u >= 0):
    print(sum(ans))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if 0 < A[0]:
        return '1' if n == 0 and A[0] == 1 else '-1'

    ret = 0
    R = np.zeros(n+1, int)
    R[0] = 1
    left = 0
    base = 0
    for i in range(1, n+1):
        R[i] = 2*R[i-1]-base

        j = left+np.searchsorted(R[left:i], base+A[i], 'right')
        if j == i and R[i] <= base+A[i] and i != n:
            ret = -1
            break

        ret += sum(R[left:j]-base)+(A[i]*(1+i-j))
        left = j
        base += A[i]

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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:
    ans = -1
if 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]

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

ans = 0
if A[0] >= 1:
    ans = -1
if N == 0:
    if A[0] == 0:
        ans = 1
    else:
        ans = -1
if 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]

    for i in range(N, 0, -1):
        if node_num[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] != 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:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if 0 < A[0]:
        return '1' if n == 0 and A[0] == 1 else '-1'

    ret = 0
    R = np.zeros(n+1, int)
    R[0] = 1
    left = 0
    base = 0
    for i in range(1, n+1):
        R[i] = 2*R[i-1]-base

        j = left+np.searchsorted(R[left:i], base+A[i], 'right')
        if j == i and R[i] < base+A[i]:
            ret = -1
            break

        ret += sum(R[left:j]-base)+(A[i]*(1+i-j))
        left = j
        base += A[i]

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

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
if 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]

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

ans = 0
if A[0] >= 1:
    ans = -1
if N == 0:
    if A[0] == 0:
        ans = 1
    else:
        ans = -1
if 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]

    for i in range(N, 0, -1):
        if node_num[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 = [1] * N
    sumA = sum(A)

    if N == 0 and A[0] != 1:
        print(-1)
        return
    
    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 sys 
sys.setrecursionlimit(2*100000) 

def dfs(i,pre,n,a,ans):
    if (pre*2 < a[i]): return -1
    ans[i] += a[i]
    if (i == n):
        return a[i]

    pre = pre*2 - a[i]
    u = dfs(i+1,pre,n,a,ans);
    if (u<0 or pre*2 < u): return -1;
    ans[i] += min(pre, u)
    return min(pre, u) + a[i]



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

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

ans = [1] + [0]*n
u = dfs(1,1,n,a,ans)
if (a[0] != 0): u = -1

if (u >= 0):
    print(sum(ans))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if n == 0:
        return '1' if A[0] == 1 else '-1'

    ret = 0
    R = np.zeros(n+1, int)
    R[0] = 1-A[0]
    left = 0
    base = 0
    for i in range(1, n+1):
        R[i] = 2*R[i-1]-base

        j = left+np.searchsorted(R[left:i], base+A[i], 'right')
        if j == i and R[i] < base+A[i]:
            ret = -1
            break

        ret += sum(R[left:j]-base)+(A[i]*(1+i-j))
        left = j
        base += A[i]

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
import sys 
sys.setrecursionlimit(2*100000) 

def dfs(i,pre,n,a,ans):
    if (pre*2 < a[i]): return -1
    ans[i] += a[i]
    if (i == n):
        return a[i]

    pre = pre*2 - a[i]
    u = dfs(i+1,pre,n,a,ans);
    if (u<0 or pre*2 < u): return -1;
    ans[i] += min(pre, u)
    return min(pre, u) + a[i]



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

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

ans = [1] + [0]*n
u = dfs(1,1,n,a,ans)
if (n!=0 and a[0] != 0): u = -1

if (u >= 0):
    print(sum(ans))
else:
    print(-1)

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 and b*2 >j-L[i]:
#                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:
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
k = 1 - a[0]
ans = 1

for i in range(1,n + 1):
    if k * 2 <= s:
        k *= 2
    else:
        k = s
    ans += k
    k -= a[i]
    s -= a[i]

if k == 0 and s == 0:
    print(ans)
else:
    print(-1)

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
if 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]

    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)