← 返回题目列表

Codeforces · 1942/D

D. 学习绘画

中文机器翻译题面 查看原题

Elsie 正在学习绘画。她的画布上有 $$$n$$$ 个单元格,编号从 $$$1$$$ 到 $$$n$$$,并且可以绘制任何(可能是空的)单元格子集。

Elsie 有一个二维数组 $$$a$$$,她将用它来评估绘画。设绘画中绘制单元的最大连续间隔为$$$[l_1,r_1],[l_2,r_2],\ldots,[l_x,r_x]$$$。这幅画的美丽在于$$$a_{l_i,r_i}$$$ 与所有$$$1 \le i \le x$$$ 的总和。在上图中,绘制单元格的最大连续间隔为$$$[2,4],[6,6],[8,9]$$$,绘画的美度为$$$a_{2,4}+a_{6,6}+a_{8,9}$$$。

有 $$$2^n$$$ 种方法来绘制条带。在所有这些方法中,帮助 Elsie 找到她可以获得的一幅画的最大可能价值 $$$k$$$。请注意,这些 $$$k$$$ 值不一定必须是不同的。保证至少有 $$$k$$$ 种不同的方法来绘制画布。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。

每个测试用例的第一行包含 $$$2$$$ 整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^3$$$, $$$1 \leq k \leq \min(2^n, 5 \cdot 10^3)$$$) — 您必须的画作美感的单元格数量和最大值数量找到。

每个测试用例接下来的 $$$n$$$ 行描述 $$$a$$$,其中第 $$$i$$$ 包含 $$$n-i+1$$$ 整数 $$$a_{i,i},a_{i,i+1},\ldots,a_{i,n}$$$ ($$$-10^6 \leq a_{i,j} \leq 10^6$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^3$$$,所有测试用例的 $$$k$$$ 总和不超过 $$$5 \cdot 10^3$$$。

输出

对于每个测试用例,在一行中输出 $$$k$$$ 个整数:其中第 $$$i$$$ 个整数必须代表 Elsie 可以获得的第 $$$i$$$ 个最大的绘画美感值。

示例

输入 #1

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

输出 #1

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

注意

在第一个测试用例中,Elsie 可以绘制唯一的单元格,也可以不绘制它。如果她画唯一的细胞,这幅画的美丽程度为$$$-5$$$。如果她选择不画它,这幅画的美丽就是$$$0$$$。因此,她可以获得的最大美丽是$$$0$$$,她可以获得的第二大美丽是$$$-5$$$。

下面是第三个测试用例的图示。