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

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    
    if N != 0 and A[0] != 0:
        print(-1)
        return
    if N == 0 and A[0] == 0:
        print(-1)
        return
    
    v = [1]
    m = 2
    for ai in A[1:]:
        v.append(m)
        if m < ai:
            print(-1)
            return
        m -= ai
        m *= 2
    
    m = min(v[-1], A[-1])
    ans = m
    for i in range(N - 1, -1, -1):
        m = min(m + A[i], v[i])
        ans += m
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
L=list(map(int,input().split()))
R=[2**i for i in range(N)]
for i in range(N):
  R[i]=R[i]-L[i]
  for j in range(i+1,N):
    R[j]=(2**(j-i))*R[i]
  if 0 in R[:N]:
    print(-1)
    sys.exit()
print(sum(R)+N-1+L[-1])
print(R)

Submission status: Wrong Answer

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

balls = [0] * (n + 1)

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

for i in range(n+1):
  balls[i] += A[i]

box = [0] * (n + 1)
box[-1] = A[-1]

for i in range(n-1, -1, -1):
  box[i] = box[i + 1] + A[i]

ans = 0
for i, j in zip(balls, box):
  ans += min(i, j)



ans = [min(i, j) for i, j in zip(balls, box)]

if any(i * 2 < j for i, j in zip(ans, ans[1:])) or (ans[0] != 1) or any(i < 1 for i in ans):
  print(-1)
else:
  print(sum(ans))

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = list(map(int,input().split()))
check = 1
ans = 1
if A[0] != 0:
    print("-1a")
    quit()    
for i, j  in enumerate(A[1:-1]):    
    check = 2*check - j
    ans += check + j
    if check <= 0:
        print("-1b")
        quit()
temp = check
check = 2*check - A[-1]
if check < 0:
    print("-1c")
    quit()
elif check > 0:
    print(ans+2*A[-1]-temp-(1-temp%2))
else:
    print(ans + A[-1])

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
if N==0 and A[0]==0:
    print(-1)
    exit()
#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]
print(sum(A))
#print([(2**i,A[i]) for i in range(N+1)])

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 == 0:
    print(0 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:
N =int(input())
A = list(map(int,input().split()))
leaf = sum(A)
if A[0] != 0:
    print(-1)
    exit()
v = [[0,a] for a in A]
v[0][0] = 1
MAX = 2
for i in range(1,N+1):
    v[i][0] = min((v[i-1][0]-v[i-1][1])*2,leaf)
    leaf -= v[i][1]
    MAX *= 2

ans = 0
for a,b in v:
    if a <= 0:
        print(-1)
        exit()
    ans += a

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)

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

c = [0]*(n+1)
c[n] = a[n]
for j in range(n):
    c[n-1-j] = c[n-j] + a[n-1-j]

d = [0]*(n+1)
e = [0]*(n+2)
flag = 0
for k in range(n+1):
    e[k+1] = b[k] - c[k]
    if b[k] < c[k]:
        d[k] = b[k]
        if d[k] <= 0:
            flag += 1
    else:
        d[k] = c[k]
        if d[k] <= 0:
            flag += 1
    if e[k+1] > 1 and e[k] < 0:
        flag += 1

print(sum(d) if flag == 0 else -1)

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 i<n and x<=0:
        print(-1)
        sys.exit()
    else:
      x=S
      ans+=x
  else:
    ans+=S
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    l = len(A)-1
    res = 0
    s = 0
    for i in range(l,-1,-1):
        s += A[i]
        if  s > 2 **i or s%2 != 0:
            if i == 0 and  s > 2 **i:
                res += 1
                continue
            print(-1)
            return
        res += s
        s = s//2
    print(res)
if __name__ == "__main__":
    main()

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)
lim[0] = 1

for i in range(1, n):
    lim[i] = lim[i-1]*2 - al[i]
    if lim[i] <= 0:
        print(-1)
        exit()
lim[-1] = lim[-2]*2

ansl = [0]*(n+1)
# print(al, lim)

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

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

print(sum(ansl))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input().split(" ")
for i in range(len(a)):
	a[i] = int(a[i])
#min = [0] * (n+1)
max = [0] * (n+1)
f = 0
t = a[-1]
if a[0] == 0:
	#min[0] = 1
	max[0] = 1
else:
	if n != 0:
		f = 1
	elif a[0] == 1:
		t = 1
	else:
		f = 1
for i in range(1, len(a)):
	#min[i] = min[i-1] - a[i-1]
	max[i] = (max[i-1] - a[i-1]) * 2
	if max[i] < a[i]:
		f = 1
max[-1] = a[-1]

for i in range(1, len(a)):
	j = n - i
	m = max[j+1] + a[j]
	if m <= max[j]:
		max[j] = m
		t += m
	elif m > max[j]:
		t += max[j]
	#if m < min[j]:
		f = 1
if f == 1:
	print(-1)
else:
	print(t)

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 not node else -1)

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 == 0:
    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:
n=int(input())
a=list(map(int,input().split()))
edge=[2**i for i in range(n+1)]
leaf=[0]*(n+1)
ans=0
for i in range(n+1):
    if a[i]>0:
        leaf[i]=a[i]
        for j in range(n+1-i):
            edge[j+i]-=2**j
edge[n]=0
leaf[n]=a[n]
for i in range(n-1,-1,-1):
    x=edge[i+1]+leaf[i+1]
    if edge[i]<x//2+x%2:
        ans=-1
        break
    if edge[i]>x:
        edge[i]=x
if ans!=-1:
    ans=sum(edge)+sum(leaf)
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    print(-1)
resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
P = [2**i for i in range(len(A))]
import sys
sys.setrecursionlimit(10**9)
# A = A[::-1]
# P = P[::-1]

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

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

ans = [0]
node = [0]
def rec(i):
    if i==0:
        ans[0]+=1
        return 1
    node[0] = node[0] + A[i]
    node[0] = min(node[0], 2*rec(i-1))
    ans[0] += node[0]
    #print (node[0],node[0]-A[i])
    if i!=N and node[0] - A[i] <= 0:
        print(-1)
        exit()
    return node[0] - A[i]
rec(N)
print (ans[0])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math

def floor(x):
    if x%2 == 1:
        return int(x+1/2)
    else:
        return int(x/2)

N = int(input())

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

n_not_leaf = 0
sum_node = 0

num_node = [0 for d in range(N+1)]
max_node = [0 for d in range(N+1)]

# 各層のnodeのmax個を計算
for d in range(N+1):
    if d == 0:
        max_node[0] = 1-A[0]
    else:
        max_node[d] = (max_node[d-1]-A[d-1])*2
    
    if d != N and max_node[d]-A[d] <= 0:
        print(-1)
        exit()


for d in reversed(range(N+1)):
    if d == N:
        num_node[N] = A[N]
    else:
        
        if floor(num_node[d+1]/2)+A[d] > max_node[d]:
            print(-1)
            exit()
        else:
            num_node[d] = min(num_node[d+1]+A[d], max_node[d])

print(sum(num_node))

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 g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
  if a<=0:
    f+=1
    break
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  if l[0]==1:
    print(1)
  else:
    print(-1)
else:
  print(-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 range(1,len(lst1)):
    res3.append(min(INF,res[-1]*2))
    cache = res[-1]*2-lst1[i]
    if cache <= 0 and i != n:
        print(-1)
        exit()
    """elif cache < 0 and i == n:
        print(-1)
        exit()"""
    res.append(min(INF,cache))

#案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 in range(len(res3)):
    ans += min(res2[i],res3[i])
print(ans)
"""print(*res)
print(*res3)
print(*ans)
"""

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]
        num = min(num, maxNodePerLevel[depth-1])
        total_node += num
        lastLevelNode = num
    print(total_node)


checkBinaryTree(N, leafNodesPerLevel)

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):
  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_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 (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()))
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]
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
B[-1] = 0
print(-1 if not isOK else sum(A)+sum(B))

Submission status: Wrong Answer

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

ans = 0
prev = 1
M = max(A)
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 > M:
        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, 0, -1):
        if L[i-1] == "inf" or num+A[i-1] <= L[i-1]:
            num += A[i-1]
        else:
            num = L[i-1]+A[i-1]
        ans += num
    print(ans)

else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if a[0] == 1:
    if n == 0:
        print(1)
    else:
        print(-1)
        exit()
elif a[0] != 0:
    print(-1)
    exit()
acc = [0 for i in range(n+1)]
acc[-1] = a[-1]
for i in range(n, 0,-1):
    acc[i-1] = acc[i] + a[i-1]
ans = count = 1
for i in range(1,n+1):
    #print("{}回目:　count = {}".format(i, count))
    count *= 2
    if count < a[i]:
        print(-1)
        exit()
    if count > acc[i] - a[i]:
        count = acc[i] - a[i]
    else:
        count -= a[i]
    ans += a[i]
    ans += count
if count != 0:
    print(-1)
    exit()
#print("{}回目:　count = {}".format(i, count))
print(ans)

Submission status: Wrong Answer

Solution code:
from math import log2

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=1
count=1
"""
for i in range(1,n+1):
    ans+=count*2
    count*=2
#print(ans)
"""
ans=1
count=1
now=1
for i in range(n+1):
    count=(count-a[i])*2
    if a[i]%2==1:
        now=now*2-a[i]-1
    else:
        now=now*2-a[i]
    ans+=count
    #print(count,ans,now)

print(max(-1,ans))

Submission status: Wrong Answer

Solution code:
N =int(input())
A = list(map(int,input().split()))
leaf = sum(A)
if A[0] != 0:
    print(-1)
    exit()
v = [[0,a] for a in A]
v[0][0] = 1
MAX = 2
for i in range(1,N+1):
    v[i][0] = min((v[i-1][0]-v[i-1][1])*2,leaf)
    leaf -= v[i][1]
    MAX *= 2

ans = 0
for a,b in v:
    if a < 0:
        print(-1)
        exit()
    ans += a

print(ans)

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]>1:
            print("-1")
            exit()
        elif N==0 and A[0]==0:
            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:
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]*2<A[i]+b[i]:
        print(-1)
        exit()
    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()))
L=[0]*(n+1)
L[n]=a[n]
for i in range(n-1,-1,-1):
    L[i]=L[i+1]+a[i]
ans=sum(L)

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]<=0:
        ans=-1
        break
ans=min(ans,sum(L))
print(ans)

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 range(1,len(lst1)):
    res3.append(min(INF,res[-1]*2))
    cache = res[-1]*2-lst1[i]
    if cache <= 0 and i != n:
        print(-1)
        exit()
    elif cache < 0 and i == n:
        print(-1)
        exit()
    res.append(min(INF,cache))

#案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 in range(len(res3)):
    ans += min(res2[i],res3[i])
print(ans)
"""print(*res)
print(*res3)
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)
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:-1]):
    # print(n,ch[e],-1)
    if i >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+1)

Submission status: Wrong Answer

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

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

flag = True
for i in range(n):
    if a[i+1] != 0:
        flag = False
        break
if a[0] == 1 and flag:
    print(1)
    exit()
elif a[0] != 0 and flag == False:
    print(-1)
    exit()

nleaf = 1
ans = 0
v = list()

for i in range(n):
    nleaf -= a[i]
    v.append(nleaf)
    nleaf *= 2

nleaf = a[n]
ans += a[n]
for i in range(n-1, 0, -1):
    if v[i]*2 < nleaf:
        print(-1)
        exit()
    if v[i] > nleaf:
        v[i] = nleaf
    nleaf = v[i] + a[i]
    ans += nleaf
print(ans + 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
saidaiA =[]
oya = 1
flag = True
for i in range(len(A)):
    ko = oya *2
    if i == 0:
        ko = 1
    oya = ko - A[i]
    saidaiA.append(ko)
    # print("i=",i)
    # print("ko =",ko)
    # print("oya =",oya)
    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(int(ans)+1)
else:
    print(-1)

Submission status: Wrong Answer

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

if bottom == 0 or A[0] >= 1:
  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
n=int(input())
a=list(map(int,input().split()))

max_v=[0 for _ in range(n+1)]
max_v[0]=1-a[0]
if(max_v[0]<=0):
    print(-1)
    sys.exit()
#print(0,max_v[0])

for i in range(1,n+1):
    max_v[i]=2*max_v[i-1] - a[i]
#    print(i,max_v[i])
    if(max_v[i]<=0 and i<n):
        print(-1)
        sys.exit()
#print(max_v)
ans=a[-1]
v=a[-1]
for i in range(n-1,-1,-1):
    v=min(v,max_v[i])
    v+=a[i]
    ans+=v
#    print(i,v,ans)
print(ans)

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 = [min(2**(i),int(1e8)) 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:
# C

N = int(input())
A_N = list(map(int, input().split()))
reversed_A_N = list(reversed(A_N))
if N == 0:
    print(1 if A_N[0] == 1 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:
N = int(input())
A = list(map(int,input().split()))

B = [2 **i for i in range(N)]

S = 1
OK = 0
Sum = 0

for i in range(N+1):

  
  Sum += A[i]+2**(-(-A[i] // 2)) -1
  
  if A[i] > S:
    break
  S = S - A[i]
  S = S*2
  
  if i == N-1:
    OK = 1
  if not A[i] == 0:
    OK = 0

  
if OK == 0:
  print(-1)
else:
  print(Sum)

Submission status: Wrong Answer

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

def cc(a):
    ans = 0
    pre = 0
    for i in range(n+1):
        ans += 2**i
    for i in range(n, 1, -1):
        if i > n and a[i] == 0:
            ans -= 2**i - pre - a[i]
        elif i == n:
            ans -= 2**i - a[i]
        elif a[i] != 0:
            pre = a[i]

    return ans


if a[0] == 1 and n == 0:
    print("1")
elif a[0] == 1:
    print("-1")
elif f:
    print("-1")
else:
    print(cc(a))

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)
A = A[::-1]

ans = 0
n = 0
for e,i in enumerate(A[:-1]):
    # print(n,ch[e],-1)
    if i >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',ans+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]>1:
            print("-1")
            exit()
        elif N==1 and A[0]==0:
            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:
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 and i!=n:
        print(-1)
        exit()
print(sum(a)+sum(c))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0:
	print(-1)
elif a[0]!=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:
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
    if n > 0:
        num[-1] = a[-1]

    if a[0] > 0 and n >= 1:
        print(-1)
    elif a[0] == 1 and n == 0:
        print(1)
    elif n == 0 and a[0] == 0:
        print(-1)
    elif n == 1 and a[1] == 0:
        print(-1)
    elif n == 1 and a[1] == 1:
        print(2)
    elif n == 1and a[1] == 2:
        print(3)
    elif n >= 1 and a[-1] == 0:
        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()))
ok=True

v=[0 for i in range(n+2)]
import time

#start=time.time()
nextv=0

nec=2**n

for i in range(n,-1,-1):

    if nec>=v[i+1]+a[i]:
        v[i]=v[i+1]+a[i]
    else:
        v[i]=nec

    nec=nec >>1



#print(time.time()-start)

for i in range(1,n+1):
    if v[i-1]-a[i-1]<0:
        ok=False
        break
    if (v[i-1]-a[i-1])*2<v[i]:
        v[i]=(v[i-1]-a[i-1])*2


if n==0:
    if a[0]!=1:ok=False
else:
    if a[0] != 0:ok = False



ans=sum(v)
if ans==0:ok=False

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=1
count=1
"""
for i in range(1,n+1):
    ans+=count*2
    count*=2
#print(ans)
"""
ans=1
count=1
now=1
for i in range(n):
    count=(count-a[i])*2
    if a[i]%2==1:
        now=now*2-a[i]-1
    else:
        now=now*2-a[i]
    ans+=count
    #print(count,ans,now)

print(max(-1,ans))