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 sys #追加
from collections import deque
sys.setrecursionlimit(10**9) #追加

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

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

start = 1
way = sum(A)

for i in range(1,n+1):
    start *= 2

    if start < A[i]:
        print(-1)
        exit()
    if start > way:
        start = way

    ans += start
    #print(start, start-A[i])
    start -= A[i]
    way -= A[i]
#print()
print(ans+1)

Submission status: Wrong Answer

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

L[0]=1
for i in range(1,n+1):
    L[i]=min((L[i-1]-a[i-1])*2, L[i])
    if L[i]<a[i]:
        ans=-1
        break
else:
    ans=sum(L)
print(ans)

Submission status: Wrong Answer

Solution code:

from math import ceil
N = int(input())
A = list(map(int, input().split()))
if(A[0] != 0):
    print(-1)
    exit(0)
# curは作り出せる最大ノード数
if(N == 0 and A[0] == 0):
    print(-1)
    exit(0)
if(N == 1 and A[0] == 0 and A[1] != 2):
    print(-1)
    exit(0)
cur = 0
S = [0] * (N + 1)
for i in range(N, 0, -1):
    cur += A[i]
    S[i - 1] = cur
# print(S)

ans, cur = 0, 2
node = [0] * (N + 1)
a = [0] * (N + 1)
node[0] = 2
for i in range(1, N):
    if(A[i] > cur):
        print(-1)
        exit(0)
    cur = 2 * (cur - A[i])
    node[i] = cur

    if(node[i] > S[i]): node[i] = S[i]
    a[i] = node[i - 1] + cur
    #print("i={}, cur={}".format(i, cur))
# print(node)
# print(a)
# 最初の頂点
print(sum(node) + 1)
'''
cur = 0
for i in range(N, 0, -1):
    cur += A[i]
    if(cur >= 2**(i - 1)): cur = 2**(i - 1)
    #if(cur >= 2 * A[i - 1]): cur = 2 * A[i - 1]
    ans += cur
    print(cur, ans)
print(ans)

'''

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [1]
if a[0] != 0:
    print(-1)
    exit()
cnt = 2
ans = 1
for i in range(1, n+1):
    if i != n:
        if a[i] > cnt:
            ans = -1
            break
        l.append(a[i]+(cnt-a[i])//2)
        ans += cnt
        cnt -= a[i]
        cnt *= 2
    if i == n:
        if cnt < a[i]:
            ans = -1
        else:
            ans += cnt
            l.append(cnt//2)
if ans == -1:
    print(ans)
elif cnt == a[n]:
    print(ans)
else:
    for i in range(n, -1, -1):
        if i == 0:
            break
        if cnt - l[i] <= a[n]:
            ans += (cnt - a[n]) * (-n-1+i)
            cnt = a[n]
            break
        else:
            cnt -= l[i]
            ans += l[i] * (-n-1+i)
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0 and a[0]==1:
	print(1)
elif n==0:
	print(-1)
elif a[0]!=0:
	print(-1)
elif a[n]==0:
	print(-1)
else:
	ruisekiwa = [0 for _ in range(n+1)]
	ruisekiwa[n] = a[n]
	for i in range(n)[::-1]:
		ruisekiwa[i] = a[i] + ruisekiwa[i+1]
	cnt=1
	ans=1
	for i in range(1,n+1):
		target = a[i]
		if cnt*2 - target <= 0 and i != n:
			print(-1)
			exit()
		elif i == n:
			if cnt * 2 - target < 0:
				print(-1)
				exit()
			else:
				cnt = min(cnt*2, a[n])
				ans += cnt
		else:
			if cnt*2-a[i] < ruisekiwa[i]:
				ans += cnt*2
				cnt = cnt*2-a[i]
			else:
				ans += ruisekiwa[i]
				cnt = ruisekiwa[i]
	print(ans)

Submission status: Wrong Answer

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

f=0
ok=[]
r=int(1)
for i in range(n+1):
  if r<int(a[i]):
    print(-1)
    f=1
    break
  ok.append(r)
  r -= int(a[i])
  r *= 2

if f==1:
  print(-1)
else:
  
  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: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A == [0]:
            print('-1')
        elif A == [1]:
            print('1')
        else:
            print('-1')
        return

    if N == 1:
        if A == [0, 1]:
            print('2')
        elif A == [0, 2]:
            print('3')
        else:
            print('-1')
        return

    f = [0 for i in range(N)]

    f[0] = 1
    count = sum(A) - 1
    if sum(A) == 0:
        print('-1')
        return
    elif sum(A) == 1 and A[-1] != 1:
        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)
        if f[d] < 0:
            print('-1')
            return
    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: Wrong Answer

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

Submission status: Wrong Answer

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

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: Wrong Answer

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]
    for i in range(1,N+1):
        B[i] = (B[i-1]-A[i-1]) * 2
        C[N-i] = C[N+1-i]+A[N-i]
    sum = 0
    flag = True
    for i in range(0,N+1):
        sol = min(B[i],C[i])
        if (i < N and sol <= A[i]) or (i == N and sol < A[i]): 
            flag = False
            break
        sum += sol
    if flag == True:
        print(sum)
    else:
        print(-1)

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**30, node_max[i-1]*2-a[i]))

a.reverse()
node_max.reverse()

node_max
ans = 0
main = 0
node_max.append(0)


flag = 1

for i in range(n+1):
    main = min(main+a[i], node_max[i+1])
    ans += main + a[i]
    if i == 0:
        continue
    if (main+a[i]) > node_max[i+1]*2:
        flag = 0
        break


print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
edge=[0]*(n+1)
ans=0
edge[0]=1
for i in range(1,n):
    edge[i]=edge[i-1]*2-a[i]
for i in range(n-1,-1,-1):
    bcnt=edge[i+1]+a[i+1]
    if bcnt//2+bcnt%2>edge[i]:
        ans=-1
        break
    if bcnt<edge[i]:
        edge[i]=bcnt
if a[0]>0:
    ans=-1
if ans!=-1:
    ans=sum(edge)+sum(a)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
sum_value = sum(A)
chiled_value = 1
top_value = 1
if(N==1 & A[0]==1):
    print(1)
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: Wrong Answer

Solution code:
import sys #追加
from collections import deque
sys.setrecursionlimit(10**9) #追加

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

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

start = 1
way = sum(A)

for i in range(1,n+1):
    start *= 2

    if start < A[i]:
        print(-1)
        exit()
    if start > way:
        start = way

    ans += start
    #print(start, start-A[i])
    start -= A[i]
    way -= A[i]
#print()
print(ans+1)

Submission status: Wrong Answer

Solution code:
# C
 
N = int(input())
A_N = list(map(int, input().split()))
if N == 0:
    if A_N[0] == 1:
        print(1)
    elif A_N[0] == 0:
        print(0)
    else:
        print(-1)
    exit()

reversed_A_N = list(reversed(A_N))
for i in range(1, N + 1):
    reversed_A_N[i] += reversed_A_N[i - 1]
r_reversed_A_N = list(reversed(reversed_A_N))
 
 
r_reversed_A_N[0] = 1
for i in range(N):
    max_next_nodes = (r_reversed_A_N[i] - A_N[i]) * 2 - A_N[i+1]
    if max_next_nodes < 0:
      print(-1)
      exit()
    elif max_next_nodes >= r_reversed_A_N[i+1]:
        break
    else:
        r_reversed_A_N[i+1] = max_next_nodes + A_N[i+1]
 
r_reversed_A_N[i+1] = list(reversed(reversed_A_N))[i+1]# A_N[-1]
print(sum(r_reversed_A_N))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
li = list(map(int,input().split()))

if li[0]!=0:
    print(-1)
    exit()

tmp = 1
for i,l in enumerate(li):
    if i == 0:
        continue
    tmp *= 2
    if l > tmp:
        print(-1)
        exit()
    else:
        tmp -= l

max_li = [1]
for i,l in enumerate(li):
    if i == 0:
        continue
    la = (max_li[-1]-li[i-1])*2
    max_li.append(la)


li.reverse()
ans = 0
codomo = li[0]
for i,l in enumerate(li):
    if i == 0:
        if l > 2**(n-i):
            print(-1)
            exit()
        else:
            ans += codomo
    else:
        tmp = codomo + l
        fin = min(min(2**(n-i),tmp),max_li[n-i])
        #print(min(2**(n-i),tmp),max_li[i],i,'i')
        ans += fin
        codomo = fin
    #print(ans,'ans')
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
l = list(map(int,input().split()))

if l[0]  != 0:
    print('-1')
    sys.exit()
    
count = 1
edge = 1
sum_ = sum(l)
for i in range(1,len(l)-1):
#     print(i-1, edge, count)

    sum_ -= l[i]
    
    if l[i] >= edge *2:
        print('-1')
        sys.exit()
    
    if edge * 2 - l[i] <= sum_:
        count += edge * 2
        edge = edge * 2 -l[i]
#         print(i, 'max', edge,count)
        continue

        
    if edge * 2 - l[i] > sum_:
        count += sum_ + l[i]
        edge = sum_
        
#         print(i, 'notmax', edge,count)
        continue

        
        
#n回目の処理
if not edge <=  l[len(l)-1] <= edge * 2:
    print('-1')
    sys.exit()
    
else:
    count +=   l[len(l)-1] 
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

b = 2**n
e = 2**n
B = [0]*(n+1)
for i in range(n+1):
    e -= A[i] * b
    b = b // 2
    if i == 0:
        B[i] = 1 - A[i]
    else:
        B[i] = 2*(B[i-1]) - A[i]
if e < 0:
    print(-1)
else:
    ans = 0
    p = A[-1]
    t = 0
    for i in range(1,n+2):
        t += A[-1*i]
        if t > B[-1*i]:
            t = B[-1*i] + A[-1*i]
        ans += t
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
a_list_r = a_list[::-1]
ruisekiwa = [a_list_r[0]]
for i in range(1,n+1):
  ruisekiwa.append(ruisekiwa[-1] + a_list_r[i])
ruisekiwa = ruisekiwa[::-1]
max_leaf = a_list[-1]
count = 0
check = True
node = 0
for i in range(n):
  if i == 0:
    if  n == 0 and a_list[0] == 1:
      count = 1
      break
    elif a_list[0] != 0:
      check = False
      break
    else:
      count = 1
      node = 1
  else:
    cand = 2 * node
    if cand < a_list[i]:
      check = False
      break
    node = min(ruisekiwa[i+1],2*node - a_list[i])
    count += node + a_list[i]
if check == False:
  print(-1)
elif 2 * node < a_list[-1]:
  print(-1)
else:
  print(count + a_list[-1])

Submission status: Wrong Answer

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

MAX = [P[-1]] * (N+1)
MIN = 0
J = True

for i in range(N):
  MAX[N-1-i] = MAX[N-i] + P[N-1-i]

#print(MAX)

follow = 1
hikaku = True
ans = 0
for i in range(N+1): 
  p = follow + P[i]
  if follow < 0:
    J = False
  if hikaku:
    if p > MAX[i]:
      hikaku = False
      ans += MAX[i]
    else:
      ans += p
      follow *= 2
      if i != N:
        follow -= P[i + 1]
      else:
        follow += P[-1]
  else:
    ans += MAX[i]
  
  
if P[0] != 0:
  J = False
if P[-1] == 0:
  J = False
  
if J:
  print(ans)  
else:
  print(-1)

Submission status: Wrong Answer

Solution code:


def resolve():
  N = int(input())
  if N == 0:
    print(-1)
    return True
  A = [int(x) for x in input().split(" ")]
  max_node_in_depth = [sum(A[i:]) for i in range(len(A))]

  # 各 depth における最小値
  min_node_in_depth = [0] * (len(A))
  min_node_in_depth[-1] = max_node_in_depth[-1]
  index = -1
  for i in range(1, len(A)):
    min_node_in_depth[index] = -(-min_node_in_depth[index + 1] // 2) + A[index]
    index = index - 1

  node = [0] * (len(A))
  node[0] = 1

  for i in range(1, len(A)):
    num_of_node = (node[i - 1] - A[i - 1]) * 2
    if num_of_node < min_node_in_depth[i]:
      print(-1)
      return True

    if num_of_node <= max_node_in_depth[i]:
      node[i] = num_of_node
    else:
      node[i] = max_node_in_depth[i]

  print(sum(node))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

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

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

ans[n]=a[n]

def dfs(fukasa):
    if fukasa == 0:
        return True

    mi = a[fukasa] -(-ans[fukasa+1]//2)
    ans[fukasa] = mi
    if not dfs(fukasa-1):
        return False

    tmp = a[fukasa]+ans[fukasa+1]
    tmp = min(tmp,2**fukasa)

    while tmp >= a[fukasa] -(-ans[fukasa+1]//2):
        ans[fukasa]=tmp
        tmpp = dfs(fukasa-1)



        if tmpp:
            ans[fukasa]=tmp
            break
        tmp -= 1
    else:
        return False
    return True


tmp = dfs(n-1)

if tmp:
    print(sum(ans))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10


    N = II()
    A = LMIIS()


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


    if N == 0:
        if A[0] != 0:
            print(-1)
        else:
            print(1)
        return
    if A[0] != 0:
        if sum(A[1:]) == 0:
            print(1)
        else:
            print(-1)
        return


    sum_top = 1

    tmp = 1
    
    for i in range(1,N+1):
        max_l = tmp*2
        if max_l >= max_nodes[i]:
            print(sum_top+sum(max_nodes[i:]))
            return
        sum_top += max_l
        tmp = max_l - A[i]
        if tmp < 0:
            print(-1)
            return

    dbg(sum_top)
    print(-1)


main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

deep = int(input())
list = []
list = input().split(" ")
ans = []
sum = 0
print(list)

for i in range(deep, -1, -1):
    sum = sum + int(list[i])
    ans.append(sum)

print(ans)

k=0
for i in range(deep, -1, -1):
    print(ans[i])
    if ans[i] > 2**k:
        ans[i] = 2**k
    k = k+1
    
print(ans)
    
ans_num = 0
for i in range(len(ans)):
    ans_num = ans[i] + ans_num

print(ans_num)

Submission status: Wrong Answer

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

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

if A[0] != 0:
    print(-1)
else:
    for index, a in enumerate(A[1:], start=1):
        nodes[index] = nodes[index - 1] * 2 - a
        if nodes[index] < 0:
            print(-1)
            break
    else:
        fixed_nodes = [0] * (N + 1)
        fixed_nodes[-1] = A[-1]
        for i in reversed(range(N)):
            fixed_nodes[i] = min(nodes[i], fixed_nodes[i + 1])
            fixed_nodes[i] += A[i]
        else:
            if any([n == 0 for n in fixed_nodes]):
                print(-1)
            else:
                print(sum(fixed_nodes))

Submission status: Wrong Answer

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

max_v=[0 for _ in range(n+1)]
max_v[0]=1-a[0]
if(max_v[0]<=0 or a[-1]<=0):
    print(-1)
    sys.exit()
#print(0,max_v[0])

for i in range(1,n+1):
    max_v[i]=2*max_v[i-1] - a[i]
#    print(i,max_v[i])
    if(max_v[i]<=0 and i<n):
        print(-1)
        sys.exit()
#print(max_v)
ans=a[-1]
v=a[-1]
for i in range(n-1,-1,-1):
    if(v>2*max_v[i]):
        print(-1)
        sys.exit()
    v=min(v,max_v[i])
    v+=a[i]
    ans+=v
#    print(i,v,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ok=True
ans=[0]
a=[int(i) for i in input().split()]
lima=[2**i-a[i] for i in range(n+1)]
a=a[::-1]
lima=lima[::-1]

for i in range(n+1):
    ans.append(min(a[i]+ans[-1],lima[i]))
    if ans[-1]<=0:
        ok=False
        break
if ok:
    #print(ans)
    #print(lima)
    print(sum(ans))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==1:
  if a==[0,1]:
    print(2)
  elif a==[0,2]:
    print(3)
  else:
    print(-1)
  exit()
if n==0:
  if a==[1]:
    print(1)
  elif a==[2]:
    print(2)
  else:
    print(-1)
  exit()



subt=[0]*(n)
if a[0] == 0:
  subt[0]=2
elif a[0]== 1:
  subt[0]=1
else:
  print(-1)
  exit()

for i in range(n-1):
  #subt[i+1]=subt[i]-subt[i]*2
  #print(subt[i])
  if a[i+1] > subt[i]-1:
    if i<n-1:
      print(-1)
      #print(n)
      #print(subt[i])
      exit()
      #pass
    elif a[i+1] > subt[i]:
      print(-1)
      exit()
      #pass
  else:  
    subt[i+1]=(subt[i]-a[i+1])*2
if a[n]> subt[-1]:
  print(-1)
  exit()
if a[n] > subt[-2]:
  subt[-1]=a[n]
else:
  subt[-1]=a[n]
  for j in range(2,n):
    if (subt[-j]-a[-j])*2 < subt[1-j]:
      print(-1)
      exit()
    if (subt[-j]-a[-j]) <= subt[1-j]:
      pass
    else:
      subt[-j]=subt[1-j]+a[-j]
  
    #pass
  
print(sum(subt)+1)
    
#print(subt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
C = 1
for i in range(N):
  if A[i] > C:
    ans = -1
    C = 0
  else:
    ans += C
    C = (C-A[i])*2
    #print(ans)

if A[N] > C:
    ans = -1
else:
  ans += C
  b = C-A[N]
  ans -= b
  while (b-C//2)>0:
    ans -= b-C//2
    b = b-C//2
    C = C//2
print(ans)

Submission status: Wrong Answer

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
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    ans=0
    for i in range(N):
        if A[i] > 2**i:
            ans = -1
            break
        else:
            ans += A[i]-1
    if A[N] >2**N:
        ans = -1
    else:
        if ans == -1:
            pass
        else:
            ans = ans + A[N]
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if A[0] != 0:
    print(-1)
    exit()
A.reverse()
B = []
ans = 0
num = 0
num2 = 0
for i in range(N+1):
    lim = 2**(N-i)
    if A[i] > lim:
        print(-1)
        exit()
    num = min(num+A[i],lim)
    B.append(num)
A.reverse()
B.reverse()
for i in range(N):
    num2 = B[i]-A[i]
    if num2*2 < B[i+1]:
        B[i+1] = num2*2
print(sum(B))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)

b[0] = 1
for i in range(n):
    b[i+1] = 2*(b[i] - a[i])

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]

d = [0]*(n+1)
flag = 0
for k in range(n+1):
    if b[k] < c[k]:
        d[k] = b[k]
        if d[k] <= 0:
            flag += 1
    else:
        d[k] = c[k]
        if d[k] <= 0:
            flag += 1

for l in range(n):
    flag += 1 if d[l+1] < d[l] - a[l] or 2*d[l] - a[l] < d[l+1] else 0
    flag += 1 if a[l] + (d[l+1]+1)//2 > d[l] or d[l] > d[l+1] + a[l] else 0

print(sum(d) if flag == 0 else -1)

Submission status: Wrong Answer

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

n = int(input())
a = list(mapi())
res =a[n]
mp = [min(2**(i),int(1e8)) for i in range(n+1)]
#print(*mp)
lst = 1
pst = [0]*(n+1)
for i in range(n+1):
    #print(lst,a[i])
    #res+=lst
    pst[i] = lst
    if pst[i]<=0:
        print(-1)
        exit()
    lst-=a[i]
    lst*=2
#print(*pst,"c")
#print(*mp,"d")
mx = a[n]
for i in range(n-1,-1,-1):
    if a[i]>=mp[i] or mx+a[i]>pst[i]:
        res = -1
        break
    mx = min(mx+a[i],mp[i])
    res+=min(mx,pst[i])
    #print(res,mx,mp[i],a[i])
print(res)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
li = list(map(int,input().split()))

if n == 0:
    print(0)

if li[0]!=0:
    print(-1)
    exit()

tmp = 1
for i,l in enumerate(li):
    if i == 0:
        continue
    tmp *= 2
    if l > tmp:
        print(-1)
        exit()
    else:
        tmp -= l

max_li = [1]
for i,l in enumerate(li):
    if i == 0:
        continue
    la = (max_li[-1]-li[i-1])*2
    max_li.append(la)


li.reverse()
ans = 0
codomo = li[0]
for i,l in enumerate(li):
    if i == 0:
        if l > 2**(n-i):
            print(-1)
            exit()
        else:
            ans += codomo
    else:
        tmp = codomo + l
        fin = min(min(2**(n-i),tmp),max_li[n-i])
        #print(min(2**(n-i),tmp),max_li[i],i,'i')
        ans += fin
        codomo = fin
    #print(ans,'ans')
print(ans)

Submission status: Wrong Answer

Solution code:
# C
 
N = int(input())
A_N = list(map(int, input().split()))
if N == 0:
    print(1 if A_N[0] == 1 or A_N[0] == 0 else -1)
    # print(1 if A_N[0] == 1 else -1)
    exit()

reversed_A_N = list(reversed(A_N))
for i in range(1, N + 1):
    reversed_A_N[i] += reversed_A_N[i - 1]
r_reversed_A_N = list(reversed(reversed_A_N))
 
 
r_reversed_A_N[0] = 1
for i in range(N):
    max_next_nodes = (r_reversed_A_N[i] - A_N[i]) * 2 - A_N[i+1]
    if max_next_nodes < 0:
      print(-1)
      exit()
    elif max_next_nodes >= r_reversed_A_N[i+1]:
        break
    else:
        r_reversed_A_N[i+1] = max_next_nodes + A_N[i+1]
 
r_reversed_A_N[i+1] = list(reversed(reversed_A_N))[i+1]# A_N[-1]
print(sum(r_reversed_A_N))

Submission status: Wrong Answer

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

ans = 1
flag = 1
for i in range(N):
    e = (e - A[i]) * 2
    if e < A[i+1]:
        flag = 0
        break
    tmp = min(e, s)
    s -= A[i+1]
    ans += tmp
if flag == 0:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

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

B = dict()
sm = 0
for i in range(len(A)-1, -1, -1):
    sm += A[i]
    B[i] = sm


cnt = 1
roots = 1
for i in range(N):
    roots = roots * 2
    k = B[i+1]
    if roots > k:
        roots = k

    if roots - A[i+1] <= 0:
        print("-1")
        exit()

    cnt += roots
    roots -= A[i+1]
print(cnt)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A == [0]:
            print('-1')
        elif A == [1]:
            print('1')
        else:
            print('-1')
        return

    if N == 1:
        if A == [0, 1]:
            print('2')
        elif A == [0, 2]:
            print('3')
        else:
            print('-1')
        return

    f = [0 for i in range(N)]

    f[0] = 1
    count = sum(A) - 1
    if sum(A) == 0:
        print('-1')

    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)
        if f[d] < 0:
            print('-1')
            return
    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: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
 
if n == 0:
    print(1 if a[0] == 1 else -1)
    exit()

if a[0] != 0:
    print(-1)
    exit()
 
ans = 1
sm = sum(a)
limit = 1
for i in range(1, n):
    ans += a[i]
    limit = 2*limit - a[i]
    if limit <= 0:
        print(-1)
        exit()
    else:
        sm -= a[i]
        if limit <= sm:
            ans += limit
        else:
            ans += sm
 
ans += a[-1]
 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys #追加
from collections import deque
sys.setrecursionlimit(10**9) #追加

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

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

start = 1
way = sum(A)

for i in range(1,n+1):
    start *= 2

    if start < A[i]:
        print(-1)
        exit()
    if start > way:
        start = way

    ans += start
    #print(start, start-A[i])
    start -= A[i]
    way -= A[i]
#print()
print(ans+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0 and a[0]==1:
	print(-1)
elif n==0:
	print(-1)
elif a[0]!=0:
	print(-1)
elif a[n]==0:
	print(-1)
else:
	ruisekiwa = [0 for _ in range(n+1)]
	ruisekiwa[n] = a[n]
	for i in range(n)[::-1]:
		ruisekiwa[i] = a[i] + ruisekiwa[i+1]
	cnt=1
	ans=1
	for i in range(1,n+1):
		target = a[i]
		if cnt*2 - target <= 0 and i != n:
			print(-1)
			exit()
		elif i == n:
			if cnt * 2 - target < 0:
				print(-1)
				exit()
			else:
				cnt = min(cnt*2, a[n])
				ans += cnt
		else:
			if cnt*2-a[i] < ruisekiwa[i]:
				ans += cnt*2
				cnt = cnt*2-a[i]
			else:
				ans += ruisekiwa[i]
				cnt = ruisekiwa[i]
	print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = [int(a) for a in map(int, input().split())]
root = [1 - A[0]]
for i in range(1, A.__len__()):
    r = root[i-1] * 2 - A[i]
    if r > 0:
        root.append(r)
    elif r == 0 and i == N:
        root.append(r)
    else:
        print(-1)
        sys.exit()

ans = 0
for a in A:
    ans += a
for i in range(A.__len__() - 1):
    ans += min(root[i], A[N])

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

revA = reversed(A)
ans = 0

l = list(accumulate(revA))
for i in range(N+1):
    if l[i] > 2**(N-i):
        if i == 0:
            ans = -1
            break
        l[i] = 2**(N-i)

for i in range(N):
    if 2*(l[N-i]-A[i]) < l[N-i-1]:
        l[N-i-1] = 2*(l[N-i]-A[i])

for i in range(N+1):
    if l[i] > 0:
        ans += l[i]
    else:
        ans = -1
        break

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

Submission status: Wrong Answer

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 <= 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: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    if n == 0:
        if a[0] == 1:
            print(1)
        else:
            print(-1)
    else:
        check = [2 ** i - 1 for i in range(n)] + [2 ** (n + 1)]
        ans = [1] * n + [a[-1]]
        for i in range(n + 1):
            if check[- 1 - i] < a[- 1 - i]:
                print(-1)
                break
        else:
            for i in range(1, n):
                ans[i] = (ans[i - 1] - a[i - 1]) * 2
            for i in range(n - 1):
                ans[- 2 - i] = min(ans[- 2 - i], ans[- 1 - i] + a[- 2 - i])
            print(sum(ans))

main()