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

sum_a = [ sum( a ) ]
for d in range( 1, n + 1 ):
    sum_a_next = sum_a[ -1 ] - a[ d - 1 ]
    sum_a.append( sum_a_next )
d_vertex = [ 0 for d in range( n + 1 ) ]

d_vertex[ 0 ] = 1
num_of_v = d_vertex[ 0 ]
for d in range( 1, n + 1 ):
    d_vertex[ d ] = min( sum_a[d], ( d_vertex[ d - 1 ] - a[ d - 1 ] ) * 2 )
    if d_vertex[ d ] <= 0:
        print( -1 )
        exit()
    num_of_v += d_vertex[ d ]
    # print( d, d_vertex )

print( num_of_v )

Submission status: Wrong Answer

Solution code:
import sys
import math


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

R=list(A)

nodes=0
log2=math.log(2)

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

elif A[0]==1 and N==0:
    nodes = 1
else:
    nodes = 1
    R[N]=0
    R[0]=1
    if math.log(A[N])>N*log2:
        nodes = -1
        print(nodes)
        sys.exit(0)
    
    for i in range(N-1,0,-1):
        if A[i] > 0 and (math.log(A[i]) > float(i)*log2):
            nodes = -1
            print(nodes)
            sys.exit(0)

        if N>30:
            R[i]=R[i+1]+A[i+1]
        else:
            R[i]=min(2**i-A[i], R[i+1]+A[i+1])
    # print(R)    

    nodes=1
    for i in range(1,N+1):
        if A[i] <= 2*R[i-1]:
            if i<N:
                R[i] = min(R[i], 2*R[i-1]-A[i])
            else:
                R[N] = 0
            nodes += (R[i]+A[i])
        else:
            nodes = -1
            print(nodes)
            sys.exit(0)

    # print(R)    
    print(nodes)

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline
mod = 10**9+7

N = Int()
A = IntList()

tmp = 0

for i in range(N+1):
    tmp += A[i]*2**(N-i)
    
if tmp > 2**N:
    print(-1)
    sys.exit()


B = A[::-1]
ans = 1
par = 1
C = []
MAXpar = B[0]

for i in range(N):
    leaf = B[i]
    if len(C)>=1:
        MINP = C[-1][0]
        MAXP = C[-1][1]
        C.append([(MINP+leaf+1)//2,MAXP+leaf])
    else:
        C.append([(leaf+1)//2,leaf])
        

D = C[::-1]
#print(D)
for i in range(1,N):
    minp,maxp = D[i]
    
    ans += A[i]+min(maxp,2*par-A[i])
    #print(A[i],min(maxp,2*par-A[i]))
    par = min(maxp,2*par-A[i])
    
ans += A[-1]
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]
    Limit = [2 * 10 ** 8] * (N + 1)

    for i in reversed(range(N)):
        leaf = A[i]
        Limit[i] = min(Limit[i], high + leaf)
        if i <= 30: Limit[i] = min(pow(2, i), Limit[i])
        low = (low + 1) // 2 + leaf
        high += leaf
        if low > Limit[i]:
            print(-1)
            break
        else: 
            lowN[i] = low
            maxN[i] = min(high, Limit[i])
    else:
        #print(maxN)
        for i in range(N - 1):
            if (maxN[i] - A[i]) * 2 <= maxN[i+1]: maxN[i + 1] = (maxN[i] - A[i]) * 2
        if maxN[N-1] - A[N-1] <= A[N] <= 2 * (maxN[N-1] - A[N-1]): print(sum(maxN))
        else: print(-1)
        #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()))
su = sum(a)
# print(su)
l = [su]*(n+1)
for i in range(1,n+1):
    l[i]=l[i-1]-a[i-1]
# print(l)
count=0
x = 0
m=[1]*(n+1)
for j in range(1,n+1):
    m[j] = m[j-1]*2
    if m[j]>l[j]:
        m[j]=l[j]
    if (m[j]<a[j])or(m[j]==a[j] and j!=n):
        # print(m[j],a[j])
        x = 1
        break
    # print(m[j])
    count += m[j]
    m[j] -= a[j]
count+=1

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

Submission status: Wrong Answer

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

n = int(input())
a = list(mapi())
res =a[n]
mp = [2**(i) for i in range(n+1)]
#print(*mp)
lst = 1
pst = [0]*(n+1)
for i in range(n+1):
    #print(lst,a[i])
    #res+=lst
    pst[i] = lst
    lst-=a[i]
    lst*=2
#print(*pst,"c")
#print(*mp,"d")
mx = a[n]
for i in range(n-1,-1,-1):
    if a[i]>=mp[i]:
        res = -1
        break
    mx = min(mx+a[i],mp[i])
    res+=min(mx,pst[i])
    #print(res,mx,mp[i],a[i])
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from math import ceil
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()

INF = 2 ** 40
n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] == 0:
    print(-1)
    exit()
# その層で作ることができるノードの最大値
max_i = defaultdict(lambda: INF)
max_i[0] = 1

for i in range(1, n+1):
    if max_i[i-1] * 2 - a[i] < INF:
        max_i[i] = max_i[i-1] * 2 - a[i]
    else:
        break
for i in max_i.keys():
    if i == 0:
        continue
    max_i[i] += a[i]

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

print(cnt)

Submission status: Wrong Answer

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

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

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

# 根の数
node = 1
root = 0

s = sum(A)

for i in range(len(A) - 1):
    node = min(s, node * 2) - A[i + 1]
    if node <= 0 and len(A) - 1 != i:
        print(-1)
        exit()
    
    s -= A[i + 1]
    root += node

print(root + sum(A) + 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+1):
  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())
leafNodesPerLevel = [int(s) for s in input().split()]

MAX_VALUE = 4 * (10 ** 10)

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

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


checkBinaryTree(N, leafNodesPerLevel)

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[d+1]
    else:
      ans+=min(h_sita[d+1],2*b)
      b=min(h_sita[d+1],2*b)-l[d+1]
      if b<=0 or 2*b<l_sita[d+1]:
        ans=-1
        break
  print(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))
if N == 1:
    print(1 if A_N[0] == 0 else -1)
    exit()

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]

r_reversed_A_N[-1] = A_N[-1]
print(sum(r_reversed_A_N))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 変更
def dfs(i,c,f):
  global ans
  if f==0 and i==1:
    ans=max(ans,c)
  elif f==0:
    ans=-1
  else:
    for k in range(i//2+1):
      if i-k+a[f-1]<=2**(f-1):
        dfs(i-k+a[f-1],c+i-k+a[f-1],f-1)
n=int(input())
a=list(map(int,input().split()))
ans=-1
if a[0]==1:
  print(1)
elif a[0]>=2:
  print(-1)
else:
  dfs(a[n],a[n],n)
  if ans !=-1:
    print(ans)
  else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        if A[i] > 2**i:
            print(-1)
            break
        else:
            pass
resolve()

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
minal=[0]*(N+1)
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
  minal[N-i-1]=mina
leaf=A[0]
a=maxal[0]
ans=a+leaf
for i in range(1,N+1):
  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:
N=int(input())
A=list(map(int,input().split()))
if N>0 and A[0]>0:
    print(-1)
    exit()
b=[1]
for i in range(1,N):
    if b[-1]*2<A[i]:
        print(-1)
        exit()
    b.append(b[-1]*2-A[i])
b.append(0)
c=[]
for i in range(N,-1,-1):
    if b[i-1]>A[i]+b[i]:
        b[i-1]=A[i]+b[i]
    t=A[i]+b[i]
    c.append(t)
print(sum(c))

Submission status: Wrong Answer

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

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

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

# 根の数
node = 1
root = 0

s = sum(A)

for i in range(len(A) - 1):
    node = min(s, node * 2) - A[i + 1]
    if node <= 0:
        print(-1)
        exit()
    
    s -= A[i + 1]
    root += node

print(root + sum(A) + 1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
#N=10**5
#A=[0 for i in range(30)]+[10**8 for i in range(N+1-30)]
#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**15:
        #以降に関わらず構成可能
        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))
#print([(2**i,A[i]) for i in range(N+1)])

Submission status: Wrong Answer

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

if bottom <= 0:
  print(-1)
  exit()

ret = 1
children = 1 - A[0]
bottom -= A[0]

for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def rec(i, A, ok_v):
    # print(i, A, ok_v)
    if ok_v <= 0:
        return -1, -1
    if i == len(A) - 1:
        return A[-1], A[-1]
    # if i > 70:
    #     child, ans = rec(i + 1, A, -1)
    #     if child == ans == -1:
    #         return -1, -1
    #     else:
    #         return child + A[i], child + A[i] + ans
    child, ans = rec(i+1, A, (ok_v - A[i]) * 2)
    #print("\t", i, child, ans)
    if child == ans == -1:
        return -1, -1
    num_v = min(ok_v, child + A[i])
    return num_v, ans + num_v


def main() -> None:
    N = int(input())
    A = [int(x) for x in input().split()]
    if N == 0:
        print(1 if A[0] == 1 else -1)
        return
    elif A[0] != 0:
        print(-1)
        return

    _, ans = rec(1, A, 2)
    print(ans + 1 if ans > 0 else -1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if n>=1 and a[0]>=1:
  print(-1)
  exit()

p=1
ans=1
for i in range(1,n):
  if a[i]>=p:
    print(-1)
    exit()

  p*=2
  if p-a[i]>=a[-1]:
#    print(p-a[i],i,a[i],p)
    ans+=a[-1]*(n-i)
#    print(-1)
    break
  else:
    p-=a[i]
  ans+=p

print(ans+sum(a))

Submission status: Wrong Answer

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

if a[0]!=0:
    print(-1)
    exit()
c = 1
for i in range(1,n+1):
    c = c*2
    if a[i]>c:
        print(-1)
        exit()


x = [0]*(n+1)
x[0] = 1
for i in range(n):
    x[i+1] = 2*(x[i]-a[i])
    if x[i+1]<0:
        print(-1)
        exit()

if x[-1]<a[-1]:
    print(-1)
    exit()
x[-1] = a[-1]

for i in range(n-1,-1,-1):
    if a[i]>x[i]:
        print(-1)
        exit()
    x[i] = min(x[i],x[i+1]+a[i])

c = 1
for i in range(1,n+1):
    c = c*2
    if x[i]>c:
        print(-1)
        exit()

print(sum(x))

Submission status: Wrong Answer

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

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

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

lim = [0]*(n+1)
for i in range(n):
    if i == 0:
        lim[i] = 1
    else:
        lim[i] = lim[i-1]*2 - al[i]
lim[-1] = lim[-2]*2
alt = [0]*(n+1)
limt = [0]*(n+1)
for i in range(n+1):
    alt[i] = al[n-i]
del al
for i in range(n+1):
    limt[i] = lim[n-i]
del lim
ansl = [0]*(n+1)
# print(al, lim)

for i in range(n+1):
    ansl[i] = min(ansl[i-1]+alt[i], limt[i]+alt[i])

for l in limt:
    if l <= 0:
        print(-1)
        exit()

if sum(ansl) <= 0:
    print(-1)
    exit()

print(sum(ansl))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li()

max_a = [0] * (N+1)

max_a[0] = 1 - A[0]

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

num = [0]*(N)
cnt = 0
tmp = A[-1]
for i in reversed(range(N)):

    if tmp <= max_a[i]:
        cnt += tmp
    else:
        cnt += max_a[i]
        tmp = max_a[i]

cnt += sum(A)

print(cnt)

Submission status: Wrong Answer

Solution code:
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, A = Z(), ZZ()
    if N == 0 and A[0] == 1:
        print(1)

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

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

    for i in range(N):
        x = v[i][1] - A[i]
        if x < 0:
            print(-1)
            return
        v[i+1][1] = 2 * x
    if v[N][0] > A[N] or A[N] > v[N][1]:
        print(-1)
        return
    v[N] = [A[N], A[N]]
    for i in range(N):
        x = (v[N-i][0]+1)//2 + A[N-i-1]
        y = v[N-i][1] + A[N-i-1]
        v[N-i-1][0] = max(v[N-i-1][0], x)
        v[N-i-1][1] = min(v[N-i-1][1], y)
        if v[N-i-1][0] > v[N-i-1][1]:
            print(-1)
            return
    v[0] = [1, 1]
    output = 0
    for i in range(N+1): output += v[i][1]
    print(output)

    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 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 += a[0]
    q = a[0]
    for i in range(1,n+1):
        if 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=[int(i) for i in input().split()]
#N=10**5
#A=[0 for i in range(30)]+[10**8 for i in range(N+1-30)]
#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**13:
        #以降に関わらず構成可能
        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))
#print([(2**i,A[i]) for i in range(N+1)])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ans=0
bef=0

tmp=[]

for i in range(N+1):
    if i==0:
        if A[0]==1:
            bef=0
        elif A[0]==0 or A[0]>1:
            print("-1")
            exit()
        else:
            bef=1
        tmp.append(1)
        continue
    elif (bef*2-A[i])>=0:
        bef=bef*2-A[i]
        tmp.append(bef)
    else:
        print("-1")
        exit()

for i in range(N+1):
    current=A[-(i+1)]
    if i==0:
        bef=current
        ans+=current
        continue
    else:
        tmpp = tmp[-(i+1)]
        if current+bef > tmpp:
            ans+=tmpp+current
            bef=tmpp+current
        else:
            ans+=current+bef
            bef=current+bef

print(ans)

Submission status: Wrong Answer

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

if l[0]  != 0:
    print('-1')
    sys.exit()
    
count = 1
edge = 1
for i in range(1,len(l)-1):
#     print(i-1, edge, count)

    
    
    if l[i] >= edge *2:
        print('-1')
        sys.exit()
    
    if edge * 2 - l[i] <= sum(l[i + 1:]):
        count += edge * 2
        edge = edge * 2 -l[i]
#         print(i, 'max', edge,count)
        continue

        
    if edge * 2 - l[i] > sum(l[i + 1 :]):
        count += sum(l[i + 1:]) + l[i]
        edge = sum(l[i+ 1:])
        
#         print(i, 'notmax', edge,count)
        continue

        
        
#n回目の処理
if not edge <=  l[len(l)-1] <= edge * 2:
    print('-1')
    sys.exit()
    
else:
    count +=   l[len(l)-1] 
print(count)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    if A[0] != 0:
        print(-1)
        exit()
    tree = [2 ** i for i in range(n + 1)]
    tree[-1] = A[-1]
    for i in range(n):
        if A[i] > tree[i]:
            print(-1)
            exit()
    for i in range(n - 1, 0, -1):
        cnt = A[i] + tree[i + 1]
        tree[i] = min(tree[i], cnt)
        #print(tree)
    print(sum(tree))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
least = [0] * (n+2)
good = 1
for i in reversed(range(n+1)):
	least[i] = (least[i+1] + 1) // 2 + a[i]
	if i <= 62 and least[i] > 2**i:
		good = 0
		break
if good == 0:
	print(-1)
	exit(0)

ans = [0] * (n+2)
for i in reversed(range(n+1)):
	if i >= 500:
		ans[i] = ans[i+1] + a[i]
		continue

	lo, hi = 0, ans[i+1]//2
	while lo < hi:
		mid = (lo + hi) // 2
		v = ans[i+1] + a[i] - lo
		good = 1
		if i <= 62 and v > 2**i:
			good = 0
		for j in reversed(range(i)):
			v = (v + 1) // 2 + a[j]
			if j <= 62 and v > 2**j:
				good = 0
				break
		if good == 1:
			hi = mid
		else:
			lo = mid + 1
	ans[i] = ans[i+1] + a[i] - lo
print(sum(ans))

Submission status: Wrong Answer

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

if bottom == 0:
  print(-1)
  exit()

ret = 1
children = 1 - A[0]
bottom -= A[0]

for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
cnt = 0
dic = defaultdict(int)
prv = -1
ans = 0
nya = False
max_ = 0
for i in range(n+1):
    if i == 0:
        if A[i] == 0:
            max_ = max(A[i],max_)
            dic[0] = 1
            cnt += 1
        else:
            print(-1)
            exit()
    else:
        if max_ <= A[i]:
            if not dic[A[i]]:
                max_ = max(A[i],max_)
                dic[A[i]] = 1
                ans += A[i] * cnt
            else:
                if A[i] != 0:
                    dic[A[i]] += 1
                    ans += cnt * dic[A[i]]
                    #cnt += 1
                    cnt += 1
                else:
                    cnt += 1
                max_ = max(A[i],max_)
        else:
            if dic[A[i]]:
                ans += cnt * dic[A[i]] if A[i] != 0 else cnt
                cnt += 1
            else:
                print(-1)
                exit()
    #print(ans)
print(ans)

Submission status: Wrong Answer

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

flag=True
if a[0]!=0:
    flag=False
top_list=[1]
bot_list=[a[-1]]

for i in range(n):
    top_list.append((top_list[i]-a[i])*2)
# print(top_list)

for i in range(1,n+1):
    bot_list.append(bot_list[i-1]+a[n-i])
bot_list.reverse()
# print(bot_list)

total=0
for i in range(n+1):
    if top_list[i]<=0 or bot_list[i]<=0:
        flag=False
    total+=min(top_list[i],bot_list[i])

print(total if flag else -1)

Submission status: Wrong Answer

Solution code:
import math

def read_N():
    return int(input())

def read_A():
    return [int(s) for s in input().split()]

def main():
    N = read_N()
    A = read_A()
    b = 0
    output = 0
    for i in range(N+1):
        c = b + A[N-i]
        
        if c > 2**(N-i):
            output = -1
            break
        else:
            if c%2 == 0 and c != 2**(N-i):
                b = c
            else:
                b = math.ceil(c/2)
            output += c
            
    print(output)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
B[0] = 1-A[0]
M = 1
i = 1
while i < N:
  B[i] = B[i-1]*2-A[i]
  i += 1
B[-1] = A[-1]
print(B)
i = N-1
isOK = True
while i >= 0:
  if B[i] < 1:
    isOK = False
    break
  else:
    B[i] = min(B[i], B[i+1])
  i -= 1
print(B)
B[-1] = 0
print(-1 if not isOK else sum(A)+sum(B))

Submission status: Wrong Answer

Solution code:
import sys
import math


def input():
    return sys.stdin.readline()[:-1]

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

sumA = sum(A) - 1
vert = [1]
bool_ = 0
for i,a in enumerate(A):
	#print(i, a, sumA)
	if a > 2**i:
		bool_ = 1
		break
	
	if i == 0:
		if a != 0:
			bool_ = 1
			break
	else:
		if sumA > 0:
			if sumA > vert[i-1]:
				sumA -= vert[i-1]
				#print(vert[i-1]*2 - a)
				if vert[i-1]*2 - a < 0:
					bool_ = 1
					break
				else:
					vert.append(vert[i-1]*2 - a)
			else:
				if sumA*2 + vert[i-1]-sumA - a < 0:
					bool_ = 1
					break
				else:
					vert.append(sumA*2 + vert[i-1]-sumA - a)
					sumA = 0
		else:
			if vert[i-1]- a < 0:
				bool_ = 1
				break
			else:
				vert.append(vert[i-1] - a)

#print(vert)
if bool_ == 1:
	print(-1)
else:
	print(sum(vert) + sum(A))

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()
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):
    l = lst[-1] - a[i-1]
    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:
import sys
n=int(input())
a=list(map(int,input().split()))
for i in range(min(n+1,40)):
  if a[i]>2**i:
    print(-1)
    sys.exit()
if a[0]!=0 and n!=0:
  print(-1)
  sys.exit()
A=[0]
for i in range(n+1):
  A.append(A[-1]+a[i])
s=sum(a)
ans=1
x=1
for i in range(1,n+1):
  S=s-A[i]
  if i<=50:
    if x*2<S:
      ans+=x*2
      x*=2
      x-=a[i]
      if x<=0:
        print(-1)
        sys.exit()
    else:
      x=S
      ans+=x
  else:
    ans+=S
print(ans)

Submission status: Wrong Answer

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

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

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

# 根の数
node = 1
root = 0

s = sum(A)

for i in range(len(A) - 1):
    node = min(s, node * 2) - A[i + 1]
    if node < 0:
        print(-1)
        exit()
    
    s -= A[i + 1]
    root += node

print(root + sum(A) + 1 if node <= A[N - 1] else -1)