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
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))
if n == 0:
    if lst1[0] == 1:
        print(1)
        exit()
    else:
        print(-1)
        exit()
if lst1[0] != 0:
    print(-1)
    exit()
res2 = [0]
for i in lst1[::-1]:
    res2.append(res2[-1]+i)

res2.reverse()
INF = res2[0]
res = [1] 
res3 = [1]
for i in range(1,len(lst1)):
    res3.append(min(INF,res[-1]*2))
    cache = res[-1]*2-lst1[i]
    if cache <= 0 and i != n:
        print(-1)
        exit()
    elif cache < 0 and i == n:
        print(-1)
        exit()
    res.append(min(INF,cache))

ans = 0
res2 = res2[:-1]
for i in range(len(res3)):
    ans += min(res2[i],res3[i])
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)
		exit()
	else:
		print(-1)
		exit()
M=[1]
now=2
r=sum(a)
for i in range(n):
	M.append(now)
	now-=a[i+1]
	if now<0:
		print(-1)
		exit()
	elif now<r:
		now*=2
now=a[-1]
for i in range(n):
	M[-i-1]=min(now,M[-i-1])
	now=min(now,M[-i-1])
	now+=a[-i-2]
if a[0]!=0:
	print(-1)
	exit()
for i in range(n+1):
	if M[i]<=0:
		print(-1)
		exit()
print(sum(M))

Submission status: Accepted

Solution code:
import sys
# import math

N = int(input())
A = list(map(int, input().split()))
kari = [0] * (N+1)

ans = 0
nokori = 1

for i in range(N+1):
    if (nokori == 0)or(A[i] > nokori):
        print(-1)
        sys.exit()

    nokori -= A[i]
    ans += A[i]
    # dump((i,ans,nokori))
    kari[i] = nokori
    nokori *= 2

mx = A[N]

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

print(ans)

Submission status: Accepted

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

v=[0 for i in range(n+2)]
import time

#start=time.time()
nextv=0

nec=2**n

for i in range(n,-1,-1):

    if nec>=v[i+1]+a[i]:
        v[i]=v[i+1]+a[i]
    else:
        v[i]=nec

    nec=nec >>1



#print(time.time()-start)

for i in range(1,n+1):
    if v[i-1]-a[i-1]<0:
        ok=False
        break
    if (v[i-1]-a[i-1])*2<v[i]:
        v[i]=(v[i-1]-a[i-1])*2


if n==0:
    if a[0]!=1:ok=False
else:
    if a[0] != 0:ok = False

if v[n]!=a[n]:ok=False

ans=sum(v)
if ans==0:ok=False

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

Submission status: Accepted

Solution code:
N=int(input())+1
a=[int(x) for x in input().split()]
poss=True
interm = [0 for i in range(N)]
inter = [0 for i in range(N)]
s=[0 for i in range(N)]
for i in range(N-1, -1, -1):
    if (i!=N-1):
        s[i]=a[i]+s[i+1]
    else:
        s[i]=a[i]
n=[0 for i in range(N)]
n[0]=min(s[0], 1)
for i in range(1,N):
    n[i]=min(s[i], 2*(n[i-1]-a[i-1]))
    #print(n[i-1]-a[i-1], a[i])
    if (n[i-1]-a[i-1]<(a[i]//2+a[i]%2)):
        #print(n[i-1], a[i-1], a[i])
        poss = False
#print(s)
#print(n)
if n[-1]!=a[-1]:
    print(-1)
    exit()
if poss:
    print(sum(n))
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def input_one_number():
    return int(input())

def input_multiple_number():
    return map(int, input().split())

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


N= input_one_number()
A = input_multiple_number_as_list()

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

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

eda = A[-1]
ans = eda
for i in range(N):

	if eda > edamax[N+1-2-i]:
		if (eda+1)//2  > edamax[N+1-2-i]:
			print(-1)
			exit(0)
		else:
			eda = edamax[N+1-2-i]
	ans += eda
	eda += A[N+1-2-i]
	ans += A[N+1-2-i]



print(ans)

Submission status: Accepted

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

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

flag=0
ans,point=[1],1
for i in range(1,n+1):
    if point<=0 or sum_A<=0:print(-1);exit()
    if flag==0:
        point *=2
    if point>=sum_A:
        point=sum_A
        flag=1
    ans.append(point)
    point -=A[i]
    sum_A -=A[i]
if sum_A!=0 or point!=0:print(-1);exit()
print(sum(ans))

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 math

N=int(input())
listA = list(map(int, input().strip().split()))
saisyou=listA[N]
saidai=listA[N]
i=N-1
k=0
count=1
kiroku = 1
listsum=0
while k<=N:
  listsum=listsum+listA[k]
  k=k+1

while i>=0:
  saisyou = math.ceil(saisyou/2)+listA[i]
  i=i-1
if(saisyou != 1):print(-1)
#print(saisyou)
if(saisyou == 1):
  i=0
  while i<N:
    listsum=listsum-listA[i]
    kiroku = min(2*(kiroku-listA[i]),listsum)
    count = count+kiroku
    i=i+1
  print(count)

Submission status: Accepted

Solution code:
depth = int(input())
vertex = input().split(' ')
vertex = [int(x) for x in vertex]

maxs = []
v_cnt = 1
is_error = False
for i in range(depth + 1):
    v_cnt -= vertex[i]
    if v_cnt > 0 or (i == depth and v_cnt >=0):
        maxs.append(v_cnt)
        v_cnt *= 2
    else:
        is_error = True
        break

output = 0
if is_error:
    output = -1
else:
    for i in range(depth, -1, -1):
        if i == depth:
            output += vertex[i]
            next_v = vertex[i]
        else:
            next_v = min([maxs[i], next_v]) + vertex[i]
            output += next_v
print(output)

Submission status: Accepted

Solution code:
import sys
import math


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

R=list(A)

nodes=0
log2=math.log(2)

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

elif A[0]==1 and N==0:
    nodes = 1
    print(nodes)
    sys.exit(0)

else:
    nodes = 1
    R[N]=0
    R[0]=1
    if math.log(A[N])>N*log2:
        nodes = -1
        print(nodes)
        sys.exit(0)
    
    for i in range(N-1,0,-1):
        if A[i] > 0 and (math.log(A[i]) > float(i)*log2):
            nodes = -1
            print(nodes)
            sys.exit(0)

        if N>30:
            R[i]=R[i+1]+A[i+1]
        else:
            R[i]=min(2**i-A[i], R[i+1]+A[i+1])
    # print(R)    

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

    # print(R)    
    print(nodes)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
tot=sum(A)
cur=1
total=0
for d in range(N+1):
    if tot>=cur:
        total+=cur
    cur-=A[d]
    tot-=A[d]
    if cur<0:
        total=-1
        break
    cur=min(cur*2,tot)
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()

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

rev_a = A[::-1][1:]

for i in range(len(A)-1):
    need_node = rev_a[i] + (need_node + 1) // 2
    if need_node > 2 ** (N - i - 1):
        print(-1)
        exit()

# check OK
b = [0] * (N + 1)
b[0] = 1
for i in range(len(A) - 1):
    b[i + 1] = 2 * (b[i] - A[i])

node_total = 0
now_node = 0
reva = A[::-1]
revb = b[::-1]
for i in range(len(A)):
    now_node = min(reva[i] + now_node, revb[i])
    node_total += now_node

print(node_total)

Submission status: Accepted

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

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

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

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

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

D = [min(b,c) for b,c in zip(B,C)]
print(sum(D))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
A = LI()
ANS = [0]*(n+1)
ANS[0] = 1
CONTINUE = 0
if A[0] == 0:
    CONTINUE = 1
elif A[0] == 1:
    CONTINUE = 0
else:
    print(-1)
    exit()

tmp = 0
for i in range(1, n+1):
    if A[i] > CONTINUE*2:
        print(-1)
        exit()
    else:
        CONTINUE = CONTINUE*2 - A[i]
        ANS[i] = CONTINUE + A[i]

for i in reversed(range(n+1)):
    tmp += A[i]
    ANS[i] = min(ANS[i], tmp)

print(sum(ANS))

Submission status: Accepted

Solution code:
n=int(input())
sums=[0]*(n+1)
node=[0]*(n+1)
p=list(map(int,input().split()))
flag=False

sums[n]=p[n]
for i in reversed(range(n)):
    sums[i]=p[i]+sums[i+1]

sums[0]=1
for i in range(1,n):
    c=(sums[i-1]-p[i-1])*2
    if c<=0:
        flag=True
        break
    if c<sums[i]:
        sums[i]=c
    else:
        break

if n==0:
    if p[0]==1:
        print(1)
    else:
        print(-1)
elif flag or (sums[n-1]-p[n-1])*2<sums[n]:
    print(-1)
else:
    print(sum(sums))

Submission status: Accepted

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

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

s = [0] * (n+2)
for i in range(n+1)[::-1]:
    s[i] = s[i+1]+a[i]

x = 1
ans = 0
for i in range(n+1):
    ans += x
    if x == s[i]:
        x -= a[i]
        continue
    x -= a[i]
    if (x <= 0 and i != n) or x < 0: print(-1); exit()
    if x*2 >= s[i+1]: x = s[i+1]
    else: x *= 2

print(ans)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
ans=0
s=sum(a)
p=1
b=True
for j in a:
    if p<j:
        print(-1)
        exit()
    ans+=p
    p-=j
    s-=j
    if p<s and b:
        if p*2<s:p*=2
        else:p=s
    if p==s:b=False
print(ans)

Submission status: Accepted

Solution code:
def solve(n,A):
    if n==0:
        if A[0]==1:
            return 1
        return -1
    if A[0]!=0:
        return -1
    if A[-1]>pow(2,n):
        return -1
    Num=[0]*(n+1)
    Num[0]=1
    Num[-1]=A[-1]
    Cap=[0]*(n+1)
    Cap[0]=1
    for i in range(1,n+1):
        Cap[i]=Cap[i-1]*2-A[i]
    for i in range(1,n)[::-1]:
        min_num=(Num[i+1]+1)//2+A[i]
        max_num=Num[i+1]+A[i]
        if min_num>Cap[i-1]*2:
            return -1
        Num[i]=min(max_num,Cap[i-1]*2)
    if Num[1]>2 or Num[1]<1:
        return -1
    return sum(Num)

def main():
    n=int(input())
    A=tuple(map(int,input().split()))
    ans=solve(n,A)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split( )))
Nodes = [1 for _ in range(N+1)]
for i in range(1,N+1):
  Nodes[i] = (Nodes[i-1]-A[i-1])*2
before = 0
ans = 0
for a,n in zip(A[::-1],Nodes[::-1]):
    if (n - a) >= before:
        before = before + a
    elif (n - a)*2 >= before :
        before = n
    else:
        ans = -1
        break
    ans += before
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def rec(i, A, ok_v):
    # print(i, A, ok_v)
    if ok_v <= 0:
        return -1, -1
    if i == len(A) - 1:
        if A[-1] > ok_v:
            return -1, -1
        else:
            return A[-1], A[-1]
    # if i > 70:
    #     child, ans = rec(i + 1, A, -1)
    #     if child == ans == -1:
    #         return -1, -1
    #     else:
    #         return child + A[i], child + A[i] + ans
    child, ans = rec(i+1, A, (ok_v - A[i]) * 2)
    # print("\t", i, child, ans)
    if child == ans == -1:
        return -1, -1
    num_v = min(ok_v, child + A[i])
    return num_v, ans + num_v


def main() -> None:
    N = int(input())
    A = [int(x) for x in input().split()]
    if N == 0:
        print(1 if A[0] == 1 else -1)
        return
    elif A[0] != 0:
        print(-1)
        return

    _, ans = rec(1, A, 2)
    print(ans + 1 if ans > 0 else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
k=sum(a)
if n==0:
    print(1 if a[0]==1 else -1)
    exit()
ans=1
e=1
for i in range(n):
    e-=a[i]
    k-=a[i]
    if e<0:
        print(-1)
        exit()
    elif e==0 and k>0:
        print(-1)
        exit()
    if 2*e<k:
        e*=2
    elif e<k:
        e=k
    #print("e",e)
    ans+=e
print(ans if e==k else -1)

Submission status: Accepted

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
rl = sys.stdin.readline
mod = 10**9+7

N = Int()
A = IntList()

tmp = 0

for i in range(N+1):
    tmp += A[i]*2**(N-i)
    
if tmp > 2**N:
    print(-1)
    sys.exit()
    
if N==0:
  print(1)
  sys.exit()


B = A[::-1]
ans = 1
par = 1
C = []
MAXpar = B[0]

for i in range(N):
    leaf = B[i]
    if len(C)>=1:
        MINP = C[-1][0]
        MAXP = C[-1][1]
        C.append([(MINP+leaf+1)//2,MAXP+leaf])
    else:
        C.append([(leaf+1)//2,leaf])
        

D = C[::-1]
#print(D)
for i in range(1,N):
    minp,maxp = D[i]
    
    ans += A[i]+min(maxp,2*par-A[i])
    #print(A[i],min(maxp,2*par-A[i]))
    par = min(maxp,2*par-A[i])
    
ans += A[-1]
print(ans)

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()
c = 1
for i in range(1,n+1):
    c = c*2
    if a[i]>c:
        print(-1)
        exit()


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

if x[-1]<a[-1]:
    print(-1)
    exit()
x[-1] = a[-1]

for i in range(n-1,-1,-1):
    if a[i]>x[i]:
        print(-1)
        exit()
    x[i] = min(x[i],x[i+1]+a[i])


print(sum(x))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
V = [0]*(N+1)
A_sum = A[:] #その深さ以降で必要な葉の数

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

for i in range(N,0,-1):
    A_sum[i-1] += A_sum[i]
#print(A_sum)
V[0] = 1

for i in range(1,N+1):
    if A[i] > 2*(V[i-1] - A[i-1]):
        print(-1)
        exit()
    V[i] = min(2*(V[i-1] - A[i-1]), A_sum[i])
ans = sum(V)
print(ans)

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A[0] > 1:
            print(-1)
            return
        elif A[0] == 1:
            print(1)
            return

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


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

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

    prev = 1
    answer = 1
    
    for i in range(1,N+1):
        cur = min(prev*2,safe_line[i])
        answer += cur
        prev = cur - A[i]
        
        if prev <= 0 and i < N:
            print(-1)
            return
        elif prev < 0 and i <= N:
            print(-1)
            return
    
    print(answer)
    return

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()))
b = []
limit = 0
present = 1
total = 0
for i in range(n+1):
    limit += a[i]
for i in range(n+1):
    limit -= a[i]
    b.append(limit)
for i in range(n+1):
    if present > a[i]:
        total += present
        present = min((present-a[i])*2, b[i])
    elif present == a[i] and i == n:
        total += present
    else:
        total = -1
        break;
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)
    else:
        print(a[0])
    exit()
if a[0] > 0:
    print(-1)
    exit()
l = [0] * (n + 1)
u = [0] * (n + 1)
l[n] = a[n]
u[n] = a[n]
for i in range(n, 0, -1):
    l[i - 1] = -(-l[i] // 2) + a[i - 1]
    u[i - 1] = u[i] + a[i - 1]
if l[0] > 1:
    print(-1)
    exit()
u[0] = 1
itr = 0
while True:
    update = False
    for i in range(n):
        if u[i] < l[i]:
            print(-1)
            exit()
        n_u = 2 * (u[i] - a[i])
        if n_u < u[i + 1]:
            update = True
            u[i + 1] = n_u
    if not update:
        break
    update = False
    for i in range(n, 0, -1):
        if u[i] < l[i]:
            print(-1)
            exit()
        n_u = u[i] + a[i - 1]
        if n_u < u[i - 1]:
            update = True
            u[i - 1] = n_u
    if not update:
        break
for i in range(n + 1):
    if u[i] < l[i]:
        print(-1)
        exit()
print(sum(u))

Submission status: Accepted

Solution code:
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, A = Z(), ZZ()

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

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

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

    for i in range(N):
        x = v[i][1] - A[i]
        if x < 0:
            print(-1)
            return
        v[i+1][1] = 2 * x
    if v[N][0] > A[N] or A[N] > v[N][1]:
        print(-1)
        return
    v[N] = [A[N], A[N]]
    for i in range(N):
        x = (v[N-i][0]+1)//2 + A[N-i-1]
        y = v[N-i][1] + A[N-i-1]
        v[N-i-1][0] = max(v[N-i-1][0], x)
        v[N-i-1][1] = min(v[N-i-1][1], y)
        if v[N-i-1][0] > v[N-i-1][1]:
            print(-1)
            return
    v[0] = [1, 1]
    output = 0
    for i in range(N+1): output += v[i][1]
    print(output)

    return

if __name__ == '__main__':
    main()

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()))
now = 1

if n == 0 and a[0] == 1:
    print(1)
    exit()
if a[0] != 0:
    print(-1)
    exit()
dnl = [0] * (n+1)
for d,v in enumerate(a[:-1]):
    if now < v:
        print(-1)
        exit()
    dnl[d] = now - v
    now = (now - v) * 2
if now < a[-1]:
    print(-1)
    exit()
elif now//2 <= a[-1] <= now:
    print(sum(dnl) + sum(a))
    exit()
else:
    for i in range(n,0,-1):
        if dnl[i] + a[i] < dnl[i-1]:
            dnl[i-1] = dnl[i] + a[i] 
        else:
            break
    print(sum(dnl) + sum(a))

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
if n==0:
    if a[0]==0:
        print(0)
    elif a[0]==1:
        print(1)
    else:
        print(-1)
    quit()
if a[0]==1:
    if n!=0:
        print(-1)
        quit()

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

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

maxnode.append(0)

ans=1
for i in range(1,n+1)[::-1]: 
    # now=pow(2,i)
    # print(now)

    # if i==n:
    #     if a[i]>maxnode[-1]*2:
    #         print(-1)
    #         quit()
    #     else:
    #         maxnode[-1]=min(a[i],maxnode[-1])
    #         ans+=a[i]
    # else:
    if maxnode[i]+a[i]>maxnode[i-1]*2:
        print(-1)
        quit()
    else:
        maxnode[i-1]=min(maxnode[i]+a[i],maxnode[i-1])
        ans+=maxnode[i]+a[i]
    
print(ans)

Submission status: Accepted

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

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


# if n == 0:
#     if a[0] == 2:
#         print(3)
#     elif a[0] == 1:
#         print(2)
#     exit()

max_num_list = [0]*(n+1)
max_num_list[0] = 1
next_ = 1
for i in range(1, n+1):
    max_num = next_*2
    next_ = max_num-a[i]
    max_num_list[i] = max_num
# print(max_num_list)

list_ = [0]*(n+1)
ans = 0
before = 0
for i in range(n, -1, -1):
    max_num = max_num_list[i]
    if before > (max_num-a[i])*2:
        print(-1)
        exit()
    if max_num-a[i] <= before:
        num = max_num
    else:
        num = before+a[i]
    list_[i] = num
    before = num
    # print(list_)
list_.reverse()
print(sum(list_))

Submission status: Accepted

Solution code:
n = int(input())

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

max_leaf = [0 for i in range(n+1)]
prev_max = 0
must = 0

for i in range(n+1):
    max_leaf[-(i+1)] = prev_max + a[-(i+1)]
    prev_max = max_leaf[-(i+1)]
    must = (must+1) // 2 + a[-(i+1)]


if must != 1:
    print(-1)
else:
    num = 0.5
    ans = 0
    for i in range(n+1):
        if i == 0:
            num = 1
            ans += 1
        else:
            num = min((num-a[i-1])*2, max_leaf[i])
            ans += num

    print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [sum(a)]
for i in range(n):
    b.append(b[-1] - a[i])
flag = True
if n == 0:
    if a[0] == 1:
        count = 1
    else:
        count = -1
else:
    if a[0] != 0:
        flag = False
    else:
        count = 1
        temp = 1
        for i in range(1, n + 1):
            temp2 = min(temp * 2, b[i])
            count += temp2
            temp = temp2 - a[i]
            if temp <= 0:
                if i != n:
                    flag = False
                    break
        if temp != 0:
            flag = False
if flag == True:
    print(count)
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)
    else:
        print(-1)
    sys.exit()
w=[1-l[0]]*(n+1)
for i in range(1,n+1):
    w[i]=w[i-1]*2-l[i]
if min(w)<0:
    print(-1)
    sys.exit()
for i in range(1,n+1):
    w[i]+=l[i]
for i in range(n-1,-1,-1):
    l[i]+=l[i+1]
ans=0 
for i in range(n+1):
    ans+=min(l[i],w[i])
#print(w,w1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
aList = deque(map(int, input().split()))
sList = []
s = 0
for ra in reversed(aList):
    s += ra
    sList.append(s)
sList.reverse()
aList = deque(aList)
sList = deque(sList)

def main():
    c = 1
    a = aList.popleft()
    s = sList.popleft()
    if a > 0 and n != 0:
        return -1
    if n == 0 and a == 1:
        return 1
    su = c
    for i in range(n):
        a = aList.popleft()
        s = sList.popleft()
        t = min(c * 2, s)
        su += t
        if t < a:
            return -1
        else:
            c = t - a
    if c == 0:
        return su
    else:
        return -1

print(main())

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1
    last = A[-1]
    now = 1
    cum = [last]*(N+1)
    for i in range(N-2,-1,-1):
        cum[i] = cum[i+1]+A[i+1]
    if 1<A[0]:
        return -1
    if N == 0:
        return 1
    now -= A[0]
    for i in range(1,N):
        now *= 2
        if now<A[i] or now==0:
            return -1
        now = min(cum[i],now-A[i])
        ans += now+A[i]
    if now*2 < last:
        return -1
    return ans + last
print(solve())

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
for i in range(n+1):
    if pow(2,i) < a[i]:
        print(-1)
        exit()
    if pow(2,i) > 10**9:
        break

cnt=[]
now=0
for i in reversed(range(n+1)):
    now+=a[i]
    cnt.append(now)
cnt.reverse()
ans=sum(cnt)
nxt_max=1
for i in range(len(cnt)):
    c=cnt[i]
    if c > nxt_max:
        ans-=(c-nxt_max)
    else:
        nxt_max=c
    nxt_max-=a[i]
    nxt_max*=2
    if i!=len(cnt)-1 and nxt_max <=0:
        print(-1)
        exit()

if nxt_max!=0:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    if N==0:
        if A[0] == 1:
            print(1)
        else:
            print(-1) 
        return 
    
    s = [0]*(N+1)
    s[N] = A[N]
    for i in range(N-1, -1, -1):
        s[i] = s[i+1] + A[i] 

    leafs = 0
    ans = 0
    for i, a in enumerate(A):
        leafs = leafs*2 + a
        rem = pow(2,i) - leafs
        if i<N:
            # print(sum(A[i+1:]), s[i+1])
            k = min(rem, s[i+1])
            ans+=k
    # print(leafs)

    rem = pow(2,N) - leafs    
    if rem<0:
        print(-1)
        return
    print(ans+sum(A))
    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:
import sys, math,os
from io import BytesIO, IOBase
from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
sys.setrecursionlimit(100000)
from fractions import Fraction
INF = float('inf')
mod = 998244353


def main():

    n=int(data())
    A=mdata()
    act=[0]*(n+1)
    t=1
    if n==0 and A[0]!=1:
        out(-1)
        exit()
    for i in range(n):
        act[i]=t-A[i]
        if act[i]<0:
            out(-1)
            exit()
        t=act[i]*2
    for i in range(n,0,-1):
        if act[i-1]<(act[i]+A[i])//2+(act[i]+A[i])%2 :
            out(-1)
            exit()
        act[i-1]=min(act[i]+A[i],act[i-1])
    ans=0
    for i in range(n):
        if act[i]<(act[i+1]+A[i+1])//2+(act[i+1]+A[i+1])%2 or act[i]>(act[i+1]+A[i+1]):
            out(-1)
            exit()
    for i in range(n+1):
        ans+=act[i]+A[i]
    out(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 1
now = 1

s = sum(a)
if a[0] == 1 and n != 0:
    ans = -1
elif n == 0:
    if a[0] == 1:
        ans = 1
    else:
        ans = -1
if n == 1 and a[1] >= 3:
    ans = -1

else:
    for i in range(n):
        s -= a[i]
        if a[i] > now:
            ans = -1
            break
        elif s <= (now-a[i])*2:
            now = s
            ans += now
        else:
            now = (now-a[i])*2
            ans += now
        if i == n-1:
            if now != a[-1]:
                ans = -1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=1
flag=0
sum_=0
for i in range(N+1):
  sum_+=A[i]
node=2
if A[0]>0:
  flag=1
  if A==[1] and N==0:
    flag=2
if N!=0:
  sum_-=A[1]
for i in range(1,N+1):
  if i!=N and node-A[i]<=0:
    flag=1
  elif i!=N:
    sum_-=A[i+1]
    ans+=node
    if 2*(node-A[i])-A[i+1]<=sum_:
      node=2*(node-A[i])
    else:
      node=sum_+A[i+1]   
  else:
    if node-A[i]<0:
      flag=1
    else:
      ans+=A[i]
if N==0 and A==[0]:
  flag=1

if flag==1:
  print("-1")
elif flag==2:
  print("1")
else:
  print(ans)