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:
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==0 and A[0]!=1:
        print(-1)
        return 
    if N!=0 and A[0]!=0:
        print(-1)
        return 
    tmp=[0]
    for i,v in enumerate(A[1:][::-1]):
        tmp.append(tmp[-1]+v)
    tmp.pop(0)
    ans=1
    t=1
    for i,v in enumerate(tmp[::-1]):
        t*=2
        if A[i+1]==0:
            if t < A[i+1]:
                print(-1)
                return
            t=min(t,v)
            ans+=t
        else:
            t=min(t,v)
            if t < A[i+1]:
                print(-1)
                return
            ans+=t
            t-=A[i+1]
    print(ans)

main()

Submission status: Accepted

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

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

flg = True

branch = [1]
for depth in range(1, N+1):
    b = branch[-1] * 2 - As[depth]
    if b >= 0:
        branch.append(b)
    else:
        print(-1)
        exit()

s = 0
b = 0
for i in range(N, 0, -1):
    b += As[i]
    if b > branch[i-1] * 2:
        s += sum(branch[:i+1]) + sum(As[:i+1])
        break
    else:
        s += b
else:
    s += 1

print(s)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N=len(v)
    size=len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    global count
    count=0
    def r(n,cmin,cmax):  
        global count   
        ncmax=cmax+A[n]
        ncmin=math.ceil(cmin*0.5)+A[n]
        if n==0:
            nodes=1
            if ncmin>nodes or ncmax<nodes:
            #print(cmin,n)
                print(-1)
                exit()
            count+=1
            return min(cmax,2)
        nodes=r(n-1,ncmin,ncmax)
        if ncmin>nodes or ncmax<nodes:
            #print(cmin,n)
            print(-1)
            exit()
        
        count+=nodes
        return min(2*(nodes-A[n]),cmax)

    r(N,0,0)
    print(count)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

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

for i in range(N-1, -1, -1):
    low[i] = (low[i+1]+1)//2+A[i]
    high[i] = high[i+1]+A[i]
    lim = 2**i
    
    if low[i]>lim:
        print(-1)
        exit()
    
    high[i] = min(high[i], lim)

now = 1
ans = now

#print(low)
#print(high)

for i in range(N):
    now = min(high[i+1], 2*now)
    ans += now
    now -= A[i+1]
    
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*a = map(int, read().split())



L = [0]*(n+1)
R = [0]*(n+1)
l = r = a[n]
L[n] = R[n] = 0


ok = 1
for i in range(n-1,-1,-1):
    ai = a[i]
    l = (l+1)//2
    r = min(r,1<<i)
    if i <= 60:
        if l+ai > 1<<i:
            ok = 0
            break
        else:
            r = min(r,(1<<i)-ai)
    L[i] = l
    R[i] = r
    l += ai
    r += ai

        
if not ok or n==0 and a[0]!=1:
    print(-1)
else:
    #print(L,R)
    ans = living = R[0]
    ans += a[0]

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

        #print(living,a[i],R[i])
        
        living = min(living,R[i])
        
        ans += living + a[i]        
        
        #print(living,R[i])

    print(ans)

Submission status: Accepted

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

dp = [[0, 0] for _ in range(N + 1)]
dp[N][0] = A[N]
dp[N][1] = A[N]

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

res = [0 for _ in range(N + 1)]

tmp = 1
for i in range(N + 1):
    if tmp < dp[i][0] or dp[i][1] < tmp // 2:
        print(-1)
        break
    res[i] = min(tmp, dp[i][1])
    tmp = res[i]
    tmp -= A[i]
    tmp *= 2

else:
    print(sum(res))

Submission status: Accepted

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

s = 1
if n == 0:
    if a[0] != 1:
        print(-1)
        quit()
    else:
        print(1)
        quit()
elif a[0] > 0:
    print(-1)
    quit()
memo = [[0,0] for _ in range(n+1)]
memo[0] = [0,1]
for i in range(1,n+1):
    if s == 0:
        print(-1)
        quit()
    s = memo[i-1][1]*2
    if s > 10**15:
        s = 10**15
    memo[i][0] = a[i]
    memo[i][1] = s-a[i]
    if s-a[i] < 0:
        print(-1)
        quit()
ans = [[a[i],0] for i in range(n+1)]
for i in range(n-1,-1,-1):
    if (ans[i+1][0]+ans[i+1][1]) > memo[i][1]*2:
        print(-1)
        quit()
    else:
        ans[i][1] = min(memo[i][1],ans[i+1][0]+ans[i+1][1])
s = 0
for i in range(n+1):
    s += sum(ans[i])
print(s)

Submission status: Accepted

Solution code:
from math import ceil

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


layer=[]#(nodes leaf)
node=1
for i,leaf in enumerate(A):
    if node>leaf:#どうにかなる
        r = node-leaf
        node=r*2
        layer.append([i,leaf,r])
    elif node==leaf:#最後ならどうにかなる
        if i==N:
            node-=leaf
            layer.append([i,leaf,node])
            break
        else:
            print(-1)
            exit()
    else:
        print(-1)
        exit()

ans=1

cur_node=0
for dep,leaf,node in reversed(layer[1:]):
    ans+=leaf+cur_node
    upper_layer_node = layer[dep-1][2]
    #次のレイヤーのノードの数
    cur_node = min(upper_layer_node,leaf+cur_node)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
*A,=map(int,input().split())
Ar=A[::-1]
ans=[0]*(N+1)
i=0
count=0
while i<=N:
    count+=Ar[i]
    if count>2**(N-i):
        count=2**(N-i)
    ans[-(i+1)]=count
    i+=1

j=0
while j<N:
    if ans[j+1]>2*(ans[j]-A[j]):
        ans[j+1]=max(2*(ans[j]-A[j]),0)
    j+=1

k=0
while k<=N:
    if A[k]>2**k:
        ans[k]=0
    k+=1

l=0
while l<=N:
    if ans[l]<A[l]:
        ans[l]=0
    l+=1

if 0 in ans:
    print(-1)
else:
    print(sum(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split())) 
ans = 0
count = 1 # 頂点数
bo = 1 #作れるか判定
lena = len(a)
asum = -1       # 葉の数-1回2分する
for i in range(lena):
    asum += a[i]
    bo -= a[i]
    if bo == 0 and i != lena-1:
        print(-1)
        exit()
    if bo < 0:
        print(-1)
        exit()
    bo*=2
count2 = 0 #2分した回数
ans = 1
for i in range(lena):
    count -= a[i]
    tmp = min(count,asum-count2)
    count += tmp
    count2 += tmp
    ans += count
    #print(ans,count)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int, input().split()))
ans = 0
leaf = 1
for i in range(N+1):
    if S[i] > leaf:
        ans = -1
        break
    leaf -= S[i]
    leaf *= 2
if ans == -1:
    print(ans)
else:
    dm = [0]*(N+1)
    dm[0] = 1
    for i in range(1, N+1):
        dm[i] = dm[i-1]*2 - S[i]
    leaf = 0
    for i in range(N, -1, -1):
        ans += min(leaf, dm[i]) + S[i]
        leaf += S[i]
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
k=0
N=sum(a)
failflag=0
node=1
min1=[]
min2=[]
for i in range(0,n+1):
  node=node*2-a[i]
  if i==0:
    node=1-a[0]
  node=min(node,N)
  min1.append(node+a[i])
  if node<0:
    failflag=1
if failflag==1:
  print(-1)
else:
  current=0
  for i in range(0,n+1):
    current+=a[n-i]
    min2.append(current)
  min2.reverse()
  ans=0
  for i in range(0,n+1):
    ans+=min(min1[i],min2[i])
  print(ans)

Submission status: Accepted

Solution code:
def main():
  import math
  N = int(input())
  xyz = list(map(int, input().split()))
  S = sum(xyz)
  K = math.ceil(math.log(S, 2))
  T = 1
  table = [0] * (N+1)
  for i in range(N+1):
    if S < T:
      table[i] = S
    else:
      table[i] = T
    S -= xyz[i]
    T = (T - xyz[i]) * 2
  if T < 0:
    print(-1)
  else:
    print(sum(table))
main()

Submission status: Accepted

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


def req_node(i,belowmin,belowmax):

    thismax = belowmax+arr[i]
    thismin = (belowmin+arr[i])//2+(belowmin+arr[i])%2

    return req_node(i-1,thismin,thismax)

bmin = [arr[-1]]
bmax = [arr[-1]]


belowmin = arr[-1]
belowmax = arr[-1]
for i in range(2,n+2):
    thismax = belowmax+arr[-i]
    thismin = (belowmin)//2+(belowmin)%2+arr[-i]
    bmin.append(thismin)
    bmax.append(thismax)
    belowmax = thismax
    belowmin = thismin



bmin.reverse()
bmax.reverse()

# print(bmin)
# print(bmax)

nodes =  1
ans = 0
flag =True
for i in range(n):
    ans += nodes
    # print(nodes,ans)
    nextmax = 2*(nodes-arr[i])
    nextmin = nodes-arr[i]

    nodes = min(bmax[i+1],nextmax)
    if nextmax < bmin[i+1] or nextmin > bmax[i+1]:
        flag = False
        # print("break")
        break

# print(arr)
if flag:
    # if arr[-1] <= nodes*2:
    #     print(ans+arr[-1])
    # else:
    #     print(-1)
    if n == 0:
        if arr[0] == 0:
            print(0)
        elif arr[0] == 1:
            print(1)
        else:
            print(-1)
    else:
        print(ans + arr[-1])

else:
    print(-1)

Submission status: Accepted

Solution code:
n = int(input())
a_list = [int(x) for x in input().split()]

node = 1
flg = False
node_list = [node]

for i in range(len(a_list)-1):
  num = a_list[i]
  next = node-num
  if next < 0:
    flg = True
    break
  node = next*2
  node_list.append(node)

if node - a_list[-1] < 0:
  flg = True
else:
  diff = a_list[-1]
  res_list = [a_list[-1]]
  for i in range(len(a_list)-2,-1,-1):
    v = node_list[i] - a_list[i] # 枝の数
    diff = min(diff,v) + a_list[i]
    res_list.append(diff)

if flg:
  print(-1)
else:
  print(sum(res_list))

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    An = [int(x) for x in input().strip().split()]
    if N == 0:
        if An[0] == 1:
            print(1)
        else:
            print(-1)
        exit()
    if An[0] != 0:
        print(-1)
        exit()
    ans = 1
    node = 1
    total = sum(An)
    for n, a in enumerate(An[1:], start=1):
        node_ = min(total, node * 2)
        ans += node_
        node = node_ - a
        if node_ < 0:
            print(-1)
            exit()
        total -= a

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

P=[0]*(N+1)
P[N]=A[N]
Q=[0]*(N+1)
Q[N]=A[N]

for i in range(N,0,-1):
    mxp=P[i]+A[i-1]
    mnp=(P[i]//2) + (P[i]%2) +A[i-1]
    mxq=Q[i]+A[i-1]
    mnq=(Q[i]//2) + (Q[i]%2) +A[i-1]
    if mnp>2**i:
        print(-1)
        exit()
    P[i-1]=mnp
    Q[i-1]=min(mxq,2**i)

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

Q[0]=1

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

print(sum(Q))

Submission status: Accepted

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

max_nood = sum(A)
count_nood = 0
corrent_nood = 0
ans = True

for i in range(N+1):
    if i == 0:
        corrent_nood = 1
        count_nood += corrent_nood
        max_nood -= A[i]
    else:
        corrent_nood = min(2*(corrent_nood-A[i-1]), max_nood)
        max_nood -= A[i]
        count_nood += corrent_nood
    if corrent_nood <= 0 or A[i] > corrent_nood:
        ans = False
        # print(i)
        break
if ans:
    print(count_nood)
else:
    print(-1)

Submission status: Accepted

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

n = int(input())
p = list(map(int, input().split()))
if (n==0):
    if (p[0]==1):
        print(1)
        exit()
    else:
        print(-1)
        exit()
if (p[0]!=0):
    print(-1)
    exit()
#t = [1,1,0] #最大頂点数、最下段の空いている頂点数、閉じてない頂点数
sum_p = sum(p)
eda = 1
ans = 1
for i in range(1,n+1):
    eda *= 2
    ans += eda
    eda -= p[i]
    sum_p -= p[i]
    #print(i,eda,ans,sum_p)
    if (i!=n and eda<=0):
        print(-1)
        exit()
    if (i==n and eda<0):
        print(-1)
        exit()
    if (eda>=sum_p): #広げ切った
        ans -= (eda-sum_p)
        #print(ans)
        for j in range(i+1,n+1):
            ans += sum_p
            sum_p -= p[j]
        print(ans)
        exit()
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()

c = [1]*(n+1)
for i in range(1, n+1):
    c[i] = (c[i-1]-a[i-1])*2
if a[n]>c[n]:
    print(-1)
    sys.exit()
b = [0]*(n+1)
res = [0]*(n+1)
b[n] = a[n]
res[n] = a[n]
for i in range(n-1, -1, -1):
    if (c[i]-a[i])*2 <res[i+1]:
        print(-1)
        sys.exit()
    b[i] = min(c[i]-a[i], res[i+1])
    res[i] = a[i] + b[i]
print(sum(res))

Submission status: Accepted

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

MAX = [1]
for i in range(N):
  #print(MAX[-1],A[i+1])
  MAX.append((MAX[-1]-A[i])*2)
#print(MAX)

ans = A[-1]
mae = A[-1]

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


for i in range(N):
  #print(mae)
  if mae%2 == 0:
    tmin = mae//2
  else:
    tmin = mae//2+1
  if tmin + A[-i-2] > MAX[-i-2]:
    print("-1")
    sys.exit()
  tmax = mae+A[-i-2]
  #print(tmax,MAX[-i-2])
  mae = min(tmax,MAX[-i-2])
  ans += mae
print(ans)

Submission status: Accepted

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

ans = 1
up = [1 for _ in range(n)] # ノードの上限 - a[i]
node = [1 for _ in range(n+1)] # n層目のノード
node[-1] = a[-1]

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

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

# print(up)
for i in range(1, n):
    up[i] = up[i-1]*2 - a[i]
    if up[i] <= 0:
        print(-1)
        exit()
for i in range(n-1, -1, -1):
    tmp_node = node[i+1] + a[i]
    if node[i+1]/2 + a[i] > up[i]+a[i]:
        print(-1)
        exit()
    node[i] = min(tmp_node, up[i]+a[i])
# print(up)
# print(node)
print(sum(node))

Submission status: Accepted

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

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

for i in range(n+1):
    if pos[i] < 0:
        print(-1)
        exit()

cnt = a[-1]
memo = 0
for i in range(n-1, -1, -1):
    cnt += min(pos[i], memo + a[i+1]) + a[i]
    memo = min(pos[i], memo + a[i+1])


print(cnt)

Submission status: Accepted

Solution code:
def main():
    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)
        exit()
    C=[0]*(n+1)
    flag=True
    ans=1
    if A[0]==1:
        C[0]=0
        c=0
    else:
        C[0]=1
        c=1
    for i in range(n):
        a=A[i+1]
        c*=2
        ans+=c
        C[i+1]=c
        if c<a:
            flag=False
            break
        else:
            c-=a
    if flag:
        for i in range(n):
            if c>0:
                ans-=c
                c-=C[n-i]//2
            else:
                break
        print(ans)
    else:
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue
n = int(input())
a = list(map(int,input().split()))
xx = [0]*(n+1)
x = 1
c = 0
for i in range(n+1):
  if x >= a[i]:
    c += a[i]
    xx[i] = x-a[i]
    x = 2*(x-a[i])
  else:
    print(-1)
    exit()
y = a[n]
i = n-1
while y > 0:
  if xx[i] >= y:
    c += y
  else:
    c += xx[i]
    y = xx[i]
  y += a[i]
  if i > 0:
    i -= 1
  else:
    break
print(c)

Submission status: Accepted

Solution code:
import sys
n = int(input())
a = list(map(int, input().split()))
if n==0:
    if a[0]<2:
        print(a[0])
    else:
        print(-1)
    sys.exit()
tree = [0 for _i in range(n+2)]
tree[0] = 1
for i in range(1,n+1):
    tree[i] = tree[i-1]*2
    tree[i] -= a[i]
tree[n] += a[i]
for i in range(n, 0, -1):
    if tree[i-1]*2 < a[i]:
        print(-1)
        sys.exit()
    x = min(tree[i-1], a[i])
    a[i-1] += x
if a[0]>1:
    print(-1)
else:
    print(sum(a))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    r = 0
    t = 0
    B1 = [0] * (N + 1)
    B2 = [0] * (N + 1)
    p = 0
    for i in reversed(range(N + 1)):
        a = A[i]
        B1[i] = p
        p += a
    t = 1
    for i, a in enumerate(A):
        b1 = B1[i]
        b2 = 0
        t -= a
        if t < 0:
            return -1
        if b1 > t:
            b2 = min(t, b1 - t)
            b1 = min(t - b2, b1 - 2 * b2)
        B1[i] = b1
        B2[i] = b2
        t = b1 + 2 * b2

    return sum(A) + sum(B1) + sum(B2)

print(main())

Submission status: Accepted

Solution code:
from itertools import accumulate
n, *A = map(int, open(0).read().split())
if A[0] != 0:
    if A[0] == 1 and n == 0:
        print(1)
    else:
        print(-1)
else:
    B = list(accumulate(A[::-1]))[::-1] + [0]
    C = [0] * (n+1)
    D = [0] * (n+1)
    C[0] = 1
    D[0] = 1

    for i in range(1, n+1):
        C[i] = min(B[i], 2*D[i-1])
        D[i] = C[i] - A[i]
        if D[i] < 0:
            print(-1)
            break
    else:
        print(sum(C))

Submission status: Accepted

Solution code:
import sys

def intersection(I1, I2):
    left = max(I1[0], I2[0])
    right = min(I1[1], I2[1])
    return [left, right]


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

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

P = []

P.append([1,1])

for i in range(n):
    left = P[i][0]-A[i+1]
    right = 2*P[i][1]-A[i+1]
    P.append([left, right])

#print("Forward check")
#print(P)

if 0 < P[n][0] or P[n][1] < 0:
    print(-1)
    sys.exit()

P[n] = [0,0]
for i in reversed(range(n)):
    left = A[i+1]+P[i+1][0]
    left = -(-left//2)
    right = A[i+1]+P[i+1][1]
    P[i] = intersection(P[i], [left, right])
#print("Backward check")
#print(P)

ans = 0
for i in range(n+1):
    ans += P[i][1] + A[i]

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] >= 1:
    print(-1)
    exit()

# 根から見たときにあり得る各層最大の要素数
max_leaf = [0] * (N + 1)
max_leaf[0] = 1
leaf = 1
for i in range(N):
    leaf = 2 * (leaf - A[i]) 
    if leaf < 0:
        print(-1)
        exit()
    max_leaf[i+1] = leaf

result = [0] * (N+1)
result[N] = A[N]
for i in reversed(range(N)):
    if result[i+1] + A[i] <= max_leaf[i]:
        result[i] = result[i+1] + A[i]
    elif -(-result[i+1] // 2) > max_leaf[i]:
        print(-1)
        exit()
    else:
        result[i] = max_leaf[i]

print(sum(result))

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

if N != 0:

    if A[0] != 0:
        flag = -1
    if A[-1] == 0:
        flag = -1

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

    M = [-1]*N
    M[0] = 2
    for i in range(1,N):
        M[i] = (M[i-1]-A[i])*2
        if M[i] <= 0:
            flag = -1
    #print(S,M)

    if flag != -1:
        V = [-1]*N
        for i in range(N):
            if S[i] > M[i]:
                V[i] = M[i]
            else:
                V[i] = S[i]
        ans = sum(V)+1

        if S[-1] <= M[-1]:
            #print(V)
            print(ans)
        else:
            print(-1)
    else:
        print(-1)

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

Submission status: Accepted

Solution code:
import math
def main():
    N = int(input())
    P = list(map(int, input().split()))
    if N == 0 and P[0] == 1:
        return 1
    if P[0] >= 1:
        return -1
    ul = [1]
    ll = [1]
    for i, v in enumerate(P[1:]):
        u = (ul[-1] - P[i]) * 2
        l = v
        ul.append(u)
        ll.append(l)
    ul2 = [P[-1]]
    ll2 = [P[-1]]
    for i, v in enumerate(reversed(P[:-1])):
        u = min(ul2[-1] + v, pow(2, N-i-1))
        l = min(math.ceil(ll2[-1]/2) + v, pow(2, N-i-1))
        ul2.append(u)
        ll2.append(l)
    ul2.reverse()
    ll2.reverse()
    r = 0
    for i in range(N+1):
        a = ul[i]
        b = ll[i]
        c = ul2[i]
        d = ll2[i]
        if d > a or b > c:
            return -1
        if max(b, d) > pow(2, i):
            return -1
        r += min(a, c)
    return r
print(main())

Submission status: Accepted

Solution code:
n=int(input())
b0=input().split()
b=[int(x) for x in b0]

ret=0

if b[-1]==0:
  ret=-1
else:
  maxl=[]
  v=1
  for i in range(n+1):
    maxl.append(v)
    v=(v-b[i])*2
    if v<0:
      ret=-1
      break

v=0
vsum=0
if ret!=-1:
  for i in range(n,-1,-1):
    v=min(v+b[i],maxl[i])
    vsum+=v

if ret==-1:
  print(-1)
else:
  print(vsum)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N == 0 and A[0] == 1:
        print(1)
        return
    if A[0] != 0:
        print(-1)
        return
    piyo = 1
    work = [1]
    for a in A[1:]:
        piyo *= 2
        work.append(piyo)
        piyo -= a
    result = 0
    piyo = 0
    i = N
    for a in A[::-1]:
        piyo += a
        if a > work[i]:
            print(-1)
            return
        piyo = min(piyo, work[i])
        result += piyo
        i -= 1
    print(result)
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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


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

right=1
for i,x in enumerate(A):
    if x>right:
        print(-1)
        exit()
    right-=x
    right*=2
    right=min(right,10**10)

ans=1
tmp=0
M=[1]


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

for i,x in enumerate(A[1:],1):
    if i>=65:
        n=2**65
    else:
        n=2**i
    M.append(min(n-x,M[i-1]*2-x))
    if (i!=N and M[i]<=0) or (i==N and M[i]<0):
        print(-1)
        exit()
for i,(x,y) in enumerate(zip(A[1:][::-1],M[1:][::-1])):
    tmp+=x
    tmp=min(tmp,n,y+x)
    ans+=tmp
if A[0]+M[0]>1:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
import unittest


def solve(n, leafs):
    if leafs[0] == 1:
        if n == 0:
            return 1
        else:
            return - 1
    l = 1
    for i in range(min(28, n + 1)):
        if leafs[i] > l:
            return -1
        l *= 2

    usable_node = 1
    usable_nodes = [1]*(n+1)
    for i in range(n):
        if leafs[i] <= usable_node:
            usable_node -= leafs[i]
            usable_node *= 2
            usable_nodes[i+1] = usable_node
        else:
            return - 1
    if leafs[-1] > usable_node:
        return - 1
    usable_node -= leafs[-1]
    if usable_node + leafs[-1] > 2 ** n:
        return - 1

    max_node = [0 for i in range(n + 1)]
    max_node[n] = leafs[n]
    for i in range(n - 1, -1, -1):
        if i > 27:
            max_node[i] = min(usable_nodes[i], leafs[i]+max_node[i+1])
        else:
            max_node[i] = min(2 ** i, usable_nodes[i], leafs[i]+max_node[i+1])

    return sum(max_node)


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


class Test(unittest.TestCase):
    def test_solve_1(self):
        n = 3
        a = [0, 1, 1, 2]
        actual = solve(n, a)
        expected = 7
        self.assertEqual(actual, expected)

    def test_solve_2(self):
        n = 4
        a = [0, 0, 1, 0, 2]
        actual = solve(n, a)
        expected = 10
        self.assertEqual(actual, expected)

    def test_solve_3(self):
        n = 2
        a = [0, 3, 1]
        actual = solve(n, a)
        expected = -1
        self.assertEqual(actual, expected)

    def test_solve_4(self):
        n = 1
        a = [1, 1]
        actual = solve(n, a)
        expected = -1
        self.assertEqual(actual, expected)

    def test_solve_5(self):
        n = 10
        a = [0, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
        actual = solve(n, a)
        expected = 264
        self.assertEqual(actual, expected)

    def test_solve_6(self):
        n = 5
        a = [0, 1, 1, 1, 1, 1]
        actual = solve(n, a)
        expected = 10
        self.assertEqual(actual, expected)

    def test_solve_7(self):
        n = 3
        a = [0, 1, 2, 4]
        actual = solve(n, a)
        expected = -1
        self.assertEqual(actual, expected)

    def test_solve_8(self):
        n = 12
        a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2**12]
        actual = solve(n, a)
        expected = 2**13-1
        self.assertEqual(actual, expected)

    def test_solve_9(self):
        n = 3
        a = [0, 0, 0, 8]
        actual = solve(n, a)
        expected = 15
        self.assertEqual(actual, expected)


if __name__ == "__main__":
    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] != 0:
  print(-1)
  exit()

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

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

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

print(sum(L) + 1)

Submission status: Accepted

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

b = [0]*n
c = [0]*n

now = 1
for i in range(n):
    b[i] = now
    now -= a[i]
    if now < 0:
        print(-1)
        exit()

    if now == 0 and i != n-1:
        print(-1)
        exit()
    now *= 2

a = list(reversed(a))
c[0] = a[0]
now = a[0]
for i in range(1, n):
    now += a[i]
    c[i] = now

c = list(reversed(c))

ans = 0
for i in range(n):
    ans += min(b[i], c[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()

l = [1]
pre = 1
for i in range(n):
    if A[i] == 0:
        pre *= 2
        l.append(pre)
    else:
        pre = (l[i]-A[i])*2
        if pre <= 0:
            print(-1)
            exit()
        l.append(pre)

if A[-1] > l[-1]:
    print(-1)
    exit()
else:
    tmp = A[-1]
    ans = tmp

for i in range(2,n+2):
    if A[-i] != 0:
        tmp = min(A[-i]+tmp,l[-i])
        ans += tmp
    else:
        tmp = min(tmp,l[-i])
        ans += tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
RS = input
RI = lambda x=int: x(RS())
RA = lambda x=int: map(x, RS().split())
RSS = lambda: RS().split()


def solve():
    mi = 1
    ma = 1
    man = [0]*(n+1)
    for i in range(n+1):
        man[i] = ma
        mi -= a[i]
        ma -= a[i]

        if ma < 0:
            print(-1)
            return
        ma*= 2
    if not mi<=0<=ma:
        print(-1)
        return
    d = n-1
    c = a[n]
    ans = c
    while d>=0:
        c = min(man[d], c+a[d])
        ans += c
        d -= 1
    print(ans)
    return

def ceild(a):
    return a//2 + a%2



n = RI()
a = list(RA())
solve()