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:
n=int(input())
a=list(map(int,input().split()))
if n==1:
  if a==[0,1]:
    print(2)
  elif a==[0,2]:
    print(3)
  else:
    print(-1)
  exit()
if n==0:
  if a==[1]:
    print(1)
  else:
    print(-1)
  exit()



subt=[0]*(n)
if a[0] == 0:
  subt[0]=2
elif a[0]== 1:
  subt[0]=1
else:
  print(-1)
  exit()

for i in range(n-1):
  #subt[i+1]=subt[i]-subt[i]*2
  #print(subt[i])
  if a[i+1] > subt[i]-1:
    if i<n-1:
      print(-1)
      #print(n)
      #print(subt[i])
      exit()
      #pass
    elif a[i+1] > subt[i]:
      print(-1)
      exit()
      #pass
  else:  
    subt[i+1]=(subt[i]-a[i+1])*2
if a[n]> subt[-1]:
  print(-1)
  exit()
if a[n] > subt[-2]:
  subt[-1]=a[n]
else:
  subt[-1]=a[n]
  for j in range(2,n):
    if (subt[-j]-a[-j])*2 < subt[1-j]:
      print(-1)
      exit()
    if (subt[-j]-a[-j]) <= subt[1-j]:
      pass
    else:
      subt[-j]=subt[1-j]+a[-j]
  
    #pass
  
print(sum(subt)+1)
    
#print(subt)

Submission status: Accepted

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

apex = [0]*(N+1)
apex[0] = 1
a = 0
listed = [0]*(N+1)
listed[0] = 1
listed[N] = A[N]

if (A[0] != 0)&(N != 0):
    a = 1
elif (A[0] != 1)&(N==0):
    a = 1

for d in reversed(range(1,N)): #N-1から1まで
    listed[d] = listed[d+1] + A[d]

for d in range(1,N+1):
    listed[d] = min(listed[d],apex[d-1]*2)
    apex[d] = listed[d] - A[d]
    if A[d] > listed[d]:
        a = 1
        break


if a == 1:
    print('-1')
else:
    print(sum(listed))

Submission status: Accepted

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

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

sum_a = [ sum( a ) ]
for d in range( 1, n + 1 ):
    sum_a_next = sum_a[ -1 ] - a[ d - 1 ]
    sum_a.append( sum_a_next )

d_vertex = [ 0 for d in range( n + 1 ) ]

d_vertex[ 0 ] = 1
num_of_v = d_vertex[ 0 ]
for d in range( 1, n + 1 ):
    d_vertex[ d ] = min( sum_a[d], ( d_vertex[ d - 1 ] - a[ d - 1 ] ) * 2 )
    if d_vertex[ d ] <= 0:
        print( -1 )
        exit()
    num_of_v += d_vertex[ d ]

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

print( num_of_v )

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
if n == 0:
    print([-1, 1][a[0] == 1])
    exit()
if a[0] > 0:
    print(-1)
    exit()
s = sum(a)
ans = 1
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n):
    dp[i + 1] = min(s, 2 * dp[i])
    ans += dp[i + 1]
    dp[i + 1] -= a[i + 1]
    s -= a[i + 1]
    if dp[i] <= 0:
        print(-1)
        exit()
if dp[-1] < 0:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A_list = list(map(int, input().split()))
count_node = 0
count_pre_node = 0
sum_node = 0
Tree_list = []

for  i in range(len(A_list)):
    if i == 0:
        Tree_list.append(1)
        continue
    Tree_list.append(2*(Tree_list[i-1]) - A_list[i])
Tree_list.reverse()

A_list.reverse()
for i in range(len(A_list)):
    if n == 0 and A_list[0] == 1:
        sum_node = 1
        break

    count_node = A_list[i] + count_pre_node
    sum_node += count_node
    
    #一番上がエラーの時
    if i == 0 and A_list[-1] != 0:
        sum_node = -1
        break
    
    #ラストなら終わり
    if i == len(A_list)-1:
        break

    if count_node > 2*Tree_list[i+1]:
        sum_node = -1
        break
    
    if count_node >= Tree_list[i+1]:
        count_pre_node = Tree_list[i+1]
    else:
        count_pre_node = count_node

print(sum_node)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
flag=True
ans=0
B=[0 for i in range(N+1)]
for i in range(N+1):
  if(i==0):
    if(A[i]==0):
      B[i]=1
    if((A[i]==1 and N>0) or (N==0 and A[i]>1)):
      flag=False
  else:
    B[i]=B[i-1]*2-A[i]
  if(B[i]<0):
    flag=False
    break
x=B[N]#層の葉でない頂点数
y=A[N]#層の頂点数
ans=A[N]
for i in range(N):
  if(x>B[N-1-i]*2):
    flag=False
    break
  else:
    x=min(y,B[N-1-i])
    y=x+A[N-1-i]
    ans+=y
if flag:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
import math

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

result=0
tr=[0 for _ in range(N+1)]
miki=0
max_miki=[0 for _ in range(N+1)]

for i in range(N+1):
    if i==0:
        max_miki[i]=1
    else:
        max_miki[i]=(max_miki[i-1]-lf[i-1])*2

i=N

while i>=0:
    if i==N:
        if lf[N]>max_miki[N]:
            result=-1
            break
        tr[N]=lf[N]
        result+=lf[N]
        i-=1
    else:
        miki=int(min(tr[i+1]+lf[i],max_miki[i]))
        tr[i]=miki
        result+=miki

        if (miki-lf[i])*2<tr[i+1]:
            result=-1
            break
        i-=1

print(result)

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10


    N = II()
    A = LMIIS()


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


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

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


    sum_top = 1

    tmp = 1
    
    for i in range(1,N+1):
        max_l = tmp*2
        if max_l >= max_nodes[i]:
            print(sum_top+sum(max_nodes[i:]))
            return
        sum_top += max_l
        tmp = max_l - A[i]
        if tmp < 0:
            print(-1)
            return

    dbg(sum_top)
    print(-1)


main()

Submission status: Accepted

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

d=[0]*(N+1)

f=1
H=2**N

for i in range(N+1):
    if i==0:
        d[i]=1
    else:
        d[i]=(d[i-1]-A[i-1])*2
        
    if A[i]>d[i]:
        f=0

J=[0]*(N+1)
J[N]=A[N]

if f==0:
    print(-1)
else:
    for i in range(N-1,-1,-1):
        if d[i]>=J[i+1]+A[i]:
            J[i]=J[i+1]+A[i]
        else:
            J[i]=d[i]

    print(sum(J))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
asum=[]
s=sum(a)
for i in range(n):
    s=s-a[i]
    asum.append(s)
ans=1
x=2**n
p=1
if n==0:
    if a[0]==1:
        print(1)
    else:
        print(-1)
    sys.exit()
for i in range(n):
    x//=2
    p-=a[i]
    if 2*p<asum[i]/x or asum[i]<p:
        print(-1)
        sys.exit()
    p=min(2*p,asum[i])
    ans+=p
print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    
    cum = [0]
    for i in range(N):
        cum.append(cum[-1]+a[-i-1])
    
    cum.reverse()
    ans = 1
    if N == 0:
        if a[0] == 1:
            print(1)
        else:
            print(-1)
        exit()
    if a[0] != 0:
        print(-1)
        exit()
    base = 1
    for i in range(1,N):
        if a[i] > base*2:
            print(-1)
            exit()
        use = min(base*2,cum[i]+a[i])
        ans += use
        base = use-a[i]
    
    if base*2 < a[-1]:
        print(-1)
    else:
        print(ans+a[-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

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

cs = list(accumulate(a[::-1]))[::-1]

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

Submission status: Accepted

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

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

top_m = [0] * (n+1)
top = 1
for i, x in enumerate(a):
    top_m[i] = top - x
    top = top_m[i] * 2
top_m = top_m[::-1][1:]
# print(top_m)

p_max = a[-1]
p_min = math.ceil(p_max/2)
top = p_max
a = a[::-1][1:]
for i, x in enumerate(a):
    # print(x, p_max, p_min, top_m[i], top)
    if p_min > top_m[i]:
        print(-1)
        exit()
    now = x + min(p_max, top_m[i])
    p_max = now
    p_min = math.ceil(now/2)
    top += now
print(top)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
#len(A)=N+1
ak=1-A[0]
if ak<0:
    print(-1)
    exit()
a=[ak]
k=0
while(ak>=0 and k<N):
    ak=2*ak-A[k+1]
    a.append(ak)
    if ak<0:
        print(-1)
        exit()
    if ak>=10**14:
        #以降に関わらず構成可能
        break
    k+=1
#print(a)
M=len(a)
for k in range(N,0,-1):
    if k<=M:
        A[k-1]+=min(A[k],a[k-1])
    else:
        A[k-1]+=A[k]
        continue
print(sum(A))
#print(A)

Submission status: Accepted

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

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

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


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


for i in range(N):
    r[i] -= A[i]


q = A[N]
ans = q

for i in range(N):
    q = min(q,r[N-1-i]) + A[N-1-i]
    ans += q
print(ans)

Submission status: Accepted

Solution code:
import math
#3
#0 1 1 2

N = int(input())+1
leaves = list(map(int, input().split()))

nod = 0
total = 0

maxx = [0]*(N+1)
#toward
maxx[0] = 1
if N == 1 and leaves[0] == 1:
    total = 1
else:
    for i in range(1, N):
        notleave = maxx[i-1] - leaves[i-1]
        if notleave <= 0:
            total = -1
            break
        maxx[i] = notleave*2
        if maxx[i] < leaves[i]:
            total = -1
            break
        # if i == N-1:
        #     total += leaves[i]
        # else:
        #     total += maxx[i]



    #backward
    for i in range(1, N+1):
        ii = N-i
        #at least need newnod nodes
        newnod = int((nod+1)/2) + leaves[ii]
        if newnod > maxx[ii]:
            total = -1
            break
        #maximum is?
        newnod = nod + leaves[ii]
        if newnod > maxx[ii]: newnod = maxx[ii]
        if newnod <= 0:
            total = -1
            break
        total += newnod
        nod = newnod


if total <= 0: total = -1
print(total)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
a=[1-A[0]]
if a[0]<0:
    print(-1)
    exit()
for k in range(N):
    ak=a[-1]
    a.append(2*ak-A[k+1])
    if a[-1]<0:
        print(-1)
        exit()
    if a[-1]>10**17:
        break
M=len(a)
for k in range(N,0,-1):
    if k-1<M:
        A[k-1]=A[k-1]+min(A[k],a[k-1])
    else:
        A[k-1]=A[k-1]+A[k]
print(sum(A))

Submission status: Accepted

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

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

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

else:
    number = [1]*(N+1)
    for i in range(1, N+1):
        if number[i-1]-A[i-1] <= 0:
            print(-1)
            exit()
        else:
            number[i] = 2*(number[i-1]-A[i-1])
    if number[N] < A[N]:
        print(-1)
        exit()
    elif number[N] - A[N] > number[N-1] -A[N-1]:
        next = (number[N] - A[N]) - (number[N-1] -A[N-1])
        number[N] = A[N]
        for i in range(2, N):
            if next > (number[N-i] - A[N-i]):
                number[N-i+1] -= next
                next = next - (number[N-i] - A[N-i])
            else:
                number[N-i+1] -= next
                break
    else:
        number[N] = A[N]
print(sum(number))

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

tmp = [[1,1]]
for i in range(n+1):
    l,r = tmp[-1]
    if r < a[i]:
        print(-1)
        exit()
    if i != n:
        nl = max(0, l-a[i])
        nr = 2*max(0, r-a[i])
        tmp.append([nl, nr])
ans = 0
node = 0
for i in reversed(range(n+1)):
    ans += a[i]
    l, r = tmp[i]
    r -= a[i]
    l -= a[i]
    l = max(l, 0)
    if node <= r:
        use = node
    else:
        use = r
    ans += use
    node = use + a[i]
print(ans)

Submission status: Accepted

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

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

ans = 0
cur = 0
for i in reversed(range(N + 1)):
    cur += A[i]
    ans += min(cnt[i], cur)
        
if all(cnt[i] >= A[i] for i in range(N + 1)):
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

def floor_div(x,d):
    if x%d != 0:
        return int(x/d)+1
    else:
        return int(x/d)

N = int(input())

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

n_not_leaf = 0
sum_node = 0

num_node = [0 for d in range(N+1)]
max_node = [0 for d in range(N+1)]

# 各層のnodeのmax個を計算
for d in range(N+1):
    if d == 0:
        max_node[0] = 1
    else:
        max_node[d] = (max_node[d-1]-A[d-1])*2
    
    if d != N and max_node[d]-A[d] < 1:
        print(-1)
        exit()
if max_node[N]-A[N] < 0:
    print(-1)
    exit()


for d in reversed(range(N+1)):
    if d == N:
        num_node[N] = min(A[N], max_node[N])
    else:        
        if floor_div(num_node[d+1],2)+A[d] > max_node[d]:
            print(-1)
            exit()
        else:
            num_node[d] = min(num_node[d+1]+A[d], max_node[d])

print(sum(num_node))

Submission status: Accepted

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

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

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

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

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

ansl = [0]*(n+1)
# print(al, lim)

for i in range(n+1):
    if i == 0:
        if lim[n-i] >= al[n-i]:
            ansl[i] = al[n-i]
        else:
            print(-1)
            exit()
    else:
        ansl[i] = min(ansl[i-1]+al[n-i], lim[n-i]+al[n-i])

if sum(ansl) <= 0:
    print(-1)
    exit()

print(sum(ansl))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
s = [0]*(n+1)
y = 1
p = 0
for i in range(n+1):
    if(y-a[i] > 0):
        s[i] = y
        y -= a[i]
        y *= 2
    else:
        if(i != n):
            p = -1
            break
        elif(y == a[i]):
            s[i] = y
        else:
            p = -1
            break
if(p == -1):
    print(-1)
elif(n == 0):
    if(a[0] == 1):
        print(1)
    else:
        print(-1)
else:
    q = 0
    for i in range(n+1):
        q += a[-1-i]
        if(q <= s[-1-i]):
            p += q
        else:
            p += s[-1-i]
    print(p)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

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

cnt = [0 for _ in range(N + 1)]
cnt[0] = 1
prev = 1
pow_num = 2
for i in range(1, N + 1):
    cnt[i] = min(prev * 2, pow_num)
    if cnt[i] < A[i]:
        print(-1)
        exit(0)
    prev = cnt[i] - A[i]
    pow_num *= 2

ans = 0
sum_num = 0
for i in range(N, -1, -1):
    if (sum_num + 1) // 2 + A[i] > cnt[i]:
        print(-1)
        exit(0)
    sum_num = min(sum_num + A[i], cnt[i])
    ans += sum_num

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    
    if N != 0 and A[0] != 0:
        print(-1)
        return
    if N == 0 and A[0] != 1:
        print(-1)
        return
    
    v = [1]
    m = 2
    for ai in A[1:]:
        v.append(m)
        if m < ai:
            print(-1)
            return
        m -= ai
        m *= 2
    
    m = min(v[-1], A[-1])
    ans = m
    for i in range(N - 1, -1, -1):
        m = min(m + A[i], v[i])
        ans += m
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

ans = 0
tmp_max = 1
dp = [0]*(N+1)
for i, a in enumerate(A):
    if a <= tmp_max:
        dp[i] = tmp_max
        tmp_max = 2*(tmp_max-a)
    else:
        ans = -1
        break
if ans == -1:
    print(ans)
else:
    tmp = 0
    for i in reversed(range(N+1)):
        if tmp + A[i] >= dp[i]:
            ans += dp[i]
            tmp = dp[i]
        else:
            ans += tmp + A[i]
            tmp += A[i]
    print(ans)

Submission status: Accepted

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

"""
crt = 0
ttl = 0
for i in range(n,0,-1):
  crt += a[i]
  ttl+= crt
  print(crt)
  crt = crt // 2 + crt % 2
  print("next:{}".format(crt))
if crt!=1:
  print(-1)
else:
  print(ttl)
"""

ans = 0
ls = [0 for _ in range(n+1)]
crt = 1
ttl = 1
for i,l in enumerate(a):
  ls[i] = crt
  if crt - l < 0:
    ans =-1
    break
  if i == n:
    break
  crt = (crt-l)*2
  #print("crt{}".format(crt))
  ttl += crt
  #print("ttl{}".format(ttl))

crt = 0
for i in range(n,0,-1):
  #print("ls")
  #print(ls[i])
  #print(a[i])
  #print(crt)
  if ls[i] - a[i] - crt > 0:
    ttl -= (ls[i] - a[i] - crt)
    crt = a[i] + crt
  else:
    crt = ls[i]

if ans == -1:
  print(ans)
else:
  print(ttl)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=sum(a)-1
ans,x=0,1

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = sum(a)
if n > 0 and a[0] != 0:
    print(-1)
    exit()
if m > pow(2,n+1) - 1:
    print(-1)
    exit()
if n == 1:
    print(a[1]+1)
    exit()
l = 1
ans = 1
for i in range(n):
    x = a[i+1]
    if x > l*2:
        print(-1)
        exit()

    if m >= l*2:
        ans += l * 2
        l *= 2
    else:
        ans += m
        l = m
        #gr = False
    if x > 0:
        m -= x
        l -= x
        if m < 0:
            print(-1)
            exit()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
dmax = [0]*(n+2)
x = []*(n+1)

i = n
ne = 0
while i >= 0:
    dmax[i] = a[i] + dmax[i+1]
    i -= 1

hantei = True
ans = 0
x.append(1)

for i in range(n+1):
    if x[i] < a[i]:
        hantei = False
        break
    else:
        x.append(min((x[i]-a[i]) * 2,dmax[i+1]))
        ans += x[i]

print(ans) if hantei else print(-1)

Submission status: Accepted

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
for i in range(min(n+1,40)):
  if a[i]>2**i:
    print(-1)
    sys.exit()
if a[0]!=0 and n!=0:
  print(-1)
  sys.exit()
A=[0]
for i in range(n+1):
  A.append(A[-1]+a[i])
s=sum(a)
ans=1
x=1
for i in range(1,n+1):
  S=s-A[i]
  if x*2<S:
    ans+=x*2
    x*=2
    x-=a[i]
    if x<=0:
      print(-1)
      sys.exit()
  else:
    x=S
    ans+=x
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
# step 1 後ろからの累積
cum = [0] * (n + 1)
cum[n] = a[n]
for i in range(n):
    cum[n - 1 - i] = cum[n - i] + a[n - 1 - i]
# step2 dpを更新する
# dp はその深さに存在する頂点の数
dp = [0] * (n + 1)
dp[0] = 1
ans = dp[0]
ng = 0
for i in range(n):
    if dp[i] < a[i]:
        ng = 1
    dp[i + 1] = min(2 * (dp[i] - a[i]), cum[i + 1])
    if i < n and dp[i + 1] <= 0:
        ng = 1
    ans += dp[i + 1]
if n == 0:  # この時、a1 まで入っている。
    if a[0] == 1:
        print(1)
    else:
        print(-1)
elif a[n] != dp[n]:
    print(-1)
elif ng:
    print(-1)
else:
    print(ans)
# -1 ではないケースで落ちてる

Submission status: Accepted

Solution code:
n = int( input() )
p = [ int( pi ) for pi in input().split() ]

sump = int( 0 )
for pi in p:
    sump += pi

ans = int( 0 )
for i in range( n+1 ):
    if i == 0:
        ans += 1
        px = 1
        if p[ i ] == 1 and n == 0:
            ans = 1
            break
        if p[ i ] != 0 and p[ i ] != 1:
            ans = -1
            break
    else:
        if px*2 <= sump:
            ans += px*2
            px = px*2 - p[ i ]
            sump = sump - p[ i ]
        else:
            ans += sump
            px = sump - p[ i ]
            sump = sump - p[ i ]
#        print( px, sump )
        if i != n and px <= 0:
            ans = -1
            break
        elif i == n and sump != 0:
            ans = -1
            break
        elif i == n and px != 0:
            ans = -1
            break

print( ans )

Submission status: Accepted

Solution code:
def main():

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

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

    z, w = 1, 1
    B1 = [[1-A[0], 1-A[0]]]
    for i in range(1, N+1):
        if 2*B1[-1][1] < A[i]: return -1
        x, y = max(B1[-1][0]-A[i], 0), 2*B1[-1][1] - A[i]
        B1.append([x, y])
        z = x+A[i]
        w = y + A[i]
    if A[N] < z or A[N] > w:
        return -1
    # print(C1)

    v = A[N]
    ans = v
    for i in range(N-1, 0, -1):
        x, y = (v + 1) // 2, v
        z = 0
        if y < B1[i][0] or x > B1[i][1]: return -1
        if B1[i][0] <= y < B1[i][1]:
            z = y
        else:
            z = B1[i][1]
        v = z + A[i]
        ans += v
    # print(C2)

    return ans + 1

    # return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

balls = [0] * (n + 1)

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

for i in range(n+1):
  balls[i] += A[i]

box = [0] * (n + 1)
box[-1] = A[-1]

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

ans = 0
for i, j in zip(balls, box):
  ans += min(i, j)

ans = [min(i, j) for i, j in zip(balls, box)]

# print(balls)
# print(box)
# print(ans)

if any(i * 2 < j for i, j in zip(ans, ans[1:])) or (ans[0] != 1) or any(i < 1 for i in ans) or any(i < j for i, j in zip(ans, A)):
  print(-1)
else:
  print(sum(ans))

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def solve(N: int, A: "List[int]"):
    if N == 0:
        if A[0] == 1:
            print(1)
        else:
            print(-1)
        return
        
    ans = 2 ** (N + 1) - 1
    len_list = []
    current_len = 1
    for depth, leafs in enumerate(A):
        ans -= leafs * (2 ** (N - depth + 1) - 2)
        len_list.append(current_len - leafs)
        current_len = (current_len - leafs) * 2
    last_leaf = len_list[-1]
    if last_leaf < 0:
        print(-1)
        return
    must_delete = last_leaf
    # print(must_delete)
    for _depth, x in enumerate(len_list[::-1]):
        depth = N - _depth
        leaf = A[depth]
        if must_delete <= (x + leaf) // 2:
            ans -= must_delete
            if ans > 0:
                print(ans)
            else:
                print(-1)
            return
        ans -= must_delete
        must_delete -= (x + leaf) // 2
    print(-1)
    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:
import sys
max_int = 1000000001  # 10^9+1
min_int = -max_int

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
a_ = a[::-1]

sum = 0
prev_min = 0
prev_max = 0

prev = []

for num, one in enumerate(a_):
    prev_min = (prev_min + 1) // 2 + one
    prev_max += one
    level_maximum = 2 ** (len(a) - 1 - num)
    if prev_min > level_maximum:
        print(-1)
        exit()

    prev_max = min(level_maximum, prev_max)
    prev.append([prev_min, prev_max])

prev = prev[::-1]

sum = 0
available = 1
for one in zip(prev, a):
    available = min(available, one[0][1])
    sum += one[1]
    available -= one[1]
    sum += available

    available *= 2

print(sum)

Submission status: Accepted

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

import math

Min=[0]*(n+1)
Max=[0]*(n+1)
true=[0]*(n+1)
ans=sum(a)
fault=0

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

  else:
    print(ans)
else:
  if a[0]==0:
    Min[0]=1
    Max[0]=1


  for i in range(1,n):
    m=Min[i-1]-a[i]
    M=Max[i-1]*2-a[i]
    if M<0:
      fault=1
      #print('i')
      break
    Min[i]=max(m,0)
    Max[i]=M

#print(Min)
#print(Max)

  if a[n]<Min[n-1] or 2*Max[n-1]<a[n]:
    fault=1
#else:
  #Min[n]=a[n]
  #Max[n]=a[n]
  #true[n]=a[n]

  for i in reversed(range(1,n)): 
    true[i]=min(Max[i],true[i+1]+a[i+1])
    ans+=true[i]

  if fault==1:
    print(-1)
  else:
    print(ans+1)

Submission status: Accepted

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

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

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

# 根の数
node = 1
root = 0

s = sum(A)

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

print(root + sum(A) + 1 if not node else -1)

Submission status: Accepted

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


if n == 0 and ha[0] == 1:
    print(1)
elif ha[0] != 0:
    print(-1)
else:
    oya = [[0,0] for i in range(n+1)]
    ten = [[0,0] for i in range(n+1)]
    ten[n] = [ha[n],ha[n]]
    for i in reversed(range(n)):
        oya[i] = [int((ten[i+1][0]+1)/2),(ten[i+1][1])]
        ten[i] = [oya[i][0] + ha[i], oya[i][1] + ha[i]]

    if 1 < oya[0][0] or oya[0][1] < 1 or 1 < ten[0][0] or ten[0][1] < 1:
        print(-1)
    else:
        oya[0] = 1
        ten[0] = 1
        for i in range(1,n+1):
            ten[i] = min(oya[i-1]*2, ten[i][1])
            oya[i] = ten[i]-ha[i]
        print(sum(ten))

Submission status: Accepted

Solution code:
from math import ceil

def a():
    N = int(input())
    A = list(map(int,input().split()))
    INF = 10**13
    if N == 0:
        if A[0] == 1:
            return 1
        else:
            return -1

    BMAX = [INF] * (N+1)
    BMIN = [1] * (N+1)

    BMAX[0] = 1 - A[0]
    BMAX[N] = 0
    BMIN[0] = 1
    BMIN[N] = 0

    for i in range(N-1,-1,-1):
        BMAX[i] = min(BMAX[i],BMAX[i+1]+A[i+1])
        BMIN[i] = max(BMIN[i],ceil((BMIN[i+1]+A[i+1])/2))

    if BMIN[0] > BMAX[0]:
        return -1

    for i in range(1,N+1):
        BMAX[i] = min(BMAX[i],BMAX[i-1]*2-A[i])
        BMIN[i] = max(BMIN[i],BMIN[i-1]-A[i])
        if BMIN[i] > BMAX[i]:
            return -1
        
    return sum(BMAX)+sum(A)

print(a())

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
xl=list(reversed(l))
g=[]
a=1
k=0
f=0
for i in xl:
  k+=i
  g.append(k)
g.reverse()
for i in range(len(g)):
  if g[i]>=a:
    g[i]=a
  a-=l[i]
  a*=2
  if a<=0 and i!=len(g)-1:
    f+=1
    break
  if a<0 and i==len(g)-1:
    f+=1
    break
if f==0 and n!=0:
  print(sum(g))
elif n==0:
  if l[0]==1:
    print(1)
  else:
    print(-1)
else:
  print(-1)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
if a[0]>1 or a[0]==1 and n>1:
    print(-1)
    exit()
sm = 0  #a[n]
b = a[n]
c = [0]*(n+1)
c[0] = 1
for i in range(n):
    c[i+1] = min(BIG,2*(c[i]-a[i]))
    if c[i+1]<a[i+1]:
        print(-1)
        exit()
c[n] = a[n]
IMAX = 50
for i in range(n-1,-1,-1):
    b = (b+1)//2 + a[i]
    if i<IMAX and b>2**i:
        print(-1)
        exit()
    c[i] = min(c[i],c[i+1]+a[i])
    if i<IMAX:
        c[i] = min(c[i],2**i)
        #if i>0:
        #    c = min(c,2*(2**(i-1)-a[i-1]))
    #sm += c
    #ddprint(f"{i=} b {b} ci {c[i]}")
#ddprint(c)
print(sum(c))

Submission status: Accepted

Solution code:
import sys
import itertools

N = int(input())
A = list(input().split())
A = [int(A[i]) for i in range(N+1)]
MAX = [1 for i in range(N+1)]
A_inter = list(reversed(list(itertools.accumulate(reversed(A)))))

for i in range(N+1):
    if A[i] > MAX[i]:
        print(-1)
        sys.exit()
    elif i != N:
        MAX[i+1] = (MAX[i] - A[i]) * 2
        
print(sum([min(MAX[i], A_inter[i]) for i in range(N+1)]))