Problem:


Score : 600 points

Problem Statement

Given is an integer sequence of length N+1: A_0, A_1, A_2, \ldots, A_N. Is there a binary tree of depth N such that, for each d = 0, 1, \ldots, N, there are exactly A_d leaves at depth d? If such a tree exists, print the maximum possible number of vertices in such a tree; otherwise, print -1.

Notes

A binary tree is a rooted tree such that each vertex has at most two direct children.

A leaf in a binary tree is a vertex with zero children.

The depth of a vertex v in a binary tree is the distance from the tree's root to v. (The root has the depth of 0.)

The depth of a binary tree is the maximum depth of a vertex in the tree.

Constraints

0 \leq N \leq 10^5

0 \leq A_i \leq 10^{8} (0 \leq i \leq N)

A_N \geq 1

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0 A_1 A_2 \cdots A_N

Output

Print the answer as an integer.

Sample Input 1

3
0 1 1 2

Sample Output 1

7

Below is the tree with the maximum possible number of vertices. It has seven vertices, so we should print 7.

Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

10
0 0 1 1 2 3 5 8 13 21 34

Sample Output 5

264



Sample input:
3
0 1 1 2


Sample output:
7

Submission status: Wrong Answer

Solution code:
import sys
import math
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

n = I()
a = Intl()
if n == 0 and a[0] == 0 and a[1] == 0:print(-1)

Submission status: Wrong Answer

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

max_nood = sum(A)
count_nood = 0
corrent_nood = 0
ans = True

for i in range(N+1):
    if i != N:
        if i == 0:
            corrent_nood = 1-A[i]
            count_nood += corrent_nood
            max_nood -= A[i]
        else:
            corrent_nood = min(2*(corrent_nood-A[i-1]), max_nood)
            max_nood -= A[i]
            count_nood += corrent_nood
        if corrent_nood <= 0 or A[i] > corrent_nood:
            ans = False
            break
            # print(i)
        # print(corrent_nood)
    else:
        if i != 0:
            if corrent_nood-A[i-1] <= A[i] <= 2*corrent_nood-A[i]:
                count_nood += A[i]
            else:
                ans = False
        else:
            if A[i] == 1:
                count_nood = 1
            else:
                ans = False


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

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):
  if li[i]  > 2*ne:
    ans -= li[i] -2*ne
    #print(li[i] -2*ne)

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

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

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[1] == 1:
        print(2)
    elif a[1] == 2:
        print(3)
    else:
        print(-1)
elif ans == -1:
    print(-1)
else:
    a.reverse()
    p.reverse()
    ans += a[0]
    q = a[0]
    for i in range(1,n+1):
        if 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()))
inf = 10**18
res = 0
b = [0]*(N+1)
b[0] = 1-a[0]
for i in range(N):
    tmp = min(2*b[i] - a[i+1], inf)
    if tmp < 0:
        res = -1
        break
    b[i+1] = tmp

if res != -1:
    tmp = 0
    for i in range(N,0,-1):
        tmp += a[i]
        if 2*b[i-1] < tmp:
            tmp = 2*b[i-1]
        res += tmp
    res += 1

print(res)

Submission status: Wrong Answer

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

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

# 根から見たときにあり得る各層最大の要素数
max_leaf = [0] * (N + 1)
max_leaf[0] = 1
leaf = 1
for i in range(N):
    leaf = 2 * (leaf - A[i]) 
    if leaf < 0:
        print(-1)
        exit()
    max_leaf[i+1] = leaf

result = [0] * (N+1)
result[N] = A[N]
for i in reversed(range(N)):
    if result[i+1] + A[i] <= max_leaf[i]:
        result[i] = result[i+1] + A[i]
    elif -(-result[i+1] // 2) > max_leaf[i]:
        print(-1)
        exit()
    else:
        result[i] = max_leaf[i]

print(sum(result))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
r = [1]
for i in range(N):
    r.append(r[i]*2)


p = 0
for i in range(N):
    if A[i] != 0:
        p += A[i]
    p = p * 2 
    r[i+1] -= p
    if r[i] < A[i]:
        print(-1)
        exit()
    if i == N-1 and r[i+1] < A[i+1]:
        print(-1)
        exit()


for i in range(N):
    r[i] -= A[i]


q = A[N]
ans = q

for i in range(N):
    q = min(q,r[N-1-i]) + A[N-1-i]
    ans += q
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()))
    maxnum = [0] * (n + 1)
    num = [0] * (n + 1)
    maxnum[0] = 1
    num[0] = 1
    num[-1] = a[-1]
    r = 0
    if a[0] > 0 and n >= 1:
        print(-1)
    elif a[0] > 0 and a[0] == 1:
        print(1)
    else:
        for i1 in range(1, n + 1):
            if maxnum[i1-1] * 2 < a[i1]:
                print(-1)
                sys.exit()
            else:
                maxnum[i1] = maxnum[i1-1] * 2 - a[i1]

        for j1 in range(n-1, 0, -1):
            numt = a[j1] + min(num[j1 + 1], maxnum[j1-1]*2 - a[j1])
            num[j1] = numt

        r = sum(num)
        print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*(n+1)
c=[0]*(n+1)
flg=True
ans=0
if a[n]>2**n:
  print(-1)
else:
  b[n]=a[n]
  c[0]=1
  for i in range(n-1,-1,-1):
    b[i]=b[i+1]+a[i]
  for i in range(1,n+1):
    
    c[i]=2*(c[i-1]-a[i-1])
  
  for i in range(n+1):
    if c[i]<=0:
      flg=False
  if c[n]-a[n]<=0:
    flg=False
  
  for i in range(n+1):
    ans+=min(b[i],c[i])
  if flg:
    
    print(ans)
  else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    An = [int(x) for x in input().strip().split()]
    total = sum(An)
    if An[0] != 0:
        print(-1)
        exit()
    ans = 1
    node = 1
    for n, a in enumerate(An[1:], start=1):
        node_ = min(total, node * 2)
        if node_ < 0:
            print(-1)
            exit()
        ans += node_
        node = node_ - a
        total -= a
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if n == 0:
    print(a[0])
    exit()
if a[0] > 0:
    print(-1)
    exit()
l = [0] * (n + 1)
u = [0] * (n + 1)
l[n] = a[n]
u[n] = a[n]
for i in range(n, 0, -1):
    l[i - 1] = -(-l[i] // 2) + a[i - 1]
    u[i - 1] = u[i] + a[i - 1]
if l[0] > 1:
    print(-1)
    exit()
u[0] = 1
itr = 0
while True:
    update = False
    for i in range(n):
        if u[i] < l[i]:
            print(-1)
            exit()
        n_u = 2 * (u[i] - a[i])
        if n_u < u[i + 1]:
            update = True
            u[i + 1] = n_u
    if not update:
        break
    update = False
    for i in range(n, 0, -1):
        if u[i] < l[i]:
            print(-1)
            exit()
        n_u = u[i] + a[i - 1]
        if n_u < u[i - 1]:
            update = True
            u[i - 1] = n_u
    if not update:
        break
print(sum(u))

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
n = int(stdin.readline())
nmleaves = list(map(int, stdin.readline().strip().split()))

# pref[i]: sum of all elements in nmleaves after i, i.e. sum(nmleaves[i+1:])
full = sum(nmleaves)
tot = 0
pref = [0]*(n+1)
for i, l in enumerate(nmleaves):
    tot += l
    pref[i] = full - tot

if n==0:
    print(0)

else:
    if nmleaves[0]!=0:
        print(-1)
        exit()
    
    ## it exists
    ans = 0
    for level, leaves in enumerate(nmleaves):
        if leaves > 2**(level):
            print(-1)
            exit()

        if level == 0:
            ans += 1
            validnom = 1
        else:
            maxup = 2*validnom
            maxnom = maxup - leaves

            if level+1<len(nmleaves):
                validnom = min(maxnom, pref[level])
                ans += (leaves + validnom)
            else:
                ans += leaves
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = rl()

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

num = 1
M = [0] * (N+1)
for i in range(N+1):
	M[i] = num
	if A[i] > num:
		print(-1)
		exit()
	num = (num - A[i]) * 2
ans = sum(A)

inodes = 0
for i in range(N-1, -1, -1):
	inodes = min(M[i]-A[i], A[i+1]+inodes)
	ans += inodes
print(ans)

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]
for k in range(N):
    ak=2*ak-A[k+1]
    if ak<0:
        print(-1)
        exit()
    if ak>10**8:
        #以降に関わらず構成可能
        break
    a.append(ak)
M=len(a)
for k in range(N,0,-1):
    if k-1<M:
        A[k-1]+=min(A[k],a[k-1])
    else:
        #A[k-1]+=min(A[k],a[k-1])
        #としておきたいところだが、a[k-1]>10**8,A[k]<=10**8より
        #a[k-1]>A[k]よりmin(A[k],a[k-1])=A[k]
        A[k-1]+=A[k]
        continue
print(sum(A))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N=len(v)
    size=len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    global count
    count=0
    def r(n,cmin,cmax):  
        global count   
        ncmax=cmax+A[n]
        ncmin=math.ceil(cmin*0.5)+A[n]
        if ncmin>2**(n+1):
            #print(ncmin,n)
            print(-1)
            exit()
        
        if n==0:
            count+=1
            return min(cmax,2)

        
        nodes=r(n-1,ncmin,ncmax)
        count+=nodes
        return min(2*(nodes-A[n]),cmax)

    r(N,0,0)
    print(count)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
flag=True
ans=0
B=[0 for i in range(N+1)]
for i in range(N+1):
  if(i==0):
    if(A[i]==0):
      B[i]=1
    if(A[i]==1 and N>1):
      flag=False
  else:
    B[i]=B[i-1]*2-A[i]
  if(B[i]<0):
    flag=False
#print(B)
x=B[-1]#層の葉でない頂点数
y=A[-1]#層の頂点数
ans=A[-1]
#print(x,y,ans)
for i in range(N):
  if(x>B[N-1-i]*2):
    flag=False
    break
  else:
    #ans+=min(y,B[N-1-i])
    x=min(y,B[N-1-i])
    y=x+A[N-1-i]
    ans+=y
if flag:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    if A[0] != 0:
        print(-1)
        return
    
    # 下から全く連結なしに子から枝を伸ばしたとして、部分木の個数を確認
    B = [0] * (N + 1)
    B[-1] = A[-1]
    for i in range(N - 1, -1, -1):
        B[i] = B[i + 1] + A[i]
    
    # 次に根から順にみてうまくつなぎ合わせ
    vertex = 1
    root = 1
    for i in range(1, N):
        if root * 2 - 1 < A[i]:
            print(-1)
            return
        if root < A[i]:
            root = min(B[i + 1], root * 2 - A[i])
            vertex += A[i] + root
        else:
            root = min(B[i + 1], root * 2 - A[i])
            vertex += A[i] + root
    
    # 最後N段目でつじつま合うか確認
    if root * 2 < A[-1]:
        print(-1)
        return
    vertex += A[-1]
    print(vertex)
    





if __name__ == "__main__":
    main()

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(0)
    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)


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

    if i==n:
        if a[i]>maxnode[-1]*2:
            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()))
import math
ans=0
for i in range(N, 0, -1):
    if A[i]>2**(i):
        ans=-1
        break
    if i!=0:
        q=math.ceil(A[i]/2)
        if q==0:
            q=1
        print(A[i]+q)
        ans=ans+A[i]+q
print(ans)

Submission status: Wrong Answer

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

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

B = [0]*(N+1)
B[0] = 1
C = [0] * N
D = A[:]

for i in range(N):
    B[i+1] = 2*(B[i]-A[i])
    C[i] = B[i] - A[i]
    if max(B[i],A[i+1]) > B[i+1]:
        print(-1)
        exit()
D[N] = B[N]

B.append(0)
for i in range(N,-1,-1):
    #print(A,B,C,D)
    if A[i] < D[i]:
        if A[i] >= C[i-1]:
            B[i] = A[i]
            break
        else:
            r = D[i] - A[i]
            B[i] = B[i+1] + A[i]
            D[i-1] += r-C[i-1]
            #D.pop()

print(sum(B))

Submission status: Wrong Answer

Solution code:
def pow(i):
    if i>30:
        return 200000001
    else:
        return 2**i

n=int(input())
a=[int(i) for i in input().split()]
b=[None for i in range(n)]
if n==0:
    if a[0]==1:
        print(1)
    else:
        print(-1)
else:
    a.reverse()
    for i in range(n):
        b[i]=(a[i]+1)//2
        a[i+1]+=b[i]
    if a[-1]>1:
        print(-1)
    else:
        a.reverse()
        b.reverse()
        b.append(0)
        res=a[n]
        ma=[10000000000 for i in range(n+1)]
        ma[0]=1
        for i in range(1,n+1):
            ma[i]=min((ma[i-1]-a[i-1]+b[i-1])*2,ma[i])
        for i in range(n-1,-1,-1):
            a[i]=min(ma[i],a[i+1]+a[i]-b[i])
            res+=a[i]
        print(res)

Submission status: Wrong Answer

Solution code:
from itertools import *
n,*a=map(int,open(0).read().split())
b=list(accumulate(a[::-1]))
b=b[::-1][1::]
c=[1]*n
if a[0]!=0:
    print(-1)
    exit()
for i in range(1,n):
    c[i]=min(c[i-1]*2-a[i],b[i])
    if c[i-1]*2-a[i]<1:
        print(-1)
        exit()
print(sum(a)+sum(c))

Submission status: Wrong Answer

Solution code:
N=int(input())
*A,=map(int,input().split())
Ar=A[::-1]
ans=[0]*(N+1)
i=0
count=0
while i<=N:
    count+=Ar[i]
    if count>2**(N-i):
        count=2**(N-i)
    ans[-(i+1)]=count
    i+=1

j=0
while j<N:
    if ans[j+1]>2*(ans[j]-A[j]):
        ans[j+1]=max(2*(ans[j]-A[j]),0)
    j+=1

if 0 in ans:
    print(-1)
else:
    print(sum(ans))

Submission status: Wrong Answer

Solution code:

n = int(input())
arr = list(map(int , input().split()))
if arr[0] > 0 or arr[-1] == 0:
	print("-1")
else:
	f = 1
	possible = 2
	ans = 1
	for i in range(1,n+1):
		#print(possible, ans)
		if arr[i] > possible:
			print(-1)
			f = 0
			break
		ans+=possible
		#if i == n:
		#	break
		possible-=arr[i]
		possible = 2*possible
	if f: print(ans)

Submission status: Wrong Answer

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

if n == 0:
  if A[0] == 1:
    print(1)
    exit()
  else: 
    print(-1)
    exit()
   
l = [1]
pre = 1
for i in range(n):
    if A[i] == 0:
        pre *= 2
        l.append(pre)
    else:
        pre = (l[i]-A[i])*2
        if pre <= 0:
            print(-1)
            exit()
        l.append(pre)

tmp = A[-1]
ans = tmp

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

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()
res2 = [0]
for i in lst1[::-1]:
    res2.append(res2[-1]+i)

res2.reverse()

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# C

N = int(input())
A_N = list(map(int, input().split()))
reversed_A_N = list(reversed(A_N))

for i in range(1, N + 1):
    reversed_A_N[i] += reversed_A_N[i - 1]

r_reversed_A_N = list(reversed(reversed_A_N))


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

print(sum(r_reversed_A_N))

Submission status: Wrong Answer

Solution code:
n=int(input())
sums=[0]*(n+1)
node=[0]*(n+1)
p=list(map(int,input().split()))
flag=True

sums[n]=p[n]
for i in reversed(range(n)):
    sums[i]=p[i]+sums[i+1]

node[0]=1
check=-1
for i in range(1,n+1):
    if node[i-1]-p[i-1]<0:
        flag=False
        break
    node[i]=(node[i-1]-p[i-1])*2
    if node[i]>sums[i]:
        check=i
        break
    elif node[i]==sums[i]:
        check=i+1
        break

if not flag or check==-1:
    print(-1)
else:
    ans=0
    for i in range(check):
        ans+=node[i]
    for i in range(check,n+1):
        ans+=sums[i]
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


for i in range(N):
  B[N-i-1] += B[N-i]
  
if(A[0] != 0):
  print(-1)
  exit()
a = 1
sum = a
for i in range(1, N):
  if(2*(a-A[i-1]) > B[i]):
    a = B[i]
  else:
    a = 2*(a-A[i-1])
    
  if(a <= A[i]):
    print(-1)
    exit()
  sum += a
  
print(sum + A[-1])

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    # N = int(input().strip())
    # A = list(map(int, input().strip().split(" ")))
    N = 3
    A = list(map(int, "0 1 1 2".strip().split(" ")))

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

    tree = [0]*(sum([2 ** i for i in range(N+1)]))
    for i, a in enumerate(A[::-1]):
        depth = len(A) - 1 - i
        depth_hierarchy_start_index = sum([2 ** i for i in range(depth)]) if depth != 0 else 0
        depth_hierarchy_end_index = sum([2 ** i for i in range(depth + 1)]) if depth != 0 else 1

        # keisho
        if depth != N:
            for i in range(depth_hierarchy_start_index, depth_hierarchy_end_index):
                if tree[2 * i+ 1] != 0 or tree[2 * i + 2] != 0:
                    tree[i] = 2

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


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

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    if n == 0 and a[0] == 0:
        print(-1)
        exit()
    suma = sum(a)
    ans = a[0]
    can = 1
    for i,ai in enumerate(a):
        if ai > can:
            print(-1)
            exit()
        suma -= ai
        ans += can
        if (can-ai)*2 >= suma:
            can = suma
        else:
            can = (can-ai)*2

    print(ans)




    return

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 ans == -1:
    print(-1)
else:
    a.reverse()
    p.reverse()
    ans += a[0]
    q = a[0]
    for i in range(1,n+1):
        if 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:
import sys
from math import ceil
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(20000000)
MAX = 10**12
n = int(input())
a = list(map(int, input().split()))

# その層で作ることができるノードの最大値
max_i = [MAX] * (n+1)
max_i[0] = 1

for i in range(1, min(n+1, 30)):
    max_i[i] = max_i[i-1] * 2 - a[i]
for i in range(1, min(n+1, 30)):
    max_i[i] += a[i]

# print(max_i)

a = a[::-1]
cnt = 0
# 下の層の頂点の数
pre_cnt = 0
for i, v in enumerate(a):
    idx = n - i
    if v + ceil((pre_cnt) / 2) > max_i[idx]:
        # print(ceil((v + pre_cnt) / 2), max_cnt + v)
        print(-1)
        exit()
    # 上の頂点数
    pre_cnt = min(v + pre_cnt, max_i[idx])
    cnt += pre_cnt
    # print(pre_cnt, cnt)

print(cnt)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    if A[0] != 0:
        print(-1)
        return
    piyo = 1
    work = [1]
    for a in A[1:]:
        piyo *= 2
        work.append(piyo)
        piyo -= a
    result = 0
    piyo = 0
    i = N
    for a in A[::-1]:
        piyo += a
        if a > work[i]:
            print(-1)
            return
        piyo = min(piyo, work[i])
        result += piyo
        i -= 1
    print(result)
main()

Submission status: Wrong Answer

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

ans = 1
now = 1

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

else:
    for i in range(n):
        if a[i] > now:
            ans = -1
            break
        elif sum(a[i+1:]) <= (now-a[i])*2:
            now = sum(a[i+1:])
            ans += now
        else:
            now = (now-a[i])*2
            ans += now
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a2 = [0] * (n + 1)
d = [1] * (n + 1)
ans = 1
a2[0] = sum(a)
for i in range(n):
    a2[i + 1] = a2[i] - a[i + 1]
for i in range(n):
    if d[i] - a[i] <= 0:
        ans = -1000000000000
    if (d[i] - a[i]) * 2 >= a2[i]:
        d[i + 1] = a2[i]
    else:
        d[i + 1] = (d[i] - a[i]) * 2

if ans < 0:
    ans = -1
else:
    ans = sum(d)
print(ans)

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()))

right=1
for i,x in enumerate(A):
    right-=x
    right*=2
    right=min(right,10**10)

ans=1
tmp=0
M=[1]


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))
for i,(x,y) in enumerate(zip(A[1:][::-1],M[1:][::-1])):
    tmp+=x
    tmp=min(tmp,n,y+x)
    ans+=tmp
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    low, high = A[N], A[N]
    maxN = [0] * (N + 1)
    lowN = [0] * (N + 1)
    maxN[N] = A[N]
    lowN[N] = A[N]

    for i in reversed(range(N)):
        leaf = A[i]
        maxNode = 10 ** 9
        if i < 30: maxNode = pow(2, i)
        low = (low + 1) // 2 + leaf
        high += leaf
        lowNG = False
        divLow = low
        count = 0
        while divLow > 0:
            divLow //= 2
            count += 1
        if count > i + 1: lowNG = True
        
        if lowNG or high < low: 
            print(-1)
            break
        else: 
            lowN[i] = low
            maxN[i] = min(high, maxNode)
    else:
        #print(maxN)
        for i in range(N):
            if (maxN[i] - A[i]) * 2 < lowN[i+1]:
                print(-1)
                break
            elif (maxN[i] - A[i]) * 2 <= maxN[i+1]: maxN[i + 1] = (maxN[i] - A[i]) * 2
        else: print(sum(maxN))
        #print(maxN)
        #print(lowN)
            
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
H = [0]*(n+1)
s = sum(A)
flag= True
if A[0]>= 1:
    print(-1)
    flag = False
else:
    H[0] =1
    i = 1
    while i <=n:
        if A[i] > H[i-1]*2:
            print(-1)
            flag =False
            break
        else:
            if s >=2*(H[i-1]-A[i-1]):
                H[i] = 2*(H[i-1]-A[i-1])
            else:
                H[i] = s
            
            s -= A[i]
            i +=1

if flag:
    print(sum(H))

Submission status: Wrong Answer

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

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

# 根から見たときにあり得る各層最大の要素数
max_leaf = [0] * (N + 1)
max_leaf[0] = 1
leaf = 1
for i in range(N):
    leaf = 2 * (leaf - A[i])
    if leaf < 0:
        print(-1)
        exit()
    max_leaf[i+1] = leaf

result = [0] * (N+1)
result[N] = A[N]
for i in reversed(range(N)):
    if result[i+1] + A[i] <= max_leaf[i]:
        result[i] = result[i+1] + A[i]
    elif -(-result[i+1] // 2) > max_leaf[i]:
        print(-1)
        exit()
    else:
        result[i] = max_leaf[i]

print(sum(result))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import accumulate

def main():
    N = int(input())
    A = list(map(int, input().split()))
    accumA = list(accumulate(A[::-1]))[::-1]
    ans = 1
    ne = [0] * (N+1)
    ne[0] = 1

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

    for i in range(1,N+1):
        if i == N:# 最後の深さ
            if ne[i-1] > A[i] or ne[i-1] * 2 < A[i]:
                print(-1)
                exit()
            else:
                ans += A[i]
        else:
            tmp_ne = min(ne[i-1]*2 - A[i], accumA[i+1])
            if tmp_ne < 0:
                print(-1)
                exit()
            else:
                ne[i] = tmp_ne
                ans += tmp_ne + A[i]
    print(ans)
    # print(ne,accumA)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
M=[1]
now=2
for i in range(n):
	M.append(now)
	now-=a[i+1]
	if now<=10**18:
		now*=2
now=a[-1]
for i in range(n):
	M[-i-1]=min(now,M[-i-1])
	now=min(now,M[-i-1])
	now+=a[-i-2]
if a[0]!=0:
	print(-1)
	exit()
for i in range(n+1):
	if M[i]<=0:
		print(-1)
		exit()
print(sum(M))

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()
if A[0]==1 and len(A)==1: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 or sum_A<=0:print(-1);exit()
    point -=A[i]
    sum_A -=A[i]
print(sum(ans))