| Fişierul intrare/ieşire: | padurari.in, padurari.out | Sursă | Summer Challenge 2009, Runda 2 |
| Autor | Din Folclor | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Padurari
De-a lungul unei şosele în linie dreaptă cresc N copaci. K pădurari au primit sarcina de a tăia o parte din copaci. Fiecare pădurar trebuie să taie exact 2 copaci. Pădurarii se deplasează cu maşina până la primul copac pe care îl au de tăiat, iar apoi pornesc pe jos spre celălalt copac. Ei doresc să se organizeze în aşa fel încât suma distanţelor pe care le vor parcurge pe jos sa fie minimă.
Date de intrare
Fişierul de intrare padurari.in conţine pe prima linie numerele N şi K. Pe următoarele N linii se află câte un număr întreg. A i-a linie conţine distanţa Di de la al i-ulea copac până la începutul şoselei. Distanţele sunt date în ordine crescătoare.
Date de ieşire
În fişierul de ieşire padurari.out se va afla un singur număr întreg reprezentând suma minimă a distanţelor pe care le vor parcurge pădurarii.
Restricţii
- 2 ≤ N ≤ 200 000
- 1 ≤ K ≤ N/2
- 0 ≤ Di ≤ 109
- Pentru 20% din teste, N ≤ 1 000.
Exemplu
| padurari.in | padurari.out |
|---|---|
| 6 2 1 6 8 12 13 16 | 3 |
Explicaţie
Un pădurar va tăia copacii 2 şi 3 şi un alt pădurar va tăia copacii 4 şi 5.
