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
#input = sys.stdin.readline
def main():
    N = int( input())
    A = list( map( int, input().split()))
    root = 1
    if A[0] == 1:
        if N == 0:
            print(1)
        else:
            print(-1)
        return
    B = A[::-1]
    low = high = B[0]
    # Low = []
    Hight = [high]
    
    for b in B[1:]:
        low = max(1, (low+1)//2) + b
        high = high + b
        Hight.append(high)
    if low > 1:
        print(-1)
        return
    ans = 1
    now = 1
    BHight = Hight[::-1]
    for i in range(1,N+1):
        if now == 0:
            print(-1)
            return
        h = BHight[i]
        leaf = A[i]
        # print("h",h)
        now = min(h, now*2)
        ans += now
        now -= leaf
        if now < 0:
            print(-1)
        # print(now)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    A = list( map( int, input().split()))
    root = 1
    if A[0] == 1:
        if N == 0:
            print(1)
        else:
            print(-1)
        return
    B = A[::-1]
    low = high = B[0]
    # Low = []
    Hight = [high]
    
    for b in B[1:]:
        low = max(1, (low+1)//2) + b
        high = high + b
        Hight.append(high)
    if low > 1:
        print(-1)
        return
    ans = 1
    now = 1
    BHight = Hight[::-1]
    for i in range(1,N+1):
        h = BHight[i]
        leaf = A[i]
        # print("h",h)
        now = min(h, now*2)
        ans += now
        now -= leaf
        # print(now)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

n=int(input())
A=list(map(int,input().split()))
now=1
s=sum(A)
ans=1
if n==0:
    if A[0]!=1:
        print(-1)
    else:
        print(1)
    sys.exit()
if A[0]!=0:
    print(-1)
    sys.exit()
for i in range(1,n+1):
    if A[i]>2*now:
        print(-1)
        sys.exit()
    if s>=2*now:
        ans+=2*now
        now=2*now-A[i]

    else:
        ans+=s
        now=s-A[i]
    s-=A[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
total = []
num = 0
for i in reversed(range(N+1)):
    num += A[i]
    total.append(num)
total.reverse()
if A[0] == 1 and N == 0:
    print(1)
    exit()
if A[0] != 0:
    print(-1)
    exit()
ans = 1
num = 1
for i in range(1,N+1):
    num = min(2*num, total[i])
    ans += num
    num -= A[i]
    if num < 0:
        print(-1)
        exit()
print(ans)

Submission status: Accepted

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

b = [1]
for i in range(n):
    tmp = b[i] - a[i]
    b.append(min(tmp * 2, a_min[i + 1]))
    if tmp < 1 or tmp * 2 < a[i + 1]:
        print(-1)
        break
else:
    if n == 0:
        ans = 1 if a[0] == 1 else -1
        print(ans)
    else:
        print(sum(b))

Submission status: Accepted

Solution code:
import math
import sys
a=int(input())
List=list(map(int,input().split()))
s=sum(List)
r=1
count=0
for i in range(a+1):
  count+=r
  r-=List[i]
  s-=List[i]
  if r<0:
    print(-1)
    sys.exit()
  r=min(s,2*r)
print(count)

Submission status: Accepted

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

# if a_l[0] != 0:
#     if n == 0 & a_l[0] == 1:
#         print(1)
#     else:
#         print(-1)
#     exit()

tree = [0]*(n+1)
tree[0] = 1
for i in range(1,n+1):
    tree[i] = (tree[i-1] - a_l[i-1]) * 2
# print(tree)

if tree[-1] < a_l[-1]:
    print(-1)
    exit()

# print(tree)
tree[-1] = a_l[-1]
for i in range(2,n+2):
    # print(i, tree[-i], tree[-(i-1)] + a_l[-i])
    if tree[-i] == tree[-(i-1)] + a_l[-i]:
        break
    else:
        tree[-i] = min(tree[-i], tree[-(i-1)] + a_l[-i])
    # print(tree)
# print(tree)

# while tree[-1] != a_l[-1]:
#     tree[-1] -= 1
#     i = 1
#     while True:
#         i += 1 
#         if tree[-(i-1)] >= (tree[-i] - a_l[-i]):
#             break
#         tree[-i] -= 1
# print(tree)

ans = 0
for val in tree:
    ans += val
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline

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

c = 1
ans = 1

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

# 数える
A = A[::-1]

cnt = A[0]
c = A[0]

can = [A[0]]

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

    if c > 2**(N - i):
        c = 2**(N - i)

    cnt += c
    can.append(c)

can = can[::-1]
A = A[::-1]

for i in range(1, N + 1):
    if can[i] > (can[i - 1] - A[i - 1]) * 2:
        can[i] = (can[i - 1] - A[i - 1]) * 2

print(sum(can) if A[-1] == can[-1] else -1)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
MAX = 10 ** 100

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

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


# ok[i] : 深さiの葉以外の頂点の最大数
ok = [1]
for i in range(1, n + 1):
    t = ok[i - 1] * 2 - A[i]
    if i < n and t <= 0:
        print(-1)
        exit()
    ok.append(min(t, MAX))

if ok[n] < 0:
    print(-1)
    exit()

ans = [0] * (n + 1)

ans[n] = A[n]
# 深さ[親]の許容範囲を超えないように、できるだけたくさん親を使う
for i in range(n, 0, -1):
    ans[i - 1] = min(ok[i - 1], ans[i]) + A[i - 1]
# ans[上] = min(ok[上]*2, (ans[今]+A[今]))//2

print(sum(ans))

# print(ok)
# print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
A = list(map(int,input().split()))
leaf= [-1 for i in range(N+1)]
notleaf = [-1 for i in range(N+1)]
flag=0

if N == 0 and A[0] == 1:
    print(1)
elif N==0 and A[0]!=1:
    print(-1)
elif N != 0 and A[0]>=1:
    print(-1)
else:
    leaf[0]=0
    notleaf[0]=1
    for d in range(1, N+1):
        leaf[d] = A[d]
        notleaf[d] = 2*notleaf[d-1] - leaf[d]
        if notleaf[d]<0:
            flag=1
            print(-1)
            break
    if flag == 1:
        pass
    else:
        sleaf = 0
        for i in range(N+1):
            sleaf += leaf[i]
        
        d1 = 0
        for i in range(N+1):
            d1 += (i+1) * leaf[i]
        
        sleaf -= 1
        for i in range(1,N+1):
            if sleaf>0:
                d1 -= i*( min(sleaf, leaf[i]+notleaf[i] - notleaf[i-1]))
                sleaf -= (leaf[i]+notleaf[i] - notleaf[i-1])
            else:
                break
        print(d1)

Submission status: Accepted

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

ans = 1
flag = 1

if N == 0:
    if s >= 2:
        flag = 0
    else:
        ans = 1
else:
    for i in range(N):
        e = (e - A[i]) * 2
        if e < A[i+1]:
            flag = 0
            break
        tmp = min(e, s)
        s -= A[i+1]
        ans += tmp
if flag == 0:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
isOK = True
B = [0]*(N+1)
B[0] = 1-A[0]
M = 1
i = 1
while i <= N:
  B[i] = B[i-1]*2-A[i]
  i += 1
if B[-1] < 0 or N > 0 and A[-1] == 0:
  isOK = False
B[-1] = A[-1]
i = N-1
while i >= 0:
  if B[i] < 1 or i > 0 and B[i] > B[i-1]*2:
    isOK = False
    break
  else:
    B[i] = min(B[i], B[i+1])+A[i]
  i -= 1
print(-1 if not isOK else sum(B))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
edge=[0]*(n+1)
ans=0
edge[0]=1
for i in range(1,n):
    edge[i]=edge[i-1]*2-a[i]
for i in range(n-1,-1,-1):
    bcnt=edge[i+1]+a[i+1]
    if bcnt//2+bcnt%2>edge[i]:
        ans=-1
        break
    if bcnt<edge[i]:
        edge[i]=bcnt
if n==0:
    if a[0]!=1:
        ans=-1
    else:
        edge[0]=0
elif a[0]>0:
    ans=-1
if ans!=-1:
    ans=sum(edge)+sum(a)
print(ans)

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):

    logical_max = [1]
    prev = 1
    for a in A:
        prev = (prev - a)*2
        logical_max.append(prev)
    for l in logical_max:
        if l < 0:
            print(-1)
            return

    logical_max = logical_max[:-1]


    nodes_at_depth = [0] * (N+1)
    d = N
    nodes = 0
    for lg_max, a in zip(logical_max[::-1], A[::-1]):

        nodes += a
        if nodes > lg_max:
            nodes = lg_max
            
        nodes_at_depth[d] = nodes
        d -= 1

    print(sum(nodes_at_depth))

    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()))
t = 1
c = [1-a[0]]+[1]*(n)
# print(c)
if n == 0 and a[0] > 1:
    print(-1)
    exit()
if a[0] == 1 and n >= 1:
    print(-1)
    exit()
for i in range(1,n+1):
    c[i] = c[i-1]*2-a[i]
    # print(i)
    if c[i] < 0:
        # print(c)
        print(-1)
        # print(c)
        exit()
# print(c)
c[n] = 0
m = a[n]
for i in range(n-1,-1,-1):
    # print(i)
    c[i] = min(c[i],m)
    m+=a[i]
# print(c)
print(sum(a)+sum(c))
# b = [0]*(n) + [a[-1]]
# for i in range(n-1,-1,-1):
#     b[i] = min(b[i+1]+a[i],2**(i))
# print(b)

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()
if n == 0:
    if a[0] == 1 or a[0] == 0:
        print(1)
        quit()
    else:
        print(-1)
        quit()
for i in range(n):
    if a[i] > 2**i - 1:
        print(-1)
        quit()
if a[-1] > 2**n:
    print(-1)
    quit()

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

i = n-1
tmp = a[-1]
ans = 0
lst2 = [a[-1]]
while i >= 0:
    tmp += a[i]
    tmp = min(tmp, 2**i)
    lst2.append(tmp)
    i -= 1
lst2 = lst2[::-1]
for i in range(n+1):
    ans += min(lst[i], lst2[i])
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    n_usable_child_list = [0 for _ in range(N + 1)]
    n_usable_child = 1 - A[0]
    for d in range(N):
        n_usable_child_list[d] = n_usable_child
        if n_usable_child < 0:
            print(-1)
            return
        n_usable_child = 2 * n_usable_child - A[d + 1]
    n_usable_child_list[-1] = n_usable_child
    if n_usable_child < 0:
        print(-1)
        return
    ans, cur = 0, 0
    for d in reversed(range(N + 1)):
        cur = min([cur, n_usable_child_list[d]]) + A[d]
        ans += cur
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
n_l = [1]
n = 1
A = [int(a) for a in input().split()]
for i in range(1,N+1):
    a = A[i-1]
    n = (n - a) * 2
    n_l.append(n)
    if n <= 0:
        Good = False
        break
if n >= A[N]:
    counter = A[N]
    m = A[N]
    Good = True
else:
    Good = False
if Good:
    for i in range(N-1,-1,-1):
        n = n_l[i]
        m = min(m+A[i],n)
        counter += m
    print(counter)
else:
    print(-1)

Submission status: Accepted

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

if n == 0:
    if l[0] == 1:
        print('1')
        sys.exit()
    else:
        print('-1')
        sys.exit()

if l[0]  != 0:
    print('-1')
    sys.exit()
    
count = 1
edge = 1
sum_ = sum(l)
for i in range(1,len(l)-1):
#     print(i-1, edge, count)

    sum_ -= l[i]
    
    if l[i] >= edge *2:
        print('-1')
        sys.exit()
    
    if edge * 2 - l[i] <= sum_:
        count += edge * 2
        edge = edge * 2 -l[i]
#         print(i, 'max', edge,count)
        continue

        
    if edge * 2 - l[i] > sum_:
        count += sum_ + l[i]
        edge = sum_
        
#         print(i, 'notmax', edge,count)
        continue

        
        
#n回目の処理
if not   l[len(l)-1] <= edge * 2:
    print('-1')
    sys.exit()
    
else:
    count +=   l[len(l)-1] 
print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
capacity = [1 for k in range(N+1)]
cut = 0
for k in range(N+1):
    #print(capacity)
    if A[k] >= capacity[k] and k!= N:
        print(-1)
        break
    if A[k] > capacity[k] and k == N:
        print(-1)
        break
    if k < N:
        capacity[k+1] = 2*(capacity[k] - A[k])
    if k == N:
        ans = [0 for k in range(N+1)]
        ans[0] =1
        sumA = 0
        for m in range(1, N+2):
            sumA += A[-m]
            ans[-m] = min(capacity[-m], sumA)
        print(sum(ans))

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque
inf = 10 ** 15
mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
preoya = 1
arieruoya = [0 for i in range(n+1)]
for i in range(n):
    arieruoya[i] = preoya
    l = a[i]
    if l > preoya*2-1:
        print(-1)
        sys.exit()
    preoya = min((preoya-l)*2,10**13)
if a[n] > preoya:
    print(-1)
    sys.exit()
arieruoya[n] = 0

a.reverse()
premax = a[0]
premin = (a[0]+1)//2
ans=premax
for i in range(1,n+1):
    l = a[i]
    premax = min(arieruoya[n-i], premax+l)
    ans+=premax
print(ans)

Submission status: Accepted

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

flag = True
for i in range(n):
    if a[i+1] != 0:
        flag = False
        break

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

nleaf = 1
ans = 0
v = list()

for i in range(n):
    nleaf -= a[i]
    v.append(nleaf)
    nleaf *= 2

if nleaf < a[n]:
    print(-1)
    exit()

nleaf = a[n]
ans += a[n]
for i in range(n-1, -1, -1):
    if v[i]*2 < nleaf:
        print(-1)
        exit()
    if v[i] > nleaf:
        v[i] = nleaf
    nleaf = v[i] + a[i]
    ans += nleaf
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
import bisect
from sys import exit
n = int(input())
A = list(map(int, input().split()))

coutner = 0
dp = dd(int)
dp[1] = 1
limit = [0] * (n + 1)
total = 0
for i in range(n, -1, -1):
    total += A[i]
    limit[i] = total
#print(limit)

"""
for depth in range(n):
    mov_dic = dd(lambda: 0)
    for now_num, total in dp.items():
        if now_num - A[depth] > 0:
            mov_dic[now_num - A[depth]] = total
    #print("mov_dic", mov_dic)

    dp = dd(int)
    mov_dic_keys = set(mov_dic.keys())
    for now_num, total in mov_dic.items():
        mov_dic_keys.remove(now_num)
        for next_num in range(now_num, min(now_num*2 + 1, limit[depth] + 1)):
            if now_num in mov_dic_keys:
                break
            dp[next_num] = max(total + next_num, dp[next_num])
    #print(limit[depth], "dp", dp)

if dp[A[-1]] == 0:
    print(-1)
else:
    print(dp[A[-1]])
"""

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

now_num = 1
now_total = 1
for depth in range(n):
    mov_num = now_num - A[depth]
    #print(mov_num)

    if mov_num > 0:
        now_num = min(mov_num * 2, limit[depth+1])
        now_total += now_num
    else:
        print(-1)
        exit()
if now_num == A[n]:
    print(now_total)
else:
    print(-1)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
node=[1 for _ in range(N+1)] #深さiで、葉にならない頂点の個数node[i]
S=sum(A) #生産しなければならない葉の枚数の合計
ans=1 #深さ0である根は最初にカウントする

#深さiの時点であと何枚の葉が必要か計算しつつ、必要な分だけノードを生産する
#ノードの個数がその時点でのSまで届いたら、あとは各頂点が1つずつノードを生産し、
#各層でA[i]個のノードが生産を止めて葉となる

for i in range(1,N+1): 
    if node[i-1]*2<=S: #葉の生産量はノードの2倍ずつ、ノルマを超えるまでは最速で生産する
        ans+=node[i-1]*2
        node[i]=node[i-1]*2
    elif node[i-1]<=S<node[i-1]*2: #全てのノードが2倍になるとノルマを過ぎてしまう場合はノルマピッタリで止める
        node[i]=S
        ans+=S
    node[i]-=A[i] #葉となるノード数を差し引き、生産に寄与するノード数にして次の層に引き継ぐ
    S-=A[i] #葉になった枚数だけノルマも減らす
    if node[i]<0: #生産が間に合わなかった場合(要求された葉＞生産可能なノード数)はループ停止
        ans=-1
        break

if A[0]>0: #深さ0に葉があったら基本的にアウトだが…
    ans=-1
if N==0 and A[0]==1: #N=0の時だけ、深さ0に葉が1つという状況が許される
    ans=1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())+1
a = list(map(int, input().split()))
m_node = [1]*n
node = 0
total = 0

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

for i in range(1, n):
    m_node[i] = (m_node[i-1] - a[i-1])*2
    if m_node[i] <= 0:
        print("-1", end="")
        exit()
for i in reversed(range(n)):
    if a[i] > m_node[i]:
        print("-1", end="")
        exit()
    node = min((node+a[i]), m_node[i])
    total += node

print(total, end="")

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
temp=1
summ=0
cont=0
templist=[1]
for i in range(N+1):
  #print(temp)
  if A[i]<temp:
    if i<N:
      summ+=temp
      temp=2*(temp-A[i])
      templist.append(temp)
    elif i==N:
      summ+=temp
      cont+=1
  elif A[i]==temp:
    if i==N:
      summ+=temp
      #templist.append(temp)
      cont+=1
    else:
      print("-1")
      break
  else:
    print("-1")
    break
    
if cont==1:
  if A[N]==temp:
  	print(summ)
  else:
    #print(templist)
    #print(A)
    comp=A[-1]
    for i in range(N):
      summ-=(templist[-(i+1)]-comp)
      comp+=A[-(i+2)]
      #print(comp)
      #print(templist[-(i+2)])
      #print(summ)
      if comp>templist[-(i+2)]:
        print(summ)
        break
      if i==N-1:
        print(summ)
        break

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

num = [0]*(N+1)  # 各層で葉を除いたとれるノードの限界

ma = 1
for i, a in enumerate(A):
	if i == N and a <= ma:
		num[i] = ma-a
	elif a <= ma-1:
		num[i] = ma-a
		ma = (ma-a)*2
	else:
		print(-1)
		exit()

tmp = 0
ans = 0
for i, a in enumerate(A[::-1]):
	d = N-i
	if tmp > num[d]:
		tmp = num[d]
	tmp += a
	ans += tmp

print(ans)

Submission status: Accepted

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

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

    # max node
    MN = [0 for _ in range(N)]
    MN[0] = 1
    for i in range(1, N):
        MN[i] = (MN[i-1] - A[i-1]) * 2
        if MN[i] <= 0:
            return -1

    if A[N-1] > MN[N-1]:
        return -1

    results = [0 for _ in range(N)]
    results[N-1] = A[N-1]
    if results[N-1] <= 0:
        return -1
    for i in range(N-2, -1, -1):
        results[i] += min(results[i+1] + A[i], MN[i])
        if results[i] <= 0:
            return -1

    return sum(results)

    # print(MI)
    # print(results)


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

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


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

maxs = [1]

for i in range(1,n+1):
    nex = maxs[i-1]*2 - a[i]
    maxs.append(nex)

if(maxs[n] < 0):
    print('-1')
    sys.exit()

results = [a[n]]

for i in range(n):
    if(results[i] > maxs[n-i-1]):
        results.append(maxs[n-i-1]+a[n-i-1])
    else:
        results.append(results[i]+a[n-i-1])


print(sum(results))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
depth = int(input()) 
leaves = list(map(int, input().split(" ")))
limited = []
limited_a = []

def solve (depth) :
    cur = 1
    i = 0 
    while i <= depth :
        limited_a.append( cur )
        if cur <= 0 and leaves[i] != 0 :
            return False
        cur=(cur-leaves[i])*2
        i+=1 
    
    _min = _max = 0
    i = depth
    while i >= 0 :
        if i==depth: 
            if leaves[i] > limited_a[i] :
                return False
            limited.append(leaves[i])
            _max = leaves[i]
            _min = (leaves[i]+1)//2
        else :
            _max = min(limited_a[i], _max+leaves[i])
            _min = (_min+leaves[i]+1)//2
            if _max < _min :
                return False 
            limited.append(_max)
        i -= 1
    return True

if solve(depth) :
    print(sum(limited))
else :
    print (-1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
if A[0] == 1 and N == 0:
    print(1)
    exit()
if A[0] != 0:
    print(-1)
    exit()
A.reverse()
B = []
ans = 0
num = 0
num2 = 0
for i in range(N+1):
    lim = 2**(N-i)
    if A[i] > lim:
        print(-1)
        exit()
    num = min(num+A[i],lim)
    B.append(num)
A.reverse()
B.reverse()
for i in range(N):
    num2 = B[i]-A[i]
    if num2*2 < A[i+1]:
        print(-1)
        exit()
    if num2*2 < B[i+1]:
        B[i+1] = num2*2
print(sum(B))

Submission status: Accepted

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

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

if v[N][0] != v[N][1]:
    print('-1')
    exit()

ans = 0

for a,b in v:
    if a <= 0:
        print('-1')
        exit()
    ans += a

print(ans)

Submission status: Accepted

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

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

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

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

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

if(2*(a-A[-2]) < A[-1]):
  print(-1)
  exit()
print(sum + A[-1])

Submission status: Accepted

Solution code:
#import numpy as np
#import math

#H1, M1, H2, M2, K = map(int, input().split())
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

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

sum_a = sum(A)
count = 1
root_num = 1
count_leaf = 0

def calc_node_num(leaf_num, root_num, count_leaf, count):
    count_leaf += leaf_num
    next_root_num = min(root_num*2-leaf_num, sum_a-count_leaf)
    count += (next_root_num + leaf_num)
    return next_root_num, count_leaf, count
    

if (N==0)&(A[0]>0)&(A[0]<=1):
    print(A[0])
elif (N==0)&(A[0]==0):
    print(-1)
elif (N==0)&(A[0]>1):
    print(-1)
else:
    for i in range(1,N+1):
        root_num, count_leaf, count = calc_node_num(A[i], root_num, count_leaf, count)
        if A[0]>0:
            print(-1)
            break
        if (i<N)&(root_num==0):
            print(-1)
            break
        if root_num < 0:
            print(-1)
            break
    else:
        print(count)

Submission status: Accepted

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

pa = 1
ch = 1
node = 0
flag = True
A_score = sum(A)

for d in range(N+1):
  pa = ch
  A_score -= A[d]
  if A_score >= (pa - A[d]) * 2:
    ch = (pa - A[d]) * 2
  elif (pa - A[d]) * 2 >= A_score:
    ch = A_score
  else:
    ch = pa - A[d]
  node += pa
  if ch < 0:
    flag = False

if flag:
  print(node)
else:
  print(-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()
if A[0] != 0:
    print(-1)
    exit()

#INF = 10**9
mxs = [1]
for a in A[1:]:
    p = mxs[-1]*2 - a
    if p < 0:
        print(-1)
        exit()
    mxs.append(p)

ans = p = A[-1]
for i in range(N-1,-1,-1):
    if mxs[i]+A[i] < (p+1)//2:
        print(-1)
        exit()
    n = min(p, mxs[i]) + A[i]
    ans += n
    p = n
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

if N == 0:
    if A_list[0] == 1:
        print(1)
    else:
        print(-1)
elif A_list[0] != 0:
    print(-1)
elif N == 1:
    if A_list[1] == 1 or A_list[1] == 2:
        print(A_list[1] + 1)
    else:
        print(-1)
else:
    ans = 1
    deathable_node = 1
    sum_rest_A = sum(A_list)
    for i in range(1, N + 1):
        now_A = A_list[i]
        deathable_node = min(sum_rest_A, deathable_node * 2) - now_A

        if deathable_node < 0:
            print(-1)
            break

        sum_rest_A -= now_A
        ans += deathable_node + now_A
#         print(i, now_A, sum_rest_A, deathable_node, ans)
#         if deathable_node == 0 and i != N:
#             print(-1)
#             break
    else:
        if deathable_node == 0:
            print(ans)
        else:
            print(-1)

Submission status: Accepted

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

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

B = dict()
sm = 0
for i in range(len(A)-1, -1, -1):
    sm += A[i]
    B[i] = sm


cnt = 1
roots = 1
for i in range(N):
    roots = roots * 2
    k = B[i+1]
    if roots > k:
        roots = k

    if roots - A[i+1] < 0:
        print("-1")
        exit()

    cnt += roots
    roots -= A[i+1]
print(cnt)

Submission status: Accepted

Solution code:
import math
n = int(input())
li = list(map(int,input().split()))

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

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

tmp = 1
for i,l in enumerate(li):
    if i == 0:
        continue
    tmp *= 2
    if l > tmp:
        print(-1)
        exit()
    else:
        tmp -= l

max_li = [1]
for i,l in enumerate(li):
    if i == 0:
        continue
    la = (max_li[-1]-li[i-1])*2
    max_li.append(la)


li.reverse()
ans = 0
codomo = li[0]
for i,l in enumerate(li):
    if i == 0:
        if l > 2**(n-i):
            print(-1)
            exit()
        else:
            ans += codomo
    else:
        tmp = codomo + l
        fin = min(min(2**(n-i),tmp),max_li[n-i])
        #print(min(2**(n-i),tmp),max_li[i],i,'i')
        ans += fin
        codomo = fin
    #print(ans,'ans')
print(ans)

Submission status: Accepted

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

max_v=[0 for _ in range(n+1)]

max_v[0]=1-a[0]
if(n==0 and a[0]==1):
    print(1)
    sys.exit()
elif(max_v[0]<=0 or a[-1]<=0):
    print(-1)
    sys.exit()
#print(0,max_v[0])

for i in range(1,n+1):
    max_v[i]=2*max_v[i-1] - a[i]
#    print(i,max_v[i])
    if(max_v[i]<=0 and i<n):
        print(-1)
        sys.exit()
#print(max_v)
ans=a[-1]
v=a[-1]
for i in range(n-1,-1,-1):
    if(v>2*max_v[i]):
        print(-1)
        sys.exit()
    v=min(v,max_v[i])
    v+=a[i]
    ans+=v
#    print(i,v,ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
P = [2**i for i in range(len(A))]
import sys
sys.setrecursionlimit(10**9)
# A = A[::-1]
# P = P[::-1]

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

if N==0 and A[0]==1:
    print(1)
    exit()
if A[0] > 0:
    print(-1)
    exit()
# if A[-1] > 2**N:
#     print (-1)
#     exit()

# for a,p in zip(A[::-1],P[::-1]):
#     if a > p:
#         print (-1)
#         exit()

ans = [0]
node = [0]
def rec(i):
    if i==0:
        ans[0]+=1
        return 1
    node[0] = node[0] + A[i]
    node[0] = min(node[0], 2*rec(i-1))
    ans[0] += node[0]
    #print (node[0],node[0]-A[i])

    if (i!=N and node[0] - A[i] <= 0) or (node[0] - A[i] < 0):
        print(-1)
        exit()
    return node[0] - A[i]
rec(N)
print (ans[0])