Weasel finds Staircase
All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Weasel loves histograms. Weasel feels that he is very much out of shape and asks for Chef’s advice. Chef convinced Weasel that the only way to get back in shape is to work out. Weasel decides to follow Chef’s advice and has formulated the greatest workout plan - to reflect his love for histograms - in which he will go down the staircase every day. However, Weasel is not in the best shape, so, for starters, he can only go down at most K steps.
Formally, a staircase is a set of adjacent rectangles with at most K changes of height. These rectangles should have either increasing or decreasing heights. The rectangles should start from the bottom (see images in the explanation section for clarification), and the height of rectangle at i-th position shouldn't be more than histogrami.
For each of the T cases, you have to find the greatest area of a staircase that matches the above-mentioned restrictions.
The first line of the input contains an integer T, denoting the number of test cases.
For each of the T cases, you will be given two integers N, denoting the number of elements of the histogram, and K, the maximum number of steps, on the first line.
For each of the T cases, you will be given histogram array on the second line.
For each test case you should print an integer, the maximum area of a staircase that satisfies Weasel's conditions.
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 105
- 0 ≤ K ≤ 50
- The sum of N over all testcases does not exceed 105.
- 0 ≤ histogrami ≤ 105
- Subtask #1 (10 points): K = 0.
- Subtask #2 (30 points): The sum of N over all testcases does not exceed 1,500.
- Subtask #3 (60 points): original constraints
Input: 4 5 2 1 2 3 4 5 5 3 9 8 7 6 4 5 1 8 7 5 7 8 4 10 0 1 1 0 Output: 13 33 29 2
The cells which form the staircase are colored with yellow. The discarded cells are colored with grey.
The computed area is 1 + 2 × 2 + 4 × 2 = 13.
There are 2 changes of height: we start with a height of 1, we change to 2 and then we change to 4.
The computed area is 9 + 7 × 2 + 6 + 4 = 33.
The computed area is 7 × 2 + 5 × 3 = 29.
Here is another possible solution:
We take the second and the third cell. We have 0 changes in height. This is a viable solution because we can also have staircases with less than K changes.
|Tags||bciobanu, dynamic-programming, med-hard, persistent-convex, sept17|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.