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:
*a,=map(int,[*open(0)][1].split())
c=sum(a)
s=b=1
for a in a:c-=a;b=min(c,b-a<<1);s+=b
print(max(-1,s))

Submission status: Accepted

Solution code:
c=sum(a:=[*map(int,[*open(0)][1].split())])
s=b=1
for a in a:b=min(c:=c-a,b-a<<1);s+=b
print(max(-1,s))

Submission status: Accepted

Solution code:
*a,=map(int,[*open(0)][1].split())
c=sum(a)
s=b=1
for a in a:c-=a;b=min(c,(b-a)*2);s+=b
print(max(-1,s))

Submission status: Accepted

Solution code:
c=sum(a:=[*map(int,[*open(0)][1].split())])
s=b=1
for a in a:b=min(c:=c-a,(b-a)*2);s+=b
print(max(-1,s))

Submission status: Accepted

Solution code:
c=sum(a:=[*map(int,[*open(0)][1].split())])
s=b=1
for a in a:b=min(c:=c-a,2*(b-a));s+=b
print(-(s<0)or s)

Submission status: Accepted

Solution code:
c=sum(a:=[*map(int,[*open(s:=0)][1].split())])
b=1
for a in a:s=-(b<a)or s+b;b=min(c:=c-a,(b-a)*2)
print(s)

Submission status: Accepted

Solution code:
*a,=map(int,[*open(s:=0)][1].split())
c=sum(a)
b=1
for a in a:
  if b<a:
    s=-1
    break
  s+=b
  c-=a
  b=min(c,(b-a)*2)
print(s)

Submission status: Accepted

Solution code:
*a,=map(int,[*open(0)][1].split())
c=[s:=0]
for i in a[:0:-1]:c+=c[-1]+i,
b=1
for a in a:
  if b<a:
    s=-1
    break
  s+=b
  b=min(c.pop(),(b-a)*2)
print(s)

Submission status: Accepted

Solution code:
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


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

    l = [0]*(n+1)
    l[n] = (A[n], A[n])
    for i in reversed(range(1, n+1)):
        l[i-1] = (max(math.ceil(l[i][0]/2)+A[i-1], 1), l[i][1]+A[i-1])

    if 1 not in range(l[0][0], l[0][1]+1):
        print(-1)
    else:
        ans = [0]*(n+1)
        ans[0] = 1
        cnt = 1
        for i in range(n):
            ans[i+1] = min((ans[i]-A[i])*2, l[i+1][1])
        print(sum(ans))


resolve()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n==0:
  if a[0]==1:
    print(1)
    exit()
  else:
    print(-1)
    exit()
if a[0]>0:
  print(-1)
  exit()

ans=1
pre_no_ha=1
all_ha=sum(a)

for ai in a[1:]:
  if pre_no_ha<=0:
    print(-1)
    exit()
  if ai>pre_no_ha*2:
    print(-1)
    exit()
  
  pre_no_ha*=2
  pre_no_ha-=ai
  all_ha-=ai
  pre_no_ha=min(pre_no_ha,all_ha)
  ans+=pre_no_ha+ai

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
def Ii():return int(sys.stdin.buffer.readline())
def Mi():return map(int,sys.stdin.buffer.readline().split())
def Li():return list(map(int,sys.stdin.buffer.readline().split()))

n = Ii()
a = Li()
b = [0]*(n+1)
bm = [0]*(n+1)
b[0] = 1
if a[0] > 1:
  print(-1)
  exit(0)
bm[-1] = a[-1]
for i in range(1,n+1):
  bm[-1-i] = bm[-i]+a[-i-1]
  b[i] = (b[i-1]-a[i-1])*2
b = np.array(b)
bm = np.array(bm)
b = np.amin([[b],[bm]], axis=0)
if a[-1] != b[-1,-1]:
  print(-1)
  exit(0)
if np.any(b <= 0):
  print(-1)
  exit(0)
print(np.sum(b))

Submission status: Accepted

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

lim = [0]*(n+1)
aa = 0
for i in range(n+1):
    aa += a[n-i]
    lim[n-i] = aa
    
if n == 0:
    if a[0] != 1:
        print(-1)
        sys.exit()
    else:
        print(1)
        sys.exit()
        
if a[0] != 0:
    print(-1)
    sys.exit()
    
ha = [[0]*(n+1) for i in range(2)]
ha[0][0] = 1
ha[1][0] = 1
for i in range(n):
    ha[1][i+1] = min(ha[0][i]*2 , lim[i+1])
    ha[0][i+1] = ha[1][i+1] - a[i+1]
    if ha[0][i+1] <= 0 and i != n-1:
        print(-1)
        sys.exit()
    if ha[0][i+1] < 0 and i == n-1:
        print(-1)
        sys.exit()
        
print(sum(ha[1]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    # verification
    x = 1
    mx = [0] * (N+1)
    for i, a in enumerate(A):
        if i != N and x <= a:
            print(-1)
            return
        if i == N and x < a:
            print(-1)
            return
        x -= a
        mx[i] = x
        x *= 2
    ans = 0
    edge = 0
    for i in range(N+1)[::-1]:
        a = A[i]
        edge = min(edge, mx[i])
        ans += edge + a
        edge += a
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def error():
    print(-1)
    quit()

n = inp()
a = inpl()
if n == 0 and sum(a) == 1:
    print(1)
    quit()
can = [0] * (n+1); can[0] = 1
b = [0] * (n+1)
res = [0] * (n+1)

if a[0] != 0:
    error()

for i in range(n):
    can[i+1] = can[i]*2 - a[i+1]
    if can[i+1] < 0:
        error()
can[-1] = 0
b[-1] = 0
res[-1] = a[-1]
for i in range(n)[::-1]:
    b[i] = min(res[i+1], can[i])
    res[i] = a[i] + b[i]
print(sum(res))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0 for i in range(n+1)]
leaf = sum(a)

if n == 0 and a[0] != 1:
    print(-1)
    exit()
b[0] = 1 - a[0]
leaf -= a[0]
ans = 1
for i in range(1,n+1):
    kosu = min(b[i-1] * 2,leaf)
    ans += kosu
    b[i] = kosu - a[i]
    if b[i] < 0:
        print(-1)
        exit()
    leaf -= a[i]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
nums = list(map(int, input().split()))
if n == 0:
  if nums[0] == 1:
    print(1)
  else:
    print(-1)
  exit()
if n > 0 and nums[0] != 0:
  print(-1)
  exit()
n_nods = 1
ans = 1
ret = sum(nums)
for i in range(1,n+1):
  n_nods = min(n_nods*2,ret)
  ans += n_nods
  ret -= nums[i]
  n_nods -= nums[i]
  if n_nods < 0:
    print(-1)
    exit()
  if n_nods == 0 and i < n:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
import math

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

#_1 木の一番下から順に各深さの頂点数[min, max]を取得
seq = [[folia[-1], folia[-1]]]
for i in range(n): # 深さ'n'分
    tmp = folia[-(i+2)]
    sml = math.ceil(seq[i][0] / 2) + tmp 
    big = seq[i][1] + tmp
    seq += [[sml, big]]
#print(seq)

#_2 一番根本の頂点数[min, max]に'1'を含まない場合は '存在しない木'
if not (seq[-1][0] <= 1 <= seq[-1][1]):
    print(-1)
    exit()

#_3 木の一番上から順に各深さで理論最大頂点数と'#_1のmax'との'min'をとる
ans =[1]
for j in range(n): # 深さ'n'分
    tmp = min((ans[j] - folia[j]) * 2, seq[-(j+2)][1])
    ans.append(tmp)
print(sum(ans)) # その合計が'ans'

Submission status: Accepted

Solution code:
import math

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

seq = [[folia[-1], folia[-1]]]

for i in range(n): # 深さ'n'分
    tmp = folia[-(i+2)]
    sml = math.ceil(seq[i][0] / 2) + tmp 
    big = seq[i][1] + tmp
    seq += [[sml, big]]
#print(seq)

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

ans =[1]
for j in range(n): # 深さ'n'分
    tmp = min((ans[j] - folia[j]) * 2, seq[-(j+2)][1])
    ans.append(tmp)
print(sum(ans))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import math

n = readint()
a = readints()

flag = 0

node = [1]
for i in range(n):
    if a[i]>node[-1]:
        flag = 1
        break
    else:
        node.append((node[-1]-a[i])*2)

if a[-1]>node[-1]:
    flag = 1

if flag:
    print(-1)
    exit()

node[n] = a[n]

for i in range(n-1,-1,-1):
    if node[i]>a[i]+node[i+1]:
        node[i] = a[i] + node[i+1]
    else:
        break
print(sum(node))

Submission status: Accepted

Solution code:
N=int(input())

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

M=[0 for i in range(N+1)]
M[0]=1
if N==0:
    if L[0]==1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
if L[0]==1:
    print(-1)
    exit()

for i in range(1,N+1):
    M[i]=M[i-1]*2-L[i]
    if M[i]<0:
        print(-1)
        exit()
#print(L)
#print(M)

M[-1]=0
for i in range(1,N+1):
    if M[-1-i]<(M[-i]+L[-i]+1)//2:
        print(-1)
        exit()
    elif (M[-i]+L[-i])>=M[-1-i] and M[-1-i]>=(M[-i]+L[-i]+1)//2:
        continue
    else:
        M[-1-i]=(M[-i]+L[-i])
#print(L)
#print(M)
print(sum(L)+sum(M))

Submission status: Accepted

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

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

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

node = [1]
komoti = [1]
for i in range(1, n+1):
    ai = a[i]
    if komoti[-1]*2 >= ai:
        node.append(min(ruiseki[i], komoti[-1]*2))
        komoti.append(node[-1]-ai)
    else:
        print(-1)
        exit()

print(sum(node))

Submission status: Accepted

Solution code:
# 深さdの現実的な上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))

# 深さdのノード数の上限
limit = [1]  # ルートのノードの上限数 : 当然1
for d in range(1, N+1):
    if d == N:  # 1番深いところの上限はA[N]
        limit.append(A[d])
    else:
        limit.append((limit[-1]-A[d-1])*2)
        # limit[-1] < A[d-1]の場合，葉を確保することができていない
        if limit[-1] < 0:
            print(-1)
            exit()

# Nが0の時の処理
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()

# 1番深いところから構築して最後にsumを取る
ans = [limit[-1]]
# 1番深いところから構築しており，今現在のオードの数
now_node = limit[-1]
for d in range(N-1, -1, -1):
    # limitは深さが浅いところから押さえつけながら構築したと考える
    ans.append(min(now_node+A[d], limit[d]))  # now_nodeは深さd+1のノードの数, 今は深さdの部分の構築をしている
    now_node = ans[-1]  # 現在のノードの数

# 構築したものに対してジャッジする
ans.reverse()
for d in range(N):
    if (ans[d]-A[d])*2 < A[d+1]:  # 1つ深い部分の葉を構築するだけの労力を確保できているかどうか
        print(-1)
        exit()
print(sum(ans))

Submission status: Accepted

Solution code:
# 深さdの現実的な上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))

# 深さdのノード数の上限
limit = [1]  # ルートのノードの上限数 : 当然1
for d in range(1, N+1):
    if d == N:  # 1番深いところの上限はA[N]
        limit.append(A[d])
    else:
        limit.append((limit[-1]-A[d-1])*2)
        # limit[-1] < A[d-1]の場合，葉を確保することができていない
        if limit[-1] < 0:
            print(-1)
            exit()

# Nが0の時の処理
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()

# 1番深いところから構築して最後にsumを取る
ans = [limit[-1]]
# 1番深いところから構築しており，今現在のオードの数
now_node = limit[-1]
for d in range(N-1, -1, -1):
    ans.append(min(now_node+A[d], limit[d]))
    now_node = ans[-1]  # 現在のノードの数

# 構築したものに対してジャッジする
ans.reverse()
for d in range(N):
    if (ans[d]-A[d])*2 < A[d+1]:
        print(-1)
        exit()
print(sum(ans))

Submission status: Accepted

Solution code:
# 深さdの現実的な上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))

# 深さdのノード数の上限
limit = [1]  # ルートのノードの上限数 : 当然1
for d in range(1, N+1):
    if d == N:  # 1番深いところの上限はA[N]
        limit.append(A[d])
    else:
        limit.append((limit[-1]-A[d-1])*2)
        if limit[-1] < 0:
            print(-1)
            exit()

# Nが0の時の処理
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()

# 1番深いところから構築して最後にsumを取る
ans = [limit[-1]]
# 1番深いところから構築しており，今現在のオードの数
now_node = limit[-1]
for d in range(N-1, -1, -1):
    ans.append(min(now_node+A[d], limit[d]))
    now_node = ans[-1]  # 現在のノードの数

# 構築したものに対してジャッジする
ans.reverse()
for d in range(N):
    if (ans[d]-A[d])*2 < A[d+1]:
        print(-1)
        exit()
print(sum(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""NOMURA プログラミングコンテスト 2020: C - Folia
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_c
"""


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

    leaves_count = sum(As)
    node_count = 1
    ans = 0
    for i, a in enumerate(As):
        leaves_count -= a
        next_node_count = min(leaves_count, (node_count - a) * 2)
        if next_node_count < 0:
            ans = -1
            break
        ans += node_count
        node_count = next_node_count

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""NOMURA プログラミングコンテスト 2020: C - Folia
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_c
"""


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

    leaves_count = sum(As)
    node_count = 1
    ans = 0
    for i, a in enumerate(As):
        leaves_count -= a
        next_node_count = min(leaves_count, (node_count - a) * 2)
        if next_node_count < 0:
            print(-1)
            break
        ans += node_count
        node_count = next_node_count
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.sum(A)-np.cumsum(np.append(0, A[:len(A)-1]))
v=0
k=0
for i in range(N+1):
  if i==0:
    if N==0 and A[0]==1:
      k=1
    elif A[0]==0:
      k=1
    else:
      print(-1)
      break
  elif i==N:
    if B[i]<=2*(k-A[i-1]):
      k=B[i]
    else:
      k=0
      print(-1)
      break
  else:
    k=min(2*(k-A[i-1]),B[i])
    if k<=0:
      print(-1)
      break
  v+=k
if k>0:
  print(v)

Submission status: Accepted

Solution code:
# なるべく根本に近いところで枝分かれさせたい。
# 根から葉に向かって考えると「ここで枝分かれするべきか?」の答えがその先（つまりもっと葉側）を読まなければいけないので厄介
# だが実はそれは「その先の葉の個数の合計」だけ見れば良い。できそう。
# 葉から根に向かって考えると「ここで枝を統合するべきか?」の答えがその先（つまりもっと根側）を読まなければいけないので厄介
# これは根本近くのどの位置に数字があるかに依存して変わるから難しい。
# 根から考えるのが良さそう。

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

# コーナーケース先に潰しておこう
if n == 0:
    if nums[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
if n > 0 and nums[0] >= 1:
    print(-1)
    exit()

# 根から葉に向かう

rest = sum(nums)

n_node = 1
ans = 1
for i in range(1, n+1):
    # なるべく根本に近いところで枝分かれさせたい。
    # 「ここで枝分かれするべきか?」→基本的にはそう。しかしその先の葉の合計を超えてはいけない。
    n_node = min(n_node * 2, rest)
    ans += n_node

    # 葉を引く
    n_node -= nums[i]
    rest -= nums[i]

    # 負ならダメ 0 0 5とか
    if n_node < 0:
        print(-1)
        exit()
    # 最後ではないのに0になったらダメ 0 0 4 1とか
    if n_node == 0 and i < n:
        print(-1)
        exit()

print(ans)

Submission status: Accepted

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

s = 1
S = 1
if a[0] > 1 or (a[0] >= 1 and len(a) > 1):
    S = -1
else:
    for i in range(1,n+1):
        if a[i] > 2*s:
            S = -1
            break
        if s*2 <= N:
            S += s*2
            s += s - a[i]
        else:
            S += N
            s += N - s - a[i]
        N -= a[i]
print(S)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
# import math
from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


n = int(input())
A = list(map(int, input().split()))
sA = list(itertools.accumulate(A[::-1]))[::-1]
# print(sA)

num = 0
par = 1
for i in range(n+1):
    tmp_num = min(par, sA[i])
    if tmp_num <= 0:
        print(-1)
        exit()
    # print(tmp_num)
    num += tmp_num
    par = 2*(tmp_num-A[i])
    # print(par)

print(-1 if par < 0 else num)

Submission status: Accepted

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

Submission status: Accepted

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

if N == 0 and A[0] != 1:
  print(-1)
elif N != 0 and A[0] != 0:
  print(-1)
else:
  ans = 1
  nodes = 1
  preF = 0
  sucF = sum(A)
  
  for d in range(1, N+1):
    fol = A[d]
    nodes = min((nodes-preF)*2, sucF)
    
    if nodes < fol:
      print(-1)
      exit()
    
    ans += nodes
    preF = fol
    sucF -= fol
  print(ans)

Submission status: Accepted

Solution code:
import math

ceil = math.ceil

def main(N, A):
    A.reverse()
    pos = [(A[0], A[0])]
    for i in range(len(A)-1):
        tmpmin = ceil(pos[-1][0]/2) + A[i+1]
        tmpmax = pos[-1][1] + A[i+1]
        pos.append((tmpmin, tmpmax))

    l,r = pos.pop()
    if l > 1:
        return -1
    
    ki = [1]
    A.reverse()
    for j in range(N):
        m = (ki[j]-A[j])*2
        l, r = pos.pop()
        if m < l:
            return -1
        ki.append(min(r, m))
    
    return sum(ki)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = main(N, A)
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
al = list(map(int, input().split()))
bl = [0]*(n+1)
acc = [0]*(n+2)
for i in range(n+1):
    acc[i+1] = al[i]+acc[i]

res = 0
for d in range(n+1):
    if d==0:
        res += 1
        bl[0] = 1 - al[0]
    else:
        r1 = 2*bl[d-1] - al[d]
        r2 = acc[-1] - acc[d+1]
        bl[d] = min(r1,r2)
        res += al[d]+bl[d]
    if bl[d]<0:
        print(-1)
        exit()

print(res)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    lfs = list(map(int, input().strip().split()))
    ans = 0
    L = 1 << N
    lo = lfs[-1]
    hi = lfs[-1]
    memo = [0] * (N + 1)
    for i in range(N - 1, -1, -1):
        if lo > L:
            return -1
        memo[i + 1] = hi
        lo = (lo + 1) // 2 + lfs[i]
        hi = hi + lfs[i]
        L = L >> 1

    if lo > L:
        return -1
    memo[0] = hi
    
    curr = 1
    for i in range(N + 1):
        ans += min(memo[i], curr)
        curr = (curr - lfs[i]) << 1
    return ans

print(solve())

Submission status: Accepted

Solution code:
from math import ceil

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

bottom_n_list = [(0, 0) for _ in range(n + 1)]
bottom_n_list[n] = (a[n], a[n])
for i in range(n-1, -1, -1):
    leaf_num = a[i]
    min_a_node_num = ceil(bottom_n_list[i + 1][0] / 2)
    max_a_node_num = min(bottom_n_list[i + 1][1], 2 ** i - leaf_num)
    if max_a_node_num < min_a_node_num:
        print(-1)
        exit()
    bottom_n_list[i] = (min_a_node_num + leaf_num, max_a_node_num + leaf_num)

top_n_list = [0]*(n+1)
if 1 < bottom_n_list[0][0] or bottom_n_list[0][1] < 1:
    print(-1)
    exit()
top_n_list[0] = 1
ans = 1
for i in range(1, n+1):
    top_n_list[i] = min(bottom_n_list[i][1], (top_n_list[i-1]-a[i-1])*2)
    ans += top_n_list[i]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

node = 1
# 作成しなければならない葉の残りの数
leaf = sum(A)
max_node = 1
judge = True
ans = 0
for i, a in enumerate(A):
    ans += node
    leaf -= a
    if node < a+1 and leaf > 0:
        judge = False
        break
    # 次の深さのノード
    max_node = (node - a) * 2
    node = min(leaf, max_node)
    

if judge and max_node == 0:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

s=sum(A)

ans=1
eda=1

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

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

# 階層iが取り得る最小値と最大値を記録する
minV = [0 for i in range(N + 1)]
maxV = [0 for i in range(N + 1)]

minV[-1] = A[-1]
maxV[-1] = A[-1]
for i in range(len(A) - 2, -1, -1):
  leaf = A[i] # その階層に必要な葉の数
  minV[i] = (minV[i + 1] + 1) // 2 + leaf
  maxV[i] = maxV[i + 1] + leaf

if 1 < minV[0] or maxV[0] < 1:
  print(-1)
  exit(0)

# 最大頂点数を確定していく
V = [0] * (N + 1)
V[0] = 1
for i in range(1, N + 1):
  V[i] = min((V[i - 1] - A[i - 1]) * 2, maxV[i]) # 親の頂点数から葉の数を引いたものの2倍

print(sum(V))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
if n == 0 and a[0] != 1:
    print(-1)
    exit(0)
b = [0] * (n + 2)
for i in range(n, 0, -1):
    b[i - 1] = b[i] + a[i]
t = 1 - a[0]
ans = 1
for i in range(n):
    m = min(t * 2, b[i])
    if m < a[i + 1]:
        print(-1)
        exit(0)
    ans += m
    t = m - a[i + 1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
 
    section_needed = sum(a)
    ans = 0
    section_count = 1
    total_section = 1
    for i in range(n+1):
        ans += section_count
        section_count -= a[i]
        if section_count <= 0 and i != n:
            print(-1)
            return
        if i == n and total_section != section_needed:
            print(-1)
            return
        next_branch = min(max(0, section_needed - total_section), section_count)
        total_section += next_branch
        section_count += next_branch
 
    print(ans)
 
main()

Submission status: Accepted

Solution code:
from math import ceil
n = int(input())
A = list(map(int,input().split()))[::-1]
mn,mx = A[0], A[0]
step = [[mn,mx]]
for i in range(1, n+1):
    mn = ceil(mn/2) + A[i]
    mx = mx + A[i]
    step.append([mn,mx])
if not mn<=1 and 1<=mx:
    print(-1)
else:
    step = step[::-1]
    A = A[::-1]
    now = 1
    ans = 1
    for i in range(1, n+1):
        now = min(step[i][1],
                  (now-A[i-1])*2)
        ans += now
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
n = int(stdin.readline())
nmleaves = list(map(int, stdin.readline().strip().split()))

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

# pref[i]: sum(nmleaves[i:]), i.e., the number of leaves at or below level i.
pref = [0]*(n+1)
totsum = sum(nmleaves)
pref[0] = totsum
t = 0
for i in range(1, n+1):
    t += nmleaves[i-1]
    pref[i]  = totsum - t

prev_nl = 1
ans = 1
for lev in range(1, n+1):
    nodes = min(prev_nl*2, pref[lev])
    ans += nodes
    prev_nl = nodes - nmleaves[lev]
    if prev_nl < 0:
        print(-1)
        exit()
    elif prev_nl == 0 and lev+1<n+1 and pref[lev + 1]>0:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft


def main():
    n = int(input())
    n += 1
    a = list(map(int, input().split()))
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i] + a[i]
    ans = [0] * n
    for i in range(n):
        ans[i] = c[n] - c[i]
    if n == 1 and a[0] == 0:
        print(-1)
        return
    if n > 1 and a[0] > 0:
        print(-1)
        return
    ans[0] = min(1, ans[0])
    if ans[0] < a[0]:
        print(-1)
        return
    for i in range(1, n):
        ans[i] = min(ans[i], (ans[i-1]-a[i-1]) * 2)
        if ans[i] < a[i]:
            print(-1)
            return

    print(sum(ans))
main()

Submission status: Accepted

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

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

b = [0 for _ in range(n)]
b.append(a[-1])
for i in range(n)[::-1]:
   b[i] = b[i+1] + a[i]

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
nums = list(map(int, input().split()))
nodes = []
currentLeaf = 1
fail = False
#check from top
for i in range(N + 1):
	nodes.append(currentLeaf)
	currentLeaf = (currentLeaf-nums[i])*2
	if (currentLeaf < 0):
		fail = True
		break 
if (fail):
	print(-1)
else:
  #check from bottom
  currentLeaf = 0
  totalNode = 0
  for i in reversed(range(N+1)):
      currentLeaf += nums[i]
      currentLeaf = min(currentLeaf, nodes[i])
      totalNode += currentLeaf

  if (fail):
      print(-1) 
  else:
      print(totalNode)

Submission status: Accepted

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

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

B=[0 for _ in range(N)]

B.append(A[-1])
for i in range(N)[::-1]:
    B[i]=B[i+1]+A[i]

r=1
ans=1
for i in range(1,N+1):
    t=min(r*2,B[i])
    ans+=t
    r=t-A[i]
    if r<0:
        print(-1)
        exit()

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A == [0]:
            print('0')
        elif A == [1]:
            print('1')
        else:
            print('-1')
        return

    if N == 1:
        if A == [0, 1]:
            print('2')
        elif A == [0, 2]:
            print('3')
        else:
            print('-1')
        return

    if A[0] != 0:
        print('-1')
        return

    f = [0 for i in range(N)]

    f[0] = 1
    count = sum(A) - 1

    for d in range(1, N):
        f[d] = 2 * min(f[d - 1], count) - A[d] + min(max(f[d - 1] - count, 0), f[d - 1])
        count -= min(f[d - 1], count)
        if f[d] <= 0:
            print('-1')
            return

    if A[-1] > 2 * f[N-1]:
        print('-1')
        return

    print(sum(f) + sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if a[0]:
  if n==0 and a[0]==1:
    print(1)
  else:
    print(-1)
  exit()
b=[0]*n
b.append(a[-1])
for i in range(n)[::-1]:
  b[i]=b[i+1]+a[i]
ro=1
ans=1
for i in range(1,n+1):
  t=min(ro*2,b[i])
  ans+=t
  ro=t-a[i]
  if ro<0:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
bunretsu = sum(A) - 1
zanretsu = 1
souwa = 0
for i in range(N+1):
    souwa += zanretsu
    if A[i] <= zanretsu:
        zanretsu -= A[i]
    else:
        souwa = -1
        break
    if bunretsu >= 1 and bunretsu <= zanretsu:
        zanretsu += bunretsu
        bunretsu = 0
    elif bunretsu >= 1 and bunretsu > zanretsu:
        bunretsu -= zanretsu
        zanretsu *= 2
print(souwa)

Submission status: Accepted

Solution code:
import operator
from itertools import accumulate

def main():
  N = int(input())
  A = list(map(int, input().split()))
  A_sum = list(reversed(list(accumulate(reversed(A))))) + [0]
  B = [0] * (N+1)

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

print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul

mod = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

n = I()
A = LI()
max_ret = 0
min_ret = 0
max_arr = [0] * (n + 1)
min_arr = [0] * (n + 1)
for i in range(n, -1, -1):
    max_ret = max_ret + A[i]
    min_ret = (min_ret + 1) // 2 + A[i]
    max_arr[i] = max_ret
    min_arr[i] = min_ret

if max_ret >= 1 >= min_ret:
    ans = 1
    ret = 1
    for j in range(1, n + 1):
        ret = min((ret - A[j-1]) * 2, max_arr[j])
        ans += ret
    print(ans)
else:
    print(-1)