CF1796D Maximum Subarray

给定一个由 $n$ 个整数构成的数组 $a_1, a_2, \dots, a_n$，以及两个整数 $k$ 和 $x$。 你需要恰好进行一次如下操作：将 $x$ 加到恰好 $k$ 个不同位置上的元素上，并将 $x$ 从其余所有元素上减去。 例如，如果 $a = [2, -1, 2, 3]$，$k = 1$，$x = 2$，并且我们选择第一个元素，那么操作后数组 $a = [4, -3, 0, 1]$。 定义 $f(a)$ 为数组 $a$ 的一个子数组的最大可能和。数组的子数组指的是数组中一段连续的部分，即 $a_i, a_{i+1}, \dots, a_j$，其中 $1 \le i \le j \le n$。空子数组也需要考虑，其和为 $0$。 记 $a'$ 为对 $a$ 进行上述操作后的数组。请以使 $f(a')$ 最大为目标进行操作，并输出 $f(a')$ 的最大可能值。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n$、$k$ 和 $x$（$1 \le n \le 2 \cdot 10^5$；$0 \le k \le \min(20, n)$；$-10^9 \le x \le 10^9$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$）。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示 $f(a')$ 的最大可能值。

由 ChatGPT 4.1 翻译