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:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n = int(input())
    n += 1
    a = list(map(int, input().split()))
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i] + a[i]
    ans = [0] * n
    for i in range(n):
        ans[i] = c[n] - c[i]
    if n == 1 and a[0] == 0:
        print(-1)
        return
    if n > 1 and a[0] > 0:
        print(-1)
        return
    ans[0] = min(1, ans[0])
    for i in range(1, n):
        ans[i] = min(ans[i], (ans[i-1]-a[i-1]) * 2)
        if ans[i] < a[i]:
            print(-1)
            return

    print(sum(ans))
main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n = int(input())
    n += 1
    a = list(map(int, input().split()))
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i] + a[i]
    ans = [0] * n
    for i in range(n):
        ans[i] = c[n] - c[i]
    if a[0] > 0 and n > 1:
        print(-1)
        return
    ans[0] = min(1, ans[0])
    for i in range(1, n):
        ans[i] = min(ans[i], (ans[i-1]-a[i-1]) * 2)
        if ans[i] < a[i]:
            print(-1)
            return

    print(sum(ans))
main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n = int(input())
    n += 1
    a = list(map(int, input().split()))
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i] + a[i]
    ans = [0] * n
    for i in range(n):
        ans[i] = c[n] - c[i]
    if a[0] > 0:
        print(-1)
        return
    ans[0] = min(1, ans[0])
    for i in range(1, n):
        ans[i] = min(ans[i], (ans[i-1]-a[i-1]) * 2)
        if ans[i] < a[i]:
            print(-1)
            return

    print(sum(ans))
main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n = int(input())
    n += 1
    a = list(map(int, input().split()))
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i] + a[i]
    ans = [0] * n
    for i in range(n):
        ans[i] = c[n] - c[i]
    if a[0] > 0:
        print(-1)
        return
    ans[0] = 1
    for i in range(1, n):
        ans[i] = min(ans[i], (ans[i-1]-a[i-1])* 2)
    if [i for i in ans if i < 0] or ans[-1] == 0:
        print(-1)
        return
    print(sum(ans))
main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n = int(input())
    n += 1
    a = list(map(int, input().split()))
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i] + a[i]
    ans = [0] * n
    for i in range(n):
        ans[i] = c[n] - c[i]
    if a[0] > 0:
        print(-1)
        return
    ans[0] = 1
    for i in range(1, n):
        ans[i] = min(ans[i], (ans[i-1]-a[i-1])* 2)
    if [i for i in ans if i < 0]:
        print(-1)
        return
    print(sum(ans))
main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import operator
from itertools import accumulate

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

  B[0] = 1 - A[0]

  d = A_sum[0] + B[0]
  for i in range(1, N+1):
    B[i] = min(B[i - 1] * 2 - A[i], A_sum[i+1])
    
    if B[i] < 0:
      return -1
    d += B[i]
  return d

print(main())

Submission status: Wrong Answer

Solution code:
import operator
from itertools import accumulate

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

  B[0] = 1 - A[0]

  d = A_sum[0] + B[0]
  for i in range(1, N+1):
    B[i] = min(B[i - 1] * 2 - A[i], A_sum[i+1])
    
    if B[i] < B[i - 1] - A[i] or B[i] < 0:
      return -1
    d += B[i]
  return d

print(main())

Submission status: Wrong Answer

Solution code:
n,*a,p=map(int,open(0).read().split()),print;t=sum(a);p(sum([w:=1]+[exit(p(-1))if(w:=min(2*(w-q),t:=t-q))<0 else w for q in a]))

Submission status: Wrong Answer

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = LIST()


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


node_min, node_max = [0]*(N+1), [0]*(N+1)
node_min[-1] = A[-1]
node_max[-1] = A[-1]
for i in reversed(range(N)):
    node_min[i] = max(node_min[i+1]//2, 1) + A[i]
    node_max[i] = node_max[i+1] + A[i]


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

ans = 1
node = 1
for i in range(1, N+1):
    node = min(node_max[i], 2*node)
    ans += node
    node = node - A[i]


print(ans)

Submission status: Wrong Answer

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = LIST()

# # init_nodes = [0]*(N+1)
# stems = [0]*(N+1)
# init_nodes[0] = 1
# stems[0] = 1

node_min, node_max = [0]*(N+1), [0]*(N+1)
node_min[-1] = A[-1]
node_max[-1] = A[-1]
for i in reversed(range(N)):
    node_min[i] = max(node_min[i+1]//2, 1) + A[i]
    node_max[i] = node_max[i+1] + A[i]


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

ans = 1
node = 1
for i in range(1, N+1):
    node = min(node_max[i], 2*node)
    ans += node
    node = node - A[i]


print(ans)

Submission status: Wrong Answer

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = LIST()

# # init_nodes = [0]*(N+1)
# stems = [0]*(N+1)
# init_nodes[0] = 1
# stems[0] = 1

node_min, node_max = [0]*(N+1), [0]*(N+1)
node_min[-1] = A[-1]
node_max[-1] = A[-1]
for i in reversed(range(N)):
    node_min[i] = max(node_min[i+1]//2, 1) + A[i]
    node_max[i] = node_max[i+1] + A[i]


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

ans = 0
node = 0
for i in range(N+1):
    ans += min(node_max[i], 2**i)

print(ans)

Submission status: Wrong Answer

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
import sys

N = INT()
A = LIST()

# # init_nodes = [0]*(N+1)
# stems = [0]*(N+1)
# init_nodes[0] = 1
# stems[0] = 1

node_min, node_max = [0]*(N+1), [0]*(N+1)
node_min[-1] = A[-1]
node_max[-1] = A[-1]
for i in reversed(range(N)):
    node_min[i] = max(node_min[i+1]//2, 1) + A[i]
    node_max[i] = node_max[i+1] + A[i]


if node_min[0] > 1:
    print(-1)
    sys.exit()

ans = 0
node = 0
for i in range(N+1):
    ans += min(node_max[i], 2**i)

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

    max_node = [0 for i in range(n+1)]
    min_node = [0 for i in range(n+1)]
    res = 0

    for i in range(n, -1, -1):
        if i == n:
            max_node[i] = A[i]
            min_node[i] = A[i]
        elif i == 0:
            max_node[i] = 1
            min_node[i] = 1
        elif i == 1 and n != 1:
            max_node[i] = 2
            min_node[i] = math.ceil(min_node[i+1] /2) + A[i]
        else:
            max_node[i] = max_node[i+1] + A[i]
            min_node[i] = math.ceil(min_node[i+1] / 2) + A[i]
        
    # print('max_node:', max_node)
    # print('min_node:', min_node)

    for i in range(n):
        if i == 0:
            if n == 0 and A[i] != 1:
                res = -1
                break
            elif n != 0 and A[i] != 0:
                res = -1
                break
        else:
            if max_node[i] > 2 * (max_node[i-1] - A[i-1]):
                max_node[i] = 2 * (max_node[i-1] - A[i-1])
            if max_node[i] < min_node[i]:
                res = -1
                break
    
    if res == -1:
        print(res)
    else:
        print(sum(max_node))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] == 0:
    print(-1)
    exit()
if n != 0 and a[0] >= 1:
    print(-1)
    exit()
ar = list(reversed(a))
#print(ar)
com = [ar[0]]
for i in range(n):
    com.append(com[i] + ar[i+1])
#print(com)
com.reverse()
ans = 1
val = 1
for i in range(1,n+1):
    val *= 2
    ans += min(val,com[i])
    val -= a[i]
    if (i < n and val <= 0) or (i == n and val < 0):
        print(-1)
        exit()
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[N] = A[N]
for i in range(N-1, -1, -1):
    cond1[i] = cond1[i+1] + A[i]

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

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

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

ans = sum(cond2)
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], 2**i)
print(ans)

Submission status: Wrong Answer

Solution code:
# original submission at https://atcoder.jp/contests/nomura2020/submissions/13740836
N = int(input())
A = list(map(int, input().split()))
def solve():
    if A[0] != 0:
        if N == 0 and A[0] == 1:
            print(1)
        else:
            print(-1)
        return 0
    add_ans = list()
    add_ans.append(1)
    stem = list()
    stem.append(1)
    for i in range(1, N+1):
        last_stem = stem[-1]
        add_ans.append(2*last_stem)
        stem.append(min(last_stem*2 - A[i], 1000000000000000000))
        if stem[-1] < 0:
            print(-1)
            return 0
    
    illegal = list()
    illegal.append(stem[-1])
    ind = N
    legal_stem = list()
    legal_stem.append(0)
    while illegal[-1] > 0:
        last_illegal = illegal[-1]

        if last_illegal- legal_stem[-1]- A[ind] > 0:
            illegal.append((last_illegal- legal_stem[-1]- A[ind])//2)
            legal_stem.append(stem[ind-1] - illegal[-1])
        else:
            illegal.append(0)
        ind -= 1
    # print(stem)
    # print(illegal)
    # print(legal_stem)
    len_ill = len(illegal)
    ans = 0
    for i in range(N+1):
        ans += add_ans[i]
        if i < len_ill:
            ans -= illegal[i]
    # print(add_ans)
    # print(illegal)
    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
if a[0] != 0:
    ans = -1
p = [1-a[0]]
for i in range(n-1):
    if 2*p[-1]-a[i+1] <= 0:
        ans = -1
    p.append(2*p[-1]-a[i+1])
if n == 0 and a[0] == 1:
    print(1)
elif n == 1:
    if a[0] == 0 and a[1] == 1:
        print(2)
    elif a[0] == 0 and a[1] == 2:
        print(3)
    else:
        print(-1)
elif ans == -1:
    print(-1)
else:
    a.reverse()
    p.reverse()
    ans = 0
    ans += a[0]
    q = a[0]
    for i in range(1,n+1):
        if q < p[i-1]:
            ans += q+a[i]
            q = q+a[i]
        else:
            ans += p[i-1]+a[i]
            q = p[i-1] + a[i]
    if 2**n < -(-q//2)+a[0]:
        ans = -1        
    print(ans)

Submission status: Wrong Answer

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

node_max = [1]
for i in range(1, n+1):
    node_max.append(min(10**9, node_max[i-1]*2-a[i]))

a.reverse()
node_max.reverse()

node_max2 = [a[0]]
node_min2 = [a[0]]

for i in range(n):
    node_max2.append(node_max2[-1]+a[i+1])
    node_min2.append((node_min2[-1]+1)//2+a[i+1])

if node_min2[-1] != 1:
    print(-1)
else:
    ans = 0
    for i in range(n+1):
        ans += min(node_max[i]+a[i], node_max2[i])

    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.reverse()
min_max = [[] for _ in range(N+1)]

def main():
    min_max[0] = [A[0], A[0]]
    for i in range(1, N+1):
        a = A[i]
        pre_min, pre_max = min_max[i-1]
        min_max[i] = [(1+pre_min)//2 +a, pre_max +a]
    min_max.reverse()
    if min_max[0][0] != 1:
        return
    A.reverse()
    ans = 1
    pre = 1
    for i in range(1, N+1):
        a = A[i-1]
        pre = min(2*(pre -a), min_max[i][1])
        ans += pre
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys

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

limit = [[a[0], a[0]]]
for i in range(0, n):
    low = -(-limit[i][0] // 2) + a[i + 1]
    high = limit[i][1] + a[i + 1]
    
    limit.append([low, high])
    
limit = limit[::-1]
a = a[::-1]

if 1 < limit[0][0]:
    print(-1)
    sys.exit()

ans, leaf = 1, 2
for i in range(1, n):
    ans += min(limit[i][1], leaf)
    leaf = 2 * (leaf - a[i])
    
ans += a[n]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
leaf = inpl()
mx = [1]
pre = [1]
x = 1
if leaf[0] != 0:
    print(-1)
    quit()
for i in range(1,n+1):
    if x <= 10**10: x *= 2
    tmp = pre[-1]*2 - leaf[i]
    if (i != n and tmp <= 0) or (i==0 and tmp < 0) or leaf[i] > x:
        print(-1)
        quit()
    pre.append(tmp)
# print(pre)
res = [0] * (n+1)
res[0] = 1
res[-1] = leaf[-1]
for i in range(1,n)[::-1]:
    tmp = res[i+1] + leaf[i]
    if pre[i-1]*2 < tmp:
        tmp = pre[i-1]*2
    if tmp < leaf[i]:
        print(-1)
        quit()
    res[i] = tmp
print(sum(res))

Submission status: Wrong Answer

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

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

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

# 成り立つ木が作れるか判定してみる
en = [0]
en[0] = 1

for a in A_list:
    tmp = en[-1] - a
    if tmp < 0:
        print(-1)
        exit()
    en.append(tmp * 2)

en = en[:-1]

branch = A_list[-1]
res = A_list[-1]
nodes = en[-1]
for a, ena in zip(A_list[-2::-1], en[-2::-1]):
    branch = min(branch+a, ena)
    res += branch

print(res)

Submission status: Wrong Answer

Solution code:
DEBUG = False

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

if N == 0:
    if A[0]  == 1:
        print(1)
    else:
        print(-1)
else:
    ranges = []
    pre_range = []
    for i in range(len(A)-2, -1, -1):
        if i == (len(A)-2):
            min_val = (A[i+1] + 1) // 2 + A[i]
            max_val = A[i+1] + A[i]
        else:
            pre_min_val, pre_max_val = pre_range
            min_val = (pre_min_val + 1) // 2 + A[i]
            max_val = pre_max_val + A[i]
        ranges.append([min_val, max_val])
        pre_range = [min_val, max_val]
        if DEBUG:
            print("i: {}, min_val: {}, max_val: {}".format(i, min_val, max_val))
    ranges = ranges[::-1]
    if DEBUG:
        print("ranges: {}".format(ranges))
    if 1 in [i for i in range(ranges[0][0], ranges[0][1])]:
        list_num_nodes = []
        list_num_nodes.append(1)
        pre_num_nodes = 1
        for i in range(1, len(ranges)):
            min_val, max_val = ranges[i]
            if DEBUG:
                print("i: {}, max_val: {}".format(i, max_val))
                print("num_nodes: {}".format(num_nodes))
            num_nodes = min((pre_num_nodes-A[i-1])*2, max_val)
            list_num_nodes.append(num_nodes)
            pre_num_nodes = num_nodes
            if num_nodes < pre_min_val:
                print(-1)
                exit(0)
        list_num_nodes.append(A[-1])
        if DEBUG:
            print("list_num_nodes: {}".format(list_num_nodes))
        print(sum(list_num_nodes))
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = list(map(int, input().split()))
    node_count = [0] * (N+1)
    for i, a in enumerate(A[::-1]):
        if i == 0:
            node_count[N] = a
            continue
        node_count[N-i] = node_count[N-i+1] + a
    can_build = True
    for i, a in enumerate(A):
        if i == 0:
            if N > 0 and a > 0:
                can_build = False
                break
            node_count[0] = min(node_count[0], 1)
            continue
        if i < N and a >= 2**i:
            can_build = False
            break
        node_count[i] = min(node_count[i], node_count[i-1]*2-A[i-1]*2)
    if can_build:
        ans = sum(node_count)
    else:
        ans = -1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

sum_leaves = [0]*(n+1)
sum_leaves[0] = leaves[0]
for depth in range(n):
    sum_leaves[depth+1] = sum_leaves[depth] + leaves[depth+1]

ans = 0

root = [None] * (n + 1)
root[0] = 1
if root[0] + leaves[0] != 1:
    print(-1)
else:
    for depth in range(n):
        root[depth+1] = min(2*root[depth]-leaves[depth+1],
                            sum_leaves[n]-sum_leaves[depth+1])
        if root[depth + 1] < root[depth] - leaves[depth + 1] or root[depth+1] < 0:
            print(-1)
            break
    else:
        print(sum(root)+sum(leaves))

Submission status: Wrong Answer

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

sum_leaves = [0]*(n+1)
sum_leaves[0] = leaves[0]
for depth in range(n):
    sum_leaves[depth+1] = sum_leaves[depth] + leaves[depth+1]

ans = 0

root = [None] * (n + 1)
root[0] = 1
if root[0] + leaves[0] != 1:
    print(-1)
else:
    for depth in range(n):
        root[depth+1] = min(2*root[depth]-leaves[depth+1],
                            sum_leaves[n]-sum_leaves[depth+1])
        if root[depth + 1] < root[depth] - leaves[depth + 1] or root[depth+1] < 0:
            print(-1)
            break
    else:
        print(root)
        print(sum(root)+sum(leaves))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = list(map(int, input().split()))
    node_count = [0] * (N+1)
    for i, a in enumerate(A[::-1]):
        if i == 0:
            node_count[N] = a
            continue
        node_count[N-i] = node_count[N-i+1] + a
    can_build = True
    for i, a in enumerate(A):
        if i == 0 and N > 0:
            if a > 0:
                can_build = False
                break
            node_count[0] = min(node_count[0], 1)
            continue
        if i < N and a >= 2**i:
            can_build = False
            break
        node_count[i] = min(node_count[i], node_count[i-1]*2-A[i-1]*2)
    if can_build:
        ans = sum(node_count)
    else:
        ans = -1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

sum_leaves = [0]*(n+1)
sum_leaves[0] = leaves[0]
for depth in range(n):
    sum_leaves[depth+1] = sum_leaves[depth] + leaves[depth+1]

ans = 0

root = [None] * (n + 1)
root[0] = 1
if root[0] + leaves[0] != 1:
    print(-1)
else:
    for depth in range(n):
        root[depth+1] = min(2*root[depth]-leaves[depth+1],
                            sum_leaves[n]-sum_leaves[depth+1])
        if root[depth + 1] < root[depth] - leaves[depth + 1]:
            print(-1)
            break
    else:
        print(sum(root)+sum(leaves))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = list(map(int, input().split()))
    node_count = [0] * (N+1)
    for i, a in enumerate(A[::-1]):
        if i == 0:
            node_count[N] = a
            continue
        node_count[N-i] = node_count[N-i+1] + a
    can_build = True
    for i, a in enumerate(A):
        if i == 0:
            if a > 0:
                can_build = False
                break
            node_count[0] = min(node_count[0], 1)
            continue
        if i < N and a >= 2**i:
            can_build = False
            break
        node_count[i] = min(node_count[i], node_count[i-1]*2-A[i-1]*2)
    if can_build:
        ans = sum(node_count)
    else:
        ans = -1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    A = list(map(int, input().split()))
    node_count = [0] * (N+1)
    for i, a in enumerate(A[::-1]):
        if i == 0:
            node_count[N] = a
            continue
        node_count[N-i] = node_count[N-i+1] + a
    can_build = True
    for i, a in enumerate(A):
        if i == 0:
            if a > 0:
                can_build = False
                break
            node_count[0] = min(node_count[0], 1)
            continue
        if i < N+1 and a >= 2**i:
            can_build = False
            break
        node_count[i] = min(node_count[i], node_count[i-1]*2-A[i-1]*2)
    if can_build:
        ans = sum(node_count)
    else:
        ans = -1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

sum_leaves = [0]*(n+1)
sum_leaves[0] = leaves[0]
for depth in range(n):
    sum_leaves[depth+1] = sum_leaves[depth] + leaves[depth+1]

ans = 0

root = [None] * (n + 1)
root[0] = 1
if root[0] > sum_leaves[n] - sum_leaves[0]:
    print(-1)
else:
    for depth in range(n):
        root[depth+1] = min(2*root[depth]-leaves[depth+1],
                            sum_leaves[n]-sum_leaves[depth+1])
        if root[depth + 1] < root[depth] - leaves[depth + 1]:
            print(-1)
            break
    else:
        print(root)
        print(sum(root)+sum(leaves))

Submission status: Wrong Answer

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

sum_leaves = [0]*(n+1)
sum_leaves[0] = leaves[0]
for depth in range(n):
    sum_leaves[depth+1] = sum_leaves[depth] + leaves[depth+1]

ans = 0

root = [None] * (n + 1)
root[0] = 1
if root[0] < sum_leaves[n] - sum_leaves[0]:
    print(-1)
else:
    for depth in range(n):
        root[depth+1] = min(2*root[depth]-leaves[depth+1],
                            sum_leaves[n]-sum_leaves[depth+1])
        if root[depth + 1] < root[depth] - leaves[depth + 1]:
            print(-1)
            break
    else:
        print(root)
        print(sum(root)+sum(leaves))

Submission status: Wrong Answer

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

from_deeper_bind = [[0,0] for i in range(N+1)]
from_deeper_bind[N][0] = from_deeper_bind[N][1] = A[N]
node_num = [1]*(N+1)
node_num[N] = A[N]
from_shallower_bind = [1]*(N+1)

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


if not from_deeper_bind[0][0] <= 1 <= from_deeper_bind[0][1]:
    print(-1)
    exit()


for i in range(1,N):
    from_shallower_bind[i] = (node_num[i-1]-A[i-1])*2
    node_num[i] = min(from_shallower_bind[i],from_deeper_bind[i][1])

print(sum(node_num))

Submission status: Wrong Answer

Solution code:
N=int(input())
H=list(map(int,input().split()))
depth=[0]*(N+1)
depth[0]=1
if N==0:
    if H[0]!=1:
        print(-1)
        exit()
    else:
        print(1)
        exit()
else:
    if H[0]!=0:
        print(-1)
        exit()
    for i in range(1,N+1):
        depth[i]=(depth[i-1]-H[i-1])*2
        if depth[i]<0:
            print(-1)
            exit()
    # if depth[N-1]*2<H[N]:
    #     print(-1)
    #     exit()
    # else:
    depth[N]=min(depth[N],H[N])
    for i in range(N - 1, -1, -1):
        if depth[i + 1] == 0:
            if H[i] != 0:
                depth[i] = H[i]
            else:
                depth[i] = 0
            if i == 0:
                depth[i] = 1
        else:
            depth[i] = min(depth[i + 1] + H[i], depth[i])
    print(sum(depth))

Submission status: Wrong Answer

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

ans = 0
nodes_min = [0] * (n + 1)
nodes_max = [0] * (n + 1)
nodes_min[n] = leaves[n]
nodes_max[n] = leaves[n]

for depth in range(n, 0, -1):
    root_min = nodes_min[depth] // 2 + nodes_min[depth] % 2
    nodes_min[depth - 1] = leaves[depth - 1] + root_min
    root_max = nodes_max[depth]
    nodes_max[depth - 1] = leaves[depth - 1] + root_max
nodes = [0] * (n + 1)
nodes[0] = 1
for depth in range(n):
    roots = nodes[depth]-leaves[depth]
    nodes[depth + 1] = min(roots * 2, nodes_max[depth + 1])
    if nodes[depth+1] < nodes_min[depth+1]:
        print(-1)
        break
else:
    print(sum(nodes))

Submission status: Wrong Answer

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

sum_leaves = [0]*(n+1)
sum_leaves[0] = leaves[0]
for depth in range(n):
    sum_leaves[depth+1] = sum_leaves[depth] + leaves[depth+1]

ans = 0

root = [None] * (n + 1)
root[0] = 1
for depth in range(n):
    root[depth+1] = min(2*root[depth]-leaves[depth+1],
                        sum_leaves[n]-sum_leaves[depth+1])
    if root[depth + 1] < root[depth] - leaves[depth + 1]:
        print(-1)
        break
else:
    print(sum(root)+sum(leaves))

Submission status: Wrong Answer

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

print(sum(depth))

Submission status: Wrong Answer

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

print(sum(depth))