Problem F
Klassisk røveri
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,\ldots ,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 \leq n \leq 10^4$, $1 \leq k \leq 100$, $p \geq 0$ og $0\leq s_ i \leq 100$ for $1\leq i\leq 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.
|
Delopgave |
Point |
Garanti |
|
$1$ |
$50$ |
$p = 0$ |
|
$2$ |
$50$ |
Ingen yderligere garantier |
| Sample Input 1 | Sample Output 1 |
|---|---|
10 3 0 1 8 2 5 4 9 7 1 6 3 |
7 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 3 3 1 8 2 5 4 9 7 1 6 3 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 1 3 1 8 2 5 4 9 7 1 6 3 |
9 |
| Sample Input 4 | Sample Output 4 |
|---|---|
3 2 1 1 10 2 |
1 |
