Maximum Subarray

题意翻译

你得到了一个序列 $a_1,a_2,\cdots,a_n$，由 $n$ 个整数组成。并且你还得到了两个整数 $k,x$。 你需要执行**一次**操作：选择**恰好 $k$ 个不同**的位置加上 $x$，其余位置减去 $x$。 比如说：如果 $a=[2,-1,2,3],k=1,x=2$，然后我们选择第一个位置，操作之后的 $a=[4,-3,0,1]$。 定义 $f(a)$ 为 $a$ 序列的子串的最大可能和。$a$ 的子串是 $a$ 的一部分，即序列 $a_i,a_{i+1},\cdots a_j$ 对于某个 $1\le i\le j\le n$。同时，空数组也应该被考虑，它的和为 $0$。 让 $a'$ 为 $a$ 操作后的序列，输出 $f(a')$ 的最大可能值。 $1\le t\le 10^4;\;1\le n,\sum n\le 2\cdot 10^5;\;0\le k\le \min(20,n);\;-10^9\le a_i,x\le 10^9$

题目描述

You are given an array $ a_1, a_2, \dots, a_n $ , consisting of $ n $ integers. You are also given two integers $ k $ and $ x $ . You have to perform the following operation exactly once: add $ x $ to the elements on exactly $ k $ distinct positions, and subtract $ x $ from all the others. For example, if $ a = [2, -1, 2, 3] $ , $ k = 1 $ , $ x = 2 $ , and we have picked the first element, then after the operation the array $ a = [4, -3, 0, 1] $ . Let $ f(a) $ be the maximum possible sum of a subarray of $ a $ . The subarray of $ a $ is a contiguous part of the array $ a $ , i. e. the array $ a_i, a_{i + 1}, \dots, a_j $ for some $ 1 \le i \le j \le n $ . An empty subarray should also be considered, it has sum $ 0 $ . Let the array $ a' $ be the array $ a $ after applying the aforementioned operation. Apply the operation in such a way that $ f(a') $ is the maximum possible, and print the maximum possible value of $ f(a') $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains three integers $ n $ , $ k $ and $ x $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 0 \le k \le \min(20, n) $ ; $ -10^9 \le x \le 10^9 $ ). The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ). The sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print one integer — the maximum possible value of $ f(a') $ .

输入输出样例

输入样例 #1

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

输出样例 #1

5
7
0
44

题目大意：给定一个整数序列和一个操作规则，求操作后序列的最大子数组和。

输入数据格式：
- 第一行包含一个整数 t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例有两行，第一行包含三个整数 n, k 和 x（1≤n≤2×10^5；0≤k≤min(20, n)；-10^9≤x≤10^9），其中 n 表示序列长度，k 表示操作中选定的不同位置数量，x 表示操作的加减值。
- 第二行包含 n 个整数 a_1, a_2, …, a_n（-10^9≤a_i≤10^9），表示序列的每个位置的值。

输出数据格式：
- 对于每个测试用例，输出一行，包含一个整数，表示操作后序列的最大子数组和。

样例输入：
```
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
```

样例输出：
```
5
7
0
44
```题目大意：给定一个整数序列和一个操作规则，求操作后序列的最大子数组和。 输入数据格式： - 第一行包含一个整数 t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例有两行，第一行包含三个整数 n, k 和 x（1≤n≤2×10^5；0≤k≤min(20, n)；-10^9≤x≤10^9），其中 n 表示序列长度，k 表示操作中选定的不同位置数量，x 表示操作的加减值。 - 第二行包含 n 个整数 a_1, a_2, …, a_n（-10^9≤a_i≤10^9），表示序列的每个位置的值。 输出数据格式： - 对于每个测试用例，输出一行，包含一个整数，表示操作后序列的最大子数组和。 样例输入： ``` 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 ``` 样例输出： ``` 5 7 0 44 ```