Summer FLASG Advanced | ȚeavaAdvanced

După un live stresant, Flaviu și ASG au decis să iasă în aer liber pentru a se relaxa. Plimbându-se prin pădure, cei doi s-au rătăcit și, spre groaza lor, au realizat că trebuie să se apere de urșii și crocodilii care populau acea pădure vastă. După ce s-au calmat, au găsit $N$ bucăți de țevi de diferite lungimi $x_i$.

Flaviu a avut o idee ingenioasă: să lege bucățile de țevi cu bandă adezivă pentru a forma niște arme improvizate. Totuși, ghiozdanul lui Flaviu avea o capacitate limitată, astfel că puteau să care cel mult $k$ țevi unite.

Flaviu și ASG își doresc să construiască cele mai puternice arme posibile, iar duritatea unei țevi este determinată de media aritmetică a lungimilor bucăților de țevi unite. Scopul lor este să maximizeze duritatea ale țevilor unite, pentru a avea cele mai eficiente arme posibile.

Cerință

Găsiți modalitatea optimă de a împărți bucățile de țevi în cel mult $k$ subsecvențe de elemente contigue astfel încât suma durităților să fie maximă.

Date de intrare

Pe prima linie se vor găsi numerele $N$ și $k$. Pe a doua linie se vor găsi $N$ numere naturale, separate printr-un spațiu, reprezentând elementele șirului $x$.

Date de ieșire

Pe prima linie se va găsi un singur număr real, acesta fiind rezultatul cerinței.

Restricții și precizări

• $1\leq N \leq 500$;
• $1\leq x_i \leq 1\ 000$;
• $1\leq k \leq N$.
• Răspunsul va fi considerat corect dacă este aproximativ egal (cu o precizie de cel puțin $10^{−6}$) cu răspunsul corect.

Exemplul 1

stdin

10 3
14 16 18 4 17 15 9 20 4 19

stdout

46.5

Explicație

Se formează următoarele $3$ țevi:

[14 16 18] [4 17 15 9 20 4] [19]

Prima țeavă are duritatea 16, a doua 11.5, iar a treia 19, în total 46.5. Dacă avem în schimb

[14 16] [18 4 17 15 9 20] [4 19]

prima țeavă are duritatea 15, a doua 13.83 și ultima 11.5, pentru un total de 40.33.

Exemplul 2

stdin

10 4
50 13 31 32 31 46 47 24 9 21

stdout

148

Explicație

Aici, țevile formate sunt:

[50] [13 31 32 31] [46] [47 24 9 21]