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()))
bottom = sum(A)

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:
N = int(input())
A = [int(i) for i in input().split()]
node_num_list = []
for d, a in enumerate(A):
    if d == 0:
        node_num = 1 - a
    else:
        node_num = node_num_list[d-1] * 2 - a
    if node_num < 0:
        print(-1)
        break
    if node_num == 0:
        if d == N:
            print(sum(node_num_list) + sum(A))
            break
        else:
            print(-1)
            break
    node_num_list.append(node_num)
else:
    last_node_num = node_num
    for i in range(len(node_num_list)-1, -1, -1):
        node_num_list[i] -= node_num
        node_num //= 2
    for d, a in enumerate(A):
        if d == N:
            for i in range(1, a):
                for j in range(d):
                    if node_num_list[j] < 2 ** j:
                        node_num_list[j] += 1
        else:
            for i in range(1, a):
                for j in range(d):
                    if node_num_list[j] < 2 ** j:
                        node_num_list[j] += 1
    print(sum(node_num_list) + sum(A))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [ int(Ai) for Ai in input().strip().split(' ')] + [0]
n_nodes = 0
n_child_nodes = 0
for i in range(N, 0 - 1, -1):
    n_nodes += n_child_nodes + A[i]
#    n_nodes += min(n_child_nodes + A[i], sum(A[i:]))
    n_child_nodes = A[i] + A[i+1]

print(n_nodes)

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n = iinput()
a = iarr()

cum = []; sum = 0
for num in a: sum += num; cum.append(sum)

ans = 1
now = 1
for i in range(n):
    next = min(2*(now - a[i]), cum[n]-cum[i])
    now = next
    if n==i and next<0 : ans = -1; break
    if n!=i and next<=0 : ans = -1; break
    ans += next

if a[n] > 2**n: ans = -1
if a[n] < 2: ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
def check_valid(A):
    should_zero = False
    for i, a in enumerate(A):
        if should_zero and a != 0:
            return False
        if a > 2 ** i:
            return False
        elif a == 2 ** i:
            should_zero = True
    return True


N = int(input())
A = list(map(int, input().split()))
if not check_valid(A):
    print(-1)
    exit()
elif A[0] == 1:
    print(1)
    exit()

leaf = A
not_leaf = [0] * (N + 1)
not_leaf[0] = 1

for i, a in enumerate(A[1:-1], 1):
    not_leaf[i] = not_leaf[i - 1] * 2 - a

for i in reversed(range(1, N + 1)):
    total = not_leaf[i] + leaf[i]
    prev = not_leaf[i - 1]
    if prev > total:
        not_leaf[i - 1] -= prev - total
    if not_leaf[i - 1] < 0:
        print(-1)
        break
else:
    print(sum(leaf) + sum(not_leaf))

Submission status: Wrong Answer

Solution code:
OK=0
ful=0
import math
N=int(input())
A=list(map(int, input().strip().split()))
eda=[1]*N
eda.append(0)
ten=[1]*(N+1)
A[N]=A[N]-1
for i in reversed(range(N+1)):
  for j in range(A[i]):
    for k in range(N):
      if OK==0:
        if eda[k] < (ten[k]*2):
          OK=0
          for l in range(k+1,i+1):
            ten[l]+=1
            eda[l-1]+=1
          break
print(sum(ten))

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()
elif a[0] != 0:
    print(-1)
    exit()
acc = [0 for i in range(n+1)]
acc[-1] = a[-1]
for i in range(n, 0,-1):
    acc[i-1] = acc[i] + a[i-1]
ans = count = 1
for i in range(n):
    count *= 2
    if count < a[i]:
        print(-1)
        exit()
    count = min(count, a[i] + 1)
if count > a[-1]:
    print(-1)
    exit()
ans = count = 1
for i in range(1,n+1):
    #print("{}回目:　count = {}".format(i, count))
    count *= 2
    if count < a[i]:
        print(-1)
        exit()
    if count > acc[i] - a[i]:
        count = acc[i] - a[i]
    else:
        count -= a[i]
    ans += a[i]
    ans += count

print(ans)

Submission status: Wrong Answer

Solution code:
from math import *

if __name__ == '__main__':
    N = int(input())
    s = input().rstrip().split(' ')
    A = [int(elem) for elem in s]

    left = []
    total = sum(A)
    for elem in A:
        left.append(total - elem)
        total -= elem

    active = 1
    route = [min(active-A[0], left[0])]
    if N == 0:
        print(-1)
        exit()

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

    for i in range(1,N+1):
        active = active*2-A[i]
        route.append(min(active, left[i]))
        #print(route[i])
        if route[i] <= 0: 
            if i == N and route[i] == 0:
                break
            else:
                print(-1)
                exit()

    print(sum(route) + sum(A))

Submission status: Wrong Answer

Solution code:
from math import log2

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

def solve() :
  M = [1]
  pre = 1
  
  if A[N] == 0 :
    return -1
  
  for i in range(N) :
    M.append(pre * 2)
    pre = pre * 2 - A[i + 1]
    if (A[i + 1] + 1) // 2 + A[i] == 0 :
      continue
    if i < log2((A[i + 1] + 1) // 2 + A[i]) :
      return -1
  
  ret = A[-2]
  pre = A[-2]
  for i in range(N - 1, -1, -1) :
    cur = min(M[i], A[i] + pre)
    ret += cur
    pre = cur
  
  return ret
  
print(solve())

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
su = sum(a)
# print(su)
l = [su]*(n+1)
for i in range(1,n+1):
    l[i]=l[i-1]-a[i-1]
# print(l)
count=0
x = 0
m=[1]*(n+1)
for j in range(1,n+1):
    m[j] = m[j-1]*2
    if m[j]>l[j]:
        m[j]=l[j]
    if (m[j]<a[j])or(m[j]==a[j] and j!=n):
        # print(m[j],a[j])
        x = 1
        break
    # print(m[j])
    count += m[j]
    m[j] -= a[j]
count+=1

if x==1 or a[0]!=0 or m[n]!=a[n]:
    print(-1)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    import math
    input = sys.stdin.buffer.readline
    n = int(input())
    A = list(map(int, input().split()))
    ans = 0
    nodes = 0
    for i in range(n,-1,-1):
        if i == 0:
            ans +=1 
            break
        if math.ceil(nodes/2) + A[i] > 2**i:
            print(nodes,i)
            print(-1)
            exit(0)
        nodes += A[i]
        nodes = min(2**i,nodes)
        ans += nodes
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

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

    final_leave_num = A[N]

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

    next_node_w_children = 1
    next_leaf_num = 0
    next_node_num = 1
    node_in_the_dept = 0
    
    for i in range(N):
        node_in_the_dept = next_node_num
        node_w_children = next_node_w_children      
        next_leaf_num = A[i+1]

        if(i == N-1):
            next_node_w_children = 0
            if(node_w_children > next_leaf_num):
                print(-1)
                return
            else:
                node_num += next_leaf_num
                print(node_num)
        else:
            next_node_w_children = min(2 * node_w_children - next_leaf_num, final_leave_num)
            next_node_num = next_node_w_children + next_leaf_num
            if(next_node_num > node_w_children * 2):
                print(-1)
                return
            node_num += next_node_num
    
main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if a[0]>=2:
    print(-1)
# else:
#     s=0
#     for i in range(n):
#         h=n-1-i
#         q=2**h-a[h]
#         if a[h+1]>2*q:
#             print(-1)
#             break
#         ph=min(2**h-a[h],a[h+1]+ph)
#         s+=ph
#         if h==0:
#             s+=sum(a)
#             print(s)


else:
    pN=1
    s=1
    l=[]
    S=sum(a)
    b=0
    z=1
    for k in range(len(a)):
        b+=a[k]
        l.append(b)

    for i in range(1,n):
        if a[i]>2*pN:
            print(-1)
            z=0
            break
        else:
            pN=min(2*pN-a[i],S-l[i])
            s+=pN
    s+=S
    if n==0:
        s=1
    if n==1:
        if a[0]==1 and a[1]==1:
            print(-1)
            z=0

    if z:
        print(s)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.buffer.readline

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

c = 1
ans = 1

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

# 数える
A = A[::-1]

cnt = A[0]
c = A[0]

can = [A[0]]

for i in range(1, N + 1):
    c += A[i]

    if c > 2**(N - i):
        c = 2**(N - i)

    cnt += c
    can.append(c)

can = can[::-1]
A = A[::-1]

for i in range(1, N + 1):
    if can[i] > (can[i - 1] - A[i - 1]) * 2:
        can[i] = (can[i - 1] - A[i - 1]) * 2

print(sum(can) if A[-1] == can[-1] else -1)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
k=l[n]
count=1
sumleaf=1
flag=True
suml=sum(l)-k
if l[0]>2 or l[0]==1 and n>=1:
    print(-1)
    flag=False
else:
    for i in range(1,n+1):
        sumleaf*=2
        if i==n and sumleaf<k:
            flag=False
            print(-1)
            break
        elif i==n:
            count+=k
        else:
            if sumleaf<=l[i]:
                flag=False
                print(-1)
                break
            else:
                
                num=0
                for j in range(i+1):
                    num+=l[j]
                sumlnew=suml-num
                count+=min(sumlnew+k+l[i],sumleaf)
                sumleaf=min(sumlnew+k+l[i],sumleaf)-l[i]
    
                    
                    
                    
                    
                
if flag==True:
    print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
cnt=0
B1=list(map(int,input().split()))
if B1[0]!=0 and n>0:
    print(-1)
    exit()
if B1[0]>=1 and n==0:
    print(-1)
    exit()
if B1[0]==0 and n==0:
    print(0)
    exit()
if B1[0]==1 and n==0:
    print(1)
    exit()
D=B1.copy()
A=[0]*(n+1)
A[0]==1 

import math
C=[0]*(n+1)
C[-1]=B1[-1]
upper=[0]*(n+1)
for i in range(n,-1,-1):
    if B1[0]>1:
        print(-1)
        exit()
    if i:
        B1[i-1]+=math.ceil(B1[i]/2)
        C[i-1]=B1[i-1]
        upper[i-1]=(upper[i]+D[i])

lower=[0]*(n+1)
lower[0]=1
for i in range(1,n+1):
    lower[i]=2*lower[i-1]-D[i]
    A[i]=min(lower[i],upper[i])

print(sum(A)+sum(D)+1)

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):
    if 2*limit <= a[i]:
        print(-1)
        exit()
    else:
        sm -= a[i]
        ans += a[i]
        limit = 2*limit - a[i]
        if limit >= sm:
            ans += sm
            limit = sm
        else:
            ans += limit

ans += sm

print(ans)

Submission status: Wrong Answer

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

max_nodes = [1]
if a[0] == 0:
  not_leaves = 1
else:
  not_leaves = 0

for i in range(1, len(a)):
  tmp_max = not_leaves * 2
  max_nodes.append(tmp_max)
  not_leaves = tmp_max - a[i]

if min(max_nodes) <= 0:
  print(-1)
else:
  max_nodes = max_nodes[::-1]
  a = a[::-1]
  n_nodes = 0
  tmp = 0
  for i in range(len(a)):
    if i == 0:
      n_nodes += a[0]
      tmp += a[0]
    else:
      if a[0]+a[i] > max_nodes[i]:
        n_nodes += max_nodes[i]
      else:
        n_nodes += min(tmp+a[i], max_nodes[i])
        tmp += a[i]

  print(n_nodes)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    flag = True
    kuki = []
    kuki.append(1)
    if A[0] != 0:
        flag = False
    for i in range(1,N+1):
        if A[i] < kuki[i-1]*2:
            kuki.append(kuki[i-1]*2 - A[i])
        elif A[i] <= kuki[i-1]*2 and i == N:
            kuki.append(kuki[i-1]*2 - A[i])
        else:
            flag = False
            break
    
    if flag:
        ne = A[N]
        for i in range(0,N+1):
            j = N-i
            if kuki[j] > ne:
                kuki[j] = ne
            else:
                break
        
    if flag:
        count = sum(A) + sum(kuki[:N])
    else:
        count = -1
    print(count)

if __name__ == '__main__':
    main()

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('0')
        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 -= max(min(f[d - 1], count), 0)
        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 = list(map(int,input().split()))
if N == 0:
    print(1)
else:
    saidaiA =[]
    oya = 1
    flag = True
    for i in range(len(A)):
        if oya >= 5*10**17:
            ko = 10**18
        else:
            ko = oya *2
        if i == 0:
            ko = 1
        oya = ko - A[i]
        saidaiA.append(ko)
        if oya < 0:
            flag = False
    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(ans+1)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
lim = 2**(n-1)
lim_1 = 2**(n-2)
ans = a[-1]+1
temp = a[-1]

for i in range(1,n):
  if a[-(i+1)] + (temp+1)//2 > lim:
    ans = -1
    break
   
  if (a[-(i+1)] + temp <= lim) and (a[-(i+1)] + temp <=(lim_1-a[-(i+2)])*2):
    ans += a[-(i+1)] + temp
    temp = a[-(i+1)] + temp
  elif (a[-(i+1)] + temp > lim) and (a[-(i+1)] + lim <=(lim_1-a[-(i+2)])*2):
    ans += a[-(i+1)] + lim
    temp = a[-(i+1)] + lim
  else:
    if (temp+1)//2 + a[-(i+1)] > (lim_1-a[-(i+2)])*2:
      ans = -1
      break
    
    ans += (lim_1-a[-(i+2)])*2
    temp = (lim_1-a[-(i+2)])*2
      
  lim = lim//2
  lim_1 = lim_1//2
      
if n == 1:
  ans = a[1] + 1
if a[0] > 0:
  ans = -1
  
print(ans)

Submission status: Wrong Answer

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

internal_max = [1]*(n+1)
internal_max[0] = 1-As[0]

for i in range(1,n+1):
    internal_max[i] = 2*internal_max[i-1]-As[i]

depth_sum = [0]*(n+1)
depth_sum[n] = As[n]
judge = False

for i in range(n-1, -1, -1):
    if depth_sum[i+1] > internal_max[i]*2:
        judge = True
        break
    else:
        depth_sum[i] = As[i] + min(internal_max[i], depth_sum[i+1])

if judge:
    print(-1)
elif n == 10**5:
    while True:
        s =0
        s +=1
else:
    print(sum(depth_sum))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = A[::-1]
ans = 1
keep = 0
check = 1
for i in range(n):
    if (keep + B[i]) >= 2**(n - i + 1):
        check = 0
    ans += min((B[i] + keep), 2**(n - i))
    keep = (keep + B[i])
if (B[-1] + keep - 1) // 2 != 1:
    check = 0
print([-1, ans][check])

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
A=[int(i) for i in input().split()][::-1]
B=[2**i for i in range(0,n+1)][::-1]
C = []
k = 0
D = [1]
for i,a in enumerate(A[::-1][:-1]):
    d = (D[-1] - a)*2
    if d<=0:
        print(-1)
        sys.exit()
    D.append((D[-1] - a)*2)
    
for a,b,d in zip(A,B,D[::-1]):
    #print(a,b)
    #print(a,k,a+k,-(-(a+k)//2),d,b)
    if a + k <= b:
        k = min(a + k,d)
        C.append(k)
    elif -(-k//2) + a <= b:
        k = min(-(-(a+k)//2),d)
        C.append(k)
    else:
        print(-1)
        sys.exit()
    #print(a+k,C)
print(sum(C))

Submission status: Wrong Answer

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+1):
  if li[i]  > 2*ne:
    ans -= li[i] -2*ne
    #print(li[i] -2*ne)
  
  #ne = 2*ne - a_li[i]
  #print("----")
  ne = min(li[i] - a_li[i],2*ne-a_li[i])
  #print(li[i])
  #print(a_li[i])
  print(ne)
  if (i == n and ne != 0) or (i != n and ne <= 0):
    flag = False

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
MAX = 10 ** 100

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


# ok[i] : 深さiの葉以外の頂点の最大数
ok = [1]
for i in range(1, n + 1):
    t = ok[i - 1] * 2 - A[i]
    if i < n and t <= 0:
        print(-1)
        exit()
    ok.append(min(t, MAX))

if ok[n] < 0:
    print(-1)
    exit()

ans = [0] * (n + 1)

ans[n] = A[n]
# 深さ[親]の許容範囲を超えないように、できるだけたくさん親を使う
for i in range(n, 0, -1):
    ans[i - 1] = min(ok[i - 1], ans[i]) + A[i - 1]
# ans[上] = min(ok[上]*2, (ans[今]+A[今]))//2

print(sum(ans))

# print(ok)
# print(ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = inpl()
non_leaf = [0] * (n + 1)
leaf = [0] * (n + 1)
MAX = a[-1]
non_leaf[0] = 1
leaf[-1] = a[-1]
dp = [0] * (n + 1)
yoyu_idx = 0
yoyu = [0] * n
yoyu_idx = -1
if a[0] == 1:
    if n == 0:
        print(1)
    else:
        print(-1)
    exit()
elif a[0] > 1:
    print(-1)
    exit()
for i in range(n - 1):
    if non_leaf[i] < a[i + 1]:
        print(-1)
        exit()
    non_leaf[i + 1] = min(MAX, non_leaf[i] * 2 - a[i + 1])
    if MAX < non_leaf[i] * 2 - a[i + 1]:
        if yoyu_idx != -1:
            tmp = a[i + 1]
            while True:
                if yoyu[yoyu_idx] >= tmp:
                    leaf[i + 1] += (i - yoyu_idx) * tmp
                    yoyu[yoyu_idx + 1] += tmp
                    break
                else:
                    leaf[i + 1] += (i - yoyu_idx + 1) * yoyu[yoyu_idx]
                    yoyu[yoyu_idx + 1] += tmp
                    tmp -= yoyu[yoyu_idx]
                    yoyu_idx += 1
        else:
            yoyu_idx = i
            yoyu[i] = non_leaf[i] * 2 - a[i + 1] - MAX
    leaf[i + 1] += a[i + 1]
# print(non_leaf)
# print(leaf)
# print(yoyu)
print(sum(non_leaf) + sum(leaf))

Submission status: Wrong Answer

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

if A[0] != 0 or A[N] == 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]): 
            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()))

if 2**n < sum(a):
  flag=1
  print(-1)
elif n == 0:
  flag=1
  if a[0] == 1:
    print(1)
  else:
    print(-1)
else:
  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:
      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))
  else:
    print(-1)

Submission status: Wrong Answer

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

print(cnt)

Submission status: Wrong Answer

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


node_list = []
i = 0

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

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


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

    v = [tuple() for _ in range(N + 1)]
    v[N] = (A[N], A[N])

    for i in range(N - 1, -1, -1):
        low, up = v[i + 1][0], v[i + 1][1]
        up = min(2 ** i, up + A[i])
        if low % 2 == 0:
            low = low // 2 + A[i]
        else:
            low = low // 2 + A[i] + 1
        v[i] = (low, up)

    # print(v)
    for i in range(N):
        low, up = v[i][0], v[i][1]
        low = max(v[i + 1][0], low - A[i])
        up = min(v[i + 1][1], (up - A[i]) * 2)
        v[i + 1] = (low, up)

    ans = 0
    for i in range(N + 1):
        if v[i][0] < 0 or v[i][1] < 0:
            print('-1')
            exit()
        if v[i][0] > v[i][1]:
            print('-1')
            exit()
        ans += v[i][1]

    # print(v)
    print(ans)


if __name__ == '__main__':
    solve()

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==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]
        if(A[i+1]>chiled_value*2):
            print(-1)
            exit()
    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:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)

if N >= 1 and 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: Wrong Answer

Solution code:
import heapq

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

ans = N + 1

B = [i for i in range(N)]
heapq.heapify(B)

A[N] -= 1

zero = -1

for i in range(0, N + 1):
    if A[i] > 0:
        while B:
            q = heapq.heappop(B)
            if i <= q:
                print(-1)
                exit()
            A[i] -= 1
            ans += i - q
            for j in range(q + 1, i):
                heapq.heappush(B, j)
            if A[i] == 0:
                break
print(ans)

Submission status: Wrong Answer

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

ans = 0

parents = 1

if n == 0:
    if a[0] > 1:
        ans = -1
    else:
        ans = a[0]

if a[0] == 1:
    parents = 0
    ans = 1

parentsls = [0 for _ in range(n+1)]
parentsls[0] = parents

bicapls = [0 for _ in range(n+1)]

for i in range(1, n+1):
    if i != n and parents == 0:
        ans = -1    
        break
    if a[i] > parents*2:
        ans = -1
        break
    else:
        parents = parents*2 - a[i]
        parentsls[i] = parents
    
if ans != -1:
    node = 0
    for i in range(n):
        if parentsls[n-1-i] >= node + a[n-i]:
            ans += node + a[n-i]
            node = node + a[n-i]
        else:
            ans += node + a[n-i]
            node = parentsls[n-1-i]

    ans += 1

print(ans)

Submission status: Wrong Answer

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

if A[0] != 0 or A[N] == 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]): 
            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_d = [0 for i in range(n + 1)]

# 深さごとのノードの個数の最大値を求める
node_d[0] = 1
for i in range(n):
    node_d[i + 1] = 2 * (node_d[i] - a[i])
    if a[i + 1] > node_d[i + 1]:
        print(-1)
        exit()

node_d[n] = a[n]

for i in range(n - 1, 0, -1):
    # 1つ下のノードの個数+今回の葉の個数（最大値を超えないように）
    node_d[i] = min(node_d[i], node_d[i + 1] + a[i])

print(sum(node_d))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if a[0]>=2:
    print(-1)
# else:
#     s=0
#     for i in range(n):
#         h=n-1-i
#         q=2**h-a[h]
#         if a[h+1]>2*q:
#             print(-1)
#             break
#         ph=min(2**h-a[h],a[h+1]+ph)
#         s+=ph
#         if h==0:
#             s+=sum(a)
#             print(s)


else:
    pN=1
    s=1
    l=[]
    S=sum(a)
    b=0
    z=1
    for k in range(len(a)):
        b+=a[k]
        l.append(b)

    for i in range(1,n):
        if a[i]>2*pN:
            print(-1)
            z=0
            break
        else:
            pN=min(2*pN-a[i],S-l[i])
            s+=pN
    s+=S
    if n==0:
        s=1
    if n==1:
        if a[0]==1 and a[1]>=1:
            print(-1)
            z=0

    if z:
        print(s)

Submission status: Wrong Answer

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

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

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

flg = True
for a in A_list:
    tmp = en[-1] - a
    if tmp < 0:
        flg = False
        break
    en.append(tmp * 2)
en = en[:-1]

if not flg:
    print(-1)
    exit()

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

print(res)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [int(i) for i in input().split()]
l = []
# TODO N==0 の場合
if N == 0 and A[0] == 0:
    print(1)
    exit()
elif A[0]:
    print(-1)
    exit()
for i,a in enumerate(A):
    if i == 0:
        l.append(1)
    else:
        b = (l[-1] - A[i - 1])
        if b > 0:
            l.append( b * 2)
        else:
            print(-1)
            exit()
l2 = list(itertools.accumulate(A[::-1]))[::-1]
ans = sum([min(i,j) for i,j in zip(l,l2)])
print(ans)

Submission status: Wrong Answer

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

l = []

if A[0] != 0:
    print(-1)
    sys.exit()
'''
for i in range(N):
    if A[i] > A[i+1]+1:
        print(-1)
        sys.exit()
'''


temp = 1
for i in range(N+1):
    l.append(temp-A[i])
    temp = (temp-A[i])*2

for i in range(N+1):
    if l[i] < 0:
        print(-1)
        sys.exit()

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

print(l)
print(ans)