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:
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
k = 1 - a[0]
s -= a[0]
ans = 1

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

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

import math

# 葉から調査し、範囲を求める
limits = [(A[-1], A[-1])]
# for i in reversed(range(0, len(A)-1)):
for i in reversed(range(0, N)):
    min_ = math.ceil(limits[-1][0] / 2)
    max_ = limits[-1][1]
    # print("min_ {} max_ {} leaf {}".format(min_, max_, A[i]))
    limits.append((min_ + A[i], max_ + A[i]))
# print("limits: {}".format(limits))
if limits[-1][0] != 1:
    print(-1)
    quit()

# 根からにする
limits.reverse()

# 根から制約に基づき最大値を計算する
tree = [1]
for i in range(1, N+1):
    nodes = min(2 * (tree[-1] - A[i-1]), limits[i][1])
    tree.append(nodes)
# print(limits)
# print(tree)

ans = sum(tree)
print(ans)

Submission status: Accepted

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

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

# Bound max non-leaves by how many expansions the previous level can do
maxNonLeafs = [None for i in range(N + 1)]
maxNonLeafs[0] = 1 - numLeafs[0]
for i in range(1, N + 1):
    maxNonLeafs[i] = 2 * maxNonLeafs[i - 1] - numLeafs[i]
    if maxNonLeafs[i] < 0:
        print(-1)
        exit()

# Tighten max non-leaves by how many available children are on next level
maxNonLeafs[N] = 0
for i in range(N - 1, -1, -1):
    maxNonLeafs[i] = min(maxNonLeafs[i], maxNonLeafs[i + 1] + numLeafs[i + 1])


count = 0
for i in range(N + 1):
    count += maxNonLeafs[i] + numLeafs[i]
print(count)

Submission status: Accepted

Solution code:

def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  min_maxs = [0] * len(A)
  min_maxs[len(A)-1] = [A[-1], A[-1]]

  for index in reversed(range(len(A)-1)):
    min_maxs[index] = [min_maxs[index+1][0] // 2 + A[index], min_maxs[index+1][1] + A[index]]

  result = 1
  recent = 1
  for index in range(1, len(A)):
    num_of_node = (recent - A[index-1]) * 2
    if num_of_node < min_maxs[index][0]:
      print(-1)
      return True
    
    result += min(num_of_node, min_maxs[index][1])
    recent = min(num_of_node, min_maxs[index][1])

  print(result)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  min_maxs = [0] * len(A)
  min_maxs[len(A)-1] = [A[-1], A[-1]]

  for index in reversed(range(len(A)-1)):
    min_maxs[index] = [min_maxs[index+1][0] // 2 + A[index], min_maxs[index+1][1] + A[index]]

  result = 1
  recent = 1
  for index in range(1, len(A)):
    num_of_node = (recent - A[index-1]) * 2
    if num_of_node < min_maxs[index][0]:
      print(-1)
      return True
    
    result += min(num_of_node, min_maxs[index][1])
    recent = min(num_of_node, min_maxs[index][1])

  print(result)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

n = int(input())
a = [int(x) for x in input().split()]

max_a = [0]*(n + 1)
"""
if n == 0 and a[0] == 0:
    print(-1)
    sys.exit()
"""
for i in range(n + 1):
    if i == 0:
        max_a[i] = 1
    else:
        max_a[i] = (max_a[i - 1] - a[i - 1])*2
        if max_a[i] < 0:
            print(-1)
            sys.exit()
# print(max_a)
for i in range(n, -1, -1):
    if i == n:
        if max_a[i] < a[i]:
            print(-1)
            sys.exit()
        max_a[i] = a[i]
    else:
        min_p = max_a[i + 1] // 2 + int(max_a[i + 1] % 2 == 1)
        max_p = max_a[i + 1]
        if max_a[i] < min_p:
            print(-1)
            sys.exit()
        max_a[i] = min(max_p + a[i], max_a[i])
print(sum(max_a))
# print(max_a)

Submission status: Accepted

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

n = int(input())
a = [int(x) for x in input().split()]

max_a = [0]*(n + 1)

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

for i in range(n + 1):
    if i == 0:
        max_a[i] = 1
    else:
        max_a[i] = (max_a[i - 1] - a[i - 1])*2
        if max_a[i] < 0:
            print(-1)
            sys.exit()
# print(max_a)
for i in range(n, -1, -1):
    if i == n:
        if max_a[i] < a[i]:
            print(-1)
            sys.exit()
        max_a[i] = a[i]
    else:
        min_p = max_a[i + 1] // 2 + int(max_a[i + 1] % 2 == 1)
        max_p = max_a[i + 1]
        if max_a[i] < min_p:
            print(-1)
            sys.exit()
        max_a[i] = min(max_p + a[i], max_a[i])
print(sum(max_a))
# print(max_a)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
V = [0]*(N+1)
flug = 0
Lsum= sum(A)
 
V[0] = 1
for i in range(N):
    V[i+1] = (V[i]*2 - A[i+1])
    if V[i+1] < 0 :
        flug = 1
    Lsum = Lsum - A[i+1]
    if V[i+1] > Lsum :
        V[i+1] = Lsum
 
ans = sum(V)+sum(A)
if A[0] != 0 or A[N] == 0:
    ans = -1
if flug == 1:
   ans = -1
if N == 0 and A[0] != 1:
    ans = -1
elif N == 0 and A[0] == 1:
    ans = 1
 
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import accumulate

    n = int(input())
    a = list(map(int, readline().split()))
    a_cum = [0] * (n + 1)
    a_cum[n] = a[n]

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

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

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

    ans = 0
    for i in range(n + 1):
        if b[i] < a[i]:
            print(-1)
            sys.exit()
        ans += b[i]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MAX = [1] * (N+1)
ans = [0] * (N+1)
INF = 10**15

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

for i in range(1, N+1):
    MAX[i] = min((MAX[i-1] - A[i-1]) * 2, INF)
    if MAX[i] < A[i]:
        print(-1)
        exit()

ans[N] = A[N]

for i in reversed(range(N)):
    ans[i] = min(ans[i+1]+A[i], MAX[i])

print(sum(ans))

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
g=[1]
for i in range(n):
  #葉となるノード以外のノードの最大個数を作っていく。
  #各深さの限界がgとなる。
  g+=[(g[-1]-l[i])*2]
a=0
t=0
#後ろノードから見ていく。
for i in range(n,-1,-1):
  #-1出力のための限界値
  if l[i]>g[i]:
    print(-1)
    break
  #計算する前のtは、前のノードの個数
  #最大個数より小さくなることはない。
  t=min(l[i]+t,g[i])
  #このtが各深さによるノードの個数となっている。
  a+=t
else:
  print(a)

Submission status: Accepted

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

if a_list[0] > 1:
    print(-1)
    exit()

ans = 1
temp1 = [""]*(N+1)
temp1[-1] = a_list[-1]
for n in range(N-1, 0, -1):
    temp1[n] = temp1[n+1]+a_list[n]
    
temp2 = 1
for n in range(1, N+1):
    temp2 = (temp2-a_list[n-1])*2
#     print(temp2, temp1[n])
    ans_temp = min(temp2, temp1[n])
    temp2 = min(temp2, temp1[n])
    
    if ans_temp < a_list[n]:
        print(-1)
        exit()
    
    ans += ans_temp
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
l = [1]
for i in range(n + 1):
    s -= a[i]
    m = min(s, (l[i] - a[i]) * 2)
    if m < 0:
        print(-1)
        exit()
    l.append(m)
print(sum(l))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
 
n = I()
a = LI()
L = [1]
if a[-1] > 2**n:
    print(-1)
    quit()
if n == 0:
    if a[0] == 0:
        print(-1)
        quit()
L2 = [a[-1]]
for i in range(n)[::-1]:
    L2.append(min(L2[-1] + a[i], 2**i))
L2 = L2[::-1]
ans = 0
for i in range(n+1):
    if i == 0:
        tmp = 1
    else:
        tmp = (L[-1] - a[i-1]) * 2
    if tmp <= 0:
        print(-1)
        quit()
    ans += min(tmp, L2[i])
    L.append(tmp)
if L[-1] - a[-1] < 0:
    print(-1)
    quit()
print(ans)

Submission status: Accepted

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

    if n  == 0:
        if A[0] == 1:
            return 1
        else:
            return -1
    elif A[0] != 0:
        return -1
    
    bound = [0]*(n+1)
    bound[n] = A[n]
    for i in range(n-1, -1, -1):
        bound[i] = bound[i+1] + A[i]

    B = [0] * (n+1)
    for i in range(n+1):
        if i == 0:
            B[i] = 1
        else:
            above = (B[i-1] - A[i-1]) * 2
            if  (i < n and above <= 0) or above < 0:
                return -1
            B[i] = min(above, bound[i])
    if B[n] < A[n]:
        return -1
    # print('B: ', B)
    return sum(B)

print(main())

Submission status: Accepted

Solution code:
from sys import exit
from collections import deque
N = int(input())
D = deque(map(int, input().split()))
if N == 0:
  d = D.pop()
  if d == 1:
    print(1)
  else:
    print(-1)
  exit()
R = [[] for i in range(N + 1)]
leaf = D.pop()
R[-1].append(leaf)
R[-1].append(leaf)
for i in range(N - 1, -1, -1):
  leaf = D.pop()
  R[i].append(R[i + 1][0]//2 + R[i + 1][0] % 2 + leaf)
  R[i].append(R[i + 1][1] + leaf)
  R[i].append(leaf)
if not(R[0][0] <= 1 <= R[0][1]):
  print(-1)
  exit()
node = 1
ans = 1
for i in range(1, N + 1):
  node = min(R[i][1], 2 * (node - R[i-1][2]))
  ans += node
print(ans)

Submission status: Accepted

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

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

if a[0] > 1:
    print(-1)
    exit()

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

print(sum(lst))

Submission status: Accepted

Solution code:
import sys
N=int(input())
alist=list(map(int,input().split()))

if N==0 and alist[0]!=1:
  print(-1)
  sys.exit(0)
elif N>0 and alist[0]>0:
  print(-1)
  sys.exit(0)

#pow2d=1<<N
blist=[0]*(N+1)
for d in reversed(range(1,N+1)):
  if d>50:
    blist[d-1]=alist[d]+blist[d]
  else:
    blist[d-1]=min(alist[d]+blist[d],(1<<(d-1))-alist[d-1])
  if blist[d-1]<0:
    print(-1)
    sys.exit(0)
  #pow2d>>=1
  
#print(alist,blist)
cmax_bu=[0]*(N+1)
for d in range(N+1):
  cmax_bu[d]=alist[d]+blist[d]
#print(cmax_bu)

pow2d=1
blist=[0]*(N+1)
if alist[0]==0:
  blist[0]=1
for d in range(1,N+1):
  if pow2d<10**10:
    pow2d<<=1
    c=min(2*blist[d-1],pow2d,cmax_bu[d])
  else:
    c=min(2*blist[d-1],cmax_bu[d])
  blist[d]=c-alist[d]
  if blist[d]<0:
    print(-1)
    sys.exit(0)
#print(alist,blist)

answer=0
for i in range(N+1):
  answer+=alist[i]+blist[i]
  
print(answer)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = [0] * (N + 1)
    if A[0] >= 2:
        print(-1)
        exit()
    if A[0] == 1:
        if len(A) == 1:
            print(1)
            exit()



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

        B[i] = tmp
    ans += A[N]
    C = [0] * (N+1)

    C[N] += A[N]
    for i in range(N-1,0,-1):
        
        if C[i+1] + A[i] <= B[i]:
            ans += A[i] + C[i+1]
            C[i] = A[i] + C[i+1]
        else:
            ans += B[i]
            C[i] = B[i]
            
    print(ans)
        







if __name__ == "__main__":
    main()

Submission status: Accepted

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

rng = [[A[N], A[N]]]

for i in range(N - 1, -1, -1):
    merged = (rng[-1][0] + 1) // 2 + A[i]
    nonmerged = rng[-1][1] + A[i]
    rng.append([merged, nonmerged])
if rng[-1][0] > 1:
    print(-1)
    exit()
rng.reverse()
prev_non_leaf = 1
ans = 1
for i in range(1, N + 1):
    _, u = rng[i]
    ans += min(prev_non_leaf * 2, u)
    prev_non_leaf = prev_non_leaf * 2 - A[i]
print(ans)

Submission status: Accepted

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

Pmax = [0 for _ in range(N+1)]
Pmax[0] = 1-A[0]
for i in range(1, N+1):
    Pmax[i] = 2*Pmax[i-1] - A[i]

ans = 0
v = 0
for i in range(N, -1, -1):
    if Pmax[i]*2 < v:
        ans = -1
        break
    v = min(v, Pmax[i])+A[i]
    ans += v

print(ans)

Submission status: Accepted

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

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


if As[0] != 0:
    print(-1)
    exit()

b = 1
ans = 1
acc = list(accumulate(As))
s = acc[-1]
for ac,a in zip(acc[1:], As[1:]):
    # print(s-ac,2*b-a)
    b = min(2*b-a, s-ac)
    if b < 0:
        print(-1)
        exit()
    ans += b+a
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 0
li = [0]*(n+1)

for i,a in enumerate(a_li):
  ans += (i+1)*a

for i,a in enumerate(a_li[::-1]):
  if i >= 1:
    li[i] = li[i-1]+a
  else:
    li[i] = a

li = li[::-1]

flag = True
ne = 0.5
for i in range(n+1):
  if li[i]  > 2*ne:
    ans -= li[i] -int(2*ne)

  
  ne = min(li[i] - a_li[i],int(2*ne)-a_li[i])

  if (i == n and ne != 0) or (i != n and ne <= 0):
    flag = False

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

Submission status: Accepted

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

error = False
capacity = [0]
cap = 1
for i, a in enumerate(A):
    cap = cap - a
    if cap < 0:
        error = True
        break
    capacity.append(cap)
    cap *= 2

if error:
    print(-1)
else:
    total = 0
    carry = 0
    for d in range(N, -1, -1):
        cap = capacity[d]
        a = A[d]
        check = carry + a
        if check <= cap:
            total += check
            carry += a
        else:
            total += check
            carry = cap

    print(total)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import accumulate

n = int(readline())
a = list(map(int, readline().split()))
cumsum = list(accumulate(a[::-1]))
ans = 0
check = 1
for aa, v in zip(a, cumsum[::-1]):
    if aa > check:
        print(-1)
        exit()
    else:
        ans += min(check, v)
        check -= aa
        check *= 2
print(ans)

Submission status: Accepted

Solution code:
# C - Folia
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(int(x) for x in readline().split())

# 上から順に取りうる頂点数を数えていく

leaf = sum(A) # 葉の残り数
tmp = 1 # 葉を除く頂点数
ans = 0 
for a in A:
    # その深さの葉の数が頂点数より多ければNG
    if tmp < a:
        ans = -1
        break
    # その深さまでで見た時、残りの葉の数と頂点数は一致（葉の数に合わせる）
    ans += min(tmp, leaf) 
    # その深さで使った葉の数を、葉の残り数と葉を除く頂点数からそれぞれ引いておく
    leaf -= a 
    tmp -= a 
    # 次の階層の頂点数の最大数は、葉を除く頂点数*2である
    tmp *= 2

print(ans)

Submission status: Accepted

Solution code:

def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print(-1)
    return True
  min_maxs = {}
  min_maxs[len(A)-1] = [A[-1], A[-1]]

  for index in reversed(range(len(A)-1)):
    min_maxs[index] = [min_maxs[index+1][0] // 2 + A[index], min_maxs[index+1][1] + A[index]]
  # print(min_maxs)
    # min_maxs.insert(0, [min_maxs[0][0] // 2 + a, min_maxs[0][1] + a])
  # print(min_maxs)
  # max_node_in_depth = [sum(A[i:]) for i in range(len(A))]

  # # 各 depth における最小値
  # min_node_in_depth = [0] * (len(A))
  # min_node_in_depth[-1] = max_node_in_depth[-1]
  # index = -1
  # for i in range(1, len(A)):
  #   min_node_in_depth[index] = -(-min_node_in_depth[index + 1] // 2) + A[index]
  #   index = index - 1

  # for min_max in min_maxs:
  #   print(min_max)

  result = 1
  recent = 1
  for index in range(1, len(A)):
    num_of_node = (recent - A[index-1]) * 2
    # print(min_max, num_of_node)
    if num_of_node < min_maxs[index][0]:
      print(-1)
      return True
    
    result += min(num_of_node, min_maxs[index][1])
    recent = min(num_of_node, min_maxs[index][1])

  print(result)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from itertools import accumulate

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

b = list(accumulate(a))
v = 1
cnt = 1
for i in range(n):
    if (v - a[i]) * 2 - a[i + 1] < 0:
        print(-1)
        exit()
    v = min((v - a[i]) * 2, b[-1] - b[i])
    cnt += v
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    a = list(map(int, input().split()))
    maxnum = [0] * (n + 1)
    num = [0] * (n + 1)
    maxnum[0] = 1
    num[0] = 1
    if n > 0:
        num[-1] = a[-1]

    if n == 0 and a[0] == 1:
        print(1)
    elif n == 0 and a[0] == 0:
        print(-1)
    elif n == 0 and a[0] > 1:
        print(-1)
    elif n >= 1 and a[0] > 0:
        print(-1)
    elif n == 1 and a[1] == 1:
        print(2)
    elif n == 1 and a[1] == 2:
        print(3)
    else:
        for i1 in range(1, n + 1):
            if maxnum[i1-1] * 2 < a[i1]:
                print(-1)
                sys.exit()
            else:
                maxnum[i1] = maxnum[i1-1] * 2 - a[i1]

        for j1 in range(n-1, 0, -1):
            numt = a[j1] + min(num[j1 + 1], maxnum[j1-1]*2 - a[j1])
            num[j1] = numt
        r = sum(num)
        print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

s=0
cap=[]
flag=False
for i,a in enumerate(A):
    s*=2
    s+=a
    cap.append(min(2**i-s,(n+1-i)*10**8))
    if s>2**i:
        flag=True
        break

if flag:
    print(-1)
else:
    remain=2**n-s
    ans=0
    node=0
    for i in range(n,-1,-1):
        a=A[i]
        c=cap[i]
        node=min(c,node)+a
        ans+=node
    print(ans)

Submission status: Accepted

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

rng = [[A[N], A[N]]]

for i in range(N - 1, -1, -1):
    merged = (rng[-1][0] + 1) // 2 + A[i]
    nonmerged = rng[-1][1] + A[i]
    rng.append([merged, nonmerged])
if rng[-1][0] > 1:
    print(-1)
    exit()
rng.reverse()
prev_non_leaf = 1
ans = 1
for i in range(1, N + 1):
    l, u = rng[i]
    ans += min(prev_non_leaf * 2, u)
    prev_non_leaf = prev_non_leaf * 2 - A[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
sa = sum(A)
last = A[-1]
count = last
root = 1
for i in range(N):
  sa -= A[i]
  if root <= A[i]:
    print(-1)
    break
  elif root-A[i] > sa:
    root = sa + A[i]
  count+=root
  root = (root-A[i])*2
else:
  if count == 0 or root < last:
    count = -1
  print(count)

Submission status: Accepted

Solution code:
# C - Folia
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(int(x) for x in readline().split())

leaf = sum(A)
tmp = 1
ans = 0
for a in A:
    if tmp < a:
        ans = -1
        break
    ans += min(tmp, leaf)
    leaf -= a
    tmp -= a
    tmp *= 2

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1
laS = [0 for i in range(N+1)]
laS[-1] = A[-1]

for i in range(N):
    laS[-2-i] = A[-2-i] + laS[-1-i]
    nodeS[i+1] = (nodeS[i]-A[i])*2

for i in range(N+1):
    if nodeS[i] <= 0:
        print(-1)
        exit()

for i in range(N+1):
    if nodeS[i] >= laS[i]:
        break
    if i == N:
        print(-1)
        exit()

print(sum(nodeS[:i]) + sum(laS[i:]))

Submission status: Accepted

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

b = [1]
f = True
for i in range(n+1):
    sa -= a[i]
    d = min(sa, (b[i] - a[i]) * 2)
    if d < 0:
        f = False
        break
    b.append(d)

print(sum(b) if f else -1)

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

nodeS = [0 for i in range(N+1)]
nodeS[0] = 1
laS = [0 for i in range(N+1)]
laS[-1] = A[-1]

for i in range(N):
    laS[-2-i] = A[-2-i] + laS[-1-i]
    nodeS[i+1] = min(10**18,(nodeS[i]-A[i])*2)

for i in range(N+1):
    if nodeS[i] <= 0:
        print(-1)
        exit()

for i in range(N+1):
    if nodeS[i] >= laS[i]:
        break
    if i == N:
        print(-1)
        exit()

print(sum(nodeS[:i]) + sum(laS[i:]))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline

n = int(input())
# n+1個
A = list(map(int, input().split()))

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

ans = 0
max2 = 0
kouho = [0] * (n + 1)
for i in range(n, 0, -1):
    max1 = pow(2, i)
    max2 += A[i]
    max2 = min(max1, max2)
    kouho[i] = max2
kouho[0] = 1
not_leave = 1
for i in range(1, n + 1):
    cnt = 0
    not_leave *= 2
    temp = min(kouho[i], not_leave)
    ans += temp
    not_leave -= A[i]
    if not_leave <= 0 and i != n:
        print(-1)
        exit()
    if i == n:
        if not_leave == 0:
            continue
        elif not_leave < 0:
            print(-1)
            exit()
ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
a=input()
a=[int(s)for s in a.split()]
M=1
Q=1
m=sum(a)
if a[0]>=1:
    if a[0]==1 and n==0:
        print(1)
        sys.exit()
    else:    
        print(-1)
        sys.exit()
for i in range(n):
    M=2*M-a[i+1]
    if M<0:
        print(-1)
        sys.exit()
    M1=M+a[i+1]
    m=m-a[i]
    Q=Q+min(M1,m)
print(Q)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
if n == 0:
  if A[0] == 1:
    print(1)
  else:
    print(-1)
  exit()
C = list(accumulate(A[::-1]))[::-1] + [0]
B = [-1]*(n+1)
B[0] = 1 - A[0]
for i in range(1, n+1):
  B[i] = min(C[i+1], 2*B[i-1]-A[i])
  if B[i] < 0 or B[i] < B[i-1] - A[i]:
    print(-1)
    exit()
ans = sum(A) + sum(B)
print(ans)

Submission status: Accepted

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

if A_list[0] > 1:
    print(-1)
    exit()
elif A_list[0] == 1:
    if N == 0:
        print(1)
    else:
        print(-1)
    exit()


sumA = sum(A_list)
node = 1
count = 1
for i in range(len(A_list) - 1):
    temp = min([node * 2, sumA])
    count += temp
    node = temp - A_list[i + 1]

    if node < 0:
        print(-1)
        exit()

    sumA -= A_list[i + 1]

print(count)

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


MAX = 10 ** 18
lst = [1] * (10 ** 5 + 10)

#純粋な2分木としたときの最大値
for i in range(N + 1):
    lst[i + 1] = min(MAX, lst[i] * 2)

# print (lst[:10])
for i in range(N + 1):
    tmp = lst[i] - A[i]
    if tmp < 0:
        print (-1)
        exit()
    lst[i + 1] = min(lst[i + 1], tmp * 2)

# print (lst[:10])

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

# print (lst[:10])
ans = 1
tmp = 0
for i in range(N, 0, -1):
    ans += lst[i]
    lst[i - 1] = min(lst[i] + A[i - 1], lst[i - 1])

# print (lst[:10])
print (ans)

Submission status: Accepted

Solution code:

N=int(input())
A=list(map(int,input().split()))
sum_value = sum(A)
chiled_value = 1
top_value = 1
if(N==0 and A[0]==1):
    print(1)
    exit()
if(A[0]!=0):
    print(-1)
    exit()
for i in range(1,N):
    if(sum_value >= chiled_value*2):
        top_value += chiled_value*2
        chiled_value = chiled_value*2-A[i]
        sum_value=sum_value-A[i]
        if(A[i+1]>chiled_value*2):
            print(-1)
            exit()
    elif(sum_value < chiled_value*2):
        chiled_value=sum_value
        top_value += chiled_value
        sum_value=sum_value-A[i]
    if(A[i]>=2**i):
        print(-1)
        exit()
if((sum_value-A[N])!=0):
    print(-1)
    exit()
print(top_value+A[N])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
node = [0 for i in range(n+1)]
if n == 0:
    if a[0] != 1:
        print(-1)
        exit()
    else:
        print(1)
        exit()
if a[0] != 0:
    print(-1)
    exit()
node[0] = 1
count = 1
for i in range(1,n+1):
    count = min(count * 2, 10**18)
    if a[i] > count:
        print(-1)
        exit()
    node[i] = node[i-1] - a[i-1]
    node[i] *= 2
if node[-1] < a[-1]:
    print(-1)
    exit()
node[-1] = a[-1]
for i in range(n-1, -1, -1):
    if a[i] > node[i]:
        print(-1)
        exit()
    node[i] = min(node[i], node[i+1] + a[i])
print(sum(node))

Submission status: Accepted

Solution code:
# 解説放送

def main():
    N = int(input())
    *A, = map(int, input().split())

    mis = [0]
    mas = [0]
    for x in reversed(A):
        mis.append((mis[-1] + 1) // 2 + x)
        mas.append(mas[-1] + x)

    if not (mis[-1] <= 1 <= mas[-1]):
        print(-1)
        return

    mas.reverse()

    ans = [1]
    for i, x in enumerate(A, start=1):
        ans.append(min(mas[i], (ans[-1] - x) * 2))

    print(sum(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li()

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

max_a = [0] * (N+1)
max_a[0] = 1 - A[0]

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

cnt_list = [0]*(N)
cnt_list[-1] = min(A[-1], max_a[N-1])

for i in reversed(range(N-1)):
    if cnt_list[i+1] + A[i+1] <= max_a[i]:
        cnt_list[i] = cnt_list[i+1] + A[i+1]
    else:
        cnt_list[i] = max_a[i]

cnt = sum(cnt_list[:N+1]) + sum(A)

print(cnt)

Submission status: Accepted

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

SUM = sum(A)
ans = 0

for i in range(N+1):
    SUM -= A[i]
    if i == 0:
        res = min(1 - A[0], SUM)
    else:
        res = min(2*B-A[i], SUM)
    if res < 0:
        ans = -1
        break
    ans = ans + res + A[i] 
    B = res
    
print(ans)

Submission status: Accepted

Solution code:
import math

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

end_flag = False
count = sum(leaf)
ans = 0
node = 1

for i in range(N+1):
    if end_flag:
        break
    ans += node
    count -= leaf[i]
    node = min(count, (node-leaf[i])*2)

    if node < 0:
        end_flag = True

if end_flag:
    print('-1')
else:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
P=[0]*(N+1)
P[N]=A[N]
Q=[0]*(N+1)
Q[N]=A[N]
 
for i in range(N,0,-1):
    mxp=P[i]+A[i-1]
    mnp=(P[i]//2) + (P[i]%2) +A[i-1]
    mxq=Q[i]+A[i-1]
    mnq=(Q[i]//2) + (Q[i]%2) +A[i-1]
    P[i-1]=mnp
    Q[i-1]=min(mxq,2**i)
 
if P[0]!=1:
    print(-1)
    exit()
 
Q[0]=1
 
for i in range(1,N):
    if Q[i]>2**i:
        Q[i]=2**i
    if Q[i]>(Q[i-1]-A[i-1])*2:
        Q[i]=(Q[i-1]-A[i-1])*2
 
print(sum(Q))

Submission status: Accepted

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

pm = sum(a)
e = 1
te = 1
for i in a:
    pm -= i
    e = min((e-i)*2, pm)
    if e < 0:
        break
    te += e
if e < 0:
    print(-1)
else:
    print(te)

Submission status: Accepted

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

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