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:
depth = int(input()) 
leaves = list(map(int, input().split(" ")))
limited = []
def find( i, depth) :
    if i == depth :
        limited.append(leaves[i])
        return ( leaves[i], (leaves[i]+1)//2 )
    _max, _min = find(i+1, depth)
    _max = min(pow(2,i), _max+leaves[i])
    _min += leaves[i]
    if _max < _min :
        return (-float('inf'), float('inf') )
    limited.append(_max)
    return ( _max, (_min+1)//2 )

find(0, depth) 
if len(limited) != depth+1 :
    print(-1)
else :
    ans = 0
    cur = 1
    leaves.append(0)
    for i in range(depth+1) :
        ans += min(cur, limited[-i-1])
        cur = (cur-leaves[i])*2  
    
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

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

ans = 0
li = [0]*(n+1)

for i,a in enumerate(a_li):
  ans += (i+1)*a

for i,a in enumerate(a_li[::-1]):
  if i >= 1:
    li[i] = li[i-1]+a
  else:
    li[i] = a

li = li[::-1]

#print(li)
#print(ans)


flag = True
ne = 0.5
for i in range(n):
  if li[i]  > 2*ne:
    ans -= li[i] -2*ne
    #print(li[i] -2*ne)

  ne = 2*ne - a_li[i]
  #print(ne)
  if ne <= 0:
    flag = True

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
saidaiA =[]
oya = 1/2
flag = True
for i in range(len(A)):
    ko = oya *2
    oya = ko - A[i]
    saidaiA.append(ko)
    # print("i=",i)
    # print("ko =",ko)
    # print("oya =",oya)
    if oya < 0:
        flag = False
        break
ans = 0
# print(saidaiA)
motikosi = 0
for i in range(len(A)):
    if A[-i] + motikosi >= saidaiA[-i]:
        ans += saidaiA[-i]
        motikosi = saidaiA[-i]
    else:
        ans += A[-i] + motikosi
        motikosi = A[-i] + motikosi
if flag == True:
    print(int(ans))
else:
    print(-1)

Submission status: Runtime Error

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

node = 1
flg = False
node_list = [node]

for i in range(len(a_list)-1):
  num = a_list[i]
  next = node-num
  if next < 0:
    flg = True
    break
  node = next*2
  node_list.append(node)

if node - a_list[-1] < 0:
  flg = True

diff = a_list[-1]
res_list = [a_list[-1]]
for i in range(len(a_list)-2,-1,-1):
  v = node_list[i] - a_list[i] # 枝の数
  diff = min(diff,v) + a_list[i]
  res_list.append(diff)

if flg:
  print(-1)
else:
  print(sum(res_list))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
saidaiA =[]
oya = 1/2
flag = True
for i in range(len(A)):
    ko = oya *2
    oya = ko - A[i]
    saidaiA.append(ko)
    # print("i=",i)
    # print("ko =",ko)
    # print("oya =",oya)
    if oya < 0:
        flag = False
        break
ans = 0
print(saidaiA)
motikosi = 0
for i in range(len(A)):
    if A[-i] + motikosi >= saidaiA[-i]:
        ans += saidaiA[-i]
        motikosi = saidaiA[-i]
    else:
        ans += A[-i] + motikosi
        motikosi = A[-i] + motikosi
if flag == True:
    print(int(ans))
else:
    print(-1)

Submission status: Runtime Error

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


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1
    upper = sum([2 ** i for i in range(N)])
    if sum(A) > upper:
        print('-1')
        return
    for d in range(1, N):
        f[d] = 2 * min(f[d-1], count) - A[d] + min(max(f[d-1]-count, 0), f[d-1])
        count -= min(f[d-1], count)
    print(sum(f)+sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
a=1
k=0
f=0
if n==0:
  print(l(0))
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if a<=0:
    f+=1
    break
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  if l[0]==0:
    print(0)
  elif l[0]==1:
    print(1)
  else:
    print(-1)
else:
  print(-1)

Submission status: Runtime Error

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

tree = [0 for _i in range(n+2)]
tree[0] = 1
for i in range(1,n+1):
    tree[i] = tree[i-1]*2
    tree[i] -= a[i]
tree[n] += a[i]
for i in range(n, 0, -1):
    if tree[i-1]*2 < a[i]:
        import sys
        print(-1)
        sys.exit()
    x = min(tree[i-1], a[i])
    a[i-1] += x
if a[0]>1:
    print(-1)
else:
    print(sum(a))

Submission status: Runtime Error

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

node = 1
sum_node = 1
flg = False
node_list = [node]

for i in range(len(a_list)-1):
  num = a_list[i]
  next = node-num
  if next < 0:
    flg = True
    break
  node = next*2
  node_list.append(node)
  sum_node += node
  
diff = node - a_list[-1]
if diff < 0:
  flg = True

diff = a_list[-1]
res_list = [a_list[-1]]
for i in range(len(a_list)-2,-1,-1):
  v = node_list[i] - a_list[i] # 枝の数
  diff = min(diff,v) 
  res_list.append(diff+a_list[i])
  diff = diff + a_list[i]

if flg:
  print(-1)
else:
  print(sum(res_list))

Submission status: Runtime Error

Solution code:
import sys

def main():
    if A[0] >= 2:
        print(-1)
        sys.exit()

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

    tree = [set() for _ in range(N+1)]
    tree[0].add(1)

    for i in range(N):
        unsuitable = set()
        for ver_i in tree[i]:
            notleef = ver_i - A[i]
            if notleef <= 0:
                print(-1)
                sys.exit()
                unsuitable.add(ver_i)
                continue
            minimum = notleef
            maximum = 2 * notleef
            tree[i+1] = tree[i+1] | set([j for j in range(minimum, maximum+1)])
        tree[i] -= unsuitable
        print()

    if A[-1] in tree[-1]:
        tree[-1] = set([A[-1]])
    else:
        print(-1)
        sys.exit()
        
    print(sum([max(i) for i in tree]))

main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
import math
ans=0
for i in range(N, 0, -1):
    if A[i]>2**(i):
        ans=-1
        break
    if i!=0:
        q=math.ceil(A[i]/2)
        if q==0:
            q=1
        print(A[i]+q)
        ans=ans+A[i]+q
if A[0]>0 and len(a)!=0:       
    print(-1)
else:
    peint(ans)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))
if lst1[0] != 0:
    print(-1)
    exit()
res2 = [0]
for i in lst1[::-1]:
    res2.append(res2[-1]+i)

res2.reverse()

INF = res2[0]
res = [1] 
res3 = [1]
for i in lst1[1:]:
    res3.append(min(INF,res[-1]*2))
    res.append(min(INF,res[-1]*2-i))

#案2
for i in range(len(res)):
    if i == len(res)-1:
        break
    if res[i] <= 0:
        print(-1)
        exit()

ans = 0
res2 = res2[:-1]
for i in range(len(res3)):
    ans += min(res2[i],res3[j])
print(ans)
"""print(*res)
print(*res3)
print(*ans)
"""

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
        for i in range(0, 2 ** depth, 2):
            if tree[depth_hierarchy_start_index + i] == 0:
                tree[depth_hierarchy_start_index + i] = 1
                count += 1
            if count == a:
                break
        if count < a:
            for i in range(0, 2 ** depth, 2):
                if tree[depth_hierarchy_start_index + i + 1] == 0:
                    tree[depth_hierarchy_start_index + i + 1] = 1
                    count += 1
                if count == a:
                    break
        if count < a:
            print(-1)
            exit()


    print(sum([1 if i != 0 else 0 for i in tree]))

Submission status: Runtime Error

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

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


zero = -1

for i in range(0, N + 1):
    if A[i] > 0:
        C = [0] * (N + 1)
        for j in range(zero + 1, i):
            B[j] += C[j]
            if B[j] > 0:
                h = min(A[i], B[j])
                B[j] -= h
                A[i] -= h
                C[j] += h
                ans += h * (i - j)
                if B[j] == 0:
                    zero = j
            C[j + 1] += C[j]
        if A[i] > 0:
            print(-1)
            exit()
    print(A)
    print(B)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
saidaiA =[]
oya = 1/2
flag = True
for i in range(len(A)):
    ko = oya *2
    oya = ko - A[i]
    saidaiA.append(ko)
    # print("i=",i)
    # print("ko =",ko)
    # print("oya =",oya)
    if oya < 0:
        flag = False
        break
ans = 0
# print(saidaiA)
motikosi = 0
for i in range(len(A)):
    if A[-i] + motikosi >= saidaiA[-i]:
        ans += saidaiA[-i]
        motikosi = saidaiA[-i]
    else:
        ans += A[-i] + motikosi
        motikosi = A[-i] + motikosi
if flag == True:
    print(int(ans)+1)
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
        for i in range(2 ** depth):
            if tree[depth_hierarchy_start_index + i] == 0:
                tree[depth_hierarchy_start_index + i] = 1
                count += 1
            if count == a:
                break
        if count < a:
            print(-1)
            exit()


    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()))
ans=1
flag=0
sum_=0
for i in range(N+1):
  sum_+=A[i]
node=2
if A[0]>0:
  flag=1
  
sum_-=A[1]
for i in range(1,N+1):
  if i!=N and node-A[i]<=0:
    flag=1
  elif i!=N:
    sum_-=A[i+1]
    ans+=node
    if 2*(node-A[i])-A[i+1]<=sum_:
      node=2*(node-A[i])
    else:
      node=sum_+A[i+1]   
  else:
    ans+=A[i]

if flag==1:
  print("-1")
elif flag==2:
  print("1")
else:
  print(ans)

Submission status: Runtime Error

Solution code:
import math

def find_max_verticies(A, i, verticies, prev_verticies):
	max_leaves = 2**i
	a = A[i]
	if a > max_leaves:
		return -1
	if i == 0:
		if a != 0:
			return -1
		return verticies + 1
	if i == N:
		return find_max_verticies(A, i-1, a, a)
	else:
		min_nonleaf = math.ceil(prev_verticies/2)
		max_nonleaf = min(prev_verticies, max_leaves - a)
		if min_nonleaf + a > max_leaves:
			return -1
		max_v = 0
		for j in reversed(range(min_nonleaf, max_nonleaf+1)):
			v = find_max_verticies(A, i-1, verticies + j + a, j + a)
			if v > 0:
				return v
		return -1


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

print(find_max_verticies(A, N, 0, 0))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
import math
ans=0
for i in range(N, 0, -1):
    if A[i]>2**(i)
        ans=-1
        break
    if i!=0:
        q=math.ceil(A[i]/2)
        if q==0:
            q=1
        print(A[i]+q)
        ans=ans+A[i]+q
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=1
flag=0
sum_=0
for i in range(N+1):
  sum_+=A[i]
node=2
if A[0]>0:
  flag=1
  if A==[1] and N==0:
    flag==2
sum_-=A[1]
for i in range(1,N+1):
  if i!=N and node-A[i]<=0:
    flag=1
  elif i!=N:
    sum_-=A[i+1]
    ans+=node
    if 2*(node-A[i])-A[i+1]<=sum_:
      node=2*(node-A[i])
    else:
      node=sum_+A[i+1]   
  else:
    ans+=A[i]

if flag==1:
  print("-1")
elif flag==2:
  print("1")
else:
  print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

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

ans = 0
li = [0]*(n+1)

for i,a in enumerate(a_li):
  ans += (i+1)*a

for i,a in enumerate(a_li[::-1]):
  if i >= 1:
    li[i] = li[i-1]+a
  else:
    li[i] = a

li = li[::-1]

flag = True
ne = 0.5
for i in range(n+1):
  if li[i]  > 2*ne:
    ans -= li[i] -2*ne

  ne = 2*ne - a_li[i]
  if i == n+1 and ne <= 0:
    flag = False

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
req = [0] * n
req[-1] = a[-1]
for i in range(2, n+1):
    req[-i] = req[-(i-1)] + a[-i]
l = [0] * (n + 1)
l[0] = 1
for i in range(1, n+1):
    M = (l[i-1] - a[i-1]) * 2
    l[i] = min(M, req[i-1])
if l[-1] < a[-1]:
    print(-1)
else:
    print(sum(l))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
elif A[0] != 0:
    print(-1)
else:
    rest = [1]
    for i in range(1, N+1):
        rest.append(min(rest[i-1]*2 - A[i], 10**13))
    ans, cnodes = A[N], A[N]
    for i in range(N-1, -1, -1):
        if cnodes//2 + cnodes%2 > rest[i]:
            print(-1)
            exit()
        else:
            cnodes = min(cnodes, rest[i]) + A[i]
            ans += cnodes
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

inf = float('inf')

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

d = dict()


def bin_tree_cost(left, right, depth):

    if right - left == 1:
        return A[left] * depth

    if (left, right, depth) in d:
        return A[(left, right, depth)]

    res = inf
    for mid in range(left + 1, right):
        t = bin_tree_cost(left, mid, depth + 1) + bin_tree_cost(mid, right, depth + 1)
        res = min(res, t)

    A[(left, right, depth)] = res
    return res


print(bin_tree_cost(0, N, A[0]))

Submission status: Runtime Error

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

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

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

M = [-1]*N
M[0] = 2
for i in range(1,N):
    M[i] = (M[i-1]-A[i])*2
    if M[i] <= 0:
        flag = -1
#print(S,M)

if flag != -1:
    V = [-1]*N
    for i in range(N):
        if S[i] > M[i]:
            V[i] = M[i]
        else:
            V[i] = S[i]
    ans = sum(V)+1
    #print(V)
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from numba import njit

@ngit
def main(N, A):
    num = 1
    ans = 1
    if A[N] == 0:
        return -1
    for i in range(N+1):
        num -= A[i]
        if i < N:
            num *= 2
            ans += num
        if num <= 0 and i < N:
            return -1
    eda=0
    for i in range(N+1):
        ans -= num
        eda+=A[N-i]
        num -= eda
        num = num//2
        if num <= 0:
            num += A[N-i]
            break
    return ans


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

print(main(N, A))

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
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()
    if i == n-2:
        val2 = val
val3 = (val2 - a[-2])
val -= val3
if val//2 > val2:
    print(-1)
    exit()
ans -= val//2
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())+1
ali = list(map(int,input().split()))
nli = [0]*N

maxn = 2**(N-1)
nli[-1] = ali[-1]

for i in range(1,N+1):
  nli[-i] = min(maxn,nli[-i+1] + ali[-i])
  maxn //= 2
  

ulim = 1
for i in range(N):
  nli[i] = min(nli[i],ulim)
  ulim = (ulim - ali[i])*2
  if i != N-1 and ulim <= 0:
    print(-1)
    print(nli[N+1])
    exit()
  
print(sum(nli))

Submission status: Runtime Error

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

cnt = [[0, 0] for _ in range(N + 1)]
cnt[-1] = [A[-1], A[-1]]
exists = True
for i in reversed(range(N)):
    if i > 45:
        cnt[i] = [cnt[i + 1][0] + A[i][0]] * 2
    else:
        nex_min = cnt[i + 1][0] // 2 + cnt[i + 1][0] % 2
        nex_max = cnt[i + 1][1] // 2 + cnt[i + 1][1] % 2
        lim = pow(2, i)
        if lim < nex_min + A[i]:
            exists = False
            break
        
        cnt[i][0] = min(lim, nex_min + A[i])
        cnt[i][1] = min(lim, cnt[i + 1][1] + A[i])

if exists:
    print(sum(v for _, v in cnt))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
k = sum(A)　###syuutenの個数
c = 1  ###考えている列の〇の個数(次の列につながる個数)
aa = 1
ans = 1
if A[0] != 0:
    print(-1)
else:
    for i in range(1,N + 1):
        c *= 2 ##次の列につながる個数の最大値
        if A[i] > c:
            ###A[i]はここが終点になるということ。終点の方が多いことは認められない
            aa = 0
            break
        elif A[i] == c:
            ###終点と同数だとこれより下には繋がらない。もし最下段でなければアウト
            if i != N:
                aa = 0
                break
            else:
                ans += c
        else:
            c -= A[i]
            k -= A[i]
            ans += A[i]
            ###終点の個数を引く。ここで終点の個数だけansを足す
            if c >= k:
                ###次の列につながる個数はこれよりしたにある終点の個数を超えれない
                c = k
            ans += c
            ###この段で下につながる個数を足す

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

Submission status: Runtime Error

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

    if leaf<0 or (leaf==0 and m>0): print(-1);sys.exit()
    tmp=leaf
    for j in range(min(n-i,50)):
        tmp*=2
        if tmp>=m: break
    if tmp<m: print(-1);sys.exit()        
    if leaf*2>=m: leaf=m
    else: leaf*=2
print(ans)

Submission status: Runtime Error

Solution code:


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

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

    tree = [0]*(sum([2 ** N for i in range(N+1)]))
    for i, a in enumerate(A):
        depth = len(A) - i
        depth_hierarchy_start_index = sum([2 ** N for i in range(depth)]) if depth != 0 else 0
        depth_hierarchy_end_index = sum([2 ** N 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 [2 * (i + 1) + 1] != 0 or [2 * (i + 1) + 2] != 0:
                tree[i] = 2

        # 1 ume
        count = 0
        for i in range(2 ** depth):
            if tree[depth_hierarchy_start_index + i] == 0:
                tree[depth_hierarchy_start_index + i] = 1
                count += 1
            if count == a:
                break
        if count < a:
            print(-1)
            exit()

    print(sum([1 for i in tree if i != 0 else 0])

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
ma = [None]*n
ma[0] = 1
for i in range(n-1):
    ma[i+1] = (ma[i]-a[i])*2
node = a[-1]
ans = node
for i in range(n-1, -1, -1):
    mi = (node+1)//2
    if ma[i]-a[i]<mi:
        print(-1)
        exit()
    node = min(ma[i]-a[i], node) + a[i]
    ans += node
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
Al=list(map(int,input().split(" ")))
v=1
c=0
if Al[0]!=0 and N!=0:
    c=1
El=[0]*(N)
El[0]=min(2,sum(Al[1:]))
v+=El[0]
for i in range(1,N):
    ch=0
    diff=(El[i-1]-Al[i])*2
    for j in range(i+1,N+1):
        diff-=Al[j]
        if diff <= 0:
            ch=1
            break
    if ch==1:
        El[i]=(El[i-1]-Al[i])*2
    else:
        El[i]=-diff+(El[i-1]-Al[i])*2
    v+=El[i]

if El[N-1]!=Al[N] or c==1:
    print(-1)
else:
    print(v)

Submission status: Runtime Error

Solution code:
N=int(input())
Al=list(map(int,input().split(" ")))
v=1
c=0
if Al[0]!=0 and N!=0:
    c=1
El=[0]*(N)
El[0]=min(2,sum(Al[1:]))
v+=El[0]
for i in range(1,N):
    El[i]=min((El[i-1]-Al[i])*2,sum(Al[i+1:]))
    v+=El[i]

if El[N-1]!=Al[N] or c==1:
    print(-1)
else:
    print(v)

Submission status: Runtime Error

Solution code:
#3
#0 1 1 2

N = int(input())+1
leaves = list(map(int, input().split()))

nod = 0
total = 0

maxx = [0]*(N+1)
#toward
maxx[0] = 1
for i in range(1, N+1):
    notleave = maxx[i-1] - leaves[i-1]
    maxx[i] = notleave*2

#backward
for i in range(1, N+1):
    ii = N-i
    #at least need newnod nodes
    newnod = int((nod+1)/2) + leaves[ii]
    if newnod > 2**ii:
        total = -1
        break
    #maximum is?
    newnod = nod + leaves[ii]
    if newnod > maxx[ii]: newnod = maxx[ii]
    total += newnod
    nod = newnod

print(total)

Submission status: Runtime Error

Solution code:
n = int(input())

a = [0]*n

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

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

Submission status: Runtime Error

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

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

ans = 1
b = 0
L = [[0,0] for i in range(n)]
# L[-1][0] = A[-1]
# L[-1][1] = A[-1]
l = A[-1]
r = A[-1]
for i in range(n-1,-1,-1):

    L[i][0] = (l+1)//2 + A[i]
    L[i][1] = r + A[i]
    l = L[i][0]
    r = L[i][1]

if L[0][0] != 1:
    print(-1)
else:
    ans = 1
    now = 1
    for i in range(1, n):
        now = min(L[i][1], now*2)
        # print(i,now)
        ans += now
        now -= A[i]
    print(ans + A[-1])