Batches of tests
Tests are checked in order, one after another. They are split into batches of consecutive tests; each batch is one sandbox run: first S ms to start, then the batch's tests one by one. The verdicts of all tests of a batch appear at the moment the batch finishes. The first batch starts at moment 0, and each next one right after the previous.
Split the tests into batches so that the sum of the moments at which the verdicts of all tests appear is the smallest, and print this sum.
The third test is 1776 runs of the catalogue's reference solutions in checking order, with times from the measurement of 17 October 2026; the fourth is the same in a cycle, two hundred thousand of them.
Input
The first line holds n and S (1 ≤ n ≤ 2 · 10⁵, 0 ≤ S ≤ 1000). The second holds n test times t1, …, tn in milliseconds (1 ≤ ti ≤ 1000).
Output
The smallest sum of moments, in milliseconds. It fits in 64 bits.
Examples
Example 1
5 10 5 1 3 2 8
123
Example 2
4 100 1 1 1 1
416
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The moment of a verdict depends on all batches before it, and computing it head-on is awkward. Look at it differently: by how many verdicts does one batch increase the sum?
2Hint 2
A batch of tests j + 1 … i lasts S + Ti − Tj, where T are prefix sums of the times, and shifts the verdicts of all tests after j. Hence a DP over the last cut. Trying every j takes 2 · 10¹⁰ steps. What function of Ti stands under the minimum for a fixed j?
3The idea
best[i] = minj < i best[j] + (S + Ti − Tj) · (n − j). For a fixed j this is a line in x = Ti with slope n − j. The slopes decrease and x grows: an envelope of lines in a deque.
4Walkthrough
At step i add line j = i − 1 to the end of the deque, throwing out from the back lines it has made redundant: b is redundant between a and c if (bc − ba)(ka − kb) ≤ (bb − ba)(ka − kc). Then advance the front of the deque while the next line is no higher than the front one at the point Ti, and take the front line's value. There is no need to keep the whole array best: a line is built from the last value.
4+Solution
5Complexity
O(n): each line enters and leaves the deque at most once. The answer is at most n · (nS + Tn) ≈ 8 · 10¹³.
6Common mistakes
- Trying every last cut. This is
wrong.py: it copes with the catalogue's 1776 tests, but not with two hundred thousand. - Greed. “Cut when a batch gets longer than S” or “batches of equal length” are not optimal: the best batches are large at the start and small at the end, because a batch at the start delays everyone.
- The line after the query. If line i − 1 is added after query i, the option “the last batch is a single test” is lost.
- S = 0. Then each test is its own batch, and the answer is the sum of prefix sums; the deque copes with this too, but check that equal values do not break the comparisons.