Problem F
Bygga plank
Gustav älskar sina grannar, och har därför byggt ett plank som består av $N$ brädor. Brädorna är alla $1 \text { dm}$ breda men kan vara olika höga. För att trakten ska kunna blomstra vill nu Gustav hänga upp en rektangulär anslagstavla på detta plank. Gustav känner att anslagstavlan han hänger upp måste vara perfekt, och behöver därför din hjälp!
Mer precist vill Gustav att anslagstavlan ska vara så stor som möjligt (alltså ha så stor area som möjligt). Anslagstavlan behöver också hänga stadigt, vilket betyder att det som mest får finnas $K$ stycken brädor bakom anslagstavlan som inte räcker hela vägen upp till dess övre kant. För att anslagstavlan ska kunna hänga över huvud taget måste den såklart också ha minst en bräda bakom sig som räcker hela vägen upp till dess övre kant.
Indata
Den första raden innehåller två heltal $N$ ($1 \le N \le 50\, 000$) och $K$ ($0 \le K \le 20$), antalet brädor som planket består av och antalet brädor som får fattas bakom anslagstavlan.
Den andra raden innehåller $N$ heltal $h_{1}$, $h_{2}$, …, $h_{N}$ ($1 \le h_{i} \le 10^{9}$) där $h_ i$ är höjden på den $i$:te brädan från vänster i decimeter.
Utdata
Skriv ut den största arean som den rektangulära anslagstavlan kan ha, i $\text {dm}^{2}$.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
$1$ |
$9$ |
$N \le 100, K = 1$ |
|
$2$ |
$22$ |
$h_{1} < h_{2} < \ldots < h_{N}$ |
|
$3$ |
$25$ |
$K = 0$ |
|
$4$ |
$16$ |
$N \le 2000 $ |
|
$5$ |
$28$ |
Inga ytterligare begränsningar. |
Förklaring av exempelfall
I det första exemplet får ingen bräda bakom anslagstavlan vara under tavlans övre kant. Genom att sätta upp en tavla med höjd $4\text { dm}$ framför de tre mittersta brädorna får tavlan arean $12\text { dm}^2$, vilket är det bästa som går att uppnpå.
I det andra exemplet är Gustavs bästa alternativ att sätta upp en tavla längs med hela planket med höjd $4 \text { dm}$. Plankorna med höjd $1\text { dm}$ och $2 \text { dm}$ är visserligen under anslagstavlans kant, men det är acceptabelt då $K = 2$.
I det tredje exemplet spelar det inte någon roll hur många brädor som är under tavlans övre kant. Istället träder kravet att tavlan måste ha minst en bräda bakom sig som räcker hela vägen upp in, så dess höjd kan ändå inte överstiga $9 \text { dm}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 0 6 2 5 4 5 1 6 |
12 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 2 6 2 5 4 5 1 6 |
28 |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 6 9 1 6 2 3 5 |
54 |
