Learning to Paint
Contest: CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2100
Tags: binary search, data structures, dfs and similar, dp, greedy, implementation, sortings

Elsie is learning how to paint. She has a canvas of $$$n$$$ cells numbered from $$$1$$$ to $$$n$$$ and can paint any (potentially empty) subset of cells.

Elsie has a 2D array $$$a$$$ which she will use to evaluate paintings. Let the maximal contiguous intervals of painted cells in a painting be $$$[l_1,r_1],[l_2,r_2],\ldots,[l_x,r_x]$$$. The beauty of the painting is the sum of $$$a_{l_i,r_i}$$$ over all $$$1 \le i \le x$$$. In the image above, the maximal contiguous intervals of painted cells are $$$[2,4],[6,6],[8,9]$$$ and the beauty of the painting is $$$a_{2,4}+a_{6,6}+a_{8,9}$$$.

There are $$$2^n$$$ ways to paint the strip. Help Elsie find the $$$k$$$ largest possible values of the beauty of a painting she can obtain, among all these ways. Note that these $$$k$$$ values do not necessarily have to be distinct. It is guaranteed that there are at least $$$k$$$ different ways to paint the canvas.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of test cases.

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^3$$$, $$$1 \leq k \leq \min(2^n, 5 \cdot 10^3)$$$) — the number of cells and the number of largest values of the beauty of a painting you must find.

The next $$$n$$$ lines of each test case describe $$$a$$$ where the $$$i$$$-th of which contains $$$n-i+1$$$ integers $$$a_{i,i},a_{i,i+1},\ldots,a_{i,n}$$$ ($$$-10^6 \leq a_{i,j} \leq 10^6$$$).

It is guaranteed the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$ and the sum of $$$k$$$ over all test cases does not exceed $$$5 \cdot 10^3$$$.

Output format:
For each test case, output $$$k$$$ integers in one line: the $$$i$$$-th of them must represent the $$$i$$$-th largest value of the beauty of a painting Elsie can obtain.

Constraints:
Time limit: 4.5 s
Memory limit: 512.0 MB

Note:
In the first test case, Elsie can either paint the only cell or not paint it. If she paints the only cell, the beauty of the painting is $$$-5$$$. If she chooses not to paint it, the beauty of the painting is $$$0$$$. Thus, the largest beauty she can obtain is $$$0$$$ and the second largest beauty she can obtain is $$$-5$$$.

Below is an illustration of the third test case.

Example input:
4
1 2
-5
2 4
2 -3
-1
3 8
2 4 3
1 3
5
6 20
0 -6 -3 0 -6 -2
-7 -5 -2 -3 -4
7 0 -9 -4
2 -1 1
1 -2
-6

Example output:
0 -5 
2 0 -1 -3 
7 5 4 3 3 2 1 0 
8 8 7 7 5 5 2 2 1 1 1 1 1 1 0 0 0 0 0 -1

Editorial:
Let $$$\texttt{dp}[i]$$$ store a list of all $$$\min(k, 2^i)$$$ highest beauties of a painting in non-increasing order if you only paint cells $$$1,2,\ldots ,i$$$.
Let's define merging two lists as creating a new list that stores the $$$k$$$ highest values from the two lists.
First, let's look at a slow method of transitioning. We iterate over the left endpoint $$$l$$$ such that $$$l \ldots i$$$ is a maximal painted interval. At each $$$l$$$, we merge $$$\texttt{dp}[l - 2]$$$, with $$$a_{l,i}$$$ added to each value, into $$$\texttt{dp}[i]$$$. We also merge $$$\texttt{dp}[i - 1]$$$ into $$$\texttt{dp}[i]$$$ to handle the case in which we do not paint cell $$$i$$$. If implemented well, transitioning takes $$$\mathcal{O}(nk)$$$ time leading to a $$$\mathcal{O}(n^2k)$$$ solution which is too slow.
We can speed this up. This merging process boils down to finding the $$$k$$$ largest elements from $$$n$$$ **non-increasing** lists in $$$\mathcal{O}((n + k) \log n)$$$ time. We can use a priority queue that stores ($$$\texttt{element}, \texttt{index}$$$) for each list. We can do the following $$$k$$$ times: add the top of the priority queue to our answer, advance its index, and update the priority queue accordingly. This allows us to transition in $$$\mathcal{O}((n + k) \log n)$$$ time which leads to a $$$\mathcal{O}((n^2 + nk) \log n)$$$ solution.