Vacances organitzades P43543
En unes vacances organitzades d’n dies de durada es pot fer una excursió cada dia. La satisfacció que produeix l’excursió i-èsima es si. Volem maximitzar la suma total de satisfaccions, amb una sola restricció: no es poden fer més de k excursions seguides.
Entrada
L’entrada consisteix en diversos casos, només amb nombres enters, cadascun amb n, k, i les n satisfaccions si. Podeu suposar 2 ≤ n ≤ 104, 1 ≤ k ≤ min(n − 1, 10), i 1 ≤ si ≤ 109.
Sortida
Per a cada cas, escriviu la màxima satisfacció possible.
Public test cases
Input
2 1 10 20 5 2 1 1 1 1 1 7 2 1000000000 1 1000000000 1 1000000000 1 1000000000 9 3 42 20 42 23 20 42 23 42 42
Output
20 4 4000000000 250
Information
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++