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 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 n==0 and a[0]>1: ans = -1
print(ans)

Submission status: Wrong Answer

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

flag = 1

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

ans = 1
cnt = 1
max_list = [a[n]]

for i in reversed(range(0,n)):
    max_list.append(max_list[n-i-1]+a[i])

max_list = max_list[::-1]

for i in range(0,n):
    if i != 0:
        if max_list[i] < a[i]*2:
            print("-1")
            exit(0)
        else:
            ans += min(max_list[i], cnt*2)
            cnt = cnt * 2 - a[i]

print(ans+a[n])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):

    logical_max = [1]
    prev = 1
    for a in A:
        prev = (prev - a)*2
        logical_max.append(prev)
    logical_max = logical_max[:-1]

    for l in logical_max:
        if l <= 0:
            print(-1)
            return

    nodes_at_depth = [0] * (N+1)
    d = N
    nodes = 0
    for lg_max, a in zip(logical_max[::-1], A[::-1]):

        nodes += a
        if nodes > lg_max:
            nodes = lg_max
            
        nodes_at_depth[d] = nodes
        d -= 1

    print(sum(nodes_at_depth))

    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())
l=list(map(int,input().split()))
b=1

l_sita=[0]*n
h_sita=[0]*n
ans=1
if l[0]>0:
  print(-1)
else:
  r=0
  if l[n]%2==1:
    r=l[n]//2+1
  else:
    r=l[n]//2
  l_sita[n-1]=r+l[n-1]
  h_sita[n-1]=l[n]+l[n-1]
  for d in range(n-2):
    r=0
    if l[n-d-1]%2==1:
      r=l[n-d-1]//2+1
    else:
      r=l[n-d-1]//2
    l_sita[n-d-2]=r+l[n-d-2]
    h_sita[n-d-2]=h_sita[n-d-1]+l[n-d-2]
  for d in range(n):
  #深さdに対してl[d]は葉の数。
  #bは深さdでの枝の数。
  #d+1での葉の数+dの葉の数
  #深さdの最大頂点数
  #上二つのうち小さい方が最大値。
  #枝の最小値はd+1の葉の数/2(切り上げ)+dの葉の数
    if d==n-1:
      ans+=l[n]
      if 2*b<l[n] or b>l[n]:
        ans=-1
        break
    else:
      ans+=min(h_sita[d+1],2*b)
      if b<=0 or 2*b<l_sita[d+1]:
        ans=-1
        break
      b=min(h_sita[d+1],2*b)-l[d+1]
  print(ans)

Submission status: Wrong Answer

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

target = A[-1]
ans = 0


for i in range(N+1):
    if i == 0:
        child = 2**i
    if i == N:
        ans += target
        print(ans)
        exit()


    leaf = A[i]

    if child > target:
        child = target
        valid_child = child
    else:
        valid_child = child - leaf

    if valid_child + leaf <= 2**i:
        ans += leaf
    else:
        print('-1')
        exit()
    ans += valid_child

    child = valid_child*2


    if child <= 0:
        print('-1')
        exit()

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]<a[j])or(m[j]==a[j] and j!=n):
        # print(m[j],a[j])
        x = 1
        break
    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 m[0]<=a[0]:
    print(-1)
else:
    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(-1)
    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 = input(int())
A = list(map(int, input().split()))

count = 0

for i in A:
    count += i + 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
D = [0]*(N+1)
prev = 0
if A[0]!= 0 and N != 0:
    print(-1)
    exit()
for i in range(N,-1,-1):
    D[i] = prev+A[i]
    prev = D[i]
prev = 1
for i in range(N+1):
    tmp = min(2**i,prev*2)
    if D[i] > tmp:
        D[i] = tmp
    prev = tmp-A[i]
for i in range(N,-1,-1):
    tmp = 0
    if i != N:
        tmp = (A[i+1]+1)//2
    if tmp+A[i] > 2**i:
        print(-1)
        exit()
print(sum(D))

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
  
  for i in range(N - 2, -1, -1) :
    if A[i] != 0 :
      if A[-2] < A[i] :
        return -1
      break
    else :
      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:
# 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 N == 0:
    if A[0] == 1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
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 reversed(range(0, N)):
    C[i] = min(A[i + 1] + C[i + 1], B[i])
print(sum(A) + sum(C))
# print('A:', A)
# print('C:', C)
# print('B:', B)

Submission status: Wrong Answer

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

ans = 1
flag = 1
if N == 0:
    if A[0] == 0:
        ans = 0
    else:
        flag = 0
else:
    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:
num = int(input())
a_i = list(map(int, input().split()))
ans = 0
reaf = a_i[num]
keep = [a_i[0]]
for x in range(num):
    keep.append(max(keep[x] * 2, a_i[x + 1]))
if a_i[0] != 0: print(-1)
else:
    for d in range(num):
        ans += reaf
        if 2 ** (num - d) < (reaf + 1) // 2 + a_i[num - (d + 1)]:
            ans = -1
            break
        val = max(2 ** (num - (d + 1)) - keep[num - (d + 1)], (reaf + 1) // 2 + a_i[num - (d + 1)])
        reaf = min(val, reaf + a_i[num - (d + 1)])
    print(ans + reaf)

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)
    while True:
        s=0
        s +=1
else:
    print(sum(depth_sum))

Submission status: Wrong Answer

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

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

maxs = [1]

for i in range(1,n+1):
    nex = maxs[i-1]*2 - a[i]
    maxs.append(nex)

if(maxs[n] < 0):
    print('-1')
    sys.exit()

results = [a[n]]

for i in range(n):
    if(results[i] > maxs[n-i-1]):
        results.append(maxs[n-i-1]+a[n-i-1])
    else:
        results.append(results[i]+a[n-i-1])


print(sum(results))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
level = [0 for i in range(n+1)]
cur_pow = 1
if A[0] > 0 and n >= 1:
    print(-1)
    exit()
if A[0] > cur_pow:
    print(-1)
    exit()
level[0] = 1
for i in range(1, n+1):
    if A[i] > cur_pow:
        print(-1)
        exit()
    cur_pow *= 2
    if level[i-1] < A[i-1]:
        print(-1)
        exit()
    level[i] = min(cur_pow, 2*(level[i-1]-A[i-1]))
if level[-1] < A[-1]:
    print(-1)
    exit()
level[-1] = A[-1]
for i in range(n-1, -1, -1):
    level[i] = min(level[i], level[i+1]+A[i])
print(sum(level))

Submission status: Wrong Answer

Solution code:
t = int(input())
num_list = list(map(int, input().split()))

pair_node_list = []
not_flag = False
for i,num in enumerate(num_list):
  if i==0:
    if num!=0:
      not_flag = True
      break
    elif num==0:
      pair_node_list.append(1)
  else:
    _pair_num = pair_node_list[i-1]*2 - num
    if _pair_num >= 0:
      pair_node_list.append(_pair_num)
    else:
      not_flag = True
      break
      
if not_flag:
  print(-1)
else:
  print(sum(num_list+pair_node_list))

Submission status: Wrong Answer

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

ls = []

for i,s in enumerate(A):
  ans = s+1
  if ans > 2**i:
    print(-1)
    quit()
  ls.append(ans)
  
print(sum(ls)-1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
miss=False
leaf=A[-1]
mina=0
maxa=0
maxal=[0]*(N+1)
for i in range(N):
  maxa=min(maxa+leaf,2**(N-i-1)-A[N-1-i])
  mina=(mina+leaf+1)//2
  if mina>maxa:
    miss=True
    break
  leaf=A[N-1-i]
  maxal[N-i-1]=maxa
leaf=A[0]
a=maxal[0]
ans=leaf
for i in range(1,N+1):
  leaf=A[i]
  a=min(a*2-leaf,maxal[i])
  if a+leaf==0:
    miss=True
    break
  ans+=(a+leaf)
if miss:
  print(-1)
else:
  print(int(ans))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
A = list(map(int,input().split()))
leaf= [-1 for i in range(N+1)]
notleaf = [-1 for i in range(N+1)]
flag=0

if N == 0 and A[0] == 1:
    print(1)
elif N != 0 and A[0]>=1:
    print(-1)
else:
    leaf[0]=0
    notleaf[0]=1
    for d in range(1, N+1):
        leaf[d] = A[d]
        notleaf[d] = 2*notleaf[d-1] - leaf[d]
        if notleaf[d]<0:
            flag=1
            print(-1)
            break
    #if flag==0 and notleaf[N] != 0:
    #    print(-1)
    
    sleaf = 0
    for i in range(N+1):
        sleaf += leaf[i]
    
    d1 = 0
    for i in range(N+1):
        d1 += (i+1) * leaf[i]
    
    sleaf -= 1
    for i in range(1,N+1):
        if sleaf>0:
            d1 -= i*( min(sleaf, leaf[i]+notleaf[i] - notleaf[i-1]))
            sleaf -= (leaf[i]+notleaf[i] - notleaf[i-1])
        else:
            break
    print(d1)

Submission status: Wrong Answer

Solution code:
# 0や1のケースに注意
# index out of range
# 貪欲

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    l = list(map(int, input().split()))
    limit = [1-l[0]]
    total = 0
    if n == 0:
        print(-1)
        exit()
    for i in range(1, n+1):
        total = total*2 + l[i-1]*2
        limit.append(pow(2, i) - total)

    for i in limit:
        if i <= 0:
            print(-1)
            break
    else:
        res = []
        temp = 0
        flag = 1
        for i in range(n, -1, -1):
            if limit[i] > temp+l[i] and flag == 1:
                temp = temp+l[i]
            else:
                temp = limit[i]
                flag = 0
            res.append(temp)
        print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
if a[0] != 0:
    ans = -1
p = [1-a[0]]
for i in range(n-1):
    if 2*p[-1]-a[i+1] <= 0:
        ans = -1
    p.append(2*p[-1]-a[i+1])
if n == 0 and a[0] == 1:
    print(1)
elif n == 1:
    if a[0] == 0 and a[1] == 1:
        print(2)
    elif a[0] == 0 and a[1] == 2:
        print(3)
    else:
        print(-1)
elif ans == -1:
    print(-1)
else:
    a.reverse()
    p.reverse()
    ans = 0
    ans += a[0]
    q = a[0]
    for i in range(1,n+1):
        if n < 1001 and 2**(n-i) < -(-q//2)+a[i]:
            ans = -1
            break
        elif q < p[i-1]:
            ans += q+a[i]
            q = q+a[i]
        else:
            ans += p[i-1]+a[i]
            q = p[i-1] + a[i]
    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()
if sum(A) == 0:
    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:
n = int(input())
A = list(map(int, input().split()))
if A[0]>0:
    print(-1)
    exit()
if A[-1]>2**n:
    print(-1)
    exit()
node1=[0]*(n+1)
node1[0]=1
node2=[0]*(n+1)
node2[-1]=A[-1]
for i in range(n):
    x=(node1[i]-A[i])*2
    if x<1:
        print(-1)
        exit()
    node1[i+1]=x
#print(node1)
for i in range(n-1,-1,-1):
    x=(node2[i+1]+A[i])
    if i<32:
        x=min(2**i, x)
    node2[i]=x
ans=[]

for i in range(n+1):
    ans.append(min(node1[i],node2[i]))
print(sum(ans))

Submission status: Wrong Answer

Solution code:
DELIM = 1

def kaijo(r, n):
    if(n == 0):
        return 1
    if(n == 1):
        return r
    else:
        mod = n % 2
        n_red = n // 2
        if(mod == 1):
            return (r * ((kaijo(r, n_red) % DELIM)**2) % DELIM) % DELIM
        else:
            return ((kaijo(r, n_red) % DELIM)**2) % DELIM

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 = 0
    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 = node_in_the_dept - A[i]        
        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:
import math
import sys
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a_li = list(map(int, input().split()))
if a_li[0]>0 and n>0:
    print(-1)
else:
    cnt = 1
    node = 1
    for i in range(1, n+1):
        tmp = node*2-a_li[i]
        if tmp < 0:
            print(-1)
            break
        if i!=n:
            node = min(tmp, sum(a_li[i+1:]))
            cnt += node + a_li[i]
        else:
            cnt += a_li[i]
    else:
        print(cnt)

Submission status: Wrong Answer

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

ans = 0

parents = 1

if n == 1:
    if a[0] != 1:
        ans = -1

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

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()))
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)
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 a[0]!=0:
    if n == 0:
        print(0)
        exit()
    else:
        print(-1)
        exit()

x = 1
count = 1

for i in range(n):
    if a[i+1]>=2*x:
        if a[i+1]==2*x and (i+1)==n:
            count += 2*x
            print(count)
            exit()
        else:
            print(-1)
            exit()
    
    else:
        x = 2*x - a[i+1]
        count += a[i+1] + x
        
print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
a = LI()
if n == 0:
    if a[0] == 1:
        print(1)
        quit()
    else:
        print(-1)
        quit()
for i in range(n):
    if a[i] > 2**i - 1:
        print(-1)
        quit()
if a[-1] > 2**n:
    print(-1)
    quit()

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

Submission status: Wrong Answer

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

cnt = 0
ans = 0

if n==0:
    if a[0] == 1:
        cnt = 1
    else:
        cnt = -1
else:
    setsu = 1
    if a[0] != 0:
        cnt = -1
    else:
        setsu = 1
        cnt = 0
        for i in range(1,n+1):
            ha = a[i]
            ha_max = setsu*2
            if ha > ha_max:
                cnt = -1
                break
            else:
                if i != n:
                    cnt += ha + setsu
                    setsu = ha_max - ha
                else:
                    cnt += ha + min(setsu,ha)

print(cnt)

Submission status: Wrong Answer

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

ans = 0
prev = 1
L = [0]*(N+1)
L[0] = 1
for i in range(1, N+1):
    if prev*2 > A[i]:
        prev = prev*2-A[i]
    elif prev*2 == A[i] and i == N:
        continue
    else:
        ans = -1
        break
    L[i] = prev
    if prev > 10**10:
        for j in range(i+1, N+1):
            L[j] = "inf"
        break

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

if ans == 0:
    num = A[-1]
    ans += A[-1]
    for i in range(N-1, -1, -1):
        if L[i] == "inf" or num <= L[i]:
            num += A[i]
        else:
            num = L[i]+A[i]
        ans += num
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N==0:
    print(1 if A[0]==1 else -1)
    exit()
if A[0] != 0:
    print(-1)
    exit()

INF = 10**9
mxs = [1]
for a in A[1:]:
    p = mxs[-1]*2 - a
    if p < 0:
        print(-1)
        exit()
    mxs.append(min(p, INF))

ans = p = A[-1]
for i in range(N-1,-1,-1):
    if mxs[i]+A[i] < (p+1)//2:
        print(-1)
        exit()
    n = min(p, mxs[i]) + A[i]
    ans += n
    p = n
print(ans)

Submission status: Wrong Answer

Solution code:
depth = int(input()) 
leaves = list(map(int, input().split(" ")))
limited = []
limited_a = []

def solve (depth) :
    _min = _max = 0
    cur = 1
    i = 0 
    
    while i <= depth :
        limited_a.append( cur )
        if cur <= 0 and leaves[i] != 0 :
            return False
        cur=(cur-leaves[i])*2
        i+=1 

    i = depth
    while i >= 0 :
        if i==depth: 
            limited.append(leaves[i])
            _max = leaves[i]
            _min = (leaves[i]+1)//2
        else :
            _max = min(limited_a[i], _max+leaves[i])
            if _max < _min :
                return False 
            limited.append(_max)
            _min = (_min+leaves[i]+1)//2
        i -= 1
        cur = (cur-leaves[i])*2
    return True

if solve(depth) :
    print(sum(limited))
else :
    print (-1)

Submission status: Wrong Answer

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

# 木が存在するかチェックをして，後でノード数を計算する
# チェック-1辺
pre_a = A[0]
if N == 0 and pre_a == 1:
    print(1)
    sys.exit()
elif N == 0 and pre_a != 1:
    print(-1)
    sys.exit()
elif pre_a != 0:
    print(-1)
    sys.exit()

flag = True
for i in range(1, N+1):
    cur_a = A[i]
    if i <= 30:
        sqrt_d = 2 ** i - 2 * pre_a
    else:
        break
    if i == N:
        if cur_a <= sqrt_d:
            continue
        else:
            flag = False
            break
    else:
        if cur_a < sqrt_d:
            continue
        else:
            # print(cur_a)
            flag = False
            break
    pre_a = cur_a
# INF = 10**13
if flag:
    tmp = [1 for i in range(32)]
    ans = A[N]
    pre_a = A[N]
    for i in range(N-1, 0, -1):
        cur_a = A[i]
        if i <= 30:
            sqrt_d = 2**i - A[i-1]*2
            diff = min(cur_a + pre_a, sqrt_d)
            tmp[i] = diff
        else:
            diff = cur_a + pre_a
            # sqrt_d = INF
        ans += diff
        pre_a = diff
    ans += 1
    tmp_sum = 0
    for i in range(1, min(N+1, 31)):
        # print(tmp[i])
        if tmp[i] > (tmp[i-1]-A[i-1]) * 2:
            # print('aaa', tmp[i] - (tmp[i-1]-A[i-1]) * 2)
            ans -= (tmp[i] - (tmp[i-1]-A[i-1]) * 2)
            tmp[i] -= (tmp[i] - (tmp[i-1]-A[i-1]) * 2)
        # tmp_sum = tmp_sum * 2 + A[i] * 2
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
import bisect
from sys import exit
n = int(input())
A = list(map(int, input().split()))

coutner = 0
dp = dd(int)
dp[1] = 1
limit = [0] * (n + 1)
total = 0
for i in range(n, -1, -1):
    total += A[i]
    limit[i] = total
#print(limit)

"""
for depth in range(n):
    mov_dic = dd(lambda: 0)
    for now_num, total in dp.items():
        if now_num - A[depth] > 0:
            mov_dic[now_num - A[depth]] = total
    #print("mov_dic", mov_dic)

    dp = dd(int)
    mov_dic_keys = set(mov_dic.keys())
    for now_num, total in mov_dic.items():
        mov_dic_keys.remove(now_num)
        for next_num in range(now_num, min(now_num*2 + 1, limit[depth] + 1)):
            if now_num in mov_dic_keys:
                break
            dp[next_num] = max(total + next_num, dp[next_num])
    #print(limit[depth], "dp", dp)

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

now_num = 1
now_total = 1
for depth in range(n):
    mov_num = now_num - A[depth]
    #print(mov_num)

    if mov_num > 0:
        now_num = min(mov_num * 2, limit[depth+1])
        now_total += now_num
    else:
        print(-1)
        exit()
print(now_total)

Submission status: Wrong Answer

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

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

maxs = [1]

for i in range(1,n+1):
    nex = maxs[i-1]*2 - a[i]
    maxs.append(nex)

if(maxs[n] < 0):
    print('-1')
    sys.exit()

results = [a[n]]

for i in range(n):
    if(results[i] > maxs[n-i-1]):
        results.append(maxs[n-i-1]+a[n-i-1])
    else:
        results.append(results[i]+a[n-i-1])


print(sum(results))

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

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

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)
elif a_list[-1] == 0:
  print(-1)
else:
  print(count + a_list[-1])

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

num = [0]*(N+1)  # 各層で葉を除いたとれるノードの限界

ma = 1
for i, a in enumerate(A):
	if i == N and a <= ma:
		num[i] = ma-a
	elif a <= ma-1:
		num[i] = ma-a
		ma = (ma-a)*2
	else:
		print(-1)
		exit()

tmp = 0
ans = 0
for i, a in enumerate(A[::-1]):
	d = N-i
	if tmp > num[d]:
		tmp = -(-tmp//2)
	if tmp > num[d]:
		tmp -= 1
	tmp += a
	ans += tmp

print(ans)