| 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. Efortul depus de G. Tamplaru' I pentru a taia o scandura de lungime X este egal cu X. El nu vrea sa munceasca prea mult si va cere voua sa determinati efortul minim necesar taierii scandurii mari in lungimile dorite.
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 ≤ 2 * 109
- Rezultatul se va incadra intotdeauna in tipuri de date intregi pe 64 de biti cu semn
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.
