Problem F
Fence Building
Languages
en
sv
Gustav loves his neighbors and has therefore built a fence consisting of $N$ boards. The boards are all $1 \text{dm}$ wide, but can be of different heights.
To help the neighborhood flourish, Gustav now wants to hang a rectangular notice board on this fence. Gustav feels that the notice board he hangs up must be perfect and therefore needs your help!
Specifically, Gustav wants the notice board to be as large as possible (i.e., have the largest possible area). The notice board also needs to hang securely, which means that there can be at most $K$ boards behind the notice board that do not reach all the way up to its upper edge. For the notice board to hang at all, it must, of course, have at least one board behind it that reaches all the way up to its upper edge.
Input
The first line contains two integers $N$ ($1 \leq N \leq 50\, 000$) and $K$ ($0 \leq K \leq 20$), the number of boards that make up the fence and the number of boards that can be missing behind the notice board.
The second line contains $N$ integers $h_{1}, h_{2}, \dots , h_{N}$ ($1 \leq h_{i} \leq 10^{9}$) where $h_i$ is the height of the $i$-th board from the left in decimeters.
Output
Print an integer: the largest possilbe area of a rectangular notice board, in $\text{dm}^{2}$.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$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$ |
No additional constraints. |
Explanation of samples
In the first sample, no board behind the notice board can be below the upper edge of the board. By putting up a board with a height of $4 \text{dm}$ in front of the three middle boards, the board will have an area of $12 \text{dm}^2$, which is the best largest possible board.
In the second sample, Gustav’s best option is to put up a board along the entire fence with a height of $4 \text{dm}$. The boards with heights of $1 \text{dm}$ and $2 \text{dm}$ are indeed below the upper edge of the notice board, but this is acceptable since $K = 2$.
In the third example, it does not matter how many boards are below the upper edge of the notice board. Instead, the requirement that the board must have at least one board behind it that reaches all the way up comes into play, so its height still cannot exceed $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 |
