CF1644C Increase Subarray Sums

给定一个由 $n$ 个整数构成的数组 $a_1, a_2, \dots, a_n$，以及一个整数 $x$。 定义 $f(k)$ 为对数组 $a$ 执行如下操作后，某个连续子数组的最大和：将 $x$ 加到恰好 $k$ 个不同位置的元素上。空子数组也需要考虑，其和为 $0$。 注意，子数组不必包含所有被加过 $x$ 的元素。 请分别计算 $k$ 从 $0$ 到 $n$ 时，每个 $f(k)$ 的最大值。

第一行包含一个整数 $t$（$1 \le t \le 5000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 5000$；$0 \le x \le 10^5$），分别表示数组长度和要加的值。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^5 \le a_i \le 10^5$）。 所有测试用例中 $n$ 的总和不超过 $5000$。

对于每个测试用例，输出 $n+1$ 个整数，分别表示 $k$ 从 $0$ 到 $n$ 时每个 $f(k)$ 的最大值。

在第一个测试用例中，无论将 $x$ 加到哪些元素上，最大子数组和始终是整个数组的和。如果将 $x$ 加到 $k$ 个元素上，和会增加 $k \cdot x$。 在第二个测试用例中： - 当 $k=0$ 时，最优选择是空子数组，和为 $0$。 - 当 $k=1$ 时，最优是将第 $3$ 个元素加 $x$，最大和为 $-1+5=4$，对应子数组为 $[3,3]$。 - 当 $k=2$ 时，最优是将第 $3$ 个元素和任意一个其他元素加 $x$，最大和仍为 $4$，对应子数组为 $[3,3]$。 - 当 $k=3$ 时，必须将所有元素都加 $x$，最大和为 $(-2+5)+(-7+5)+(-1+5)=5$，对应子数组为 $[1,3]$。 由 ChatGPT 4.1 翻译