Summer FLASG Advanced | ȚeavaAdvanced

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s Memory limit: 16MB Input: Output:

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 NN bucăți de țevi de diferite lungimi xix_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 kk ț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 kk 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 NN și kk. Pe a doua linie se vor găsi NN numere naturale, separate printr-un spațiu, reprezentând elementele șirului xx.

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

  • 1N5001\leq N \leq 500;
  • 1xi1 0001\leq x_i \leq 1\ 000;
  • 1kN1\leq k \leq N.
  • Răspunsul va fi considerat corect dacă este aproximativ egal (cu o precizie de cel puțin 10610^{−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 33 ț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]

Log in or sign up to be able to send submissions!