leaves
Intr-o frumoasa zi de
toamna Radu si Mars au observat ca aleea din gradina in care obisnuiesc sa se
recreeze, e cam plina de frunze. S-au hotarat sa stranga toate frunzele in fix
K gramezi. Aleea este in linie
dreapta, iar ei si-au fixat un sistem de coordonate pe alee, cu originea la
inceputul aleii.
Pe alee sunt N frunze de diferite
greutati, asezate linie, la distanta 1
una fata de alta. Mai exact, prima frunza se afla la coordonata 1,
a doua la coordonata 2, ... ,
a N-a la coordonata N.
Initial cei doi se afla la coordonata N.
Operatia de strangere a frunzelor se intampla cand Radu si Mars pleaca din gradina,
asa incat frunzele pot fi mutate doar spre stanga. Costul mutarii unei
frunze este egal cu greutatea sa inmultita cu distanta pe care este mutata.
Evident una dintre cele K gramezi
va fi formata la coordonata 1,
insa restul pot fi oriunde.
Cerinta
Aflati care este costul total minim pentru a strange cele N frunze in fix K gramezi.
Date de intrare
In fisierul leaves.in
se afla pe prima linie doua numere naturale N
si K, separate de un spatiu,
cu semnificatia din enunt. Pe urmatoarele N
linii se afla N
numere naturale reprezentand greutatile frunzelor (pe linia i+1
se afla greutatea frunzei situate la coordonata i).
Date de iesire
Fisierul de iesire leaves.out va contine o singura linie pe care va fi scris costul minim pentru strangerea tuturor frunzelor in fix K gramezi.
Restrictii
Exemplu
leaves.in |
leaves.out |
Explicatii |
5 2 |
13 |
Cel mai bine e sa
formam cele 2 gramezi in
punctele 1 si 4.
|
Timp maxim de executie/test: 0.3 secunde
Marius
Andrei
Software engineer Google Inc
Contact:marsamg@yahoo.com