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
1
2
3
4
5
Frunzele 1, 2
si 3 se aduc in punctul
de coordonata 1, iar 4
si 5 se aduc in punctul
de coordonata 4.
Costul total este:
1 * 0 + 2 * 1 + 3 * 2 + 4 * 0
+ 5 * 1 = 13
Software engineer Google Inc
Contact:marsamg@yahoo.com