Vacances organitzades P43543


Statement
 

pdf   zip

thehtml

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++