Trees and Segments
Contest: Codeforces Round 893 (Div. 2)
Difficulty rating: 2200
Tags: brute force, data structures, dp, greedy, two pointers

The teachers of the Summer Informatics School decided to plant $$$n$$$ trees in a row, and it was decided to plant only oaks and firs. To do this, they made a plan, which can be represented as a binary string $$$s$$$ of length $$$n$$$. If $$$s_i = 0$$$, then the $$$i$$$-th tree in the row should be an oak, and if $$$s_i = 1$$$, then the $$$i$$$-th tree in the row should be a fir.

The day of tree planting is tomorrow, and the day after tomorrow an inspector will come to the School. The inspector loves nature very much, and he will evaluate the beauty of the row as follows:

- First, he will calculate $$$l_0$$$ as the maximum number of consecutive oaks in the row (the maximum substring consisting of zeros in the plan $$$s$$$). If there are no oaks in the row, then $$$l_0 = 0$$$.
- Then, he will calculate $$$l_1$$$ as the maximum number of consecutive firs in the row (the maximum substring consisting of ones in the plan $$$s$$$). If there are no firs in the row, then $$$l_1 = 0$$$.
- Finally, he will calculate the beauty of the row as $$$a \cdot l_0 + l_1$$$ for some $$$a$$$ — the inspector's favourite number.

The teachers know the value of the parameter $$$a$$$, but for security reasons they cannot tell it to you. They only told you that $$$a$$$ is an integer from $$$1$$$ to $$$n$$$.

Since the trees have not yet been planted, the teachers decided to change the type of no more than $$$k$$$ trees to the opposite (i.e., change $$$s_i$$$ from $$$0$$$ to $$$1$$$ or from $$$1$$$ to $$$0$$$ in the plan) in order to maximize the beauty of the row of trees according to the inspector.

For each integer $$$j$$$ from $$$1$$$ to $$$n$$$ answer the following question independently:

- What is the maximum beauty of the row of trees that the teachers can achieve by changing the type of no more than $$$k$$$ trees if the inspector's favourite number $$$a$$$ is equal to $$$j$$$?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3000$$$, $$$0 \le k \le n$$$) — the number of trees in the row and the maximum number of changes.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of zeros and ones — the plan description.

It is guaranteed that the sum of all $$$n$$$ values for all test cases does not exceed $$$3000$$$.

Output format:
For each test case, print $$$n$$$ integers, the $$$j$$$-th ($$$1 \le j \le n$$$) of which is the maximum beauty of the row of trees after no more than $$$k$$$ changes if $$$a = j$$$ is used to calculate the beauty.

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

Note:
In the first test case no changes are allowed, so $$$l_0 = 0$$$ and $$$l_1 = 3$$$ always hold. Thus, regardless of the value of $$$a$$$, the beauty of the row of trees will be $$$3$$$.

In the second test case for $$$a \in \{1, 2\}$$$ the teachers can, for example, change the plan $$$s$$$ to $$$0111$$$ (by changing $$$s_4$$$), and for $$$a \in \{3, 4\}$$$ — to $$$0010$$$ (by changing $$$s_2$$$). In this case, the beauty of the row for each $$$a$$$ is calculated as follows:

- For $$$a = 1$$$: $$$l_0 = 1$$$, $$$l_1 = 3$$$. The beauty of the row is $$$1\cdot 1 + 3 = 4$$$.
- For $$$a = 2$$$: $$$l_0 = 1$$$, $$$l_1 = 3$$$. The beauty of the row is $$$2\cdot 1 + 3 = 5$$$.
- For $$$a = 3$$$: $$$l_0 = 2$$$, $$$l_1 = 1$$$. The beauty of the row is $$$3\cdot 2 + 1 = 7$$$.
- For $$$a = 4$$$: $$$l_0 = 2$$$, $$$l_1 = 1$$$. The beauty of the row is $$$4\cdot 2 + 1 = 9$$$.

It can be shown that the changes described above are optimal for all $$$a$$$ from $$$1$$$ to $$$4$$$.

Example input:
5
3 0
111
4 1
0110
5 0
10000
6 2
101101
7 1
0001101

Example output:
3 3 3 
4 5 7 9 
5 9 13 17 21 
6 9 13 17 21 25 
7 10 13 17 21 25 29

Editorial:
There are many various dynamic programming solutions of this problem. We will describe one of them. Let's calculate the dynamics $$$pref_{i, \ j}$$$ = the length of the longest subsegment of zeros that can be obtained on the prefix up to $$$i$$$, which ends at index $$$i$$$ and costs exactly $$$j$$$ operations. Similarly, $$$suf_{i, \ j}$$$ is the length of the longest subsegment of zeros on the suffix starting at $$$i$$$, which starts at index $$$i$$$ and costs exactly $$$j$$$ operations. Such dynamics can be easily computed: $$$$$$ pref_{i, \ j} = \left\{ \begin{array} \\ pref_{i - 1, \ j} + 1 & \text{if} & s_i = 0 \\ pref_{i - 1, \ j - 1} + 1 & \text{if} & s_i = 1 & \text{and} & j > 0 \\ 0 & \text{otherwise} \end{array}\right. $$$$$$ In the first case, we simply prolong the existing subsegment of zeros, in the second case, we change the current $$$1$$$ to $$$0$$$, spending one operation on it (so if have $$$0$$$ operations left ($$$j = 0$$$), we cannot do anything and the value of the dynamics is $$$0$$$, meaning the segment has ended). $$$suf_{i,j}$$$ can be calculated similarly. Let's update both dynamics in such a way that $$$pref_{i,j}$$$ will mean the maximum length of a subsegment of zeros that ends no later than $$$i$$$ and costs no more than $$$j$$$ operations. This can be easily done by updating $$$pref_{i,j}$$$ with the value of $$$pref_{i - 1,j}$$$, and then with $$$pref_{i,j - 1}$$$. Similarly, we update the second dynamics.
Now let's consider a subsegment [$$$l, \ r]$$$ that we want to convert into a segment of ones. We can easily calculate the number of operations $$$x$$$ that we will need (we'll just need to calculate the number of zeros in such a segment). Now, calculate the new dynamics $$$dp_{len}$$$ for the length $$$len = r - l + 1$$$ of the segment of ones, which equals the maximum length of a subsegment of zeros that we can obtain. Update this value with $$$\max(pref_{l - 1, k - x}, suf_{r + 1, k - x})$$$.
Then, to answer the question for a fixed number $$$a$$$, we can iterate over the length $$$len$$$ of the segment of ones that will be in our answer and update the answer with the value $$$a \cdot dp_{len} + len$$$, if there exists a value for $$$len$$$ in the dynamics $$$dp$$$.
The complexity is $$$O(nk + n^2)$$$. Solutions with complexity $$$O(nk \log n)$$$ and $$$O(nk)$$$ using various optimizations of the dynamics (convex hull trick, D&C) also exist.