Problem F
Klassisk røveri

Mike Castro Demaria

Egon har planlagt århundredets røveri. Målet er en uvurderlig vase opbevaret i landets største teater, men vejen til vasen går gennem en armeret betonvæg. Væggen kan kun brydes ned via sprængstoffer, men Egon har en plan: Tyveriet bliver foretaget under en opførelse af ouverturen fra Elverhøj, og Egon har noderne. Planen er at sprænge væggen med $k$ stykker dynamit i takt til musikken, stjæle vasen og blive stinkende rige. Det eneste Egon mangler at gøre, er at udvælge de $k$ takter, dynamitten skal sprænges til. På den ene side vil han gerne sørge for så godt et dække som muligt, dvs. at den svageste af de $k$ udvalgte takter skal være så højlydt som muligt. Han skal desuden sørge for, at der er mindst $p$ takters pause mellem hver sprængning, for at hele bygningen ikke braser sammen.

Hvor godt et dække kan Egon få til sine sprængninger?

Indlæsning

Første linje af indlæsningen består af de $3$ heltal $n$, $k$ og $p$. Anden linje består af $n$ heltal $s_1,\dots ,s_n$, som er lydstyrken af de forskellige takter.

Udskrift

Udskriv et enkelt heltal: det maksimale dække, Egon kan få til sine sprængninger.

Garantier og delopgaver

Der gælder altid $1\le n\le {10}^4$, $1\le k\le 100$, $p\ge 0$ og $0\le s_i\le 100$ for $1\le i\le n$. Det er garanteret at $(k-1)\cdot (p+1)<n$, så det kan lade sig gøre at vælge $k$ takter med mindst $p$ takters pause mellem hver sprængning.

Opgaven er opdelt i delopgaver med stærkere garantier, som gør delopgaven nemmere at løse.

10 3 0
1 8 2 5 4 9 7 1 6 3

7

10 3 3
1 8 2 5 4 9 7 1 6 3

3

10 1 3
1 8 2 5 4 9 7 1 6 3

9

3 2 1
1 10 2

1