Alice's Adventures in Cutting Cake
Contest: Codeforces Round 986 (Div. 2)
Difficulty rating: 1600
Tags: binary search, dp, greedy, two pointers

Alice is at the Mad Hatter's tea party! There is a long sheet cake made up of $$$n$$$ sections with tastiness values $$$a_1, a_2, \ldots, a_n$$$. There are $$$m$$$ creatures at the tea party, excluding Alice.

Alice will cut the cake into $$$m + 1$$$ pieces. Formally, she will partition the cake into $$$m + 1$$$ subarrays, where each subarray consists of some number of adjacent sections. The tastiness of a piece is the sum of tastiness of its sections. Afterwards, she will divvy these $$$m + 1$$$ pieces up among the $$$m$$$ creatures and herself (her piece can be empty). However, each of the $$$m$$$ creatures will only be happy when the tastiness of its piece is $$$v$$$ or more.

Alice wants to make sure every creature is happy. Limited by this condition, she also wants to maximize the tastiness of her own piece. Can you help Alice find the maximum tastiness her piece can have? If there is no way to make sure every creature is happy, output $$$-1$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n, m, v$$$ ($$$1\le m\le n\le 2\cdot 10^5$$$; $$$1\le v\le 10^9$$$) — the number of sections, the number of creatures, and the creatures' minimum requirement for tastiness, respectively.

The next line contains $$$n$$$ space separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the tastinesses of the sections.

The sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output the maximum tastiness Alice can achieve for her piece, or $$$-1$$$ if there is no way to make sure every creature is happy.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, Alice can give the first and second section as their own pieces, and then take the remaining $$$10 + 1 + 1 + 10 = 22$$$ tastiness for herself. We can show that she cannot do any better.

For the second test case, Alice could give the first and second section as one piece, and the sixth section as one piece. She can then take the remaining $$$10 + 1 + 1 = 12$$$ tastiness for herself. We can show that she cannot do any better.

For the seventh test case, Alice cannot give each creature a piece of at least $$$12$$$ tastiness.

Example input:
7
6 2 1
1 1 10 1 1 10
6 2 2
1 1 10 1 1 10
6 2 3
1 1 10 1 1 10
6 2 10
1 1 10 1 1 10
6 2 11
1 1 10 1 1 10
6 2 12
1 1 10 1 1 10
6 2 12
1 1 1 1 10 10

Example output:
22
12
2
2
2
0
-1

Editorial:
Alice's piece of cake will be some subsegment $$$a[i:j]$$$. For a fixed $$$i$$$, how large can $$$j$$$ be?
To determine this, let $$$pfx[i]$$$ be the maximum number of creatures that can be fed on $$$a[:i]$$$ and $$$sfx[j]$$$ the maximum number of creatures on $$$a[j:]$$$. Then, for a given $$$i$$$, the maximum possible $$$j$$$ is exactly the largest $$$j$$$ such that $$$pfx[i] + sfx[j] \ge m$$$.
If we compute the $$$pfx$$$ and $$$sfx$$$ arrays, we can then compute these largest $$$j$$$ for all $$$i$$$ with two pointers in $$$O(n)$$$ (or with binary search in $$$O(n\log n)$$$, since $$$sfx$$$ is monotonically non-increasing).
To compute $$$pfx[i]$$$, we can use prefix sums and binary search to find the maximum $$$k < i$$$ such that $$$\sum_{\ell=k}^{i}a[\ell] \ge v$$$: then $$$pfx[i] = 1 + pfx[k]$$$. We can compute $$$sfx$$$ similarly by reversing $$$a$$$. This takes time $$$O(n\log n)$$$ (it is also possible to do this with two pointers in $$$O(n)$$$, which you can see in the model solution).
Expected complexity: $$$O(n)$$$ or $$$O(n\log n)$$$.