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:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def make_top_constraints(n, L):
        top_c = [tuple() for _ in range(n+1)]
        top_c[0] = (1, 1)    # 確定
        for i in range(1, n+1):
            # 上が取りうる最小ノードで、そこから葉を除いたノードたちから 1 本しか伸びていないケース
            minimum = max(top_c[i-1][0] - L[i-1], 0)    # さすがに 0 以上
            # 上が取りうる最大ノードで、そこから葉を除いたノードたちから 2 本ずつ伸びているケース
            maximum = max((top_c[i-1][1] - L[i-1]) * 2, 0)
            top_c[i] = (minimum, maximum)
        return top_c


    def make_bottom_constraints(n, L):
        bottom_c = [tuple() for _ in range(n+1)]
        bottom_c[n] = (L[n], L[n])    # 確定
        for i in range(n-1, -1, -1):
            # 下が取りうる最小ノードで、そこから 2 本合流 + この深さの葉
            minimum = bottom_c[i+1][0] // 2 + L[i]
            # 下が取りうる最大ノードで、そこから 1 本ずつ親に向かって伸びる + この深さの葉
            maximum = bottom_c[i+1][1] + L[i]
            bottom_c[i] = (minimum, maximum)
        return bottom_c


    def max_cross_num(L1, L2):
        left = max(L1[0], L2[0])
        right = min(L1[1], L2[1])
        if left > right:
            return -1
        else:
            return right


    def calc_max_node(n, top_down_constraints, bottom_up_constraints):
        cnt = 0
        for i in range(n+1):
            num = max_cross_num(top_down_constraints[i], bottom_up_constraints[i])
            # print(f"i:{i} node_num:{num}")
            if num < 0:
                return -1
            cnt += num
        return cnt
    
    
    n = ii()
    L = lmi()

    # constraints from d=0
    top_down_constraints = make_top_constraints(n, L)
    # constraints from d=n
    bottom_up_constraints = make_bottom_constraints(n, L)

    # print(top_down_constraints)
    # print(bottom_up_constraints)

    print(calc_max_node(n, top_down_constraints, bottom_up_constraints))


if __name__ == "__main__":
    main()

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

max_e = sum(a)
if(max_e > 2**n):
    print(-1)
    exit()

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

for i,leaf in enumerate(a):
    if(i==0):
        continue

    not_leaf[i] = min(not_leaf[i-1]*2, max_e) - leaf
    if(not_leaf[i] < 0):
        print(-1)
        exit()
    max_e -= leaf

ans = sum(a) + sum(not_leaf)
print(ans)

Submission status: Accepted

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

if '__main__' == __name__:
    main()

Submission status: Accepted

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

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

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

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

NODE=[0]*(N+5)
NODE[0]=1
rest=1
ANS=0
ind=0

for i in range(N+1):
    #print(i,ANS,NODE)
    if A[i]>rest:
        print(-1)
        sys.exit()

    else:
        x=A[i]
        while x:
            if NODE[ind]<=x:
                ANS+=(i-ind+1)*NODE[ind]
                x-=NODE[ind]
                rest-=NODE[ind]
                NODE[ind]=0
                ind+=1
            else:
                ANS+=(i-ind+1)*x
                NODE[ind]-=x
                rest-=x
                x=0

        NODE[i+1]=rest
        rest*=2
        if rest>10**20:
            rest=10**20

print(ANS)

Submission status: Accepted

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

zanki = 1
ans = 1
for i in range(N+1):
    zanki -= A[i]
    if zanki < 0:
        print(-1)
        sys.exit()
    if zanki == 0 and i != N:
        print(-1)
        sys.exit()
    zanki *= 2
    if i < N and zanki >= C[i+1]:
        zanki = C[i+1]
    ans += zanki
print(ans)

Submission status: Accepted

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

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

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

ret = a[-1]
suc = a[-1]
for i_ in range(n):
    i = n-1-i_
    ret += min(suc,par[i]) + a[i]
    suc = min(suc,par[i]) + a[i]

print(ret)

Submission status: Accepted

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

n = int(input())
a = [int(i) for i in input().split()]
maxNode = 1
total = 0
b = a[:]
for i in range(n, 0, -1):
	b[i - 1] += b[i]
for i in range(n + 1):
	maxNode = min(maxNode, b[i])
	if maxNode == 0 or maxNode < a[i]:
		print(-1)
		exit(0)
	total += maxNode
	maxNode = (maxNode - a[i]) * 2 
print(total)

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

bunki=sum(A)-1

ans=[0]*(N+1)
ans[0]=1

for i in range(N):
    if bunki>0:
        bunki_use=min(bunki,ans[i]-A[i])
        bunki-=bunki_use
        ans[i+1]=ans[i]+bunki_use-A[i]
    else:
        ans[i+1]=ans[i]-A[i]

    if ans[i+1]<1:
        print(-1)
        exit()

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

print(sum(ans))

Submission status: Accepted

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

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

if not_in[N] > 2 ** N:
  print(-1)
else:
  in_num = 0
  up = A[N]
  for i in range(N-1,-1,-1):
    in_temp = min(2 ** i - not_in[i], up)
    in_num += in_temp
    up = in_temp + A[i]
  print( in_num + sum(A) )

Submission status: Accepted

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

now = 1
allows = []
for i in range(n):
    ha = a[i]
    if ha > now:
        print(-1)
        exit()
    allows.append(now - ha)
    now = (now - ha) * 2
if now < a[n]:
    print(-1)
    exit()
result = a[n]
now = a[n]
for i in range(n):
    if now > allows[n-1-i]:
        now = allows[n-1-i]
    now = now + a[n-1-i]
    result += now
print(result)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

def solve():
    n = getN()
    nums = getList()
    # 1段しかない
    if n == 0:
        if nums[0] == 1:
            print(1)
        else:
            print(-1)
        return
    # 1段目で終わり(かなしいね)
    if nums[0] > 0:
        print(-1)
        return

    acc = []
    tmp = 0
    for i , num in enumerate(nums[::-1]):
        tmp += num
        acc.append(tmp)
    acc.reverse()

    ans = 1
    ue = 1
    for i, num in enumerate(nums[1:-1]):
        if ue * 2 <= num:
            print(-1)
            return
        konodan = min(ue * 2, acc[i+1])
        # print(konodan)
        ans += konodan
        ue = konodan - num

    if ue * 2 < nums[-1]:
        print(-1)
        return

    print(ans + nums[-1])
    return


def main():
    # n = getN()
    # for _ in range(n):
    solve()
if __name__ == "__main__":
    solve()

"""
    12
    3 2
    3 2
    0 1
    2 -1
    -3 -9
    -8 12
    7 0
    8 1
    8 2
    8 4
    0 0
    0 0
"""

Submission status: Accepted

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    # QUERYS = [input().split() for _ in range(Q)]
    # H1, M1, H2, M2, K = [int(a) for a in input().split()]
    A = [int(a) for a in input().split()]
    # T1, T2, T3 = [int(a) for a in input().split()]

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

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

    s = []
    t = 0
    for a in reversed(A):
        s.append(t)
        t += a
    s = list(reversed(s))

    res = 1
    nodes = 1

    for i in range(1, N + 1):
        max_nodes = nodes * 2
        nokori = s[i]
        leafs = A[i]
        if leafs > max_nodes:
            print(-1)
            return
        not_leafs = min(max_nodes - leafs, nokori)
        res += not_leafs + leafs
        nodes = not_leafs
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(hoge) for hoge in input().split()]
nodemax = []
cur = 0
for a in reversed(A):
    cur += a
    nodemax.append(cur)
nodemax = list(reversed(nodemax))#nodemax[d] d段目に存在できるノードのmax
ans = 1
curnode = 1
for n,a in enumerate(A):
    #n+1段目に生やすノード
    nothappa = curnode - A[n]#生やすリスト
    if n!=N:
        if nothappa <= 0:
            ans = -1
            break
        else:
            nextnode = min(nodemax[n+1],nothappa*2)
            ans += nextnode
            curnode = nextnode
    else:
        if nothappa !=0:
            ans = -1
print(ans)

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()))
    s = sum(A)

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

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

    not_leaf = 1
    # check
    for d in range(n + 1):
        if not_leaf < A[d]:
            print(-1)
            return
        not_leaf -= A[d]
        not_leaf *= 2

    res = 0
    not_leaf = 1
    count = 1 # 枝分かれの個数、最大 s
    for d in range(n + 1):
        not_leaf -= A[d]
        # 最大で not_leaf 個、枝分かれを増やせる
        add = min(s - count, not_leaf)
        count += add
        not_leaf += add
        res += not_leaf
        # print(d, add)

    print(res + 1)
resolve()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()

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

    m = [1] * (N + 1)
    m[-1] = A[-1]
    for i in range(N, 0, -1):
        m[i - 1] = (m[i] + 1) // 2 + A[i - 1]
    
    res = 0
    t = 0
    for i in range(N, -1, -1):
        if M[i] <= 0:
            print(-1)
            return

        t = min(t + A[i], M[i])
        if t < m[i]:
            print(-1)
            return

        res += t

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
l=[0]*(N+1)
l[-1]=A[-1]
for i in range(N-1,0,-1):
    l[i]=A[i]+l[i+1]
t=1
a=1
ma=10**15
for i in range(1,N+1):
    if 2*t<A[i]:
        a=-1
        break
    t=min(t*2,l[i])
    a+=t
    t-=A[i]
if A[0]!=0:
    a=-1
if N==0 and A[0]==1:
    a=1
print(a)

Submission status: Accepted

Solution code:
d,l = [list(map(int, s.split())) for s in open(0)]
d = d[0]

ans = 0
v_max = [1]
for i in range(d+1):
    if v_max[i] - l[i] < 0:
        ans = -1
        break
    v_max.append((v_max[i] - l[i])*2)
else:
    _max = 0
    for i in range(d, -1, -1):
        _max = min(_max + l[i], v_max[i])
        ans += _max
print(ans)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	Lmin = [0] * (N + 1)
	Lmax = [0] * (N + 1)
	Lmin[-1] = A[-1]
	Lmax[-1] = A[-1]
	for i in range(N - 1, -1, -1):
		if Lmin[i + 1] % 2 == 0:
			Lmin[i] = A[i] + int(Lmin[i + 1] // 2)
		else:
			Lmin[i] = A[i] + int(Lmin[i + 1] // 2) + 1
		
		Lmax[i] = Lmax[i + 1] + A[i]

	# print(Lmin)
	# print(Lmax)

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

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

	# print(Node)
	print(sum(Node))


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from sys import exit

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

sm = sum(a)
ans = 1

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

if a[0] != 0 or a[n] == 0:
  print(-1)
  exit()
  
s = 1
for i in range(1, n+1):
  if a[i] > s * 2:
    print(-1)
    exit()
  s = min(s*2, sm)
  ans += s
  sm -= a[i]
  s -= a[i]
  
print(ans)

Submission status: Accepted

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

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

li1 = [1]
for i in range(N):
    # if li1[-1]>=10**20:
    #     li1.append(10**20)
    # else:
    li1.append(min(10**15,2*li1[-1]-A[i]*2))

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

ans = 0
li3 = []
for i in range(N+1):
    ans += min(li1[i],li2[i])
    li3.append(ans) 
    if li1[i]<A[i]:
        print(-1)
        break
else:
    print(ans)



# print(*li1)
# print(*li2)
# print(ans)

# print(ans)






# if :
#     print("Yes")
# else:
#     print("No")

Submission status: Accepted

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

accR = reversed(list(accumulate(reversed(As))))
num = 1
MAX = 10 ** 13
ans = 0
for a, limit in zip(As, accR):
    tmp = min(num, limit)
    if a > tmp:
        print(-1)
        exit()
    ans += tmp
    num = (tmp - a) * 2
    if num >= MAX:
        num = MAX
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()
    
    if n==0 and aa[0]!=1:
        print(-1)
        exit()

    if n>0 and aa[0]>0:
        print(-1)
        exit()

    node=[0]*(n+1)
    node[0]=1
    node[n]=aa[n]

    for i in range(n-1,0,-1):
        a=aa[i]
        if a>(1<<i):
            print(-1)
            exit()

        node[i]=min(1<<i,node[i+1]+aa[i],((1<<(i-1))-aa[i-1])*2)

    #print(node)

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

    if node[n]!=aa[n]:
        print(-1)
        exit()
    #print(node)
    print(sum(node))


main()

Submission status: Accepted

Solution code:
def task(n, a):
    mxs = []
    current = 1

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

        if current < 0:
            print(-1)
            return

    # print(mxs)

    v = 0
    nodes = 0
    for i in reversed(range(0, n + 1)):
        nodes = min(nodes + a[i], mxs[i])
        v += nodes

    print(v)


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

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:
from math import gcd

from math import factorial as f

from math import ceil,floor,sqrt
import math

import bisect
import re
import heapq


from copy import deepcopy
import itertools
from itertools import permutations

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


yes = "Yes"
no = "No"


def main():
    n = ii()
    a = li()
    if n!=0 and a[0]!=0:
        print(-1)
        exit()
    if n == 0 and a[0]!=1:
        print(-1)
        exit()
    M = 1
    m = 1
    flag = True
    mlist = []
    for i in range(n+1):
        mlist.append(M)
        if a[i]>M:
            flag = False
            break
        M-=a[i]
        M*=2
    if not flag:
        print(-1)
        exit()
    mlist.append(0)

    ans = 0
    tmp = 0
    #print(mlist)

    for _ in range(n+1):
        i = n-_
        #print(i,ans,tmp)
        tmp = min(tmp,mlist[i+1])
        ans+=tmp
        tmp +=a[i]
        #print(i,ans,tmp)
    print(ans+1)




main()

Submission status: Accepted

Solution code:
N = int(input())

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

c = 1
M = [] #（葉でない）子ノードの数の最大値
INF = 10**16
for a in A:
    c -= a
    M.append(c)
    c *= 2

    c = min(INF, c)
    
if c < 0:
    print(-1)
else:
    cnt = A[-1]
    num = A[-1]
    for a,m in zip(reversed(A[:-1]),reversed(M[:-1])):
        n = min(num, m)
        cnt += n+a
        num = n+a
    print(cnt)

Submission status: Accepted

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

N = int(input())
A = list(map(int, (input().split())))
tmp = sum(A)
root = 0
ans = 0
for i in range(N+1):
    if i==0:
        mx = 1
    else:
        mx = root*2
    if A[i] > mx:
        ans = -1
        break
    root = min(tmp, mx) - A[i]
    tmp -= A[i]
    ans += root + A[i]

print(ans)

Submission status: Accepted

Solution code:
from sys import exit
def log2(x):
    ans = 0
    while(x):
        x //= 2
        ans += 1
    return ans

n = int(input())
n += 1
a = list(map(int, input().split()))
cnt = 1
ans = 0
s = [0 for i in range(n)]
s[-1] = a[-1]
for i in range(n - 2, -1, -1):
    s[i] = s[i + 1] + a[i]
for i in range(n):
    cnt = cnt * 2 - a[i] * 2
    if (i + 1 < n):
        ans += min(cnt, s[i + 1])
if (cnt < 0):
    print(-1)
    exit(0)
print(ans + 1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = []
now = 1
ans = 1

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

for a in A[1:]:
    now *= 2
    now -= a
    ans += a
    if now < 0:
        print(-1)
        exit()
    B.append(now)

cnt = A[-1]
for a, b in zip(A[:-1][::-1], B[:-1][::-1]):
    if cnt <= b:
        ans += cnt
    else:
        cnt = b
        ans += cnt
    cnt += a
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def div_cnt(n):
    res = 0
    while(n):
        n/=2
        res += 1
    return res
def ok(D):
    for i,d in enumerate(D):
        if(div_cnt(d) > i+1):
            return False
    return True
def main():
    N=I()
    D=LI()
    D_rev = D[::-1]
    up = 10**18
    B = [1]*(N+1) #その深さに存在出来る点の数
    for i in range(N):
        B[i + 1] = min(up, (B[i]-D[i]) * 2) 
    # print(B)
    B_rev = B[::-1]

    ans = 0
    now = 0
    for i,a in enumerate(D_rev):
        if(a>B_rev[i]):
            print(-1)
            return 
        now += a
        now = min(now, B_rev[i])
        ans += now
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
leaves = list(map(int, input().split()))
rest_leaves = [0 for i in range(n+2)]
for i in range(n, -1, -1):
	rest_leaves[i] = rest_leaves[i+1] + leaves[i]
# print("rest_leaves", rest_leaves)


def solve():
	nodes = 0
	current_active = 1
	for i in range(n+1):
		# print("i", i)
		current_active -= leaves[i]
		if current_active < 0:
			print(-1)
			return
		current_active = min(rest_leaves[i+1], current_active)
		if i == n:
			current_active = 0
		# print("current_active", current_active)
		nodes += current_active + leaves[i]
		current_active *= 2
	print(nodes)
	return


solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    if n == 0:
        if a[0] == 1:
            print(1)
        else:
            print(-1)
        return
    if a[0] == 1:
        print(-1)
        return
    k = 1-a[0]
    M = [1]
    p = 1
    for i in range(n):
        if k <= 0:
            print(-1)
            return
        M.append(min(p,k) << 1)
        k = M[i+1] - a[i+1]
        p <<= 1
    if k < 0:
        print(-1)
        return
    s = a[-1]
    ans = s
    for i in range(n)[::-1]:
        s = min(M[i],s+a[i])
        ans += s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(an) for an in input().split()]

remaining_leafs = sum(a)

layer_count = 1
vertex_count = 0
for i in range(len(a)):
    vertex_count += layer_count
    layer_count -= a[i]
    remaining_leafs -= a[i]
    if layer_count < 0:
        vertex_count = -1
        break
    layer_count = min(layer_count*2, remaining_leafs)

print(vertex_count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]
max_node = []
current = 1
for i, item in enumerate(a):
    max_node.append(current)
    current = (current - item) * 2

a.reverse()
max_node.reverse()

prev = 0
ans = 0
for i, (item, mx_nd) in enumerate(zip(a, max_node)):
    lower_bound = item + (prev + 1) // 2
    upper_bound = item + prev
    if lower_bound > mx_nd:
        print(-1)
        exit()
    prev = min(upper_bound, mx_nd)
    ans += prev
print(ans)

Submission status: Accepted

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


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A):
    max_leaves = sum(A)
    if N == 0 and A[0] == 1:
        return 1
    if A[0] > 0:
        return -1
    ans = 1
    n_nodes = 1
    for i in range(1, N+1):
        n_nodes = min(n_nodes * 2, max_leaves)
        ans += n_nodes
        if i < N and A[i] > n_nodes - 1:
            return -1
        max_leaves -= A[i]
        n_nodes -= A[i]
    if n_nodes != 0:
        return -1
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
def solve(n, a_list):

    # judge_if_possible
    b_list = [0] * (n + 1)  # nodes with child

    for d in range(n + 1):
        if d == 0:
            n_nodes = 1
        else:
            n_nodes = b_list[d - 1] * 2
        if a_list[d] > n_nodes:
            return -1
        b_list[d] = n_nodes - a_list[d]
    # print(a_list, b_list)
    # backward
    b_list[n] = 0
    for i in range(n - 1, -1, -1):
        b_list[i] = min(b_list[i], a_list[i + 1] + b_list[i + 1])
    res = sum(a_list) + sum(b_list)
    # print(a_list, b_list, res)
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(3, [0, 1, 1, 2]) == 7
    assert solve(4, [0, 0, 1, 0, 2]) == 10
    assert solve(2, [0, 3, 1]) == -1
    assert solve(10, [0, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]) == 264


if __name__ == "__main__":
    test()
    main()

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