Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | scandura.in, scandura.out | Sursă | Algoritmiada 2009, Runda 1 |
| Autor | Bogdan-Cristian Tataroiu | Adăugată de |  Bogdan-Cristian Tataroiu •bogdan2412 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 36096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Scandura
G. Tamplaru' I vrea sa-si faca un birou nou. El cunoaste dimensiunile finale ale tuturor scandurilor de care are nevoie pentru a construi biroul si a cumparat o scandura de lungime L egala cu suma lungimilor tuturor scandurilor necesare. El are o masina speciala in care poate introduce o scandura de orice lungime si aceasta o taie in maxim M bucati diferite. Efortul depus de G. Tamplaru' I pentru a taia o scandura de lungime X este egal cu X.
Date de intrare
Fişierul de intrare scandura.in va contine pe prima linie doua numere naturle N si M. Pe a doua linie se vor afla, separate prin spatii, N numere naturale in ordine crescatoare.
Date de ieşire
În fişierul de ieşire scandura.out se va afisa pe prima linie efortul minim necesar.
Restricţii
- 1 ≤ N ≤ 106
- 2 ≤ M ≤ N
- 1 ≤ lungimile scandurilor ≤ 109
Exemplu
| scandura.in | scandura.out |
|---|---|
| 4 2 1 2 3 4 | 19 |
Explicaţie
Scandura initiala are lungime 10. G. Tamplaru' I efectueaza o taiere cu costul 10 si obtine 2 scanduri de lungime 4 si 6. Scandura de lungime 6 o taie apoi in 2 scanduri de lungme 3. In final, una din cele 2 scanduri de lungime 3 este taiata intr-o scandura de lungime 1 si una de lungime 2.
Efortul total este egal cu 10 + 6 + 3 = 19.
