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
N = int(input())
A = [int(c) for c in input().split()]
B = [0]*(N+1)
B[0] = 1
if A[0]>=1:
  if N==0 and A[0]==1:
    print(1)
  else:
    print(-1)
  sys.exit()
for i in range(1,N+1):
  B[i] = B[i-1]*2-A[i]
  if B[i]<0:
    print(-1)
    sys.exit()
ans = sum(A)
num = 0
for i in range(N,0,-1):
  num = min(num+A[i],B[i-1])
  ans += num
print(ans)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
L=[0]*(n+1)
L[0]=1
Chk=True
for i in range(n+1):
  if i==0:
    if A[i]>0:
      Chk=False
      break
  elif i<n:
    if L[i-1]*2<=A[i]:
      Chk=False
      break
    else:
      L[i]=L[i-1]*2-A[i]
  else:
    L[i]=L[i-1]*2

if L[-1]<A[-1]:
  Chk=False
else:
  L[-1]=0
  ans=A[-1]
  for i in range(n)[::-1]:
    if A[i+1]+L[i+1]<L[i]:
      L[i]=A[i+1]+L[i+1]
    ans+=L[i]+A[i]


if n==0 and A==[1]:
  print(1)
else:
  if Chk:
    print(ans)
  else:
    print(-1)

Submission status: Accepted

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

nodes = []
if a[0] > 0:
    if a[0] == 1 and n == 0: print(1)
    else: print(-1)
    exit()
else:
    nodes.append(1)
if a[-1] > 2 ** n:
    print(-1)
    exit()

# forward
for i in range(1, n + 1):
    x = nodes[i - 1] * 2 - a[i]
    if i < n:
        if x <= 0:
            print(-1)
            exit()
        nodes.append(x)
    else:
        if x < 0:
            print(-1)
            exit()
        nodes.append(0)

# backward
for i in range(n - 1, -1, -1):
    if nodes[i] > a[i + 1] + nodes[i + 1]:
        nodes[i] = a[i + 1] + nodes[i + 1]

print(sum(a) + sum(nodes))

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()

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

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

    node[N] = 0
    for i in range(N-1,-1,-1):
        if node[i+1]+A[i+1] > node[i] * 2:
            print(-1)
            return
        node[i] = min(node[i+1]+A[i+1],node[i])

    print(sum(node)+sum(A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
flg = 1
if n == 0 and a[0] != 1:
    print(-1)
elif n == 0:
    print(1)
else:
    acc = [0]
    for i in range(n,-1,-1):
        acc.append(acc[-1] + a[i])
    ans = 0
    s = 1

    for i in range(n+1):
        if i != 0:
            s = min(s*2,acc[-i-1])
        ans += s
        s -= a[i]
        if s < 0:
            flg = 0
        #print(s,ans)
    if flg:
        print(ans)
    else:
        print(-1)

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)
elif A[0] != 0:
    print(-1)
else:
    rest = [1]
    for i in range(1, N+1):
        rest.append(min(rest[i-1]*2 - A[i], 10**13))
    ans, cnodes = A[N], A[N]
    for i in range(N-1, -1, -1):
        if cnodes//2 + cnodes%2 > rest[i]:
            print(-1)
            exit()
        else:
            cnodes = min(cnodes, rest[i]) + A[i]
            ans += cnodes
    print(ans)

Submission status: Accepted

Solution code:
import copy

n = int(input())

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

down_max = [0 for i in range(n + 1)]

for i in range(n + 1):
    if i == 0:
        down_max[0] = 1
    else:
        down_max[i] = 2 * (down_max[i - 1] - a_i[i - 1])

answer = 0
now_point_number = 0
before_point_number = 0
cant_make = False

for i in range(n + 1):
    depth_index = - i - 1
    if i == 0:
        now_point_number = a_i[depth_index]
    else:
        if before_point_number // 2 + before_point_number % 2 + a_i[depth_index] > down_max[depth_index]:
            cant_make = True
            break
        else:
            now_point_number = min(down_max[depth_index], before_point_number + a_i[depth_index])
    answer += now_point_number
    before_point_number = copy.copy(now_point_number)

if n == 0 and a_i[0] != 1:
    cant_make = True

if cant_make:
    print(-1)
else:
    print(answer)

Submission status: Accepted

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

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

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

INF = 10**15

cond = [1]
m = INF
for a in A[1:]:
    c = min(INF, cond[-1]*2-a)
    if c<0:
        print(-1)
        exit()
    cond.append(c)

ans = 0
node = 0
for n in range(N, -1, -1):
    n1 = A[n]
    n2 = min(cond[n], node)
    node = n1 + n2
    ans += node

print(ans)

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A = LI()


def main():
    if A[0] >= 2:
        print(-1)
        return
    l, r = [None] * (N + 1), [None] * (N + 1)
    l[0], r[0] = 1, 1
    l[-1], r[-1] = A[-1], A[-1]
    for i in range(N - 1, 0, -1):
        l[i] = (l[i + 1] + 1) // 2 + A[i]
        r[i] = r[i + 1] + A[i]
    
    ans = 1
    x = 1
    for i in range(1, N + 1):
        x -= A[i - 1]
        if x < 0:
            print(-1)
            return
        s = max(x, l[i])
        t = min(2 * x, r[i])
        if s > t:
            print(-1)
            return
        x = t
        ans += t
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(raw_input())
ais = map(int, raw_input().split(' '))

def f(ais,n):
	q = 1 # number of non leaves
	r = 0
	h = {}
	for depth,nl in enumerate(ais):
		if nl > q: return -1
		elif nl == q:
			if depth < n: return -1
			q -= nl
		elif nl < q:
			q -= nl
		#r += (q + nl)
		h[depth] = q
		if depth < n: q *= 2
	
	internal = 0
	for j in range(len(ais)-1, 0, -1):
		r += ais[j] + internal
		internal = min(h[j - 1], ais[j] + internal) 
	return r + 1


print f(ais,n)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
num_node=[1]*(N+1)
for i in range(1,N+1):
    tmp=2*(num_node[i-1]-A[i-1])
    if tmp<0:
        print(-1)
        exit()
    num_node[i]=tmp

tmp=2*(num_node[N]-A[N])
if tmp<0:
    print(-1)
    exit()

num_node[-1]=A[N]
for i in range(N-1,-1,-1):
    tmp=num_node[i+1]
    tmp+=A[i]
    if tmp<=num_node[i]:
        num_node[i]=tmp

print(sum(num_node))

Submission status: Accepted

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

B = [1]
for i in range(n):
    B.append((B[i]-A[i])*2)

C = [A[n]]

for i, s in enumerate(B):
    if i == len(B)-1:
        a = 1
    elif B[i] <= 0:
        print(-1)
        exit()
if B[-1]-A[n] < 0:
    print(-1)
    exit()

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

num = 0
frag = 0
for i in range(n):
    if B[i] >= C[i]:
        frag = 1
    if frag == 0:
        num += B[i]
    else:
        num += C[i]
num += C[n]
print(num)

Submission status: Accepted

Solution code:
from math import *


if __name__ == "__main__":
    n = int(input())
    arr = [int(x) for x in input().split(' ')]
    if(arr[0] > 1):
        print("-1")
    else:
        if(n == 0):
            print("1")
        else:
            dp = [0] * (n + 1)
            fl = True
            active_node, dp[0] = 1 - arr[0], 1
            i = 1
            while(fl and i < n):
                max_node = active_node * 2
                if(arr[i] > max_node):
                    fl = False
                else:
                    dp[i] = max_node
                    active_node = max_node - arr[i]
                i = i + 1
            if(fl):
                ans = 0
                max_node = active_node * 2
                if(arr[n] > max_node):
                    print("-1")
                else:
                    dp[-1] = max_node
                    min_req, max_req = 0, 0
                    i = n
                    while(fl and i >= 0):
                        min_req, max_req = min_req + arr[i], max_req + arr[i]
                        if(dp[i] < min_req):
                            fl = False
                        else:
                            curr_node = min(dp[i], max_req)
                            min_req, max_req = curr_node // 2, curr_node
                            ans = ans + curr_node
                        i = i - 1
                    print(ans if(fl) else "-1")
            else:
                print("-1")

Submission status: Accepted

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

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

INF = 1e18
B = [1]*(N+1)
for i,a in enumerate(A[1:],1):
    B[i] = min(INF,B[i-1]*2 - a)

ans = 0
p = 0
for i,a in enumerate(A[::-1]):
    i = N - i
    m = B[i]
    if p>2*m:
        ans = -1
        break
    p = min(m,p)+a
    ans += p

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(num) for num in input().split()]
b = [0] * (n+1)
b[n] = a[-1]
for i in range(n):
    b[n-1-i] = b[n-i] + a[-i-2]
#c = [0] * (n+1)
#c[n] = a[-1]
#for i in range(n):
#    c[n-1-i] = c[n-i] // 2 + a[-i-2]
#print(c)

ans = 1
fl = True
if a[0] == 0:
    n_dep = 1
elif a[0] == 1 and n == 0:
    fl = False
else:
    ans = -1
    fl = False

if fl:
    for i in range(1,n+1):
        #print(i,n_dep)
        if a[i] > n_dep*2:
            ans = -1
            break
        elif n_dep * 2 <= b[i]:
            n_dep *= 2
            ans += n_dep
            n_dep -= a[i]
        else:
            n_dep = b[i] - a[i]
            ans += b[i]
    
print(ans)

Submission status: Accepted

Solution code:
import sys

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

s=0
for i in A:
    s+=i

S=[]
for i in range(n+1):
    S.append(s)
    s-=A[i]


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

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


ans=1
temp=1
for i in range(n-1):
    #print(ans,temp)
    if A[i+1]>=2*temp:
        print(-1)
        sys.exit()
    else:
        temp=min(S[i+1],2*temp)
        ans+=temp
        temp-=A[i+1]
        

if temp<=A[n]<=2*temp:
    ans+=A[n]
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

cap = [1]*(N+1)#0-N

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

for i in range(1,N+1,1):#1-N
    cap[i]=cap[i-1]*2 - A[i]
    if cap[i] < 0 or (cap[i]==0 and i!=N):
        print(-1)
        exit()

T = [0]*(N+1)
T[N]=A[N]#ここのキャパオーバーは上ではじけるはず
for i in range(N-1,-1,-1):
    T[i]=A[i]+min(T[i+1],cap[i])

print(sum(T))

Submission status: Accepted

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

flag = 0
node_sum = 0
now_node = 0
max_node = [1]
for i in range(1, n+1):
    max_node.append((max_node[i-1]-a_list[i-1])*2)
# print(max_node)

for d, a in enumerate(reversed(a_list)):
    d = n-d
    max_now = max_node[d]
    if (now_node+1)//2 + a > max_now:
        flag = 1
        break
    elif now_node + a > max_now:
        now_node = max_now
    else:
        now_node += a
    node_sum += now_node
    # print(f"{d} {now_node}")

if flag == 1:
    print(-1)
else:
    print(node_sum)

Submission status: Accepted

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

n = ii()
a = li()

sumnode = 0
sumleaf = sum(a)

nn = 1
sumnode = 1
if n == 0:
    if a[0] != 1:
        print(-1)
    else:
        print(1)
elif a[0] == 1:
    print(-1)
else:
    for i in range(1,n+1):
        if n == 0:
            print(-1)
            break

        if sumleaf > nn:
            nn = min(nn*2, sumleaf)
        
        sumnode += nn

        nn -= a[i]
        if nn < 0:
            print(-1)
            break
        sumleaf -= a[i]

        # print(i,nn,sumnode,sumleaf)
    else:
        print(sumnode)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

minN, maxN = A[N], A[N]

mins = [0] * (N + 1)
maxs = [0] * (N + 1)


mins[N], maxs[N] = A[N], A[N]
for i in range(N - 1, -1, -1):
    mins[i] = (mins[i + 1] + 1) // 2 + A[i]
    maxs[i] = maxs[i + 1] + A[i]

# print(mins, maxs)


def ok():
    c = 1
    ret = 0
    for i in range(N + 1):
        if not mins[i] <= c:
            return -1
        c = min(c, maxs[i])
        ret += c
        # print(i, c)
        c = 2 * (c - A[i])

    return ret

print(ok())

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    A_sum = sum(A)
    ans = 1
    tmp_v = 1
    if A[0] > 1:
        print(-1)
        sys.exit()
    if A[0] == 1:
        if N == 0:
            print(1)
        else:
            print(-1)
        sys.exit()
    for i in range(N):
        if A[i+1] > tmp_v*2:
            print("-1")
            sys.exit()
        tmp_v = min(tmp_v*2, A_sum)
        ans += tmp_v
        A_sum -= A[i+1]
        tmp_v -= A[i+1]
    print(ans)



if __name__ == '__main__':
    main()

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):
    # i 段目の許容数は上の段の許容数と上の段の歯の数で来まる
    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:
N = int(input())
A = list(map(int, input().split()))

backward = [0]
for a in reversed(A):
    backward.append(backward[-1] + a)
backward.reverse()
backward.pop()

backward_lower = [0]
for a in reversed(A):
    backward_lower.append((backward_lower[-1] + 1) // 2 + a)
backward_lower.reverse()
backward_lower.pop()

forward = [1]
for i in range(N):
    forward.append((forward[-1] - A[i]) * 2)
    if forward[-1] > backward[i]:
        break


ans = 0
for i in range(N + 1):
    if i < len(forward):
        if backward_lower[i] > forward[i]:
            print(-1)
            break
        ans += min(forward[i], backward[i])
    else:
        ans += backward[i]
else:
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())

A=[int(i) for i in input().split()]
B=[0 for i in range(n+1)]
C=[0 for i in range(n+1)]
D=[0 for i in range(n+1)]
ck=[0 for i in range(n+1)]


now=A[-1]
B[-1]=now
C[-1]=now
D[-1]=now
for i in range(n):
    q=n-1-i
    if now%2==1:
        ck[q]=1
    C[q]=now//2
    now=now//2+A[q]+now%2
    B[q]=now
    D[q]=D[q+1]+A[q]

ans=sum(B)

bonus=0
BON=[0]
for i in range(1,n):
    bonus*=2
    bonus+=ck[i-1]
    bonus=min(bonus,D[i]-B[i])
    BON.append(bonus)
    ans+=bonus

if B[0] != 1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ns = list(map(int, input().split()))
li = 1
ans = 0
max_leafs = [1]
for i in ns:
    li = (li - i) * 2
    max_leafs.append(li)
points = ns.pop()
ans += points
for i in range(len(ns)-1, -1, -1):
    a = ns[i]
    points = min(points + a, max_leafs[i])
    ans += points
if max_leafs[-1] < 0:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

mid_node = [(0,0) for i in range(N+1)]
for i in range(N-1, -1, -1):
	m,M = mid_node[i+1]
	child_leaf = A[i+1]
	mid_node[i] = ((child_leaf + m + 1)//2, child_leaf + M)

def between(n,a,b):
	return a <= n and n <= b
ans = [0 for i in range(N+1)]
if not between(1, mid_node[0][0], mid_node[0][1]):
	print(-1)
	exit()

ans[0] = (1, 0)
for i in range(1, N+1):
	b_m = ans[i-1][0]
	node_min, node_max = mid_node[i][0] + A[i], mid_node[i][1] + A[i]
	candidate_min, candidate_max = b_m, b_m*2
	if candidate_min > node_max or candidate_max < node_min:
		print(-1)
		exit()
	node = min(candidate_max, node_max)
	ans[i] = (node - A[i], A[i])
print(sum([a+b for a,b in ans]))

Submission status: Accepted

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

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

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

arr.reverse()

ar2 = [None] * (n+1)

for i, e in enumerate(arr):
    if i == 0:
        ar2[0] = (e, e)
        continue

    ar2[i] = (ar2[i-1][0]+e, (ar2[i-1][1]+1) // 2 + e)

if ar2[-1][1] > 1:
    print(-1)
    exit()

ar2.reverse()

total = 0
acc = 1
for i, t in enumerate(ar2):
    acc = min(acc, t[0])

    total += acc
    acc -= arr[n-i]
    acc *= 2

print(total)

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    A = list(map(int, input().split()))
    SA = [0]
    for i in range(N + 1):
        SA.append(SA[-1] + A[N - i])
    SA.reverse()
    res = 0
    t = 1
    for i in range(N + 1):
        if t >= SA[i]:
            t = SA[i]
        res += t
        t -= A[i]
        if t <= 0:
            if i != N:
                return -1
            else:
                if t < 0:
                    return -1
        t *= 2
    return res


print(main())

Submission status: Accepted

Solution code:
def Csum(a):
    b,c=[0],0
    for i in range(len(a)):
        c+=a[i]
        b.append(c)
    return b

n=int(input())
a=list(map(int,input().split()))
s=Csum(a)
su=sum(a)
b=1
c=0
for i in range(n+1):
    c+=b
    b-=a[i]
    if b<=0:
        if i==n and b==0:
            break
        print(-1)
        exit()
    b=min(b*2,su-s[i+1])
print(c)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())[:-1]
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [list(input())[:-1] for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
A = list(map(int,input().split()))
if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
elif A[0] != 0:
    print(-1)
else:
    band1 = deque([[A[N],A[N]]])
    for i in range(N):
        x = A[N-1-i]
        MIN = band1[0][0]
        MAX = band1[0][1]
        vmin = x+(MIN+1)//2
        vmax = MAX + x
        band1.appendleft([vmin,vmax])
    band1 = list(band1)
    band2 = [[1,1]]
    for i in range(1,N+1):
        p = A[i-1]
        MIN = band2[i-1][0] - p
        MAX = band2[i-1][1] - p
        vmin = MIN
        vmax = 2*MAX
        band2.append([vmin,vmax])
    c = 0
    ans = 0
    for i in range(N+1):
        li1 = band1[i]
        li2 = band2[i]
        if li1[1] < li2[0] or li1[0] > li2[1]:
            c = 1
            break
        else:
            ans += min(li1[1],li2[1])
    if c == 0:
        print(ans)
    else:
        print(-1)

Submission status: Accepted

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

G = []
nodes = [0]*(N+1)
nodes[0] = 1
for i in range(N):
    nodes[i+1] = nodes[i]*2

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

ans = 0
node = 1 - A[0]
nodes = [0 for i in range(N)]
nodes[0] = 1 - A[0]  # 深さi-1で、葉でない頂点の個数の最小値、最大値

# 可能性の判定 + 深さNの確定
for i in range(1, N+1):
    if i == N:
        if math.ceil(A[i]/2) > nodes[i-1]:
            print(-1)
            exit(0)
        else:
            continue
    else:
        # 自分の深さが可能かの判定
        if nodes[i-1] * 2 >= A[i]:
            nodes[i] = nodes[i-1] * 2 - A[i]
        else:
            print(-1)
            exit(0)
ans += A[i]
prev = A[-1]
for i in range(N-1, -1, -1):
    # その深さでできる最大値
    prev = min(nodes[i], prev) + A[i]
    ans += prev

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
N,*A=map(int, open(0).read().split())
if N==0:
    if A[0]==1:
        print(1)
    else:
        print(-1)
    exit()
if A[0]!=0:
    print(-1)
    exit()
R=[0]*(N+2)
R[0]=1
ans=0
for i in range(N+1):
    R[i]-=A[i]
    if R[i]<0:
        print(-1)
        exit()
    R[i+1]=min(R[i]*2,10**17)
B=list(accumulate(A[::-1]))[::-1]
ans+=sum(min(R[i]+A[i],B[i])for i in range(N+1))
print(ans)

Submission status: Accepted

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def Yes(x):print("Yes")if x==True else print("No")
n=N()
l=L()
if n==0:
    if l[0]==1:
        print(1)
    else:
        print(-1)
    quit()
if l[0]==1:
    if sum(l)==1:
        print(1)
    else:
        print(-1)
    quit()
ans=[0]*(n+1)
v=1
ans[0]=1
for i in range(1,n+1):
    v*=2
    ans[i]=v
    v-=l[i]
    if v<0:
        print(-1)
        quit()
for i in range(n,0,-1):
    ans[i]-=v
    if ans[i]>=ans[i-1]-l[i-1]:
        break
    v=ans[i-1]-l[i-1]-ans[i]
print(sum(ans))

Submission status: Accepted

Solution code:
import math

N = int(input())

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

List_re = list(reversed(List))
arr = [-1 for i in range(N+1)]
arr2 = [-1 for i in range(N+1)]
arr3 = [-1 for i in range(N+1)]

for i in range(N+1):
  a = List_re[i]
  if i == 0:
    arr3[N-i] = a    
  else:
    arr3[N-i] = math.ceil(arr3[N-i+1]/2) + a

for i in range(N+1):
  a = List_re[i]
  if i == 0:
    arr[N-i] = a    
  else:
    arr[N-i] = arr[N-i+1] + a
    
for i in range(N+1):
  a = List[i]
  if i == 0:
    arr2[i] = 1
  else:
    arr2[i] = ( arr2[i-1]-List[i-1]) *2

ans = 0

for i in range(N+1):
  a = arr[-i-1]
  b = arr2[-i-1]
  c = min(a,b)
  ans += c

if arr3[0] != 1:
  print(-1)
else:
  print(int(ans))

Submission status: Accepted

Solution code:
def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

def cum_sum(lst):
    cums = [0] * (len(lst)+1)
    cums[1] = lst[0]
    for i in range(2,len(lst)+1):
        cums[i] = cums[i-1] + lst[i-1]
    return cums


n = int(input())
a = lmp()
ar = list(reversed(a))
amx = [1]
for i in range(n):
    u = (amx[i]-a[i])*2
    if u <= 0:
        print(-1)
        exit()
    else:
        amx.append(u)
arcum = cum_sum(ar)[1:]
arcum = list(reversed(arcum))
# print(amx)
# print(arcum)
if amx[-1] < arcum[-1]:
    print(-1)
    exit()
cnt = 0
for i in range(n+1):
    cnt += min(amx[i],arcum[i])
print(cnt)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate as accum

input = sys.stdin.readline


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

    B = list(accum((A[1:])[::-1]))[::-1]

    ans = 1
    v_count = 1
    for a, b in zip(A[:-1], B):
        if a > 0:
            if a > v_count:
                ans = -1
                break
            else:
                v_count -= a
        v_count = min(2 * v_count, b)
        ans += v_count

    if v_count != A[-1]:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = [0 for i in range(N+1)]
S = sum(A)
B[0]=1
flag=1
if A[0]>1 :
    flag=0
if A[0]>0 and N>0:
    flag=0

for i in range(N):
    if flag==0:
        break

    S = S-A[i]

    if 2*(B[i]-A[i])<A[i+1]:
        flag = 0

    B[i+1]=min(2*(B[i]-A[i]),S)

if flag==0:
    print(-1)
else:
    res = sum(B)
    print(res)

Submission status: Accepted

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

def check():
    R = [0]*(N+1)
    R[0] = 1
    for i in range(N):
        if R[i] < A[i]:
            return -1
        R[i+1] = 2*(R[i]-A[i])
    if R[N] < A[N]:
        return -1
    
    
    CA = A[:]
    
    for i in range(N-1, -1, -1):
        CA[i] += CA[i+1]
    
    
    return sum(min(r, c) for r, c in zip(R, CA))


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

if N == 0:
    if A[0] == 1:
        print(1)
    else:
        print(-1)
elif A[0] or A[N] == 0:
    print(-1)
else:
    print(check())

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
MAX_INT = int(10e25)
MIN_INT = -MAX_INT
mod = 998244353
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

num = sum(a)
ans = 0
ko = 1
for i in range(N):
  ans += ko
  ko -= a[i]
  num -= a[i]
  ko = min(ko*2, num)

  if ko <= 0:
    print(-1)
    break
else:
  ans += ko
  ko -= a[-1]
  if ko < 0:
    print(-1)
  else:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Ac = [0]*(N+2)
for i in range(N+1):
    Ac[i] = Ac[i-1]+A[i]

n = [0]*(N+1)
n[0] = 1
for d in range(1,N+1):
    n[d] = min(Ac[N]-Ac[d-1],2*(n[d-1]-A[d-1]))
if n[N]!=A[N]:
    ans = -1
else:
    ans = sum(n)
print(ans)

Submission status: Accepted

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

RG1 = [None]*N
d = u = 1
for i in range(N):
    d = max(0, d - A[i+1])
    u = max(0, 2*u - A[i+1])
    RG1[i] = (d,u)

RG2 = [None]*N
d = u = 0
for i in range(N-1,-1,-1):
    RG2[i] = (d,u)
    d = (d+A[i+1]+1)//2
    u = u + A[i+1]

RG3 = [ (max(RG1[i][0],RG2[i][0]), min(RG1[i][1],RG2[i][1])) 
        for i in range(N)]

ans = 1 + sum(A)
for i in range(N):
    if RG3[i][0] > RG3[i][1]:
        print(-1)
        exit()
    else:
        ans += RG3[i][1]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

def check():
	b_max = 0
	b_min = 0
	b_max_list = [0]
	for a in reversed(A_list):
#		print(b_min, b_max)
		b_max = a + b_max
		b_max_list.append(b_max)
		b_min = (a + b_min + 1) // 2
	
	b_max_list.pop()
	
	count = 0
	branches = 1
	for a, b_max in zip(A_list, reversed(b_max_list)):
		if branches < a:
			return -1
#		print(a, b_max)
		if branches <= 0:
			return -1
#		print("b>", branches)
		count += branches
		branches = min(b_max, (branches - a) * 2)
	
	return count

result = check()
if result != None:
	print(result)
else:
	print(-1)