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: Runtime Error

Solution code:

from itertools import accumulate

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

list2 = [1]*(N+1)

for i in range(1, N+1):
    list2[i] = list2[i-1]*2 - list1[i]

list1_ = list(reversed(list1))

list3 = list(accumulate(list1_))
list4 = list(reversed(list3))

count = 0
finish = 0
for j in reversed(range(N+1)):
    if list4[j]/2 > list2[j-1]:
        finish = j+1  
        break
    else:
        count += list4[j]
    
count2 = sum(list1[0:j+1])
count3 = sum(list2[0:j+1])

sum1 = count + count2 + count3
for k in range(1,N+1):
    if list1[k-1]*2 < list2[k]:
        print(-1)
        breakA
    elif k == N:
        print(sum1)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

def main():
    n = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    INF = 10**9
    g_l = [INF] * (n + 1)
    g_l[0] = 1
    if n != 0 and A[0] == 1:
        print('-1')
        return 0
    
    for x in range(n-1):
        max_nord = (g_l[x] - A[x]) * 2
        # 存在できるノード数の最大より葉の数の多い
        if max_nord < A[x+1]:
            print('-1')
            return 0
        g_l[x+1] = max_nord
    
    #最後の深さと葉の数が合わない場合だめ
    if g_l[-2] * 2 < A[-1]:
        print('-1')
        return 0
    g_l[-1] = A[-1]
    #print(g_l)

    for i in range(n-1, 0, -1):
        # これだけなら最多
        # 親ノードになれる最大の数 + 葉の数の場合
        if g_l[i] > g_l[i+1] + A[i]:
            g_l[i] = g_l[i+1] + A[i]
            #print(g_l)
    print(sum(g_l))
    return 0

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

cnt = 0
pre = 0

for i in a:
  if i > pre*2:
    print(-1)
    exit()
  
  if i == 0:
    pre = (pre==0)×2 + pre*2
    cnt += pre
  else:
    pre = (pre - i)*2
    cnt += i

Submission status: Runtime Error

Solution code:
cur = 1
ans = 1
n = int(input())
b = input()
b = b.split(" ")
a = []
maxi = pow(2, 1000000)
for i in b:
	a.append(int(i))
flag = 1
for i in range(n):
	if cur <= a[i]:
		flag = 0
		print(-1)
		break
	cur = cur - a[i]
	temp = cur
	cur = cur * 2
	cur = min(cur, maxi)
	ans = ans + cur
if flag:
	ans = ans - cur + a[n]
	if a[n] < temp:
		extra = temp - a[n]
		while i >= 0:
			ans = ans - extra
			extra = extra - a[i] - a[i + 1];
			if extra < 0:
				break
			extra = extra // 2
			i = i - 1
	print(ans)

Submission status: Runtime Error

Solution code:

def main():
    N = int(input())
    two = [ 2**i for i in range(N+1)]
    A = list(map(int,input().split(' ')))
    for i in range(N+1):
        if two[i] > A[i]:
            print(-1)
            exit(1)
   

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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()
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])*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: Runtime Error

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

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

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

nleaf = 1
ans = 0
v = list()

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

if nleaf < a[i]:
    print(-1)
    exit()

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

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 9)

N = int(input())

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

R = [0]*2**(N+1)
R[0]= 1

res = 0
k = 0
count = []

def dfs():
    global k
    k += 1
    if k == N:
        if A[k] <= 2 * R[k-1] and A[k] >= R[k-1] :
            count.append(sum(A) + sum(R))
        k-= 1
        return
    if 1 + A[k] <= 2 * R[k-1]:
        for i in range(R[k-1] - A[k], 2 * R[k-1] - A[k] + 1):
            R[k] = i
            dfs()
    k -= 1
    return

dfs()

if count == []:
    res = -1
else:
    res = max(count)

print(res)

Submission status: Runtime Error

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

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

ret = 1
children = 1

for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    if children == 0 and i = N - 1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Runtime Error

Solution code:
n = int(input())

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

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

if t > 1:
    print('-1')
else:
    print(int(d))

Submission status: Runtime Error

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

An = An[::-1] #配列を逆に

Sum = 0
x = 1

def think():
    for i in range(N):
        s = 2**i
        if An[i] > s:
            x = 0
            break

num_list = []
for i in range(N):
    num_list.append(i+1)
    num_list.append(i+1)

if An[0] ==0:
    print("-1")
elif think() == 0:
    print("-1")
else:
    for i in An:
        if i<2:
            x = 2-i
            for j in range(x):
                del num_list[-1] #二分木の不足分を排除
        else:
            for j in range(i):
                Sum += num_list[-1]
                del num_list[-1]

    print(Sum)

Submission status: Runtime Error

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

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

nodeM = nodeS[0]-A[0]

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]


for i in range(N):
    nodeS[i+1] = nodeM*2
    nodeM = nodeS[i+1] - A[i+1]
    if nodeS[i] >= laS[i]:
        j = i
        break
    if i == N-1:
        if nodeS[i+1] >= laS[i+1]:
            print(sum(nodeS))
            exit()
        else:
            print(-1)
            exit()

for i in nodeS:
    if i < 0:
        print(-1)
        exit()
ans = sum(nodeS[:j]) + sum(laS[j::])
print(ans)

Submission status: Runtime Error

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


node_list = []
i = 0


node = 1
sum_leaf = sum(A)
for i in range(N+1):
#     print("sum_leaf", sum_leaf)
#     print("node", node)
    node_list.append(node)
    if node < A[i]:
        flg = -1
        break
    elif node == A[i]:
        flg = 0
        break
    else:
        
        if node < sum_leaf:
            if 2*(node-A[i])<sum_leaf:
                next_node = 2*(node-A[i])
                sum_leaf -= A[i]
                node = next_node
            else:
                sum_leaf -= A[i]
                next_node = sum_leaf
                node = next_node
        else:
            sum_leaf -= A[i]
            next_node = sum_leaf
            node = next_node
if flg ==-1:
    print(-1)
elif flg ==0:
    if len(node_list)==(N+1):
        print(sum(node_list))
    else:
        print(-1)
else:
    print(sum(node_list))

Submission status: Runtime Error

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

for i in range(min(N,25)):
    if arr[i] > i*2:
        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])*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: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
C=1
m=[]
for i in range(n-1):
   C=2*(C-l[i])
   m.append(C)
if C<l[n]:
    print(-1)
else:
    print(sum(m)+1+l[n]-m[n-1])

Submission status: Runtime Error

Solution code:
from collections import deque
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#import sys 
#sys.setrecursionlimit(10**8) #N回まで再起を許可する。

# = map(int,input().split())

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

# = [list(map(int,input().split())) for _ in range(XXXX)]

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


    que = deque()
    que.appendleft([0,1,0])

    while que:
        x = que.popleft()
        d = x[0]
        point = x[1]
        counter = x[2]
        counter += point
        ad = ad

        if d == n:
            if point == ad:
                print(counter)
                exit()
            else:
                continue

        #if point-ad <= 0:
        #    #すべて葉 or 葉の数がadに足りない。
        #    continue

        for nextp in range(point-ad,(point-ad)*2+1):
            if nextp-a[d+1] >= 0:
                que.appendleft([d+1,nextp,counter])

    print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

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

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

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

print(ans)

Submission status: Runtime Error

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

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

if d[-1] < 0:
    print(-1)
    print(aaaaaaa)
    exit()
else:
    d[-1] = A[-1]
for i in range(N, 0, -1):
    x = d[i]
    x += A[i-1]
    if d[i-1] * 2 < x:
        y = x - A[i-1]
        if (y+1) // 2 + A[i-1] <= d[i-1] * 2:
            x = d[i-1] * 2
    if d[i-1]*2 < x:
        print(-1)
        print(aaaaaaa)
        exit()
    d[i-1] = min(x, d[i-1]+A[i-1])
# print(d)
print(sum(d))

Submission status: Runtime Error

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()
val = 1
ans = 1
vlis = []
for i in range(n):
    ans += val * 2
    val *= 2
    val -= a[i+1]
    if val < 0:
        print(-1)
        exit()
    if val == 0 and i != (n-1):
        print(-1)
        exit()
    vlis.append(val-a[i+1])
val3 = (vlis[-2] - a[-2])
val -= val3
if val//2 > vlis[-2]:
    print(-1)
    exit()
ans -= val//2
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = [0]*(n+1)
leaf = []
x = 1
for i in range(n+1):
    if a[i] > 2*x:
        print(-1)
        exit()
    else:
        if a[i] == 0:
            ans[i] = x
            x *= 2
        else:
            ans[i] = x-a[i]
            x = (x-a[i])*2
            leaf.append(a[i])
            if i == n:
                print(chk)
                for j in range(chk, n+1):
                    ans[j] = a[i]
                    break
            chk = i
print(ans)
print(leaf)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
import numpy as np
from heapq import heapify, heappop, heappush
import copy
from math import gcd, ceil
from collections import deque
# queueとして使う場合 push, popleftを使う
from bisect import bisect_left, bisect_right
# bisect_left: 配列の順序関係が崩れない条件で挿入することができる一番左の点
# bisect_right: 配列の順序関係が崩れない条件で挿入することができる一番右の点
# A = [1, 1, 1, 2, 2, 2, 4]
# print(bisect_left(A, 2))  # 3
# print(bisect_right(A, 2))  # 6
# print(bisect_left(A, 3))  # 6
# print(bisect_right(A, 3))  # 6


def main():
    N = int(input())
    A = [int(c) for c in input().split()]

    if N == 0:
        if A[0] == 1:
            print(1)
        else:
            print(-1)
    elif A[0] == 1:
        print(-1)
        sys.exit()
    now = 0
    p = 1
    num = 1
    sums = [0] * N
    sums[N - 1] = A[N]
    if N > 1:
        sums[N - 2] = A[N]
    if N > 2:
        sums[N - 3] = A[N]
    if N > 3:
        for i in range(N - 4, -1, -1):
            sums[i] = sums[i + 1] + A[i + 3]
    while(N > now):
        max_ = sums[now]
        c = A[now + 1]
        p = min(max_, p * 2 - c)
        if p < 0:
            print(-1)
            sys.exit()
        num += p + c
        now += 1

    if c != A[-1]:
        # 最後の子
        print(-1)
        sys.exit()
    print(num - p)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

nodeM = nodeS[0]-A[0]

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]


for i in range(N):
    nodeS[i+1] = nodeM*2
    nodeM = nodeS[i+1] - A[i+1]
    if nodeS[i] >= laS[i]:
        j = i
        break
    if i == N-1:
        if nodeS[i+1] >= laS[i+1]:
            j = i+1
        else:
            print(-1)
            exit()

for i in nodeS:
    if i < 0:
        print(-1)
        exit()
ans = sum(nodeS[:j]) + sum(laS[j::])
print(ans)

Submission status: Runtime Error

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

N = int(input().rstrip('\n'))
As =[int(x) for x in input().rstrip('\n').split()] 
points = 1
deep={1:1}
miss = 0
if As[0]>0:
  miss +=1
else:
  for i in range(1,N):
    check = 2*deep[i]
    if check <= As[i]:
      miss += 1
      break
    else:
      points += check
      deep[i+1] = check-As[i]
  if deep[N-1]*2 < As[N-1]:
    miss += 1
if miss == 0:
  points += As[-1]
  for i in range(N):
    if i ==N-2:
      miss += 1
      break
    if deep[N-i] > As[-1-i]:
      sin = deep[N-i] -As[-1-i]
      points -= sin
      As[-2-i] += As[-1-i]
    else:
      break
if miss >0 :
  points=-1
print(points)

Submission status: Runtime Error

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

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

if d[-1] < 0:
    print(-1)
    print(aaaaaaa)
    exit()
else:
    d[-1] = A[-1]
for i in range(N, 0, -1):
    x = d[i]
    x += A[i-1]
    if d[i-1] * 2 < x:
        y = x - A[i-1]
        if (y+1) // 2 + A[i-1] <= d[i-1] * 2:
            x = d[i-1] * 2
    if d[i-1]*2 < x:
        print(-1)
        print(aaaaaaa)
        exit()
    d[i-1] = min(x, d[i-1]+A[i-1])
print(d)
print(sum(d))

Submission status: Runtime Error

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

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

A.reverse()
MAX.reverse()
ans = []
s = 0
for i,a in enumerate(A):
    if MAX[i] < s//2 + a:
        ans[-1] = (MAX[i] - a) * 2 + 1
        s = MAX[i]
    else:
        s += a
        s = min(MAX[i],s)
    ans.append(s)
print(sum(ans))

Submission status: Runtime Error

Solution code:
def main():
    
N=int(input())
A=list(map(int,input().split()))
sum_value = sum(A)
chiled_value = 1
top_value = 1
if(N==0 & A[0]==1):
    print(-1)
    exit()
if(A[0]!=0):
    print(-1)
    exit()
for i in range(1,N):
    if(sum_value >= chiled_value*2):
        top_value += chiled_value*2
        chiled_value = chiled_value*2-A[i]
        sum_value=sum_value-A[i]
    elif(sum_value < chiled_value*2):
        chiled_value=sum_value
        top_value += chiled_value
        sum_value=sum_value-A[i]
    if(A[i]>=2**i):
        print(-1)
        exit()
print(top_value+A[N])

Submission status: Runtime Error

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

N = int(input().rstrip('\n'))
As =[int(x) for x in input().rstrip('\n').split()] 
points = 1
deep={1:1}
miss = 0
if As[0]>0:
  miss +=1
else:
  for i in range(1,N):
    check = 2*deep[i]
    if check <= As[i]:
      miss += 1
      break
    else:
      points += check
      deep[i+1] = check-As[i]
  if deep[N-1]*2 < As[N-1]:
    miss += 1
if miss == 0:
  points += As[-1]
  for i in range(N):
    if i ==N-1:
      miss += 1
      break
    if deep[N-i] > As[-1-i]:
      sin = deep[N-i] -As[-1-i]
      points -= sin
      As[-2-i] += As[-1-i]
    else:
      break
if miss >0 :
  points=-1
print(points)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 10)

N = int(input())

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

R = [0]*2**(N+1)
R[0]= 1

res = 0
k = 0
count = []

def dfs():
    global k
    k += 1
    if k == N:
        if A[k] <= 2 * R[k-1] and A[k] >= R[k-1] :
            count.append(sum(A) + sum(R))
        k-= 1
        return
    if 1 + A[k] <= 2 * R[k-1]:
        for i in range(R[k-1] - A[k], 2 * R[k-1] - A[k] + 1):
            R[k] = i
            dfs()
    k -= 1
    return

dfs()

if count == []:
    res = -1
else:
    res = max(count)

print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
arr = list(map(int, input().split()))
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])*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: Runtime Error

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

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

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

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]


for i in range(N):
    nodeS[i+1] = nodeM[i]*2
    nodeM[i+1] = nodeS[i+1] - A[i+1]
    if nodeS[i] >= laS[i]:
        j = i
        break
    if i == N-1:
        if nodeS[i+1] >= laS[i+1]:
            j = i+1
        else:
            print(-1)
            exit()
for i in nodeM:
    if i < 0:
        print(-1)
        exit()
for i in nodeS:
    if i < 0:
        print(-1)
        exit()
ans = sum(nodeS[:j]) + sum(laS[j::])
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 7)

N = int(input())

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

R = [0]*2**(N+1)
R[0]= 1

res = 0
k = 0
count = []

def dfs():
    global k
    k += 1
    if k == N:
        if A[k] <= 2 * R[k-1] and A[k] >= R[k-1] :
            count.append(sum(A) + sum(R))
        k-= 1
        return
    if 1 + A[k] <= 2 * R[k-1]:
        for i in range(R[k-1] - A[k], 2 * R[k-1] - A[k] + 1):
            R[k] = i
            dfs()
    k -= 1
    return

dfs()

if count == []:
    res = -1
else:
    res = max(count)

print(res)

Submission status: Runtime Error

Solution code:
n = int(input())

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

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

if d <= k:
    print('-1')
else:
    print(int(d))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)


class Solver:
    def __init__(self, depth_list):
        self.ans = -1
        self.depth_list = depth_list
 
    @lru_cache(None)
    def helper(self, d, current_sum, min_nodes, max_nodes):
        if d == 0:
            if min_nodes == 1:
                self.ans = max(self.ans, current_sum+1)
                return
            else:
                return
        else:
            max_size = 2 ** d
            # if number of leaf is grater than the size of max nodes for the layer
            if min_nodes > max_size:
                return
            for c in range(min_nodes, max_nodes):
                if c > max_size:
                    continue
                min_nodes = (c // 2) + (c % 2) + self.depth_list[d - 1]
                max_nodes = c + self.depth_list[d - 1]+1
                self.helper(d-1, current_sum+c, min_nodes, max_nodes)
 
 
def main():
    N = int(input().strip())
    depth_list = [int(i) for i in input().strip().split()]
    solver = Solver(depth_list)
    solver.helper(N, 0, depth_list[-1], depth_list[-1]+1)
 
    return solver.ans


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

Submission status: Runtime Error

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

N = int(input().rstrip('\n'))
As =[int(x) for x in input().rstrip('\n').split()] 
points = 1
deep={1:1}
miss = 0
if As[0]>0:
  miss +=1
else:
  for i in range(1,N):
    check = 2*deep[i]
    if check <= As[i]:
      miss += 1
      break
    else:
      points += check
      deep[i+1] = check-As[i]
  if deep[N-1]*2 < As[N-1]:
    miss += 1
if miss == 0:
  points += As[-1]
  for i in range(N):
    if deep[N-i] > As[-1-i]:
      sin = deep[N-i] -As[-1-i]
      points -= sin
      As[-2-i] += As[-1-i]
    else:
      break
if miss >0 :
  points=-1
print(points)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
temp=1
summ=0
cont=0
templist=[1]
for i in range(N+1):
  #print(temp)
  if A[i]<temp:
    if i<N:
      summ+=temp
      temp=2*(temp-A[i])
      templist.append(temp)
    if i==N:
      summ+=temp
      cont+=1
  elif A[i]==temp:
    if i==N:
      summ+=temp
      #templist.append(temp)
      cont+=1
    else:
      print("-1")
      break
  else:
    print("-1")
    break
    
if cont==1:
  #if A[N]==temp:
  #  print(summ)
  #else:
  #print(templist)
  #print(A)
  comp=A[-1]
  for i in range(N+1):
    summ-=(templist[-(i+1)]-comp)
    comp+=A[-(i+2)]
    #print(comp)
    #print(templist[-(i+2)])
    #print(summ)
    if comp>templist[-(i+2)]:
      print(summ)
      break

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.buffer.readline

N = int(input())

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

R = [0]*2**(N+1)
R[0]= 1

res = 0
k = 0
count = []

def dfs():
    global k
    k += 1
    if k == N:
        if A[k] <= 2 * R[k-1] and A[k] >= R[k-1] :
            count.append(sum(A) + sum(R))
        k-= 1
        return
    if 1 + A[k] <= 2 * R[k-1]:
        for i in range(R[k-1] - A[k], 2 * R[k-1] - A[k] + 1):
            R[k] = i
            dfs()
    k -= 1
    return

dfs()

if count == []:
    res = -1
else:
    res = max(count)

print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
a = LI()

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

Submission status: Runtime Error

Solution code:
from sys import stdin
import math
a=int(stdin.readline())
A=stdin.readline().split()
sum=0
for k in range(0,a+1):
    sum+=int(A[k])

sum-=int(A[a])
ver=1
lay=1
K=0

for l in range(0,a):
    if lay-int(A[l])<=0:
        print(-1)
        K=1
        break
    if (lay-int(A[l]))*2-sum+int(A[l])<=int(A[a]):
        lay=(lay-int(A[l]))*2
        ver+=lay
        sum-=int(A[l])
        T=l
    else:
        lay-=int(A[l])
        sum-=int(A[l])
        x=lay-sum-int(A[a])
        if x==0:
           ver+=lay
        else:
           lay=sum+int(A[a])
           ver+=lay
        T=l
        break

if K==0:
    for u in range(T+1,a):
        lay -= int(A[u])
        sum -= int(A[u])
        ver+=lay

if K==0:
    print(ver)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)


class Solver:
    def __init__(self, depth_list):
        self.ans = -1
        self.depth_list = depth_list

    @lru_cache(None)
    def helper(self, d, current_sum, min_nodes, max_nodes):
        if d == 0:
            if min_nodes == 1:
                self.ans = max(self.ans, current_sum+1)
                return
            else:
                return
        else:
            max_size = 2 ** d
            # if number of leaf is grater than the size of max nodes for the layer
            if min_nodes > max_size:
                return
            for c in range(min_nodes, max_nodes):
                if c > max_size:
                    continue
                min_nodes = (c // 2) + (c % 2) + self.depth_list[d - 1]
                max_nodes = c + self.depth_list[d - 1]+1
                self.helper(d-1, current_sum+c, min_nodes, max_nodes)


def main():
    N = int(input().strip())
    depth_list = [int(i) for i in input().strip().split()]
    solver = Solver(depth_list)
    solver.helper(N, 0, depth_list[-1], depth_list[-1]+1)

    return solver.ans


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

Submission status: Runtime Error

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

  
ok=[]
r=int(1)
for i in range(n+1):
  if r<int(a[i]):
    print(-1)
    sys.exit(status=None)
  ok.append(r)
  r -= int(a[i])
  r *= 2

  
cnt=int(0)
node=int(0)
for i in reversed(range(n+1)):
  rep=int(node/2)
  node += int(a[i])
  node = node - min(rep,max(node-ok[i],0))

  cnt += node
  
print(cnt)

Submission status: Runtime Error

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

accum = [0]*n
new_list = list(reversed(a))
accum[0] = new_list[0]
for i in range(n-1):
    accum[i+1] = accum[i] + new_list[i+1]
hat = list(reversed(accum))
#print(hat)

b = [1]*(n+1)
flag = 0
cand = 0

for i in range(1,n+1):
  cand = (b[i-1]-a[i-1])*2
  if cand < 1:
    print(-1)
    flag = 1
    break
  if cand > hat[i-1]:
    b[i] = hat[i-1]
  else:
    b[i] = cand

#print(b)
if flag != 1:
  print(sum(b))

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A=np.zeros(N+1)
a=list(map(int,input().split()))
for i in range(N+1):
  A[i]=a[i]
v=0
j=0
k=0
B=np.zeros(N+1)
for i in range(N+1):
  B[i]=N-i
for i in reversed(range(0, N+1)):
  j+=A[i]/(2**i)
  if i==N:
    k=A[i]
  else:
    k=min(k+A[i],2**i-np.sum(A[0:i]*(2**(B[0:i]-(N-i)))))
  v+=k

if j>1:
  print(-1)
else:
  print(int(v))

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
temp=1
summ=0
cont=0
templist=[1]
for i in range(N+1):
  #print(temp)
  if A[i]<temp:
    if i<N:
      summ+=temp
      temp=2*(temp-A[i])
      templist.append(temp)
    if i==N:
      summ+=temp
      cont+=1
  elif A[i]==temp:
    if i==N:
      summ+=temp
      #templist.append(temp)
      cont+=1
    else:
      print("-1")
      break
  else:
    print("-1")
    break
    
if cont==1:
  if A[N]==temp:
    print(summ)
  else:
    #print(templist)
    #print(A)
    comp=A[-1]
    for i in range(N+1):
      summ-=(templist[-(i+1)]-comp)
      comp+=A[-(i+2)]
      #print(comp)
      #print(templist[-(i+2)])
      #print(summ)
      if comp>templist[-(i+2)]:
        print(summ)
        break

Submission status: Runtime Error

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

if A[0] != 0:
    print(-1)
else:
    B = [0]*(N+1)
    C = [0]*(N+1)
    B[0] = 1
    C[N] = A[N]
    flag = True
    for i in range(1,N+1):
        B[i] = (B[i-1]-A[i-1]) * 2
        if (i < N and B[i] <= A[i]) or (i = N and B[i] < A[i]): flag = False
        C[N-i] = C[N+1-i]+A[N-i]
    sum = 0
    for i in range(0,N+1):
        sum += min(B[i],C[i])
    if flag == True:
        print(sum)
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    N = int(input().strip())
    A = list(map(int, input().strip().split(" ")))



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

    tree = [0] * (sum([2 ** i for i in range(N + 1)]))
    for i, a in enumerate(A[::-1]):
        depth = len(A) - 1 - i
        depth_hierarchy_start_index = sum([2 ** i for i in range(depth)]) if depth != 0 else 0
        depth_hierarchy_end_index = sum([2 ** i for i in range(depth + 1)]) if depth != 0 else 1

        # keisho
        if depth != N:
            for i in range(depth_hierarchy_start_index, depth_hierarchy_end_index):
                if tree[2 * i + 1] != 0 or tree[2 * i + 2] != 0:
                    tree[i] = 2

        # 1 ume
        count = 0
        part = 2
        while True:
            for i in range(0, 2 ** depth, int(2 ** depth / part) if int(2 ** depth / part) >= 1 else 1):
                if tree[depth_hierarchy_start_index + i] == 0:
                    tree[depth_hierarchy_start_index + i] = 1
                    count += 1
                if count == a:
                    break
            part *= 2
            if count == a:
                break
            if int(2 ** depth / part) < 1 and count < a:
                print(-1)
                break


    if not count < a:
        print(sum([1 if i != 0 else 0 for i in tree]))

Submission status: Runtime Error

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

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

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

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]


for i in range(N):
    nodeS[i+1] = nodeM[i]*2
    nodeM[i+1] = nodeS[i+1] - A[i+1]
    if nodeS[i] > laS[i]:
        break
    if i == N-1:
        if nodeS[i+1] > laS[i+1]:
            i += 1
ans = sum(nodeS[:i]) + sum(laS[i::])
print(ans if -1 not in nodeM else -1)