It seems best to use as few elements as possible to create contiguous subsequences with sums of elements at least \(S\), and to divide the remaining into as many subsequences as possible. Let’s formalize this.

Let’s define the cost of a contiguous subsequence \(A[i,j]\) as \(j-i\). Let \(f(x)\) denote the minimum possible total cost to take \(x\) disjoint subsequences with sums of elements at least \(S\).

We consider the problem: is it possible to achieve a score of at least \(x\)? The necessary and sufficient conditions are \(x \leq K\) and \(f(x) \leq N-K\).

Here, \(f(x)\) will be a concave function. Let’s prove this first.

It is sufficient to consider only the minimal contiguous subsequences whose sums of elements are at least \(S\). Suppose there are \(m\) such minimal subsequences. Let’s call these \(m\) subsequences \(B_1, B_2, \cdots, B_m\) from left to right, and denote the cost of \(B_i\) as \(C_i\). Note that since \(B_i\) are minimal, they have no inclusion relationship, and their left-right order is naturally determined.

Let \(x_1 \leq \cdots \leq x_p\) denote the indices of the subsequences chosen in the optimal solution for \(f(p)\). Similarly, let \(y_1 \leq \cdots \leq y_{p+2}\) denote the indices of the subsequences chosen in the optimal solution for \(f(p+2)\). By appropriately swapping the elements of these two sequences of indices, we can create two valid solutions of size \(p+1\). For example, if there exists an \(i\) such that \(x_i \leq y_{i+1} \leq y_{i+2} \leq x_{i+1}\), then we can rearrange them into \((x_1, \cdots, x_i, y_{i+2}, \cdots, y_{p+2})\) and \((y_1, \cdots, y_{i+1}, x_{i+1}, \cdots, y_{p+2})\). In fact, if we consider sentinels \(x_0=y_0=0\) and \(x_{p+1}=y_{p+3}=m+1\), we can always find such an \(i\) that satisfies the above condition. The details are omitted, but it is helpful to consider the number of \(y\)’s minus the number of \(x\)’s for each index.

From the above, we have \(2f(p+1) \leq (\)the sum of the costs of two size \(p+1\) solutions\() = f(p) + f(p+2)\), which demonstrates the convexity of \(f\).

Once we know that \(f\) is concave, we can solve it using a technique commonly referred to as Alien DP. The explanation of this part will be left to other articles. For example, the editorial for ABC 218 H may be helpful. Note that while Alien DP is often applied in scenarios where Monge property holds, this problem does not satisfy the Monge property.

By the way, what is needed in this problem is the maximum \(x\) that satisfies \(f(x) \leq N-K\), not the value of \(f(x)\) itself. One way to solve this is to perform a binary search on \(x\). Although the computational complexity is multiplied by \(O(\log N)\), it is still possible to get AC if the constant factor is not too bad.

In fact, without doing such things, you can perform a binary search in almost the same way as finding the value of \(f(x)\) once. After deciding on the penalty in the DP, also find the minimum number of used subsequences to achieve the minimum cost. Refer to the sample solution for details.

It is sufficient to consider \([0, N]\) as the range of the penalty, and it takes \(O(N)\) time to perform the DP once, so the total computational complexity will be \(O(N \log N)\).

Sample Solution