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: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res


N=II()
AS=LI()
SM=sum(AS)
B=1
res=0
M = 1
m = 1

for a in AS:
    B = M-a
    if B < 0:
        print(-1)
        exit(0)
    res += a
    res += B
    SM -= a
    M = min(B*2, SM)
    m = B
print(res)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split());t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0:exit(print(-1))
  v+=w
print(v)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0:exit(print(-1))
  v+=w
print(v)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0:print(-1);exit()
  v+=w
print(v)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
t=sum(a);v=w=1
for q in a:
  w=min(2*(w-q),t:=t-q);(v:=v+w)
  if w<0:print(-1);exit()
print(v)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
t,v,w=sum(a),1,1
for q in a:
  w=min(2*(w-q),t:=t-q);(v:=v+w)
  if w<0:print(-1);exit()
print(v)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
t,v,w=sum(a),1,1
for q in a:
  w=min(2*(w-q),t:=t-q)
  v+=w
  if w<0:print(-1);exit()
print(v)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

n = int(rl())

li = list(map(int, rl().split()))
if n == 0 and li[0] == 1:
    print(1)
    exit()

can = [1-li[0]]

a = can[0]
for i in range(1, n+1):
    a = a*2
    can.append(a)
    a -= li[i]
    if a < 0:
        print(-1)
        exit()

ans = 0
can.reverse()
li.reverse()
temp = 0
for i in range(n+1):
    temp += li[i]
    ans += min(can[i], temp)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n=int(input())
a = list(map(int, input().split()))
if (a[0]==1 and n+1>1) or a[0]>1:
    print(-1)
    sys.exit()
if n==0 and a[0]==1:
    print(1)
    sys.exit()

su=[0]*(n+1)
for i in range(1,n+1)[::-1]:
    su[i-1]+=su[i]+a[i]
#print(su)
yo_next=min(2-a[0],su[0])
cnt=yo_next+1

for i in range(1,n):
    if yo_next-a[i]<1:
        print(-1)
        sys.exit()
    
    yo_next=min(su[i],(yo_next-a[i])*2)
    cnt+=yo_next
    #print(cnt,su[i+1],(yo_next-a[i])*2)
if yo_next<a[-1]:
    print(-1)
    sys.exit()
else:
    print(cnt)

Submission status: Accepted

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

from itertools import accumulate

copy = values[:]
copy.reverse()
acc = list(accumulate(copy))
acc.reverse()

b = 1
total = 1
for i in range(n+1):
    a = values[i]
    bCandidate = b - a
    if bCandidate < 0:
        print(-1)
        exit()
    b = min(2*bCandidate, acc[i] - a)
    total += b
print(total)

Submission status: Accepted

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

max_edge = []
for depth, a in enumerate(data):
    if depth == 0:
        edge = 1 - a
    else:
        edge = max_edge[depth-1]*2 - a
    
    if edge < 0:
        print(-1)
        exit()
    max_edge.append(edge)

ans = 0
prev_edges = 0
for idx in range(n, -1, -1):
    a = data[idx]
    cap = max_edge[idx]
    if prev_edges > 2*cap:
        print(-1)
        exit()
    edges = min(prev_edges, cap) + a
    ans += edges
    prev_edges = edges

print(ans)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
t,v=sum(a),[1]
for q in a:
  v+=[min(2*(v[-1]-q),t:=t-q)]
  if v[-1]<0:print(-1);exit()
print(sum(v))

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
t,v=sum(a),[1]
for q in a:
    v+=[min(2*(v[-1]-q),t:=t-q)]
    if v[-1]<0:print(-1);exit()
print(sum(v))

Submission status: Accepted

Solution code:
import numpy as np
import math
import collections

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


ans = 0
node_num = 1
pre_node_num = 1
B = [1 - A[0]]
ruisekiA = [0 for i in range(N + 2)]
ruisekiA[N] = A[N]
ruisekiA[N + 1] = 0
for i in range(N - 1, -1, -1):
    ruisekiA[i] = ruisekiA[i + 1] + A[i]


for i in range(1, N + 1):
    tmpB = min(2 * B[i - 1] - A[i], ruisekiA[i + 1])
    #print(tmpB, B[i - 1] - A[i])
    if (tmpB < 0) or (tmpB < B[i - 1] - A[i]):
        ans = -1
        break
    if i == N:
        tmpB = 0
    B.append(tmpB)

if N == 0 and A[0] != 1:
    ans = -1

if ans != -1:
    ans = sum(A) + sum(B)
print(ans)

Submission status: Accepted

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

if n == 0:
    if As[0] == 1: print(1)
    else: print(-1)
    exit()
    
# 下から見る
As_r = As[::-1]
p = As_r[0]
# とりうる最大値
a_pre = p
qs = [p]
# とりうる最小値
mn = As_r[0]

# 深さ n-1から0まで
# 最後の葉の数がA_N < 10**8、N<=10**5より、10**(8+5)以上の葉は生まれない。
# なので、高々50回くらいの2冪で上等
for i,a in enumerate(As_r[1:]):
    d = min(n - i - 1, 50)
    p = min(2**d, p + a)
    mn = (mn+1)//2 + a
    a_pre = a
    qs.append(p)

if mn != 1:
    print(-1)
    exit()

qs.reverse()
# print(qs,As)
ans = qs[0]
cnt = qs[0]
# 上から見る
for i in range(1,n+1):
    qs[i] = min(qs[i-1]*2, 2*(qs[i-1]-As[i-1]),qs[i])
print(sum(qs))

Submission status: Accepted

Solution code:
from itertools import accumulate
n=int(input())
a=list(map(int,input().split()))
c=list(accumulate(a))
b=[0]*(n+1)
#大きくしすぎてしまう場合がある
#いや上限を考えろや
def f():
    global n,a,b
    for i in range(n+1):
        if i==0:
            b[0]=min(c[n]-c[0],1)
        else:
            b[i]=min(2*(b[i-1]-a[i-1]),c[n]-c[i-1])

    if n==0:
        if a[0]!=1:
            print(-1)
        else:
            print(1)
    elif b[n]!=a[n]:
        print(-1)
    else:
        print(sum(b))
        #print(b)
f()

Submission status: Accepted

Solution code:
import sys
import itertools

ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())

N = ni()
A = nl()
assert len(A) == (N + 1)


def solve():
    ar = list(itertools.accumulate(A[::-1], initial=0))
    ar.reverse()
    assert len(ar) == (N + 2)
    if N == 0:
        return 1 if A[0] == 1 else -1
    if A[0] != 0:
        return -1
    inn = ans = 1
    for i in range(1, N + 1):
        b = 2 * inn - A[i]
        if b < 0:
            return -1
        inn = min(b, ar[i + 1])
        ans += inn + A[i]
    return ans


print(solve())

Submission status: Accepted

Solution code:
import sys
import itertools

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()
dbg = lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)

N = ni()
A = nl()
assert len(A) == (N + 1)


def solve():
    ar = list(itertools.accumulate(A[::-1]))
    ar.reverse()
    ar.append(0)
    assert len(ar) == (N + 2)
    if N == 0:
        return 1 if A[0] == 1 else -1
    if A[0] != 0:
        return -1
    inn = ans = 1
    for i in range(1, N + 1):
        b = 2 * inn - A[i]
        if b < 0:
            return -1
        inn = min(b, ar[i + 1])
        ans += inn + A[i]
    return ans


print(solve())

Submission status: Accepted

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

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

    if (mx <= 0 and i != n) or (mx < 0 and i == n):
        print(-1)
        exit()
    mx *= 2

a.reverse()
m.reverse()
m[0] = a[0]
for i in range(1, n+1):
    m[i] = min(m[i], m[i-1]) + a[i]

print(sum(m))

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
As  = list(map(int, input().split()))

# ノードが1個しかないとき
if n == 0:
    if As[0] == 1:print(1)
    else:print(-1)
    exit()
    
# 深さが2以上のとき、初め0ならアウト
if As[0] != 0:
    print(-1)
    exit()    

acc_r = list(accumulate(As[::-1]))
acc_r = acc_r[::-1]
# 一個ずれる
acc = acc_r[1:] + [acc_r[-1]]
p = 1
ans = 1
for s, a in zip(acc,As):
    p = min((p-a)*2, s)
    if p < 0:
        print(-1)
        exit()
    ans += p
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
s=sum(a)
if N==0:
    print(1 if a[0]==1 else -1)
    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: Accepted

Solution code:
from math import ceil
def solve():
    N = int(input())
    A = list(map(int,input().split()))

    mx = [0] * (N+1)
    mn = [0] * (N+1)

    mx[-1] = A[-1]
    mn[-1] = A[-1]

    for i in range(N-1,-1,-1):
        mx[i] = mx[i+1] + A[i]      
        mn[i] = ceil(mn[i+1]/2) + A[i]
    
    if not mn[0] <= 1 <= mx[0]:
        print(-1)
        return

    ans = 1
    now = 1
    piyo = [1]
    for i in range(1,N+1):
        nxt = (now-A[i-1]) * 2
        piyo.append(nxt)
        ans += min(mx[i],nxt)
        now = nxt

    print(ans)
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sum(a)
c=1
ans=1
if a[0]==1 and 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: Accepted

Solution code:
import math

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

up = [[] for _ in range(N+1)] # 葉から考慮した場合の、最小値
up[N] = [A[N],A[N]]
#print(up)
for i in reversed(range(N)):
    Min, Max = up[i+1]
    #print(Min,Max)
    Min_n = math.ceil(Min/2) + A[i]
    Max_n = Max + A[i]
    #print(A[i],i)
    up[i] = [Min_n, Max_n]
#print(up)

if up[0][0] >= 2:
    print(-1)
else:
    down = 1
    #print(down)
    ans = 1
    for i in range(1, N+1):
        down *= 2
        down = min(down,up[i][1]) - A[i]
        ans += down + A[i]
    print(ans)

Submission status: Accepted

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[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: Accepted

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: Accepted

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

for i in range(n,0,-1):
    x=(node2[i]+A[i-1])
    node2[i-1]=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: Accepted

Solution code:
from itertools import accumulate
N = int(input())
a = tuple(map(int,input().split()))
s = list(accumulate(a))
b = [0]*(N+1)
if N == 0 and a[0] > 1:
    print(-1)
    exit()
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: Accepted

Solution code:
import math
def solve():

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

    if(N == 0 and A[0] == 1):
        print(1)
        return
    
    leaf_list = [0] * (N+1)
    

    for d in range(N, -1 , -1):
        if(d == N):
            leaf_list[d] = (A[d],A[d])
        else:
            Min = math.ceil(leaf_list[d+1][0]/2) + A[d]
            Max = leaf_list[d+1][1] + A[d]
            leaf_list[d] = (Min,Max)
            
    if(not(leaf_list[0][0] <= 1 and leaf_list[0][1] >= 1)):
        print(-1)
        return
            
    node_list = [0] * (N+1)
    node_list[0] = 1
    
    for d in range(1, N+1):
        node_list[d] = min((node_list[d-1] - A[d-1]) * 2, leaf_list[d][1])
        
    print(sum(node_list))
solve()

Submission status: Accepted

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: Accepted

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)
    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: Accepted

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])
    if C[i] < A[i]:
        print(-1)
        exit()

#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])
print(sum(B))

Submission status: Accepted

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

ans = 0

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

# 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: Accepted

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)
    sys.exit()
elif a[0] > 1 and n == 0:
    print(-1)
    sys.exit()

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)
    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: Accepted

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

b = 1
B=[0]*(n+1)
count = 0

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

if n == 0 and A[0] > 1:
    count += 1

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

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

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

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

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    rem = sum(A)
    cur = 1
    ret = 0
    for a in A:
        cur = min(rem, cur)
        rem -= a
        ret += cur
        cur = 2*(cur-a)
        if cur < 0:
            ret = -1
            break

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
import sys
import math

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    mi = [A[-1]]
    ma = [A[-1]]
    for i in reversed(range(n)):
        mi.append(math.ceil(mi[-1] / 2) + A[i])
        ma.append(ma[-1] + A[i])

    mi = mi[::-1]
    ma = ma[::-1]

    res = []
    for i in range(n + 1):
        if i == 0:
            if mi[i] <= 1 <= ma[i]:
                res.append(1)
                continue
            else:
                break

        if mi[i] <= (res[-1] - A[i - 1]) * 2 <= ma[i]:
            res.append((res[-1] - A[i - 1]) * 2)
        else:
            res.append(ma[i])

    print(sum(res) if len(res) != 0 else -1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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: Accepted

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:
    if nodes[n] < nodes_min[n]:
        print(-1)
    else:
        print(sum(nodes))

Submission status: Accepted

Solution code:
import sys
import math
n = int(input())
A = list(map(int, input().split()))
NODE_RANGE = [0 for i in range(n+1)]
NODE_RANGE[n] = [A[n], A[n]]
NODE_MAX = [0 for i in range(n+1)]
NODE_MAX[0]=1
# d=nから見ていって、各dに対するノードの最小値、最大値を求める
for i in range(n-1, -1, -1):
    node_min = math.ceil( NODE_RANGE[i+1][0]/2 ) + A[i]
    node_max = NODE_RANGE[i+1][1] + A[i]
    NODE_RANGE[i]=[node_min, node_max]

if NODE_RANGE[0][0] > 1 or 1 > NODE_RANGE[0][1]: # d=0の時のノード数は1
    print(-1)
    sys.exit()

# print(NODE_RANGE)
# d=0から最大ノード数を確定させていく
for i in range(1, n+1):
    NODE_MAX[i] = min((NODE_MAX[i-1]-A[i-1])*2, NODE_RANGE[i][1])
    # print(NODE_MAX[i-1] + A[i], NODE_RANGE[i][1])
# print(NODE_MAX)
print(sum(NODE_MAX))

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    if 0 < A[0]:
        return '1' if n == 0 and A[0] == 1 else '-1'

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

    prev = 0
    ret = 0
    for i in range(n, -1, -1):
        if R[i] < A[i]:
            ret = -1
            break

        prev = min(R[i], A[i]+prev)
        ret += prev

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
#全体的な方針
#浅いほうから貪欲に頂点を倍化していく
#現在見ている段の頂点数がそれより深い段の葉の数を超えると余ってしまう
#よって、minで押さえつける必要がある(累積和で高速化が必要)


#累積和の定義
def Csum(a):
    b,c=[],0
    for i in range(len(a)):
        c+=a[i]
        b.append(c)
    return b

#n:二分木の深さ
#a:それぞれの段数の葉の数
#s:aの累積和をとったもの(その深さよりも浅い葉の数)
#su:aの総和(全体の葉の数)
#b:現在の深さの頂点数
#c:現在までの頂点数

n=int(input())
a=list(map(int,input().split()))
s,su,b,c=Csum(a),sum(a),1,0
for i in range(n+1):
    #頂点数カウントに現在の段を加算
    #葉の数だけ親の候補を減らしておく
    c+=b
    b-=a[i]
    #最後まで頂点を使い切ったならcを出力
    #途中で頂点が足りなくなったら-1を出力
    if b<=0:
        if i==n and b==0:
            print(c)
        else:
            print(-1)
        break
    #次の段の頂点数の更新
    #iより深い葉の数(su-s[i])を超えないようにする
    b=min(b*2,su-s[i])

Submission status: Accepted

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:
    if N == 0:
        print(1)
        exit()
    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: Accepted

Solution code:
def main():
    n = int(input().strip())
    L = list(map(int, input().strip().split()))
    
    rem=sum(L)
    cur=1
    ans=0
    for i in range(n+1):
        ans+=cur
        rem-=L[i]
        cur-=L[i]
        if cur<0 or cur==0 and i!=n:
            print(-1)
            return
        if cur<rem:
            cur=min(cur*2,rem)
            
    print(ans)

if '__main__' == __name__:
    main()

Submission status: Accepted

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 N > 0 and As[0] != 0:
        return -1
    if N == 0 and As[0] != 1:
        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: Accepted

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 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: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n = ni()
    a = nl()
    ok = -1
    ng = 10**18
    ans = -1
    while ng - ok > 1:
        v = mid = (ok + ng) // 2
        c = 0
        cnt = 0
        for x in a[:0:-1]:
            cnt += c + x
            c += x
            d = (c - 1) // 2 + 1
            if v > c - d:
                v -= c - d
                d = c
            elif v > 0:
                d += v
                v = 0
            c = d
        if a[0] + c > 1:
            ng = mid
        else:
            ok = mid
            ans = cnt + 1
    print(ans)
    return

solve()

Submission status: Accepted

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: Accepted

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 <= nodes_range[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: Accepted

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) or (leafNums[0] > 1 and n == 0):
    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: Accepted

Solution code:
N,*A = map(int, open(0).read().split())
ans = 0
temp = 0


limit = [0] * (N+1)
if N == 0:
    if A[0] == 1:
        print('1')
    else:
        print('-1')
else:
    if A[0] != 0:
        print('-1')
    else:
        limit[0] = 1
        for i in range(1,N+1):
            limit[i] = (limit[i-1]*2) - A[i]
            if limit[i] < 0:
                print('-1')
                break
            elif limit[i] == 0:
                if i < N:
                    print('-1')
                    break
        else:
            for i in range(N+1):
                if i == 0:
                    temp = A[N]
                    ans += temp
                    lower = temp
                elif i < N:
                    temp = min(lower,limit[N-i]) + A[N-i]
                    ans += temp
                    lower = temp
                else:
                    ans += 1
            else:
                print(ans)

Submission status: Accepted

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