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()))
s=sum(a)
if N==0:
    print('Yes' if a[0]==1 else 'No')
    exit()
lim=1
ans=0
for i in range(N+1):
    ans+=lim
    lim-=a[i]
    s-=a[i]
    if lim<0:
        print(-1)
        exit()
    elif lim==0 and s>0:
        print(-1)
        exit()
    lim*=2
    lim=min(lim,s)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
s=sum(a)
if N==0:
    print('Yes' if a[0]==1 else 'No')
    exit()
lim=1
ans=0
for i in range(N+1):
    ans+=lim
    if lim-a[i]<0:
        print(-1)
        exit()
    lim=(lim-a[i])*2
    s-=a[i]
    lim=min(lim,s)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
if A[0]>0:
    print(-1)
    exit()
if A[-1]>2**n:
    print(-1)
    exit()
node1=[0]*(n+1)
node1[0]=1
node2=[0]*(n+1)
node2[-1]=A[-1]
for i in range(n):
    x=(node1[i]-A[i])*2
    if x<1:
        print(-1)
        exit()
    node1[i+1]=x
#print(node1)
for i in range(n-1,-1,-1):
    x=(node2[i+1]+A[i])
    node2[i]=x
ans=[]

for i in range(n+1):
    x=min(node1[i],node2[i])
    if x<A[i]:
        print(-1)
        exit()
    ans.append(x)
print(sum(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
if A[0]>0:
    print(-1)
    exit()
if A[-1]>2**n:
    print(-1)
    exit()
node1=[0]*(n+1)
node1[0]=1
node2=[0]*(n+1)
node2[-1]=A[-1]
for i in range(n):
    x=(node1[i]-A[i])*2
    if x<1:
        print(-1)
        exit()
    node1[i+1]=x
#print(node1)
for i in range(n-1,-1,-1):
    x=(node2[i+1]+A[i])
    node2[i]=x
ans=[]

for i in range(n+1):
    ans.append(min(node1[i],node2[i]))
print(sum(ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
f=[1]*(N+1)
las=A[N]
g=[las]*(N+1)
flag=1
for i in range(0,N):
    f[i+1]=2*(f[i]-A[i])
for i in range(N,0,-1):
    g[i-1]=g[i]+A[i-1]
print(f,g)
for i in range(N+1):
    if min(f[i],g[i])<=0:
        flag=0
        break
    ans=ans+min(f[i],g[i])
if g[N]>f[N]:
    flag=0
if flag==0:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
N = int(input())
a = tuple(map(int,input().split()))
s = list(accumulate(a))
b = [0]*(N+1)
if a[0] == 0:
    b[0] = 1
ans = 1
flag = 0
for d in range(1,N+1):
    b[d] = b[d-1]-a[d]
    tmp = min(s[-1]-s[d],2*b[d-1]-a[d])
    if b[d] > tmp or tmp < 0:
        flag = 1
        break
    else:
        b[d] = tmp
if flag:
    print(-1)
else:
    print(s[-1]+sum(b))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
f=[1]*(N+1)
las=A[N]
g=[las]*(N+1)
flag=1
for i in range(0,N):
    f[i+1]=2*(f[i]-A[i])
for i in range(N,0,-1):
    g[i-1]=g[i]+A[i-1]
#print(f,g)
for i in range(N+1):
    if min(f[i],g[i])<=0:
        flag=0
        break
    ans=ans+min(f[i],g[i])
if flag==0:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=sum(a)
c=1
ans=1
if a[0]>0 and n>0:
    print(-1)
    exit()
for i in a[1:]:
    b-=i
    c=min(c*2-i,b)
    ans+=c
    if c<0:
        print(-1)
        exit()
print(ans+sum(a))

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 -1)
    exit()
if A[-1]>2**n:
    print(-1)
    exit()
node1=[0]*(n+1)
node1[0]=1
node2=[0]*(n+1)
node2[-1]=A[-1]
for i in range(n):
    x=(node1[i]-A[i])*2
    if x<1:
        print(-1)
        exit()
    node1[i+1]=x
#print(node1)

for i in range(n-1,-1,-1):
    x=(node2[i+1]+A[i])
    if i!=0 and x<A[i+1]:
        print(-1)
        exit()
    node2[i]=x
ans=[]

for i in range(n+1):
    ans.append(min(node1[i],node2[i]))
print(sum(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A_leaf = list(map(int, input().split()))
if N == 0:
    print(1 if A_leaf[0] == 1 else -1)
    exit()
s = [0]*(N+2)
for i in range(1, N+2):
    s[i] = s[i-1] + A_leaf[i-1]
node = [1]*(N+1)
for i in range(1, N+1):
    node[i] = min((node[i-1] - A_leaf[i-1])*2, s[N+1]-s[i])
    if node[i] <= A_leaf[i]:
        print(-1)
        exit()
else:
    print(sum(node))

Submission status: Wrong Answer

Solution code:
N = int(input())
A_leaf = list(map(int, input().split()))
if N == 0:
    print(1 if A_leaf[0] == 1 else -1)
    exit()
s = [0]*(N+2)
for i in range(1, N+2):
    s[i] = s[i-1] + A_leaf[i-1]
node = [1]*(N+1)
for i in range(1, N+1):
    node[i] = min((node[i-1] - A_leaf[i-1])*2, s[N+1]-s[i])
    if node[i] <= 0:
        print(-1)
        exit()
else:
    print(sum(node))

Submission status: Wrong Answer

Solution code:
N = int(input())
A_leaf = list(map(int, input().split()))
if N == 0 and A_leaf[0] == 0:
    print(-1)
    exit()
s = [0]*(N+2)
for i in range(1, N+2):
    s[i] = s[i-1] + A_leaf[i-1]
node = [1]*(N+1)
for i in range(1, N+1):
    node[i] = min((node[i-1] - A_leaf[i-1])*2, s[N+1]-s[i])
    if node[i] <= 0:
        print(-1)
        exit()
else:
    print(sum(node))

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=sum(a)
c=1
ans=1
if a[0]==1 and n==0:
    print(1)
if a[0]>0:
    print(-1)
    exit()
for i in a[1:]:
    b-=i
    c=min(c*2-i,b)
    ans+=c
    if c<0:
        print(-1)
        exit()
print(ans+sum(a))

Submission status: Wrong Answer

Solution code:
N = int(input())
A_leaf = list(map(int, input().split()))
s = [0]*(N+2)
for i in range(1, N+2):
    s[i] = s[i-1] + A_leaf[i-1]
node = [1]*(N+1)
for i in range(1, N+1):
    node[i] = min((node[i-1] - A_leaf[i-1])*2, s[N+1]-s[i])
    if node[i] <= 0:
        print(-1)
        break
else:
    print(sum(node))

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=sum(a)
c=1
ans=1
if a[0]>0 or n==0:
    print(-1)
    exit()
for i in a[1:]:
    b-=i
    c=min(c*2-i,b)
    ans+=c
    if c<0:
        print(-1)
        exit()
print(ans+sum(a))

Submission status: Wrong Answer

Solution code:
N = int(input())
A_leaf = list(map(int, input().split()))
s = [0]*(N+2)
for i in range(1, N+2):
    s[i] = s[i-1] + A_leaf[i-1]
node = [1]*(N+1)
for i in range(1, N+1):
    node[i] = min(node[i-1] - A_leaf[i-1], (s[N+1]-s[i]) / 2)*2
    if node[i] <= 0:
        print(-1)
        break
else:
    print(int(sum(node)))

Submission status: Wrong Answer

Solution code:

n,*a=map(int,open(0).read().split())
b=sum(a)
c=1
ans=1
if a[0]>0:
    print(-1)
    exit()
if n==0:
    print(1)
    exit()    
for i in a[1:]:
    b-=i
    c=min(c*2-i,b)
    ans+=c
    if c<0:
        print(-1)
        exit()
print(ans+sum(a))

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=sum(a)
c=1
ans=1
if n==0:
    print(1)
    exit()
if a[0]>0:
    print(-1)
    exit()
for i in a[1:]:
    b-=i
    c=min(c*2-i,b)
    ans+=c
    if c<0:
        print(-1)
        exit()
print(ans+sum(a))

Submission status: Wrong Answer

Solution code:
N = int(input())
A_leaf = list(map(int, input().split()))
s = [0]*(N+2)
for i in range(1, N+2):
    s[i] = s[i-1] + A_leaf[i-1]
node = [1]*(N+1)
for i in range(1, N+1):
    up = node[i-1] - A_leaf[i-1]
    down = s[N+1]-s[i]
    if up > down:
        node[i] = down
    else:
        node[i] = min(up*2, down)
    if node[i] <= 0:
        print(-1)
        break
else:
    print(sum(node))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [0]*(N+1)

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [0]*(N+1)

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [0]*(N+1)

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

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

Submission status: Wrong Answer

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

ans = 0

# node_list_1 は深いところから見たNode数の最大値
# node_list_2 は根から見たNode数の最大値
node_list_1 = [0] * (n + 1)
node_list_2 = [0] * (n + 1)

node_list_1[n] = a[n]
node_list_2[0] = 1

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

for j in range(1, n+1):
    node_list_2[j] = (node_list_2[j-1] - a[j-1]) * 2
    if node_list_2[j] < a[j]:
        print(-1)
        exit()

for k in range(n+1):
    ans += min(node_list_1[k], node_list_2[k])

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = [0]*(N+1)

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

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

Submission status: Wrong Answer

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

ans = 0

# node_list_1 は深いところから見たNode数の最大値
# node_list_2 は根から見たNode数の最大値
node_list_1 = [0] * (n + 1)
node_list_2 = [0] * (n + 1)

node_list_1[n] = a[n]
node_list_2[0] = 1

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

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

for k in range(n+1):
    ans += min(node_list_1[k], node_list_2[k])

print(ans)

Submission status: Wrong Answer

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

max_edge_num = pow(2,n)

if a[0] > 0 and n>0:
    print(-1)
    sys.exit()
if a[0] == 1 and n==0:
    print(1)
elif a[0] > 1 and n == 0:
  print(-1)
    
answer = 1
total_lost = 0
remained_alls = [1]

for depth in range(1,n+1):
    total_lost *= 2
    full_nodes = pow(2,depth)
    remained_nodes = full_nodes - total_lost
    remained_alls.append(remained_nodes)
    answer += remained_nodes
    if a[depth] > remained_nodes:
        print(-1)
        sys.exit()
    else:
        total_lost += a[depth]

max_nodes_all = [a[n]]

for depth in range(n-1,0,-1):
    possible = max_nodes_all[-1]
    now = min(possible+a[depth],remained_alls[depth])
    max_nodes_all.append(now)

max_nodes_all.append(1)

answer = 0
for nodes in max_nodes_all:
    answer+=nodes

print(answer)

Submission status: Wrong Answer

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

ans = 0

# node_list_1 は深いところから見たNode数の最大値
# node_list_2 は根から見たNode数の最大値
node_list_1 = [0] * (n + 1)
node_list_2 = [0] * (n + 1)

node_list_1[n] = a[n]
node_list_2[0] = 1

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

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

if node_list_2[-1] <= 0:
    print(-1)
    exit()

for k in range(n+1):
    ans += min(node_list_1[k], node_list_2[k])

print(ans)

Submission status: Wrong Answer

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

max_edge_num = pow(2,n)

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

answer = 1
total_lost = 0
remained_alls = [1]

for depth in range(1,n+1):
    total_lost *= 2
    full_nodes = pow(2,depth)
    remained_nodes = full_nodes - total_lost
    remained_alls.append(remained_nodes)
    answer += remained_nodes
    if a[depth] > remained_nodes:
        print(-1)
        sys.exit()
    else:
        total_lost += a[depth]

max_nodes_all = [a[n]]

for depth in range(n-1,0,-1):
    possible = max_nodes_all[-1]
    now = min(possible+a[depth],remained_alls[depth])
    max_nodes_all.append(now)

max_nodes_all.append(1)

answer = 0
for nodes in max_nodes_all:
    answer+=nodes

print(answer)

Submission status: Wrong Answer

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

max_edge_num = pow(2,n)

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

answer = 1
total_lost = 0
remained_alls = [1]

for depth in range(1,n+1):
    total_lost *= 2
    full_nodes = pow(2,depth)
    remained_nodes = full_nodes - total_lost
    remained_alls.append(remained_nodes)
    answer += remained_nodes
    if a[depth] > remained_nodes:
        print(-1)
        sys.exit()
    else:
        total_lost += a[depth]

max_nodes_all = [a[n]]

for depth in range(n-1,0,-1):
    possible = max_nodes_all[-1]
    now = min(possible+a[depth],remained_alls[depth])
    max_nodes_all.append(now)

max_nodes_all.append(1)

answer = 0
for nodes in max_nodes_all:
    answer+=nodes

print(answer)

Submission status: Wrong Answer

Solution code:
from sys import stdin

a=int(stdin.readline())
A=stdin.readline().split()
sum=0
for k in range(0,a+1):
    sum+=int(A[k])

sum-=int(A[a])
ver=1
lay=1
K=0
T=0

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

for l in range(0,a):
    if lay-int(A[l])<=0:
        print(-1)
        K=1
        break
    if (lay-int(A[l]))*2<int(A[a]) and l==(a-1):
        print(-1)
        K=1
        break
    if (lay-int(A[l]))*2-sum+int(A[l])<=int(A[a]):
        lay=(lay-int(A[l]))*2
        ver+=lay
        sum-=int(A[l])
        T=l
    else:
        lay-=int(A[l])
        sum-=int(A[l])
        x=lay-sum-int(A[a])
        if x==0:
           ver+=lay
        elif x>0:
            print(-1)
            K=1
        else:
           lay=sum+int(A[a])
           ver+=lay
        T=l
        break

if K==0:
    for u in range(T+1,a):
        lay -= int(A[u])
        sum -= int(A[u])
        ver+=lay

if K==0:
    print(ver)

Submission status: Wrong Answer

Solution code:
import sys,collections
sys.setrecursionlimit(100000)
N = int(sys.stdin.readline())
LEAVES = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
ret = 0
t = 0
com = []
for l in LEAVES[::-1]:
    t = l + t
    com.append(t)
com.reverse()

def dfs(l=0,parentB=0,t=[]):
    global ret
    lo = parentB-LEAVES[l]
    hi = 2*parentB-LEAVES[l]
    if l == 0:
        lo = 0
        hi = 1
    if parentB > com[l] or 2*parentB-LEAVES[l] < 0:
        return False
    if l == N and lo <= 0 and 0 <= hi:
        t.append(LEAVES[l])
        ret = max(ret,sum(t))
        return ret
    elif l == N:
        return False
    for p in range(lo,hi+1)[::-1]:
        if dfs(l+1,p,t+[p+LEAVES[l]]):
            return True
    return False
dfs()
if ret==0:
    print(-1)
    exit()
print(ret)

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 nodes[depth] < nodes_min[depth]:
        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())
A = list(map(int, input().split()))
 
def solve(N, A):
  
  t = A[-1]
  par = 1 - A[0]
  rt = 1
  for i, a in enumerate(A[1:]):
    max_node = par * 2
    cur = max_node - a
    cur = min(t, cur)
    if cur < 0:
      print(-1)
      return
    #print(i, N, a, cur)
    rt += a
    if i + 1 < N:
      rt += cur
    par = cur  
   
  print(rt)
  
solve(N, A)

Submission status: Wrong Answer

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

b = 1
B=[0]*(n+1)
count = 0
for i in range(n):
    B[i] = b
    if 2*(b - A[i]) < A[i+1]:
        count += 1
        break
    b = 2*(b - A[i])
B[n] = b

j = 0
while count == 0 and A[n] > B[j]:
    if j == n:
        break
    j += 1

total = 0
for i in range(j):
    total += B[i]

s = A[n]
for i in range(n-1,j-1,-1):
    total += min(B[i],s+A[i])
    s+=A[i]

if count==0:
    print(total+A[n])
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

n=int(input())
a=list(map(int,input().split()))
#print(a)

b=[]
for i in range(n+1):
    if i==0:
        if a[i]>0 and n>0:
            print(-1)
            exit()
        b.append(1)
    else:
        if b[i-1]-a[i-1]<0:
            print(-1)
#            print(-2)
            exit()
        b.append((b[i-1]-a[i-1])*2)
#b.append(a[n])
#print(b)

c=[]
for i in range(n):
    if i==0:
        c.append(a[n])
    else:
        c.append(c[i-1]+a[n-i])
c.append(1)
#print(c)

ans=0
for i in range(n+1):
#    print(min(b[i],c[n-i]))
    ans+=min(b[i],c[n-i])
print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=sum(a)
c=1
ans=1
b-=a[0]
if a[0]>0:
    print(-1)
    exit()
for i in a[1:]:
    b-=i
    c=min(c*2-i,b)
    ans+=c
    if c<0:
        print(-1)
        exit()
print(ans+sum(a))

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=sum(a)
c=1
ans=1
b-=a[0]
if a[0]>0:
    print(-1)
    exit()
for i in a[1:]:
    b-=i
    c=min(c*2-i,b)
    ans+=c
    if c<0:
        print(-1)
        exit()
    print(c)    
print(ans+sum(a))

Submission status: Wrong Answer

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

# 上限を決める
NowNode = 2**0
NextNode = (NowNode - A[0])*2
UpperLimit = [0] * (N+1)
UpperLimit[0] = 1
if A[0] == 1:
    print(-1)
    exit()
for d in range(1, N+1, 1):
    NowNode = NextNode
    NextNode = (NowNode - A[d]) * 2
    UpperLimit[d] = NowNode
# print(UpperLimit)
UpperLimit[-1] = min(A[-1], UpperLimit[-1])
# 下から見ていく
NowNode = A[-1]
ans = 0

for d in range(N, -1, -1):
    PrevNode = NowNode
    if UpperLimit[d] < A[d]:
        print(-1)
        exit()
    if NowNode + A[d] <= UpperLimit[d]:
        NowNode += A[d]
    else:
        NowNode = UpperLimit[d]
    ans += NowNode
    # print(d, NowNode)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

n=int(input())
a=list(map(int,input().split()))
#print(a)

b=[]
for i in range(n+1):
    if i==0:
        if a[i]>0:
            print(-1)
            exit()
        b.append(1)
    else:
        if b[i-1]-a[i-1]<0:
            print(-1)
            exit()
        b.append((b[i-1]-a[i-1])*2)
#b.append(a[n])
#print(b)

c=[]
for i in range(n):
    if i==0:
        c.append(a[n])
    else:
        c.append(c[i-1]+a[n-i])
c.append(1)
#print(c)

ans=0
for i in range(n+1):
#    print(min(b[i],c[n-i]))
    ans+=min(b[i],c[n-i])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
s = [0] * (N + 2)
for i in range(N + 1):
    s[i + 1] = s[i] + A[i]
node, leaf = 1, 1
for d in range(1, N + 1):
    if leaf < A[d]:
        print(-1)
        break
    leaf = min((leaf - A[d - 1]) * 2, s[N + 1] - s[d])
    if leaf < A[d]:
        print(-1)
        break
    node += leaf
else:
    print(node)

Submission status: Wrong Answer

Solution code:
import math


def main():
    depth = int(input())
    leaves = [int(x) for x in input().split()]

    nodes_range = [None] * (depth + 1)
    for i in range(depth, -1, -1):
        if i == depth:
            nodes_range[i] = (leaves[i], leaves[i])
            continue
        # 枝をなるべくまとめていく。
        min_nodes = math.ceil(nodes_range[i + 1][0] / 2) + leaves[i]
        # 枝が結合せず，平行に遡る感じ。
        max_nodes = nodes_range[i + 1][1] + leaves[i]
        nodes_range[i] = (min_nodes, max_nodes)

    if not nodes_range[0][0] != 1:
        # 根が1を取り得ない場合は実現不可能。
        print(-1)
        return

    max_noded_tree = [0] * (depth + 1)
    for i in range(depth + 1):
        if i == 0:
            max_noded_tree[i] = 1
            continue
        max_noded_tree[i] = min(
            (max_noded_tree[i - 1] - leaves[i - 1]) * 2,
            nodes_range[i][1])
    print(sum(max_noded_tree))
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# 上限を決める
NowNode = 2**0
NextNode = (NowNode - A[0])*2
UpperLimit = [0] * (N+1)
UpperLimit[0] = 1
if A[0] == 1:
    print(-1)
    exit()
for d in range(1, N+1, 1):
    NowNode = NextNode
    NextNode = (NowNode - A[d]) * 2
    UpperLimit[d] = NowNode
UpperLimit[-1] = A[-1]
# print(UpperLimit)

# 下から見ていく
NowNode = A[-1]
ans = NowNode

for d in range(N-1, -1, -1):
    PrevNode = NowNode
    if UpperLimit[d] < A[d]:
        print(-1)
        exit()
    if NowNode + A[d] <= UpperLimit[d]:
        NowNode += A[d]
    else:
        NowNode = UpperLimit[d]
    ans += NowNode
    # print(d, NowNode)
print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())
    As = list(map(int, input().split()))

    if As[0] > 0 and N > 0:
        return -1

    vertices = [1] * (N+1)
    previous = 0
    for i, a in enumerate(As[:0:-1]):
        max_n_vert = a + previous
        previous = max_n_vert
        vertices[N-i] = max_n_vert

    n_not_leaves_prev = 1
    for i, a in enumerate(As):
        if i == 0:
            continue
        # if n_not_leaves_prev == 0:
        #     return -1

        max_n_vert = 2 * n_not_leaves_prev
        vertices[i] = min(vertices[i], max_n_vert)
        n_not_leaves_prev = vertices[i] - a

        if max_n_vert < a:
            return -1

    return sum(vertices)


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
s = [0]*(N+2)
for i in range(N + 1):
    s[i+1] = s[i] + A[i]
node, leaf = 1, 1
for d in range(1, N+1):
    leaf = min((leaf - A[d - 1]) * 2, s[N + 1] - s[d])
    if leaf < A[d]:
        print(-1)
        break
    node += leaf
else:
    print(node)

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A=map(int,read().split())

bound = [0]*(N+1)
bound[0] = 1
#Nが0のとき
if N == 0:
  if A[0] == 1:
    print(1)
  else:
    print(-1)
  sys.exit()
  
#Nが0以外のとき 
#上から
for i in range(1,N+1):
  bound[i] = (bound[i-1]-A[i-1]) *2
  if bound[i] <= A[i]:
    print(-1)
    sys.exit()
    
#下からのと最小値を取る
cum_sum = 0 
for i in range(N,-1,-1):
  cum_sum += A[i]
  bound[i] = min(bound[i],cum_sum)
print(sum(bound))

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:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())
    As = list(map(int, input().split()))

    if As[0] > 0:
        return -1

    vertices = [1] * (N+1)
    previous = 0
    for i, a in enumerate(As[:0:-1]):
        max_n_vert = a + previous
        previous = max_n_vert
        vertices[N-i] = max_n_vert

    n_not_leaves_prev = 1
    for i, a in enumerate(As):
        if i == 0:
            continue
        if n_not_leaves_prev == 0:
            return -1

        max_n_vert = 2 * n_not_leaves_prev
        vertices[i] = min(vertices[i], max_n_vert)
        n_not_leaves_prev = vertices[i] - a

        if max_n_vert < a:
            return -1

    return sum(vertices)


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A=map(int,read().split())

bound = [0]*(N+1)
bound[0] = 1
#Nが0のとき
if N == 0:
  if A[0] == 1:
    print(1)
  else:
    print(-1)
  sys.exit()
  
#Nが0以外のとき 
#上から
for i in range(1,N+1):
  bound[i] = (bound[i-1]-A[i-1]) *2
  if bound[i] <= 0:
    print(-1)
    sys.exit()
    
#下からのと最小値を取る
cum_sum = 0 
for i in range(N,-1,-1):
  cum_sum += A[i]
  bound[i] = min(bound[i],cum_sum)
print(sum(bound))

Submission status: Wrong Answer

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())
    As = list(map(int, input().split()))

    if As[0] > 0:
        return -1

    vertices = [1] * (N+1)
    previous = 0
    for i, a in enumerate(As[:0:-1]):
        max_n_vert = a + previous
        previous = max_n_vert
        vertices[N-i] = max_n_vert

    n_not_leaves_prev = 1
    for i, a in enumerate(As):
        if i == 0:
            continue
        max_n_vert = 2 * n_not_leaves_prev
        vertices[i] = min(vertices[i], max_n_vert)
        n_not_leaves_prev = vertices[i] - a

        if max_n_vert < a:
            return -1

        if max_n_vert == 0:
            return -1

    return sum(vertices)


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A=map(int,read().split())

bound = [0]*(N+1)
bound[0] = 1
#Nが0のとき
if N == 0:
  if A[0] == 1:
    print(1)
  else:
    print(-1)
  sys.exit()
#Nが0以外のとき 
#上から
for i in range(1,N+1):
  bound[i] = (bound[i-1]-A[i-1]) *2
  if bound[i] <= 0:
    print(-1)
    sys.exit()
print(bound)
cum_sum = 0 
#下からのと最小値を取る
for i in range(N,-1,-1):
  cum_sum += A[i]
  bound[i] = min(bound[i],cum_sum)
print(sum(bound))

Submission status: Wrong Answer

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())
    As = list(map(int, input().split()))

    if As[0] > 0:
        return -1

    vertices = [1] * (N+1)
    previous = 0
    for i, a in enumerate(As[:0:-1]):
        max_n_vert = a + previous
        previous = max_n_vert
        vertices[N-i] = max_n_vert

    n_not_leaves_prev = 1
    for i, a in enumerate(As):
        if i == 0:
            continue
        max_n_vert = 2 * n_not_leaves_prev
        vertices[i] = min(vertices[i], max_n_vert)
        n_not_leaves_prev = vertices[i] - a

        if max_n_vert <= a and i != N:
            return -1

    return sum(vertices)


def main():
    print(solve())


if __name__ == "__main__":
    main()

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:
  if A[0]==1:
    print(-1)
    exit()
  else:
    ans=0
    for k in rg:
      ans += k[1]
    print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())
    As = list(map(int, input().split()))

    if As[0] > 0:
        return -1

    vertices = [1] * (N+1)
    previous = 0
    for i, a in enumerate(As[:0:-1]):
        max_n_vert = a + previous
        previous = max_n_vert
        vertices[N-i] = max_n_vert

    n_not_leaves_prev = 1
    for i, a in enumerate(As):
        if i == 0:
            continue
        max_n_vert = 2 * n_not_leaves_prev
        vertices[i] = min(vertices[i], max_n_vert)
        n_not_leaves_prev = vertices[i] - a

        if max_n_vert < a:
            return -1

    return sum(vertices)


def main():
    print(solve())


if __name__ == "__main__":
    main()