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:
N = int(input())
A = list(map(int,input().split()))

cap = [1]*(N+1)#0-N

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

for i in range(1,N+1,1):#1-N
    cap[i]=min(cap[i-1]*2 - A[i],10**8)
    if cap[i] < 0 or (cap[i]==0 and i!=N):
        print(-1)
        exit()

T = [0]*(N+1)
T[N]=A[N]#ここのキャパオーバーは上ではじけるはず
for i in range(N-1,-1,-1):
    T[i]=A[i]+min(T[i+1],cap[i])

print(sum(T))

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [int(x) for x in input().split()]
ans = 1
wa = sum(l)
kosuu = 1 - l[0]
flag = 0
for i in range(1,N):
    if  flag == 0:
        kosuu = kosuu * 2
    if kosuu >= wa:
        flag = 1
        kosuu = wa
    ans += kosuu
    kosuu = kosuu - l[i]
    wa = wa-l[i]
    if kosuu <= 0:
        print(-1)
        exit()
if kosuu*2 < l[N]:
    print(-1)
else:
    print(ans+l[N])

Submission status: Wrong Answer

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

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

capacity = [1 - A[0]]
for i in range(N):
    # i 段目の許容数は上の段の許容数と上の段の歯の数で来まる
    capacity += [2 * (capacity[-1] - A[i])]


corr_flag = 1
if A[-1] > capacity[-1]:
    corr_flag = 0
curr = A[-1]
ans = A[-1]
for i in range(N-1, -1, -1):
    curr = min(capacity[i], A[i] + curr)
    ans += curr
if corr_flag:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(num) for num in input().split()]
b = [0] * (n+1)
b[n] = a[-1]
for i in range(n):
    b[n-1-i] = b[n-i] + a[-i-2]
#c = [0] * (n+1)
#c[n] = a[-1]
#for i in range(n):
#    c[n-1-i] = c[n-i] // 2 + a[-i-2]
#print(c)

ans = 1
fl = True
if a[0] == 0:
    n_dep = 1
elif a[0] == 1:
    n_dep = 0
else:
    fl = False

if fl:
    for i in range(1,n+1):
        #print(i,n_dep)
        if a[i] > n_dep*2:
            ans = -1
            break
        elif n_dep * 2 <= b[i]:
            n_dep *= 2
            ans += n_dep
            n_dep -= a[i]
        else:
            n_dep = b[i] - a[i]
            ans += b[i]
    
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
if n==0:
    if a[0]==0:
        print(-1)
    else:
        print(1)
    quit()
if a[0]==1:
    if n!=0:
        print(-1)
        quit()

maxnode=[1]
for i in range(1,n):
    maxnode.append(maxnode[i-1]*2-a[i])
    if maxnode[i-1]*2-a[i]<=0:
        print(-1)
        quit()
# print(maxnode)

sita=0
ans=0
for i in range(n+1)[::-1]: 
    now=pow(2,i)
    # print(now)

    if i==n:
        if (a[i]+1)//2>maxnode[-1]:
            print(-1)
            quit()
        else:
            maxnode[-1]=min(a[i],maxnode[-1])
            ans+=a[i]
    else:
        if maxnode[i]+a[i]>maxnode[i-1]*2:
            print(-1)
            quit()
        else:
            maxnode[i-1]=min(maxnode[i]+a[i],maxnode[i-1])
            ans+=maxnode[i]+a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
# step 1 後ろからの累積
cum = [0] * (n + 1)
cum[n] = a[n]
for i in range(n):
    cum[n - 1 - i] = cum[n - i] + a[n - 1 - i]
# step2 dpを更新する
# dp はその深さに存在する頂点の数
dp = [0] * (n + 1)
dp[0] = 1
ans = dp[0]
ng = 0
for i in range(n):
    dp[i + 1] = min(2 * (dp[i] - a[i]), cum[i + 1])
    if dp[i + 1] <= 0:
        ng = 1
    ans += dp[i + 1]
if ng or n > 3 * 10 ** 4:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    A=list(map(int,input().split()))
    if n==0:
        if A[0]==1:
            print(1)
        else:
            print(-1)
        exit()
    C=[0]*(n+1)
    flag=True
    ans=1
    if A[0]==1:
        C[0]=0
        c=0
    else:
        C[0]=1
        c=1
    for i in range(n):
        a=A[i+1]
        c*=2
        ans+=c
        if c<a:
            flag=False
            break
        else:
            c-=a
            C[i+1]=c
    if flag:
        C[i+1]=c+a
        for i in range(n+1):
            if c<=0:
                break
            else:
                ans-=c
                c-=(C[n-i]+1)//2
        print(ans)
    else:
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

x = 1
ans = 0
for i in range(n+1):
    ans += x
    x -= a[i]
    if (x <= 0 and i != n) or x < 0: print(-1); exit()
    if x == s[i]: continue
    if x*2 > s[i+1]: x = s[i+1]
    else: x *= 2

print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    A = list( map( int, input().split()))
    root = 1
    if A[0] == 1:
        if N == 0:
            print(1)
        else:
            print(-1)
    B = A[::-1]
    low = high = B[0]
    # Low = []
    Hight = [high]
    
    for b in B[1:]:
        low = max(1, (low+1)//2) + b
        high = high + b
        Hight.append(high)
    if low > 1:
        print(-1)
        return
    ans = 1
    now = 1
    BHight = Hight[::-1]
    for i in range(1,N+1):
        h = BHight[i]
        leaf = A[i]
        # print("h",h)
        now = min(h, now*2)
        ans += now
        now -= leaf
        # print(now)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

max_forward = [1]
now = 1
flag = 0
for i in range(N):
    now = (now - A[i])*2
    if now <= 0:
        flag = -1
        break
    max_forward.append(now)

max_backward = [A[-1]]
now = A[-1]
for i in range(N):
    ind = N-i-1
    now = now + A[ind]
    max_backward.append(now)

if flag == -1:
    print(-1)
else:
    ans = 0
    for i in range(N+1):
        temp = min(max_forward[i], max_backward[N-i])
        #print(temp)
        ans += temp
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    A_sum = sum(A)
    ans = 1
    tmp_v = 1
    if A[0] > 0 and A_sum - A[0] > 0:
        print(-1)
        sys.exit()
    for i in range(N):
        if A[i+1] > tmp_v*2:
            print("-1")
            sys.exit()
        tmp_v = min(tmp_v*2, A_sum)
        ans += tmp_v
        A_sum -= A[i+1]
        tmp_v -= A[i+1]
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
  input()
  in_a = list(map(int, input().split()))
  leaves = [0] * len(in_a)

  if in_a[0] != 0:
    print(-1)
    return
  
  for i in range(len(in_a) - 1, 1, -1):
    leaves[i-1] = leaves[i] + in_a[i]

  node = 1
  total = 1

  for i in range(1, len(in_a)):
    n = node * 2
    r = min(n - in_a[i], leaves[i])
  
    if r < 0:
      print(-1)
      return

    total += in_a[i] + r
    node = r

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

Submission status: Wrong Answer

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()
INF = 10**8+1
res = [1]
res3 = [1]
for i in lst1[1:]:
    res3.append(min(INF,res[-1]*2)) #res3-1の値を上回った時点で不可能
    res.append(min(INF,res[-1]*2-i))

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

res2 = [0]
for i in lst1[::-1]:
    res2.append(min(INF,res2[-1]+i))

res2.reverse()

ans = []
for i,j in zip(res3,res2[:-1]):
    ans.append(min(i,j))
print(sum(ans))
"""print(*res)
print(*res3)
print(*ans)
"""

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

if N == 0:
    if A_list[0] == 1:
        print(0)
    else:
        print(-1)
elif A_list[0] != 0:
    print(-1)
else:
    ans = 1
    deathable_node = 1
    sum_rest_A = sum(A_list)
    for i in range(1, N + 1):
        now_A = A_list[i]
        deathable_node = min(sum_rest_A, deathable_node * 2) - now_A

        if deathable_node < 0:
            print(-1)
            break

        sum_rest_A -= now_A
        ans += deathable_node + now_A
        # print(i, now_A, sum_rest_A, deathable_node, ans)
    else:
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    node = [0] * (N+1)
    node[0] = 1
    z = 0
    for i in range(N):
        node[i] -= A[i]
        node[i+1] = node[i] * 2

    node[N] = 0
    for i in range(N-1,-1,-1):
        if node[i+1]+A[i+1] > node[i] * 2:
            print(-1)
            return
        node[i] = min(node[i+1]+A[i+1],node[i])

    print(sum(node)+sum(A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def Csum(a):
    b,c=[0],0
    for i in range(len(a)):
        c+=a[i]
        b.append(c)
    return b

n=int(input())
a=list(map(int,input().split()))
s=Csum(a)
su=sum(a)
b=1
c=0
for i in range(n+1):
    c+=b
    b-=a[i]
    if b<=0:
        if i==n:
            break
        print(-1)
        exit()
    b=min(b*2,su-s[i+1])
print(c)

Submission status: Wrong Answer

Solution code:
import unittest


def solve(n, leafs):
    if leafs[0] == 1:
        if n == 0:
            return 1
        else:
            return -1
    left_nodes = 1
    total_node_count = 0
    usable_nodes = [1]*(n+1)
    for i in range(n):
        if leafs[i] <= left_nodes:
            total_node_count += left_nodes
            left_nodes -= leafs[i]
            left_nodes *= 2
            usable_nodes[i+1] = left_nodes
        else:
            return - 1
    # 末端のレベルは
    total_node_count += left_nodes
    if left_nodes + leafs[-1] > 2 ** n:
        return - 1

    max_node = [0 for i in range(n + 1)]
    max_node[n] = leafs[n]
    for i in range(n - 1, -1, -1):
        if i > 28:
            max_node[i] = min(usable_nodes[i], leafs[i]+max_node[i+1])
        else:
            max_node[i] = min(2 ** i, usable_nodes[i], leafs[i]+max_node[i+1])

    return sum(max_node)


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


class Test(unittest.TestCase):
    def test_solve_1(self):
        n = 3
        a = [0, 1, 1, 2]
        actual = solve(n, a)
        expected = 7
        self.assertEqual(actual, expected)

    def test_solve_2(self):
        n = 4
        a = [0, 0, 1, 0, 2]
        actual = solve(n, a)
        expected = 10
        self.assertEqual(actual, expected)

    def test_solve_3(self):
        n = 2
        a = [0, 3, 1]
        actual = solve(n, a)
        expected = -1
        self.assertEqual(actual, expected)

    def test_solve_4(self):
        n = 1
        a = [1, 1]
        actual = solve(n, a)
        expected = -1
        self.assertEqual(actual, expected)

    def test_solve_5(self):
        n = 10
        a = [0, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
        actual = solve(n, a)
        expected = 264
        self.assertEqual(actual, expected)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

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

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

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

M = min(60,N+1)

B = [1]*M
for i in range(1,M):
    B[i] = B[i-1]*2 - A[i]

ans = 0
p = 0
for i,a in enumerate(A[::-1]):
    i = N - i
    if i<60:
        m = B[i]
    else:
        m = 1e18
    if p>2*m:
        ans = -1
        break
    p = min(m,p)+a
    ans += p

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
L=[0]*(n+1)
L[0]=1
Chk=True
for i in range(n+1):
  if i==0:
    if A[i]>0:
      Chk=False
      break
  elif i<n:
    if L[i-1]*2<=A[i]:
      Chk=False
      break
    else:
      L[i]=L[i-1]*2-A[i]
  else:
    L[i]=L[i-1]*2

if L[-1]<A[-1]:
  Chk=False
else:
  L[-1]=0
  ans=A[-1]
  cur=A[-1]
  for i in range(n)[::-1]:
    ans+=min((A[i+1]+L[i+1]),L[i])+A[i]



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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

B = [1]
for i in range(n):
    B.append((B[i]-A[i])*2)

C = [A[n]]

for i, s in enumerate(B):
    if i == len(B)-1:
        a = 1
    elif B[i] <= 0:
        print(-1)
        exit()
if B[-1] < 0:
    print(-1)
    exit()


for i in range(n):
    C.append(C[i]+A[n-1-i])
C = C[::-1]

num = 0
frag = 0
for i in range(n):
    if B[i] >= C[i]:
        frag = 1
    if frag == 0:
        num += B[i]
    else:
        num += C[i]
num += C[n]
print(num)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
sum_A=sum(A)
if A[0]!=0:print(-1);exit()

flag=0
ans,point=[1],1
for i in range(1,n+1):
    if flag==0:
        point *=2
    if point>=sum_A:
        point=sum_A
        flag=1
    ans.append(point)
    if point<0:print(-1);exit()
    point -=A[i]
    sum_A -=A[i]
print(sum(ans))

Submission status: Wrong Answer

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

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

arr.reverse()

ar2 = [None] * (n+1)

for i, e in enumerate(arr):
    if i == 0:
        ar2[0] = (e, e)
        continue

    ar2[i] = (ar2[i-1][0]+e, (ar2[i-1][1]+1) // 2 + e)

if ar2[-1][1] > 1:
    print(-1)
    exit()

ar2.reverse()

total = 0
acc = 1
for i, t in enumerate(ar2):
    acc = min(acc, t[0])

    total += acc
    acc -= arr[n-i]
    acc *= 2

print(total)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))
n=n_in()
A=l_in()

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


if A[0] != 0:
    print(-1)
    exit()
    
B=[0]*(n+1)
B[0] = 1

upper = max(A)

for i in range(1, n):
    B[i] = min(B[i-1]*2-A[i], sum(A[(i+1):]))
    if B[i] <= 0:
        print(-1)
        exit()

    

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=tuple(map(int,input().split()))
ans=1
tmp=0
M=[1]

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

for i,x in enumerate(A[1:],1):
    if i>=65:
        n=2**65
    else:
        n=2**i
    M.append(min(n-x,M[i-1]*2-x))
    if (i!=N and M[i]<=0) or (i==N and M[i]<0):
        print(-1)
        exit()
for i,(x,y) in enumerate(zip(A[1:][::-1],M[1:][::-1])):
    fukasa=N-i
    if fukasa>=30:
        n=10**8
    else:
        n=2**fukasa
    n=min(10**8,n)
    tmp+=x
    if y+x>n:
        print(-1)
        exit()
    tmp=min(tmp,n,y+x)
    ans+=tmp
if A[0]+M[0]>1:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0 and a==[1]:
	print(1)
	exit()
elif n==0 and a!=[1]:
	print(-1)
	exit()
elif a[0]==1:
	print(-1)
	exit()
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 = list(map(int, input().split()))

capacity = [1 - A[0]]
for i in range(N):
    # i 段目の許容数は上の段の許容数と上の段の歯の数で来まる
    capacity += [2 * (capacity[-1] - A[i])]


corr_flag = 1
if A[-1] > capacity[-1]:
    corr_flag = 0
curr = A[-1]
ans = A[-1]
for i in range(N-1, -1, -1):
    curr = min(capacity[i], A[i] + curr)
    ans += curr
if corr_flag:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1
    last = A[-1]
    now = 1
    cum = [last]*(N+1)
    for i in range(N-2,-1,-1):
        cum[i] = cum[i+1]+A[i+1]
    if now<A[0]:
        return -1
    now -= A[0]
    for i in range(1,N):
        if now<A[i]:
            return -1
        now = min(cum[i],now*2-A[i])
        if now==0:
            return -1
        ans += now+A[i]
    if now*2 < last:
        return -1
    return ans + last
print(solve())

Submission status: Wrong Answer

Solution code:
# coding: utf-8


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

    ret = 0

    R = [0]*(n+1)
    R[0] = 1-A[0]
    for i in range(1, n+1):
        R[i] = 2*R[i-1]
        for _ in range(A[i]):
            j = i
            if R[j] == 0:
                return '-1'

            while 0 < R[j]:
                R[j] -= 1
                ret += 1
                j -= 1

    return str(ret)


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

Submission status: Wrong Answer

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

flag = 0
node_sum = 0
now_node = 0
max_node = []
max_itr = 27
if n < 27:
    max_itr = n+1
for i in range(max_itr):
    if i == 0:
        max_node.append(1-a_list[0])
    else:
        max_node.append((max_node[i-1]-a_list[i-1])*2)
# print(max_node)

for d, a in enumerate(reversed(a_list)):
    max_now = 100000000
    d = n-d
    if d < max_itr:
        max_now = max_node[d]
    if (now_node+1)//2 + a > max_now:
        flag = 1
        break
    elif now_node + a > max_now:
        now_node = max_now
    else:
        now_node += a
    node_sum += now_node
    # print(f"{d} {now_node}")

if flag == 1:
    print(-1)
else:
    print(node_sum)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
sum_A=sum(A)
if A[0]!=0:print(-1);exit()

flag=0
ans,point=[1],1
for i in range(1,n+1):
    if flag==0:
        point *=2
    if point>=sum_A:
        point=sum_A
        flag=1
    ans.append(point)
    if point<=0:print(-1);exit()
    point -=A[i]
    sum_A -=A[i]
print(sum(ans))

Submission status: Wrong Answer

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def Yes(x):print("Yes")if x==True else print("No")
n=N()
l=L()
if l[0]==1:
    if sum(l)==1:
        print(1)
    else:
        print(-1)
    quit()
ans=[0]*(n+1)
v=1
ans[0]=1
for i in range(1,n+1):
    v*=2
    ans[i]=v
    v-=l[i]
    if v<0:
        print(-1)
        quit()
for i in range(n,0,-1):
    ans[i]-=v
    if ans[i]>=ans[i-1]-l[i-1]:
        break
    v=ans[i-1]-l[i-1]-ans[i]
print(sum(ans))

Submission status: Wrong Answer

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

def check():
    R = [0]*(N+1)
    R[0] = 1
    for i in range(N):
        if R[i] < A[i]:
            return -1
        R[i+1] = 2*(R[i]-A[i])
    if R[N] < A[N]:
        return -1
    
    
    CA = A[:]
    
    for i in range(N-1, -1, -1):
        CA[i] += CA[i+1]
    
    
    return sum(min(r, c) for r, c in zip(R, CA))


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

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

Submission status: Wrong Answer

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

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

nodes = []
if a[0] > 0:
    if a[0] == 1 and n == 0: print(1)
    else: print(-1)
    exit()
else:
    nodes.append(1)
if a[-1] > 2 ** n:
    print(-1)
    exit()

# forward
for i in range(1, n):
    x = nodes[i - 1] * 2 - a[i]
    if x <= 0:
        print(-1)
        exit()
    nodes.append(x)
nodes.append(0)

# backward
for i in range(n - 1, -1, -1):
    if nodes[i] > a[i + 1] + nodes[i + 1]:
        nodes[i] = a[i + 1] + nodes[i + 1]

print(sum(a) + sum(nodes))

Submission status: Wrong Answer

Solution code:
import copy

n = int(input())

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

down_max = [0 for i in range(n + 1)]

for i in range(n + 1):
    if i == 0:
        down_max[0] = 1
    else:
        down_max[i] = 2 * (down_max[i - 1] - a_i[i - 1])

answer = 0
now_point_number = 0
before_point_number = 0
cant_make = False

for i in range(n + 1):
    depth_index = - i - 1
    if i == 0:
        now_point_number = a_i[depth_index]
    else:
        if before_point_number // 2 + before_point_number % 2 + a_i[depth_index] > down_max[depth_index]:
            cant_make = True
            break
        else:
            now_point_number = min(down_max[depth_index], before_point_number + a_i[depth_index])
    answer += now_point_number
    before_point_number = copy.copy(now_point_number)

if cant_make or answer == 0:
    print(-1)
else:
    print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
c = [0]*(n+1)
r = [0]*(n+1)
c[0] = 1
r[n] = a[n]
ans = r[n]
fl = 1
if a[0] >= 1 and n >= 1:
  fl = 0
for i in range(1,n+1):
  c[i] = 2*c[i-1]-a[i]
  if c[i] <0:
    fl = 0
for i in reversed(range(n)):
  r[i] = min(r[i+1]+a[i],c[i]+a[i])
  ans += r[i]
if fl == 1:
  print(ans)
  #print('a',a)
  #print('c',c)
  #print('r',r)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys

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

s=0
for i in A:
    s+=i

S=[]
for i in range(n+1):
    S.append(s)
    s-=A[i]


if A[0]==1:
    if n==0:
        print(1)
    else:
        print(-1)
else:
    ans=1
    temp=1
    for i in range(n-1):
        #print(ans,temp)
        if A[i+1]>=2*temp:
            print(-1)
            sys.exit()
        else:
            temp=min(S[i+1],2*temp)
            ans+=temp
            temp-=A[i+1]
            
    
    if temp<=A[n]<=2*temp:
        ans+=A[n]
        print(ans)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
#len(A)=N+1
ak=1-A[0]
a=[ak]
k=0
while(ak>=0 and k<N):
    ak=2*ak-A[k+1]
    a.append(ak)
    if ak<0:
        print(-1)
        exit()
    if ak>=10**8:
        #以降に関わらず構成可能
        break
    k+=1
#print(a)
M=len(a)
for k in range(N,0,-1):
    if k<=M:
        A[k-1]+=min(A[k],a[k-1])
    else:
        A[k-1]+=A[k]
        continue
print(sum(A))
#print(A)

Submission status: Wrong Answer

Solution code:
def main():

    N = int(input())
    A = list(map(int, input().split()))
    SA = [0]
    for i in range(N + 1):
        SA.append(SA[-1] + A[N - i])
    SA.reverse()
    res = 0
    t = 1
    for i in range(N + 1):
        if t >= SA[i]:
            t = SA[i]
        res += t
        t -= A[i]
        if t <= 0:
            if i != N:
                return -1
        t *= 2
    return res


print(main())

Submission status: Wrong Answer

Solution code:
import math
#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):
    notleave = maxx[i-1] - leaves[i-1]
    if notleave < 0:
        total = -1
        break
    maxx[i] = notleave*2

if total >= 0:
    #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 > 0 and (math.log(newnod, 2) > ii):
            total = -1
            break
        #maximum is?
        newnod = nod + leaves[ii]
        if newnod > maxx[ii]: newnod = maxx[ii]
        total += newnod
        nod = newnod

if total <= 0: total = -1
print(total)

Submission status: Wrong Answer

Solution code:
# region header
import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div
# endregion
N = ri()
A = ri_()
# 限界値
B = [1] * (N + 1)
# 葉でない頂点の数
C = [0] * (N + 1)
if A[0] > 0:
    print(-1)
    exit()
for i in range(1, N + 1):
    B[i] = B[i - 1] * 2 - A[i]
    if B[i] <= 0:
        print(-1)
        exit()
for i in range(N - 1, -1, -1):
    C[i] = min(A[i + 1] + C[i + 1], B[i])
print(sum(A) + sum(C))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N,*A=map(int, open(0).read().split())
if N==0:
    if A[0]==1:
        print(1)
    else:
        print(-1)
    exit()
if A[0]!=0:
    print(-1)
    exit()
R=[0]*(N+2)
R[0]=1
ans=0
for i in range(N+1):
    R[i]-=A[i]
    if R[i]<0:
        print(-1)
        exit()
    R[i+1]=min(R[i]*2,10**10)
# if R[N]<A[N]:
#     print(-1)
#     exit()
B=list(accumulate(A[::-1]))[::-1]
ans+=sum(min(R[i]+A[i],B[i])for i in range(N+1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = [int(c) for c in input().split()]
B = [0]*(N+1)
B[0] = 1
if A[0]>=1:
  if N==0:
    print(1)
  else:
    print(-1)
  sys.exit()
for i in range(1,N):
  B[i] = B[i-1]*2-A[i]
  if B[i]<0:
    print(-1)
    sys.exit()
ans = sum(A)
num = 0
for i in range(N,0,-1):
  num = min(num+A[i],B[i-1])
  ans += num
print(ans)

Submission status: Wrong Answer

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()))
INF = 10**8+1
res = [1]
res3 = [1]
for i in lst1[1:]:
    res3.append(min(INF,res[-1]*2)) #res3-1の値を上回った時点で不可能
    res.append(min(INF,res[-1]*2-i))

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

res2 = [0]
for i in lst1[::-1]:
    res2.append(min(INF,res2[-1]+i))

res2.reverse()

ans = []
for i,j in zip(res3,res2[:-1]):
    ans.append(min(i,j))
"""print(*res)
print(*res3)
print(*ans)
print(sum(ans))"""

Submission status: Wrong Answer

Solution code:
N = int(input())
leafNodesPerLevel = [int(s) for s in input().split()]

MAX_VALUE = 4 * (10 ** 12)

def checkBinaryTree(N, leafNodesPerLevel):
    maxNodePerLevel = [0 for _ in range(N+1)]
    remainingNode = 1
    for depth in range(N+1):
        if remainingNode < leafNodesPerLevel[depth]:
            print(-1)
            return
        maxNodePerLevel[depth] = remainingNode
        remainingNode = min(2 * (remainingNode - leafNodesPerLevel[depth]), MAX_VALUE)

    lastLevelNode = leafNodesPerLevel[-1]
    total_node = lastLevelNode
    for depth in range(N, 0, -1):
        num = min(maxNodePerLevel[depth] // 2, lastLevelNode) + leafNodesPerLevel[depth-1]
        total_node += num
        lastLevelNode = num
    print(total_node)


checkBinaryTree(N, leafNodesPerLevel)