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()))
MAX = 10 ** 10

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:
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**10:
            ko = 10**11
        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:
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())
# n+1個
A = list(map(int, input().split()))


cnt = 0
A[-1] -= 1
temp = 0
yoryoku = [0] * (n + 1)
temp_yoryoku = 1

amari = 0
duration = 0
for i in range(1, n + 1):
    amari *= 2
    amari += 1
    amari -= A[i]
    yoryoku[i] = amari
    if amari > 0:
        duration += 1
    else:
        duration = 0


remain = 0
for i in range(n, 0, -1):
    remain += A[i] - 1
    remain = min(yoryoku[i], remain)
    cnt += remain + 1
print(cnt)

Submission status: Wrong Answer

Solution code:

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

ch = [1]

cH = [1]
if A[0]>0:
    print(-1)
    exit()
for e,i in enumerate(A[1:]):
    cH.append(cH[-1]*2-i)
    # ch.append((cH[-1]*2)//(2**i))
# print(ch)
# print(cH)

# ch = ch[:-1]
# ch = ch[::-1]
# ch[0]*=2
# print(ch)
cH = cH[:-1]
cH.append(cH[-1]*2-A[-1])
cH = cH[::-1]
# print(cH)
if 0 in cH:
    print(-1)
    exit()
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:]):
    # print(n,ch[e],-1)
    if n//2+(n%2!=0)>cH[e]:
        print(-1)
        exit()
    if n  <= cH[e]:
        # print('ans:',ans,'n:',n)
        ans += n+i
        n+=i
    else:
        # print('ans:',ans,'ch:',cH[e],'i:',i)
        ans +=cH[e]+i
        n = cH[e]+i

    # print('ans:',ans,'n:',n)
print(ans)

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]
      if b<=0:
        ans=-1
        break
  print(ans)

Submission status: Wrong Answer

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

def main():
    x = A[0]
    ans = A[0]
    d = N-1
    for i in range(1, N+1):
        a = A[i]
        # print(d, x, a, ans, pow(2,d))
        if (x+1)//2 +a > pow(2, d):
            print(-1)
            return
        if i == N:
            x = 1
        else:
            # print(x+a, 2*(pow(2,d-1) -A[i+1]))
            x = min(x+a, 2*(pow(2,d-1) -A[i+1]) )
        d -= 1
        ans += x
        # print(x, ans)
        # print(d, x, a, ans, pow(2,d+1))
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()


show_flg=False
show_flg=True
ans=0


n=I()
a=LI()
b=a[:]
c=[0]*(n+1)

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

#ans=(1<<(n+1))-1
ans=sum(b)

t=1
#show(t)
for i in range(n):
    if a[i]+1>t:
        print(-1)
        exit()
    if c[i]+a[i]>l[i]*2:
        l[i+1]=l[i]*2-a[i]
    else:
        l[i+1]=l[i]*2-a[i]
    l[i+1]=min(l[i]*2-a[i],t-a[i])
    if i+1==n:
        l[i]=0
    
    x=max(a[i]+c[i]-t,0)
    ans-=x
    #show(t,x,ans)

    t<<=1

ans=sum(l)+sum(a)
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
print(sum(leaf) + sum(not_leaf))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
if N == 0:
  if A[0] == 0:
    ans = 1
  else:
    ans = -1
    
elif N == 1:
  if A == [0,2]:
    ans = 3
  else:
    ans = -1

else:
  TOP = [0 for _ in range(len(A))]
 
  impossible =0
  TOP[0] = 1
 
  for n in range(len(A)-1):
    max_TOP = TOP[n] * 2 - A[n+1]
 
 
    if n != len(A)-2:
      if max_TOP <= 0:
        impossible = 1
        break
      else:
        TOP[n+1] = max_TOP
    else:
      if max_TOP < 0:
        impossible = 1
        break
      else:
        TOP[-1] = TOP[-2]*2
 
  if impossible == 0:
    if TOP[-1] != A[-1]:
      ans = sum(TOP)+sum(A)-TOP[-1]
      cuts = TOP[N] - A[N] - TOP[N-1]
      for n in range(N,2,-1):
        if cuts <= 0:
          break
        else:
          ans -= cuts
          cuts = cuts- TOP[n-2]
    else:
      ans = sum(TOP)+sum(A)-TOP[-1]
  else:
    ans = -1
  
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math


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

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

    peak = 0
    peak_pre = 0
    max_peak = [0] * (N + 1)
    max_peak[0] = 1
    for j in range(1, N+1):
        max_peak[j] = max_peak[j-1] * 2 - A[j]
        if (j == N):
            max_peak[j] += A[j]
    for i in range(N, 0, -1):
        a = A[i]
        if N == i and a % 2 == 1:
            print('-1')
            sys.exit()
            break
        if 2**i <= a:
            print('-1')
            sys.exit()
            break
        cur_peak = min(math.ceil(peak_pre), max_peak[i]) +a
        peak += cur_peak
        peak_pre = cur_peak
    print(peak+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    max_node = []

    for i in range(n, -1, -1):
        if i == n:
            max_node.append(A[i])
        elif i == 0:
            max_node.append(1)
        else:
            max_node.append(max_node[n-i-1] + A[i])
    
    max_node = max_node[::-1]
    res = 0

    for i in range(len(max_node)):
        if i == 0:
            continue
        elif i == 1 and max_node[i] > 2:
            max_node[i] = 2
        
        if max_node[i] > 2 * (max_node[i-1] - A[i-1]):
            max_node[i] = 2 * (max_node[i-1] - A[i-1])
        
        if max_node[i] >= max_node[i-1]*2 and max_node[i] <= A[i]:
            res = -1
            break

    
    if n != 0 and A[0] == 1:
        res = -1
    
    if res == 0:
        print(sum(max_node))
    else:
        print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x


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

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

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

  '''


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('-1')
        elif A == [1]:
            print('1')
        else:
            print('-1')
        return

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

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

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

    elif sum(A) == 1 and A[-1] != 1:
        print('-1')
        return

    for d in range(1, N):
        f[d] = 2 * min(f[d - 1], count) - A[d] + min(max(f[d - 1] - count, 0), f[d - 1])
        count -= 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:
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 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:

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]
    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()
    if(A[i]>chiled_value*2):
        print(-1)
        exit()
print(top_value+A[N])

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

ans = 0

parents = 1

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

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()))
MAX = 10 ** 10

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


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

Submission status: Wrong Answer

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

a = 1
answer = 1
f = 1
i = 0
while f == 1 and i < n:
    a = (a - vert[i]) * 2 #i+1で持てる頂点数
    if a <= 0 and i < n  - 1:
        f = 0
        break
    else:
        answer += a
        i += 1
        
if vert[n] < a:
    answer = answer - (a - vert[n])

if f == 1:
    print(answer) 
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.reverse()
ans = 0
eda = 0
if A[n] !=0:
    print("-1")
else:
    eda = A[0]
    for i in range (n):
        ans += eda
        if eda+A[i+1] > 2**(n-i):
            eda = (eda+1)//2
            if eda > 2**(n-i):
                print("-1")
                break
        else:
            eda +=A[i+1]
    print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil

print('input >>')
N = int(input())
As = list(map(int,(input().split())))

ans = 0
# edge = As[-1]
edge = 0
lim = 2 ** N

for d in range(len(As)-1, -1, -1):
    edge += As[d]
    lim 
    if edge > lim:
        edge = ceil(edge/2)
        if edge > lim:
            print(-1)
    if d < N:
        ans += edge + As[d]
    # print(d, ans, edge)
    lim //= 2

# print('-----output-----')
print(ans)

# わからないけど撤退したわけではないというアピールのためにWAつけとく

Submission status: Wrong Answer

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

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-1):
    print(-1)
    quit()

lst = [1]
for i in range(1, n):
    l = lst[-1] - a[i-1]
    if l <= 0:
        print(-1)
        quit()
    lst.append(2*l)
lst.append(a[-1])
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())
P = list(map(int, input().split()))

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

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

#print(MAX)

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

Submission status: Wrong Answer

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

L[0]=1
for i in range(1,n+1):
    L[i]=min((L[i-1]-a[i-1])*2, L[i])
    if L[i]<a[i]:
        ans=-1
        break
else:
    ans=sum(L)
    if a[0]==1 and n!=0:
        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()))

#print(a)

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

b=1
count=1

for i in range(n-1):
    if a[i+1] > 2*b:
        print(-1)
        exit(0)
    else:
        b= min(2*b-a[i+1], sum(a[i+2:]))

        count += b



print(count+ sum(a))

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]
        if i <= 30:
            num = min(num, pow(2, i))
        ans += num
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
saidai=[1]*(N+1)
back=[0]*(N+1)
if N!=0:
    ans=0
    saidai[0]=1
    for n in range(1,N+1):
        saidai[n]=(saidai[n-1]-A[n-1])*2
        if saidai[n]<=0:
            ans=-1
    for n in range(N+1):
        a=N-n
        if a==N:
            back[a]=A[a]
        else:
            back[a]=back[a+1]+A[a]
    if ans!=-1:
        c=0
        for n in range(N+1):
            a=N-n
            if c==0:
                if saidai[a]>back[a]:
                    ans+=back[a]
                else:
                    ans+=saidai[a]
                    c=1
            else:
                ans+=saidai[a]
    print(ans%1000000007)

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

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 or s == 0:
    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:

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

ch = [1]

cH = [1]
if A[0]>0:
    print(-1)
    exit()
for e,i in enumerate(A[1:]):
    cH.append(cH[-1]*2-i)
    # ch.append((cH[-1]*2)//(2**i))
# print(ch)
# print(cH)

# ch = ch[:-1]
# ch = ch[::-1]
# ch[0]*=2
# print(ch)
cH = cH[:-1]
cH.append(cH[-1]*2)
cH = cH[::-1]
# print(cH)
if 0 in cH:
    print(-1)
    exit()
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:]):
    # print(n,ch[e],-1)
    if n//2+(n%2!=0)>cH[e]:
        print(-1)
        exit()
    if n  <= cH[e]:
        # print('ans:',ans,'n:',n)
        ans += n+i
        n+=i
    else:
        # print('ans:',ans,'ch:',cH[e],'i:',i)
        ans +=cH[e]+i
        n = cH[e]+i

    # print('ans:',ans,'n:',n)
print(ans)

Submission status: Wrong Answer

Solution code:
while True:
    try:
        k=int(input())
        ok=True
        num=1
        p=2
        a=[]
        node=[1]
        a=list(map(int,input().split()))
        if a[0]!=0:
            print(-1)
            continue
        for i in range(1,k+1):
            if a[i]>p:
                ok=False
            num+=p
            node.append(p)
            p=(p-a[i])*2
        num-=node[k]-a[k]
        r=k-1
        k2=a[r]
        while r>=0 and node[r]>a[k]+k2:
            num-=node[r]-a[k]-k2
            r-=1
            k2+=a[r]
        if ok==False:
            print("-1")
        else:
            print(num)
    except:
        break

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 <= 100:
        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 = pre_a * 2 + cur_a
# INF = 10**13
if flag:
    # tmp = [1 for i in range(32)]
    tmp = [1 for i in range(103)]
    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, 103)):
        # 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:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)

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

ret = 1
children = 1

for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    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)