Bombers i iaies (2) P65894


Statement
 

pdf   zip

html

Els bombers d’un país llunyà volen protegir les iaies que es troben en n escoles. Les escoles estan en fila en un carrer, numerades en ordre de la 1 a la n. A cada escola j hi ha ij iaies. Els bombers poden formar g grups, i cada grup pot anar a una sola escola. Si un grup va a l’escola j, hi protegeix totes les iaies. A més, també protegeix indirectament la meitat de les iaies de l’escola j−1, suposant que existeixi i que no estigui ja protegida totalment per algun altre grup; i igualment amb l’escola j+1.

Quin és el màxim nombre de iaies que es poden protegir?

Entrada

L’entrada consisteix en diversos casos, cadascun amb g i n, seguides de les ij. Suposeu 1 ≤ g ≤ n ≤ 3000, i que totes les ij són naturals parells entre 2 i 105.

Sortida

Per a cada cas, escriviu quantes iaies es poden protegir.

Pista

La solució esperada per a aquest problema consisteix en una programació dinàmica amb dues recurrències encreuades i cost O(g · n).

Public test cases

  • Input

    1 1  100000
1 2  10 20
1 3  10 80 20
1 3  10 20 80
3 3  10 20 80
3 9  4 8 2 4 8 8 6 2 8
9 9  2 2 2 2 2 2 2 2 2

    Output

    100000
25
95
90
110
36
18
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++