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
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): 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)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N  = I()
A = LI()
sum = [0]*(N+2)
sum[N] = A[N]
for i in range(N-1,-1,-1):
    sum[i] = sum[i+1]+A[i]

if N==0:
    if A[0]==1:
        print(1)
    else:
        print(-1)
else:
    if A[0]!=0:
        print(-1)
    else:
        ans = 1
        b = 1
        for i in range(1,N+1):
            a = A[i]
            b_ = sum[i+1]
            if b_<b-a or 2*b-a<0:
                print(-1)
                break
            b_ = min(b_, 2*b-a)
            ans += a+b_
            b = b_
        else:
            print(ans)

Submission status: Accepted

Solution code:
n = int(input())
 
a = list(map(int,input().split()))
 
cumsum_a = a.copy()
 
for i in range(n-1, -1, -1):
    cumsum_a[i] += cumsum_a[i+1]
 
ans = 0
node = 1
 
for i in range(n + 1):
    if a[i] > node:
        ans = -1
        break
 
    ans += node
 
    if i < n:
        node = min(2 * (node - a[i]), cumsum_a[i + 1])
 
print(ans)

Submission status: Accepted

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

A_sum = sum(A)
cnt = 1
tmp = 1

for a in A:
    A_sum -= a
    tmp = min((tmp - a) * 2, A_sum)
    cnt += tmp
    if tmp < 0:
        break

if tmp < 0:
    print(-1)
else:
    print(cnt)

Submission status: Accepted

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

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

    bound = [0] * (N+1)
    bound[0] = 1
    flag = True

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

    if not flag:
        print(-1)
        exit()

    B = [0] * (N+2)
    for i in range(N, -1, -1):
        tmp = min(bound[i], B[i+1] + A[i])
        B[i] = tmp

    print(sum(B))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    res = 0
    not_leaf = 1
    s = sum(A)
    count = 1
    for d in range(n + 1):
        res += not_leaf
        if not_leaf < A[d]:
            print(-1)
            return
        not_leaf -= A[d]
        add = min(s - count, not_leaf)
        count += add
        not_leaf += add

    print(res if not_leaf == 0 else -1)
resolve()

Submission status: Accepted

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

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

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


corr_flag = 1
if A[-1] > capacity[-1]:
    corr_flag = 0
curr = A[-1]
ans = A[-1]
for i in range(N-1, -1, -1):
    curr = min(capacity[i], A[i] + curr)
    ans += curr
if corr_flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

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

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

# 一番深いところから構築して最後にsumをとる
ans = [A[-1]]
now_leaf = A[-1]  # 一番深いところから構築しており，今現在の葉の数
for i in range(N-1, -1, -1):
    # print(A[i])
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]
# 構築したものに対してジャッジする, 葉を確保できているかどうか
for i in range(N):
    # ans[N-i]とすることで，今は一番浅いところから見ている
    if (ans[N-i]-A[i])*2 < A[i+1]:  # 葉が確保できているか
        print(-1)
        exit()
print(sum(ans))

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)

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

b=1
count=1
asum =sum(a)
alim = asum

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

        count += b

print(count+ asum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    suma = sum(a)
    ans = 0
    can = 1
    for i,ai in enumerate(a):
        if ai > can:
            print(-1)
            exit()
        suma -= ai
        ans += can
        if (can-ai)*2 >= suma:
            can = suma
        else:
            can = (can-ai)*2

    print(ans)




    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

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

S = list(accumulate(A))

ans = 1
cur = 1
for a, s in zip(A, S):
    if (cur := min(2 * (cur - a), S[-1] - s)) < 0:
        print(-1)
        quit()

    ans += cur

print(ans)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    whole = sum(a)

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
k=l[n]
count=1
sumleaf=1
flag=True
i0=0
suml=[]
for i in l:
    i0+=i
    suml.append(i0)
if l[0]>2 or l[0]==1 and n>=1:
    print(-1)
    flag=False
elif n==0 and l[0]!=1:
    print(-1)
    flag=False
    
else:
    for i in range(1,n+1):
        sumleaf*=2
        if i==n and sumleaf<k:
            flag=False
            print(-1)
            break
        elif i==n:
            count+=k
        else:
            if sumleaf<=l[i]:
                flag=False
                print(-1)
                break
            else:
                sumlnew=suml[n]-suml[i-1]
                count+=min(sumlnew,sumleaf)
                sumleaf=min(sumlnew,sumleaf)-l[i]
    
                    
                    
                    
                    
                
if flag==True:
    print(count)

Submission status: Accepted

Solution code:
n = int(input())

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

cumsum_a = a.copy()

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

ans = 0
childable_node = 1

for i in range(n + 1):
    if a[i] > childable_node:
        ans = -1
        break

    ans += childable_node

    if i < n:
        b_max1 = 2 * (childable_node - a[i])
        b_max2 = cumsum_a[i + 1]
        childable_node = min(b_max1, b_max2)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,*l=map(int,open(0).read().split())
e=[1]
for i in range(n): e+=[(e[-1]-l[i])*2]
a=t=0
for i in range(n,-1,-1):
  if l[i]>e[i]: print(-1); break
  t=min(l[i]+t,e[i]); a+=t
else: print(a)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    whole = sum(a)

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

s = sum(A)

ans = 1
cur = 1
for a in A:
    s -= a

    if (cur := min(2 * (cur - a), s)) < 0:
        print(-1)
        quit()

    ans += cur

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int,input().split()))
ans = [0]*(n+1)
ans[0] = 1
c_sum = [0]*(n+1)
c_sum[0] = arr[0]
for i in range(1,n+1):
    c_sum[i] = c_sum[i-1] + arr[i]
root = [0]*(n+1)
for d in range(n+1):
    if d==0:
        ans[d] = min(1,c_sum[-1])
    else:
        ans[d] = min(root[d-1]*2,(c_sum[-1] - c_sum[d-1]))
    root[d] = ans[d] - arr[d]
    if root[d] < 0:
        print(-1)
        exit()
print(sum(ans))

Submission status: Accepted

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

s = sum(A)

ans = 1
cur = 1
for a in A:
    s -= a

    cur = min(2 * (cur - a), s)
    if cur < 0:
        print(-1)
        quit()

    ans += cur

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)
 
if N == 0:
  if A[0] != 1:
    print(-1)
  else:
    print(1)
  exit()
 
ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
cir = 1
bsum = 1
hantei=0
asum = [0 for i in range(n+1)]
asum[0] = sum(a)
for i in range(1,n+1):
    asum[i] = asum[i-1]-a[i]
#print(asum)
swi = 0
for i in range(n):
    if swi == 1:
        #print(cir,a[i])
        cir = cir-a[i]
    if swi==0:
        if (cir-a[i])*2 < asum[i]:
            cir = (cir-a[i])*2
        else:
            cir = asum[i]
            swi = 1

    bsum += cir
    if cir<=0:
        hantei=1
        break


#print(cir,a[-1])


if hantei==1 or cir!=a[-1]:
    print(-1)
else:
    print(bsum)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())

A = [int(i) for i in input().split()]

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

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

#print(nodes)

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

#print(nodes)

print(sum(nodes))

Submission status: Accepted

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

ans = 0
cnt = sum(a)
node = 1

for i in range(n + 1):
    ans += node
    cnt -= a[i]
    node = min(cnt, (node - a[i]) * 2)

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

print(ans)

Submission status: Accepted

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

v=[1]
for q in a:
    tot-=q
    v.append(min(2*(v[-1]-q),tot))
    
if all([u>=0 for u in v]):
    print(sum(v))
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import accumulate
n, *A = map(int, open(0).read().split())
if A[0] != 0:
    if A[0] == 1 and n == 0:
        print(1)
    else:
        print(-1)
else:
    B = list(accumulate(A[::-1]))[::-1]
    C = [1] * (n+1)
    D = [1] * (n+1)

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

Submission status: Accepted

Solution code:
def main():
  input()
  in_a = list(map(int, input().split()))
  leaves = [0] * len(in_a)
  leaves[-1] = in_a[-1]

  if in_a[0] > 1:
    print(-1)
    return

  #for i in range(len(in_a)-2, -1, -1):
  #  leaves[i] = leaves[i+1] + in_a[i]

  for i in range(len(in_a) - 1, 1, -1):
    leaves[i-1] = leaves[i] + in_a[i-1]
    
  node = 1
  total = 1
  
  for i in range(1, len(in_a)):
    n = (node - in_a[i-1]) * 2

    if n < in_a[i]:
        print(-1)
        return

    node = min(n, leaves[i])
    total += node

  print(total)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  n = int(input()) + 1
  a = [int(x) for x in input().split()]
  q = [0] * n
  for i in range(n):
    q[i] = (q[i - 1] - a[i - 1]) * 2 if i != 0 else 1
    # print(q[i])
    if q[i] <= 0:
      print(-1)
      return
  
  if q[n - 1] < a[n - 1]:
    print(-1)
    return
  q[n - 1] = a[n - 1]
  s = q[n - 1]
  # print('--')
  # print(q[n - 1])
  for i in range(n - 2, -1, -1):
    q[i] = min(q[i], q[i + 1] + a[i])
    if q[i] == 0:
      print(-1)
      return
    # print(q[i])
    s += q[i]
  print(s)

main()

Submission status: Accepted

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


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

    v = [tuple() for _ in range(N + 1)]
    v[N] = (A[N], A[N])

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

    for i in range(N - 1, -1, -1):
        low, up = v[i + 1][0], v[i + 1][1]
        up = min(2 ** i, up + A[i])
        if low % 2 == 0:
            low = low // 2 + A[i]
        else:
            low = low // 2 + A[i] + 1
        v[i] = (low, up)

    # print(v)
    for i in range(N):
        low, up = v[i][0], v[i][1]
        low = max(v[i + 1][0], low - A[i])
        up = min(v[i + 1][1], (up - A[i]) * 2)
        v[i + 1] = (low, up)

    ans = 0
    for i in range(N + 1):
        if v[i][0] > v[i][1]:
            print('-1')
            exit()
        ans += v[i][1]

    # print(v)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    if N == 0 and A[0] > 1:
        print(-1)
        return 0
    low, high = A[N], A[N]
    maxN = [0] * (N + 1)
    maxN[N] = A[N]
    Limit = [2 ** 50] * (N + 1)
    Limit[N] = A[N]

    for i in reversed(range(N)):
        leaf = A[i]
        Limit[i] = min(Limit[i], Limit[i+1] + leaf)
        if i <= 50: Limit[i] = min(pow(2, i), Limit[i])
        low = (low + 1) // 2 + leaf
        high += leaf
        if low > Limit[i]:
            print(-1)
            break
        else: 
            maxN[i] = min(high, Limit[i])
    else:
        for i in range(N):
            if (maxN[i] - A[i]) * 2 <= maxN[i+1]: maxN[i + 1] = (maxN[i] - A[i]) * 2
        print(sum(maxN))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
  input()
  in_a = list(map(int, input().split()))
  leaves = [0] * len(in_a)
  leaves[-1] = in_a[-1]

  if in_a[0] > 1:
    print(-1)
    return

  for i in range(len(in_a)-2, -1, -1):
    leaves[i] = leaves[i+1] + in_a[i]

  node = 1
  total = 1
  
  for i in range(1, len(in_a)):
    n = (node - in_a[i-1]) * 2

    if n < in_a[i]:
        print(-1)
        return

    node = min(n, leaves[i])
    total += node

  print(total)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

ans = 0

leaves = sum(A)
node_num = 1

for i in range(N+1):
    if A[i] > node_num:
        print(-1)
        exit()
    ans += min(node_num, leaves)

    leaves -= A[i]
    node_num -= A[i]
    node_num *= 2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = a[::-1]

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

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

ans = ans[::-1]

ans = ans[1::]
a = a[1::]

res = 1
prev_cnt = 1

for i in range(n):
    cnt = min(prev_cnt * 2, ans[i] + a[i])
    if cnt < a[i]:
        print(-1)
        exit()
    res += cnt
    prev_cnt = cnt - a[i]
print(res)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

else:
    pN=1
    s=1
    l=[]
    S=sum(a)
    b=0
    z=1
    for k in range(len(a)):
        b+=a[k]
        l.append(b)

    for i in range(1,n+1):
        if a[i]>2*pN:
            print(-1)
            z=0
            break
        else:
            pN=min(2*pN-a[i],S-l[i])
            s+=pN
    s+=S
    if n==0:
        s=1
    if a[0]==1 and n>=1:
            print(-1)
            z=0

    if z:
        print(s)

Submission status: Accepted

Solution code:
def main():
  input()
  A = list(map(int, input().split()))
  cusum = [0] * len(A)
  cusum[-1] = A[-1]

  if A[0] > 1:
    print(-1)
    return

  for i in range(len(A)-2, -1, -1):
    cusum[i] = cusum[i+1] + A[i]

  pre_node = 1
  ans = 1
  for i in range(1, len(A)):
    node = (pre_node - A[i-1]) * 2

    if node < A[i]:
        print(-1)
        return

    pre_node = min(node, cusum[i])
    ans += pre_node

  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

s = 1
if n == 0:
    if a[0] != 1:
        print(-1)
        quit()
    else:
        print(1)
        quit()
elif a[0] > 0:
    print(-1)
    quit()
memo = [[0,0] for _ in range(n+1)]
memo[0] = [0,1]
for i in range(1,n+1):
    if s == 0:
        print(-1)
        quit()
    s = memo[i-1][1]*2
    if s > 10**15:
        s = 10**15
    memo[i][0] = a[i]
    memo[i][1] = s-a[i]
    if s-a[i] < 0:
        print(-1)
        quit()
ans = [[a[i],0] for i in range(n+1)]
for i in range(n-1,-1,-1):
    if (ans[i+1][0]+ans[i+1][1]) > memo[i][1]*2:
        print(-1)
        quit()
    else:
        ans[i][1] = min(memo[i][1],ans[i+1][0]+ans[i+1][1])
s = 0
for i in range(n+1):
    s += sum(ans[i])
print(s)

Submission status: Accepted

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

ans = 1
L = [0]*(N+2)
for i in range(N+1):
    L[i+1] = L[i]+A[i]

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

print(ans)

Submission status: Accepted

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


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

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

    if N == 0:
        print('1')
        exit()

    v = [0 for _ in range(N + 1)]
    v[N] = A[N]

    for i in range(N - 1, -1, -1):
        up = min(2 ** i, v[i + 1] + A[i])
        v[i] = up

    # print(v)
    for i in range(N):
        up = min(v[i + 1], (v[i] - A[i]) * 2)
        v[i + 1] = up

    # print(v)
    ans = 0
    for i in range(N + 1):
        if v[i] < A[i]:
            print('-1')
            exit()
        ans += v[i]

    # print(v)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

ans = 0
v = 1  # 子になれる頂点数
for i in range(N+1):
    if v < A[i]:
        ans = -1
        break

    ans += v
    p = v-A[i]
    if i < N:
        v = min(Asum[i+1], 2*p)

print(ans)

Submission status: Accepted

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

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

ans = 0
v = 1  # 子になれる頂点数
for i in range(N+1):
    if v < A[i]:
        ans = -1
        break

    ans += v
    p = v-A[i]
    if i < N:
        if p > Asum[i+1]:
            ans = -1
            break
        v = min(Asum[i+1], 2*p)

print(ans)

Submission status: Accepted

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

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

ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)

Submission status: Accepted

Solution code:
def main():
    import sys
    import math
    input = sys.stdin.buffer.readline
    n = int(input())
    A = list(map(int, input().split()))
    ans = 0
    node = 1
    max_node = sum(A)
    for i in range(n+1):
        ans += node
        max_node -= A[i]
        node = min(max_node,(node-A[i])*2)
        if node < 0:
            print(-1)
            exit(0)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    if((len(A) != 1 and A[0] != 0) or (len(A) == 1 and A[0] != 1)):
        print(-1)
        return

    # Init
    node_num = 0
    next_node_w_children = 1
    next_node_num = 1
    
    for i in range(N+1):
        node_in_the_dept = next_node_num
        node_w_children = next_node_w_children      

        if(i == N):
            node_num += node_in_the_dept
            print(node_num)
        else:
            next_leaf_num = A[i+1]
            all_leave_num -=A[i]

            next_node_num = min(2 * node_w_children, all_leave_num)
            next_node_w_children = next_node_num - next_leaf_num
            if(next_node_num > node_w_children * 2 or next_node_num < node_w_children or next_node_w_children < 0):
                print(-1)
                return
            node_num += node_in_the_dept
    

main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A  = [int(_n) for _n in input().split()]
    if N == 0:
        print(1 if A[0]==1 else -1)
        return

    l = A[-1]
    L = [(1,1)]
    for i in range(1,N):
        L.append((A[i]+1, (L[i-1][1]-A[i-1])*2))
        if (L[i-1][1]-A[i-1])*2 < A[i]:
            print(-1)
            return
    L.append((A[N], (L[N-1][1]-A[N-1])*2))
    # print(L)
    if (L[N-1][1]-A[N-1])*2 < A[N]:
        print(-1)
        return
    
    R = [(A[-1],A[-1])]
    for i in reversed(range(N)):
        R.append(((R[-1][0]+1)//2+A[i], R[-1][1]+A[i]))
    res = 0
    for i in range(N+1):
        r = R[i]
        l = L[N-i]
        if r[0] > l[1] or r[1] < l[0]:
            print(-1)
            return
        # print(r,l)
        res += min(r[1], l[1])
    print(res)

        
main()

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys

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

revA = reversed(A)
ans = 0

l = list(accumulate(revA))
l.reverse()

for i in range(N+1):
    l[i] = min(l[i], 2**i)

for i in range(N+1):
    if i == N:
        if l[i] < A[i]:
            print(-1)
            sys.exit()
    else:
        l[i+1] = min(l[i+1], (l[i]-A[i])*2)

for v in l:
    if v > 0:
        ans += v
    else:
        ans = -1
        break


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
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    def min2(x, y): return x if x <= y else y

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

    if N == 0:
        if As[0] == 1:
            return 1
        else:
            return -1

    pow2 = 1
    pow2s = [pow2]
    for d in range(61):
        pow2 *= 2
        pow2s.append(pow2)
    pow2s += [pow2] * N
#    print('pow2s:', pow2s)

    maxV = min2(1, 1-As[0])
    maxVs = [maxV]
    for d in range(1, N+1):
        maxV = min2(maxV*2, pow2s[d]) - As[d]
        maxVs.append(maxV)
#    print('maxVs:', maxVs)

    numVs = [0] * (N+1)
    numVs[N] = As[N]
    for d in reversed(range(N)):
#        print('\n##### d:', d)
        numC2 = -(-numVs[d+1] // 2)
#        print('numC2:', numC2)
        if maxVs[d] < numC2:
            return -1
        num = min2(maxVs[d], numVs[d+1])
        numVs[d] = As[d] + num
#        print('As[d]:', As[d], '/ num:', num, '/ numVs[d]:', numVs[d])
        if numVs[d] > pow2s[d]:
            return -1

#    print('numVs:', numVs)
    return sum(numVs)


ans = solve()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ma1 = [1]*n
ma2 = [0]*n
mi2 = [0]*n

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

for i in range(1,n):
    ma1[i]=ma1[i-1]*2-a[i]
    if ma1[i]<0:
        print(-1)
        exit()
if n == 1:
    if a[0]==1:
        print(-1)
        exit()
    if a[0]==0:
        if a[1]==1:
            print(2)
            exit()
        elif a[1]==2:
            print(3)
            exit()
        else:
            print(-1)
            exit()

ma2[n-1]=a[n]
ma2[n-2]=ma2[n-1]
mi2[n-1]=a[n]
mi2[n-2]=mi2[n-1]//2 + mi2[n-1]%2
if n!=2:
    for i in range(2,n):
        ma2[n-1-i]=min(ma2[n-i]+a[n-i+1],2**(n-i)-a[n-i])
        mi2[n-1-i]=(mi2[n-i]+a[n-i+1])//2 + (mi2[n-i]+a[n-i+1])%2
        if mi2[n-1-i]>ma2[n-1-i]:
            print(-1)
            exit()
ma2 = [1]+ma2
ans = 0
for i in range(n):
    ans += min(ma1[i],ma2[i])
ans +=sum(a)

print(ans)

Submission status: Accepted

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

ans, cnt, node = 0, sum(a), 1
for i in range(n + 1):
    ans += node
    cnt -= a[i]
    node = min(cnt, (node - a[i]) * 2)
    if node < 0:
        print(-1)
        break
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
cusum = [0 for i in range(N+1)]
cusum[N] = A[N]

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

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

# print(cusum)
pre_node = 1
ans = 1
for i in range(1, N+1):
    node = (pre_node - A[i-1]) * 2
    if node < A[i]:
        ans = -1
        break
    pre_node = min(node, cusum[i])
    ans += pre_node
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
elif A[0] != 0:
    print(-1)
    exit()

leaf = A
not_leaf = [0] * (N + 1)
not_leaf[0] = 1

for i, a in enumerate(A[1:-1], 1):
    not_leaf[i] = not_leaf[i - 1] * 2 - a

for i in reversed(range(1, N + 1)):
    total = not_leaf[i] + leaf[i]
    prev = not_leaf[i - 1]
    if prev > total:
        not_leaf[i - 1] -= prev - total
    if not_leaf[i - 1] * 2 < total:
        print(-1)
        break
else:
    print(sum(leaf) + sum(not_leaf))