最大连续和先加版 - 题目

题目描述

给定一个由 $n$ 个整数构成的数组 $a_1, a_2, \ldots, 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}, \ldots, a_j$，其中 $1 \leq i \leq j \leq n$。空子数组也需要考虑，其值为 0。

记 $a'$ 为对 $a$ 进行上述操作后的数组。请以使 $f(a')$ 最大为目标进行操作，并输出 $f(a')$ 的最大可能值。

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

每个测试用例的第一行包含三个整数 $n$，$k$ 和 $x (-10^9 \leq x \leq 10^9)$。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n (-10^9 \leq a_i \leq 10^9)$。

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

4
4 1 2
2 -1 2 3
2 2 3
-1 2
3 0 5
3 2 4
6 2 -8
4 -1 9 -3 7 -8

$30\%$ 的数据：$\sum n \leq 500, k = 2$

$70\%$ 的数据：$1 \leq n \leq 10^5; 0 \leq k \leq \min(20, n)$

$90\%$ 的数据：$1 \leq \sum n \leq 10^6; 0 \leq k \leq \min(20, n)$

$100\%$ 的数据：$1 \leq \sum n \leq 3 \times 10^6; 0 \leq k \leq \min(20, n)$