Fişierul intrare/ieşire:scandura.in, scandura.outSursăAlgoritmiada 2009, Runda 1
AutorBogdan-Cristian TataroiuAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.5 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/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.inscandura.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content