Problem:

D: 水槽

問題

AORイカちゃんは縦 $1$ 横 $N$ の大きさの水槽をもらった。水槽は水を入れるのに十分な高さがある。
水槽には $N-1$ 個の仕切りがあり $N$ 個の区画に等間隔に区切られている。
ここに水を注いだところ、各区画の水の高さは $a_i$ になった。

AORイカちゃんはいくつか仕切りを取り除き、区画の数を $M$ 個以下にすることにした。
仕切りを取り除き終わった時、各区画の水の高さの総和の最大値を求めよ。

なお、仕切りの厚さは無視できるものとする。

制約

$1 \le N \le 500$

$1 \le M \le N$

$1 \le a_i \le 10^9$

入力は全て整数

入力

$N \ M$

$a_1 \cdots a_N$

出力

各区画の水の高さの総和の最大値を一行で出力せよ。また末尾に改行を出力せよ。
相対誤差または絶対誤差が $10^{-6}$ 以下であれば許容される。

サンプル

サンプル入力 1

5 3
9 1 2 3 9

サンプル出力 1

20.000000

 $a_2$ と $a_3$ 、$a_3$ と $a_4$ の間の仕切りをとると、その区画の水の高さは $\frac{(1 + 2 + 3)}{3} = 2$ となる。
 各区画の水の高さは $9 \ 2 \ 9$ となりこれが最大である。

サンプル入力 2

4 1
14 4 9 7

サンプル出力 2

8.500000

サンプル入力 3

8 3
11 18 9 20 4 18 12 14

サンプル出力 3

44.666667



Sample input:
5 3
9 1 2 3 9


Sample output:
20.000000

Submission status: Wrong Answer

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

INF = float('inf')

mem = [(src[i], 1) for i in range(N)]

for i in range(N-M):
    minh = INF
    mini = -1
    minl = -1
    for i,((h1,l1),(h2,l2)) in enumerate(zip(mem, mem[1:])):
        w = (h1*l1 + h2*l2)
        h = w / (l1+l2)
        if h < minh:
            minh = h
            mini = i
            minl = l1+l2
    del mem[mini]
    mem[mini] = (minh,minl)
    #print(mem)

print(sum([h for h,l in mem]))