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

rg=[ [-1,-1]for _ in range(N+1)]
rg[0]=[1,1]
rg[N]=[A[N],A[N]]

for i in range(N-1,0,-1):
  rg[i][0]= (rg[i+1][0]+1)//2 +A[i]
  rg[i][1]= rg[i+1][1]+A[i]
  
for j in range(1,N):
  rg[j][0]= max( rg[j][0], rg[j-1][0])
  rg[j][1]= min( rg[j][1], 2*(rg[j-1][1]-A[j-1]) )
  if rg[j][0]>rg[j][1]:
    print(-1)
    exit()
else:
  ans=0
  for k in rg:
    ans += k[1]
  print(ans)

Submission status: Wrong Answer

Solution code:


n = int(input())
leafNums = list(map(int, input().split()))

ans = 0

# d=0
ans += 1
currentRootNodeNum = 1
if leafNums[0] >= 1 and n <=1:
    print(-1)
    exit()

# cond2maxの計算でTLEっぽいので、事前に累積和を求めておく
leafAccumlateFromEnd = [0] * (n+1)
leafAccumlateFromEnd[n] = leafNums[n]
for i in range(n-1,-1,-1):
    leafAccumlateFromEnd[i] = leafAccumlateFromEnd[i+1] + leafNums[i]

# d=1~n
for i in range(1, n+1):
    # cond2max = sum(leafNums[i:])
    cond2max = leafAccumlateFromEnd[i]
    cond1max = currentRootNodeNum*2
    currentMax = min(cond1max, cond2max)
    ans += currentMax
    currentRootNodeNum = currentMax - leafNums[i]
    if currentRootNodeNum < 0:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

Solution code:


n = int(input())
leafNums = list(map(int, input().split()))

ans = 0

# d=0
ans += 1
currentRootNodeNum = 1
if leafNums[0] <= 1 and n <=1:
    print(-1)
    exit()

# cond2maxの計算でTLEっぽいので、事前に累積和を求めておく
leafAccumlateFromEnd = [0] * (n+1)
leafAccumlateFromEnd[n] = leafNums[n]
for i in range(n-1,-1,-1):
    leafAccumlateFromEnd[i] = leafAccumlateFromEnd[i+1] + leafNums[i]

# d=1~n
for i in range(1, n+1):
    # cond2max = sum(leafNums[i:])
    cond2max = leafAccumlateFromEnd[i]
    cond1max = currentRootNodeNum*2
    currentMax = min(cond1max, cond2max)
    ans += currentMax
    currentRootNodeNum = currentMax - leafNums[i]
    if currentRootNodeNum < 0:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

Solution code:


n = int(input())
leafNums = list(map(int, input().split()))

ans = 0

# d=0
ans += 1
currentRootNodeNum = 1
if leafNums[0] <= 1 and n <=1:
    print(-1)
    exit()

# d=1~n
for i in range(1, n+1):
    cond2max = sum(leafNums[i:])
    cond1max = currentRootNodeNum*2
    currentMax = min(cond1max, cond2max)
    ans += currentMax
    currentRootNodeNum = currentMax - leafNums[i]
    if currentRootNodeNum < 0:
        print(-1)
        exit()

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n=read()
a=list(reads())
res=0
node=[0 for _ in range(n+1)]
node[-1]=a[-1]
#node[-1][0]=node[-1][1]=a[-1]
#sub=[0]*n
for i in range(n-1,-1,-1):
  #node[i][0]=(node[i+1][0]+1)//2+a[i]
  node[i]=min(node[i+1]+a[i],1<<i)
#print(node)
for i in range(n):
  sub=node[i]-a[i]
  node[i+1]=min(node[i+1],sub*2)
#print(sub)
#print(node)
for i in range(n+1):
  if node[i]<a[i]:
    print("-1")
    exit()
  if (node[i]<=0 and i<n) :
    print("-1")
    exit()
  res+=node[i]
print(res)

Submission status: Wrong Answer

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


ans = 0
nodes_min = [0] * (n + 1)
nodes_max = [0] * (n + 1)
nodes_min[n] = leaves[n]
nodes_max[n] = leaves[n]

for depth in range(n, 0, -1):
    root_min = nodes_min[depth] // 2 + nodes_min[depth] % 2
    nodes_min[depth - 1] = leaves[depth - 1] + root_min
    root_max = nodes_max[depth]
    nodes_max[depth - 1] = leaves[depth - 1] + root_max
nodes = [0] * (n + 1)
nodes[0] = 1
for depth in range(n):
    roots = nodes[depth]-leaves[depth]
    if roots <= 0:
        print(-1)
        break
    nodes[depth + 1] = min(roots * 2, nodes_max[depth + 1])
else:
    print(sum(nodes))

Submission status: Wrong Answer

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


ans = 0
nodes_min = [0] * (n + 1)
nodes_max = [0] * (n + 1)
nodes_min[n] = leaves[n]
nodes_max[n] = leaves[n]

for depth in range(n, 0, -1):
    root_min = nodes_min[depth] // 2 + nodes_min[depth] % 2
    nodes_min[depth - 1] = leaves[depth - 1] + root_min
    root_max = nodes_max[depth]
    nodes_max[depth - 1] = leaves[depth - 1] + root_max
nodes = [0] * (n + 1)
nodes[0] = 1
for depth in range(n):
    roots = nodes[depth]-leaves[depth]
    if roots < 0:
        print(-1)
        break
    nodes[depth + 1] = min(roots * 2, nodes_max[depth + 1])
else:
    print(sum(nodes))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n=read()
a=list(reads())
if a[0]!=0:
  print("-1")
  exit()
res=0
node=[0 for _ in range(n+1)]
node[-1]=a[-1]
#node[-1][0]=node[-1][1]=a[-1]
#sub=[0]*n
for i in range(n-1,-1,-1):
  #node[i][0]=(node[i+1][0]+1)//2+a[i]
  node[i]=min(node[i+1]+a[i],1<<i)
#print(node)
for i in range(n):
  sub=node[i]-a[i]
  node[i+1]=min(node[i+1],sub*2)
#print(sub)
#print(node)
for i in range(n+1):
  if node[i]<a[i]:
    print("-1")
    exit()
  if i<n and node[i]-a[i]<node[i+1]:
    print("-1")
    exit()
  if (node[i]<=0 and i<n) or node[i]<0:
    print("-1")
    exit()
  res+=node[i]
print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0:
    print(0 if a[0]==1 else -1)
    exit()
e=[1-a[0]]
for i in range(n):
    e.append(max(e[i]-a[i],0)*2)
#print(e)
p=[i for i in a]
for i in range(n-1,-1,-1):
    if -p[i+1]//2*-1+p[i]>e[i]:
        print(-1)
        exit()
    if p[i+1]+p[i]>e[i]:
        p[i]=e[i]
    else:
        p[i]+=p[i+1]
print(sum(p))
#print(p)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n=read()
a=list(reads())
if a[0]!=0:
  print("-1")
  exit()
res=0
node=[0 for _ in range(n+1)]
node[-1]=a[-1]
#node[-1][0]=node[-1][1]=a[-1]
#sub=[0]*n
for i in range(n-1,-1,-1):
  #node[i][0]=(node[i+1][0]+1)//2+a[i]
  node[i]=min(node[i+1]+a[i],1<<i)
#print(node)
for i in range(n):
  sub=node[i]-a[i]
  node[i+1]=min(node[i+1],sub*2)
#print(sub)
#print(node)
for i in range(n+1):
  if node[i]<a[i]:
    print("-1")
    exit()
  if (node[i]<=0 and i<n) or node[i]<0:
    print("-1")
    exit()
  res+=node[i]
print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0:
    print(-1 if a[0]==1 else 0)
    exit()
e=[1-a[0]]
for i in range(n):
    e.append(max(e[i]-a[i],0)*2)
#print(e)
p=[i for i in a]
for i in range(n-1,-1,-1):
    if -p[i+1]//2*-1+p[i]>e[i]:
        print(-1)
        exit()
    if p[i+1]+p[i]>e[i]:
        p[i]=e[i]
    else:
        p[i]+=p[i+1]
print(sum(p))
#print(p)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n=read()
a=list(reads())
if a[0]>1:
  print("-1")
  exit()
elif a[0]==1 and n>0:
  print("-1")
  exit()
res=0
node=[0 for _ in range(n+1)]
node[-1]=a[-1]
#node[-1][0]=node[-1][1]=a[-1]
sub=[0]*n
for i in range(n-1,-1,-1):
  #node[i][0]=(node[i+1][0]+1)//2+a[i]
  node[i]=min(node[i+1]+a[i],1<<i)
#print(node)
for i in range(n):
  sub[i]=node[i]-a[i]
  node[i+1]=min(node[i+1],sub[i]*2)
#print(sub)
#print(node)
for i in range(n+1):
  if (node[i]<=0 and i<n) or node[i]<0:
    print("-1")
    exit()
  res+=node[i]
print(res)

Submission status: Wrong Answer

Solution code:
# 初期入力
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
child =[0]*(N+1)
child[0] =2

#根→葉に向かって、子の最大値
for i in range(1,N):
    child[i] =2*(child[i-1] -A[i])
    if child[i]<0: #子がマイナスはありえない
        print(-1)
        exit

#葉→根に向かって子と葉の関係を見る
child[N-1] =min(A[N],child[N-1])
for i in range(N-2,0,-1):
    child[i] =min(child[i],child[i+1] +A[i+1] )

print(sum(child) +1) #根も頂点、＋１

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n=read()
a=list(reads())
if a[0]!=0:
  print("-1")
  exit()
res=0
node=[0 for _ in range(n+1)]
node[-1]=a[-1]
#node[-1][0]=node[-1][1]=a[-1]
sub=[0]*n
for i in range(n-1,-1,-1):
  #node[i][0]=(node[i+1][0]+1)//2+a[i]
  node[i]=min(node[i+1]+a[i],2**i)
for i in range(n):
  sub[i]=node[i]-a[i]
  node[i+1]=min(node[i+1],sub[i]*2)
for i in range(n+1):
  if (node[i]==0 and i<n) or node[i]<0:
    print("-1")
    exit()
  res+=node[i]
print(res)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

n=read()
a=list(reads())
if a[0]!=0:
  print("-1")
  exit()
res=0
hoge=1
node=[[0,0] for _ in range(n+1)]
node[-1][0]=node[-1][1]=a[-1]
sub=[0]*n
for i in range(n-1,-1,-1):
  node[i][0]=(node[i+1][0]+1)//2+a[i]
  node[i][1]=min(node[i+1][1]+a[i],2**i)
#print(node)
for i in range(n):
  sub[i]=node[i][1]-a[i]
  node[i+1][1]=min(node[i+1][1],sub[i]*2)
#print(sub)
#print(node)
for i in range(n+1):
  if node[i][1]<0:
    print("-1")
    exit()
  res+=node[i][1]
print(res)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[]
if N>=1 and A[0]>=1:
    print(-1)
    exit()
for i in range(N+1):
    B.append(sum(A[i:]))
b=1
count=1
for l in range(1,N):
    a=A[l]
    c=0
    for m in range(b-a,2*b+1-a):
        if m<=B[l+1]:
            c=max(m,c)
    if c==0:
        print(-1)
        exit()
    else:
        b=c
    count+=b+a
count+=A[-1]
print(count)

Submission status: Wrong Answer

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

if N != 0 and A[0] != 0:
    ans = -1
else:
    ans = 1
    node = 1
    lateFolia = sum(A)
    preFolia = 0

    for d in range(1, N+1):
        folia = A[d]
        node = min((node-preFolia)*2, lateFolia)

        if node < folia:
            ans = -1
            break

        ans += node
        lateFolia -= folia
        preFolia = folia

print(ans)

Submission status: Wrong Answer

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

B = []

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

else:
    if A[0] != 0:
        print(-1)
        exit()
    else:
        B.append(1)
        for i in range(N + 1):
            B.append((B[i - 1] - A[i - 1]) * 2)
            if (A[i] > B[i] or (A[i] == B[i] and i != N)):
                print(-1)
                exit()

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

        print(ans)
        exit()

Submission status: Wrong Answer

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

B = []

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

else:
    if A[0] != 0:
        print(-1)
        exit()
    else:
        B.append(1)
        for i in range(N + 1):
            B.append((B[i - 1] - A[i - 1]) * 2)
            if (A[i] > B[i] or (A[i] == B[i] and i != N)):
                print(-1)
                exit()

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

        print(ans)
        exit()

Submission status: Wrong Answer

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

if len(A) != 1 and A[0] != 0:
    ans = -1
else:
    ans = 1
    node = 1
    lateFolia = sum(A)
    preFolia = 0

    for i in range(1, N+1):
        folia = A[i]
        if node*2 < folia:
            ans = -1
            break
        else:
            node = min((node-preFolia)*2, lateFolia)
            ans += node
            preFolia = folia
            lateFolia -= preFolia

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
*a, = map(int,input().split())
a.reverse()
b = [a[0]]
for i in range(1,n+1):
    b.append(b[-1] + a[i])
b.reverse()
c = [0 for _ in range(n+1)]; c[0] = 1
ans = -1
for i in range(1,n+1):
    c[i] = min(c[i-1]*2,b[i])
    c[i] -= a[i]
    if i < n and c[i] <= 0 or i == n and c[i] < 0:
        print(-1);exit()
print(sum(c) + sum(a[1:]))

Submission status: Wrong Answer

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

if A[0] != 0:
    ans = -1
else:
    ans = 1
    node = 1
    lateFolia = sum(A)
    preFolia = 0

    for i in range(1, N+1):
        folia = A[i]
        if node*2 < folia:
            ans = -1
            break
        else:
            node = min((node-preFolia)*2, lateFolia)
            ans += node
            preFolia = folia
            lateFolia -= preFolia

print(ans)

Submission status: Wrong Answer

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

if A[0] != 0:
    ans = -1
else:
    ans = 1
    node = 1
    preFolia = 0
    # print("0 node", node, "ans", ans)

    for i in range(1, N+1):
        folia = A[i]
        if node*2 <= folia:
            ans = -1
            break
        else:
            lateFolia = sum(A[i:])
            node = min((node-preFolia)*2, lateFolia)
            ans += node
            preFolia = folia
            # print(i, "node", node, "folia", folia,
            #       "lateFolia", lateFolia, "ans", ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
*a, = map(int,input().split())
a.reverse()
b = [a[0]]
for i in range(1,n+1):
    b.append(b[-1] + a[i])
b.reverse()
c = [1 for _ in range(n+1)]
ans = -1
for i in range(1,n+1):
    c[i] = min(c[i-1]*2,b[i])
    c[i] -= a[i]
    if c[i] < 0:
        print(-1);exit()
print(sum(c) + sum(a[1:]))

Submission status: Wrong Answer

Solution code:
n = int(input())
*a, = map(int,input().split())
a.reverse()
b = [a[0]]
for i in range(1,n+1):
    b.append(b[-1] + a[i])
b.reverse()
c = [1 for _ in range(n+1)]
ans = -1
for i in range(1,n+1):
    c[i] = min(c[i-1]*2,b[i])
    c[i] -= a[i]
    if c[i] <= 0:
        print(-1);exit()
print(sum(c) + sum(a[1:]))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
 
n = int(readline())
a = list(map(int,readline().split()))

b = [0]*(n+1)
b[-1] = a[-1]
for i in range(n-1,-1,-1):
  b[i] = b[i+1]+a[i]
#print(b)
c = [1]*(n+1)
for i in range(n):
  c[i+1] = (c[i]-a[i])*2
#print(c)
ans = 0
for i in range(n+1):
  m = min(b[i],c[i])
  ans += m
  
if n == 0:
  ans = 1
if m < 0 or a[0] != 0:
  ans = -1
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
 
n = int(readline())
a = list(map(int,readline().split()))

b = [0]*(n+1)
b[-1] = a[-1]
for i in range(n-1,-1,-1):
  b[i] = b[i+1]+a[i]
#print(b)
c = [1]*(n+1)
for i in range(n):
  c[i+1] = (c[i]-a[i])*2
#print(c)
ans = 0
for i in range(n+1):
  m = min(b[i],c[i])
  if m < 0:
    ans = -1
    break
  ans += m
  
if n == 0:
  ans = 1
if a[0] != 0:
  ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
 
n = int(readline())
a = list(map(int,readline().split()))
mod = 10**9+7
b = [0]*(n+1)
b[-1] = a[-1]
for i in range(n-1,-1,-1):
  b[i] = b[i+1]+a[i]
#print(b)
c = [1]*(n+1)
for i in range(n):
  c[i+1] = (c[i]-a[i])*2
#print(c)
ans = 0
for i in range(n+1):
  m = min(b[i],c[i])
  if m < 0 or a[i] > b[i]:
    ans = -1
    break
  ans += m
  ans %= mod
  
if n == 0:
  ans = 1
if a[0] != 0:
  ans = -1
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
 
n = int(readline())
a = list(map(int,readline().split()))
mod = 10**9+7
b = [0]*(n+1)
b[-1] = a[-1]
for i in range(n-1,-1,-1):
  b[i] = b[i+1]+a[i]
#print(b)
c = [1]*(n+1)
for i in range(n):
  c[i+1] = (c[i]-a[i])*2
#print(c)
ans = 0
for i in range(n+1):
  m = min(b[i],c[i])
  if m < 0:
    ans = -1
    break
  ans += m
  ans %= mod
  
if n == 0:
  ans = 1
if a[0] != 0:
  ans = -1
if ans > 0:
  ans %= mod
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
 
n = int(readline())
a = list(map(int,readline().split()))
mod = 10**9+7
b = [0]*(n+1)
b[-1] = a[-1]
for i in range(n-1,-1,-1):
  b[i] = b[i+1]+a[i]
#print(b)
c = [1]*(n+1)
for i in range(n):
  c[i+1] = (c[i]-a[i])*2
#print(c)
ans = 0
for i in range(n+1):
  m = min(b[i],c[i])
  if m < 0:
    ans = -1
    break
  ans += m
  ans %= mod
  
if n == 0:
  ans = 1
if a[0] != 0:
  ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))  #葉の数

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

    b=[0]*(n+1)  #葉でない頂点数
    res=0
    flag=True
    for i in range(n+1):
        if i==0:
            if a[i]==1: b[i]=0
            else: b[i]=1
            res+=1
        else:
            v_max=min(s[i],2*b[i-1])
            if v_max<a[i]:
                flag=False
                break
            else:
                b[i]=v_max-a[i]
                res+=v_max
    
    if flag:
        if a[-1]==0:
            print(-1)
        else:
            print(res)
    else:
        print(-1)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))  #葉の数

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

    b=[0]*(n+1)  #葉でない頂点数
    res=0
    flag=True
    for i in range(n+1):
        if i==0:
            if a[i]==1: b[i]=0
            else: b[i]=1
            res+=1
        else:
            v_max=min(s[i],2*b[i-1])
            if v_max<a[i]:
                flag=False
                break
            else:
                b[i]=v_max-a[i]
                res+=v_max
    
    if flag:
        print(res)
    else:
        print(-1)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))  #葉の数

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

    b=[0]*(n+1)  #葉でない頂点数
    res=0
    flag=True
    for i in range(n+1):
        if i==0:
            if a[i]==1: b[i]=0
            else: b[i]=1
            res+=1
        else:
            v_max=min(s[i],2*b[i-1])
            if v_max<a[i]:
                flag=False
                break
            else:
                b[i]=v_max-a[i]
                res+=b[i]
    
    if flag:
        if n==0:
            print(1)
        else:
            print(res+s[0])
    else:
        print(-1)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))  #葉の数

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

    b=[0]*(n+1)  #葉でない頂点数
    res=0
    flag=True
    for i in range(n+1):
        if i==0:
            if a[i]==1: b[i]=0
            else: b[i]=1
            res+=1
        else:
            v_max=min(s[i],2*b[i-1])
            if v_max<a[i]:
                flag=False
                break
            else:
                b[i]=v_max-a[i]
                res+=b[i]
    
    if flag:
        print(res+s[0])
    else:
        print(-1)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
k = 1-a[0]
ans = 1

for i in range(1,n+1):
  if k*2 <= s:
    k *= 2
  else:
    k = s
  ans += k
  k -= a[i]
  s -= a[i]

if k == 0 and s == 0:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

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

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

# 末端の葉の数で初期化
sum_arr = [arr[-1]]*N
for i in range(1,N):
	# 深さi+1での頂点数 + 深さiでの葉の数
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
# 本来の順番に反転
sum_arr = sum_arr[::-1]

# 二分木の根から見ていく
ans = [1]*(N+1)
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    tmp = min((ans[i-1]-arr[i-1])*2,sum_arr[i-1])
    ans[i] = tmp

for i in range(min(25,N+1)):
    if ans[i] > 2**i:
        print(-1)
        exit()
# if ans[N] != arr[-1]:
#     print(-1)
#     exit()

print(sum(ans))

Submission status: Wrong Answer

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

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

# 末端の葉の数で初期化
sum_arr = [arr[-1]]*N
for i in range(1,N):
	# 深さi+1での頂点数 + 深さiでの葉の数
    sum_arr[i] = sum_arr[i-1]+arr[N-i]
# 本来の順番に反転
sum_arr = sum_arr[::-1]

# 二分木の根から見ていく
ans = [1]*(N+1)
for i in range(1,N+1):
    if ans[i-1]-arr[i-1] < 0:
        print(-1)
        exit()
    tmp = min((ans[i-1]-arr[i-1])*2,sum_arr[i-1])
    ans[i] = tmp

# for i in range(min(25,N+1)):
#     if ans[i] > 2**i:
#         print(-1)
#         exit()
# if ans[N] != arr[-1]:
#     print(-1)
#     exit()

print(sum(ans))

Submission status: Wrong Answer

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

def create_dth_vertex_limits_from_tail():
	r_a = list(reversed(a))
	limits = [[r_a[0],r_a[0]]]
	prev_leaf = r_a[0]
	for i in range(1, n):
		prevmin = limits[0][0]
		prevmax = limits[0][1]
		_min = int((prevmin + (prevmin%2)) / 2) + r_a[i]
		_max = prevmax + r_a[i]
		limits.insert(0, [_min, _max])
	return limits

def check_psblty(limits):
	if limits[0][0] <= 1 and limits[0][1] > 1:
		return True
	return False

def create_dth_branch_limit_from_top(tail_limits):
	branches = [1]
	for i in range(1, n):
		tmp = 2 * branches[i-1]
		if tmp > tail_limits[i][1]:
			tmp = tail_limits[i][1]
		branches.append(tmp - a[i])
	return branches

tail_limits = create_dth_vertex_limits_from_tail()
branch_limits = create_dth_branch_limit_from_top(tail_limits)
# print(tail_limits)
# print(branch_limits)
out_array = []
for i in range(n):
	out_array.append(branch_limits[i]+a[i])
out = sum(out_array)

if not check_psblty(tail_limits):
	out = -1

print(out)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
line_data = input()
data = list(map(lambda x: int(x), line_data.split(' ')))

if N == 0:
    if data[0] == 1:
        print(1)
    else:
        print(-1)
    sys.exit(0)

if N != len(data) - 1:
    print(-1)
    sys.exit(0)
    
tmp_sum = sum(data)
tmp_data = []
for i in data:
    tmp_sum -= i
    tmp_data.append(tmp_sum)
#print(tmp_data)

num = 1
prev_leaf = 1
for i, d in enumerate(data[:-1]):
    tmp = (prev_leaf - d) * 2
    top = tmp_data[i]
    #print("((prev:{}) - (d:{})) * 2 = {}".format(prev_leaf, d, tmp))
    #print("top = {}".format(top))
    if tmp <= 0:
        num = -1
        break
    if tmp < top:
        prev_leaf = tmp
        #print('add tmp = {}'.format(tmp))
    else:
        prev_leaf = top
        #print('add top = {}'.format(top))                                                   
    num += prev_leaf
    
print(num)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
line_data = input()
data = list(map(lambda x: int(x), line_data.split(' ')))

if N == 0:
    if data[0] == 1:
        print(1)
    else:
        print(-1)
    sys.exit(0)

if N != len(data) + 1:
    print(-1)
    sys.exit(0)
    
tmp_sum = sum(data)
tmp_data = []
for i in data:
    tmp_sum -= i
    tmp_data.append(tmp_sum)
#print(tmp_data)

num = 1
prev_leaf = 1
for i, d in enumerate(data[:-1]):
    tmp = (prev_leaf - d) * 2
    top = tmp_data[i]
    #print("((prev:{}) - (d:{})) * 2 = {}".format(prev_leaf, d, tmp))
    #print("top = {}".format(top))
    if tmp <= 0:
        num = -1
        break
    if tmp < top:
        prev_leaf = tmp
        #print('add tmp = {}'.format(tmp))
    else:
        prev_leaf = top
        #print('add top = {}'.format(top))                                                   
    num += prev_leaf
    
print(num)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
line_data = input()
data = list(map(lambda x: int(x), line_data.split(' ')))

if N == 0:
    if data[0] == 1:
        print(1)
    else:
        print(-1)
    sys.exit(0)

if N != len(data):
    print(-1)
    sys.exit(0)
tmp_sum = sum(data)
tmp_data = []
for i in data:
    tmp_sum -= i
    tmp_data.append(tmp_sum)

num = 1
prev_leaf = 1
for i, d in enumerate(data[:-1]):
    tmp = (prev_leaf - d) * 2
    top = tmp_data[i]
    if tmp <= 0:
        num = -1
        break
    if tmp < top:
        prev_leaf = tmp
    else:
        prev_leaf = top
    num += prev_leaf

print(num)

Submission status: Wrong Answer

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [1] * (N)
    B.append(0)
    sumA = sum(A)
    ans = 0

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

    for i in range(1,N):
        if B[i-1] <= 0:
            print(-1)
            return
        sumA -= A[i]
        B[i] = min(2 * B[i-1] - A[i], sumA)
        if B[i] <= 0:
            print(-1)
            return

    print(sum(A+B))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [1] * (N)
    B.append(0)
    sumA = sum(A)
    ans = 0

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

    for i in range(1,N):
        sumA -= A[i]
        B[i] = min(2 * B[i-1] - A[i], sumA)
        if B[i] <= 0:
            print(-1)
            return

    print(sum(A+B))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [1] * (N)
    B.append(0)
    sumA = sum(A)
    ans = 0

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

    for i in range(1,N):
        sumA -= A[i]
        B[i] = min(2 * B[i-1] - A[i], sumA)
        if B[i] < 0:
            print(-1)
            return

    print(sum(A+B))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
g = [1]
for i in range(n):
    g = g + [(g[-1]-a[i])*2]
print(g)
b = 0
t = 0
for i in range(n,-1,-1):
    if a[i]>g[i]:
        print(-1)
        break
    t = min(a[i]+t, g[i])
    b+=t
else:
  print(b)

Submission status: Wrong Answer

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [1] * (N)
    B.append(0)
    sumA = sum(A)
    ans = 0

    if N == 0 and A[0] != 1:
        print(-1)
        return
    
    for i in range(1,N):
        sumA -= A[i]
        B[i] = min(2 * B[i-1] - A[i], sumA)
        if B[i] < 0:
            print(-1)
            return

    print(sum(A+B))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [1] * (N)
    B.append(0)
    sumA = sum(A)
    ans = 0

    if N == 0 and A[0] != 1:
        print(-1)
        return
    
    for i in range(1,N):
        sumA -= A[i]
        B[i] = min(2 * B[i-1] - A[i], sumA)

    for i in range(N+1):
        ans += A[i] + B[i]
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

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

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

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

sums = [0]
branch1 = [0] * (N+1)
branch2 = [0] * (N+1)
branch1[0] = 1
branch2[-1] = A[-1]

flag = True

for i in range(N):
    branch1[i+1] = (branch1[i] - A[i])*2
    if branch1[i+1] < 1:
        flag = False
if pow(2, N) < A[-1]:
    flag = False

for i in range(N, 0, -1):
    branch2[i-1] = branch2[i]+A[i-1]


ans = 0
m = 1
for i in range(N+1):
    ansi = min(branch1[i], branch2[i])
    if m < ansi:
        flag = False
    ans += ansi
    m *= 2

# print(branch1)
# print(branch2)

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