Maximum Subarray
Contest: Educational Codeforces Round 144 (Rated for Div. 2)
Difficulty rating: 2000
Tags: data structures, dp, greedy, two pointers

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')$$$.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
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

Example output:
5
7
0
44

Editorial:
There are greedy and dynamic programming solutions. We will describe dynamic programming solution.
The main task is to choose some segment that is the answer to the problem, while choosing $$$k$$$ positions to increase by $$$x$$$. To do this, we can use dynamic programming $$$dp_{i, j, t}$$$, where $$$i$$$ is the number of positions that have already been considered (from $$$0$$$ to $$$n$$$), $$$j$$$ is the number of elements that have already been increased by $$$x$$$ (from $$$0$$$ to $$$k$$$), $$$t$$$ is the flag showing the current state (whether we are before the chosen segment, inside the segment, or after the segment). Transitions in such dynamic programming are quite simple: we have a choice either to increase $$$j$$$ by $$$1$$$, then the value of the $$$i$$$-th element is $$$a_i + x$$$, or not to increase, then the value of the $$$i$$$-th element is $$$a_i - x$$$; we can also change the state of the flag (note that you can only switch from the current state to the subsequent ones, i.e., for example, you cannot switch from the state "the segment has already ended" to the state "inside the segment"). If the current state of the flag is "inside the segment", then $$$a_i + x$$$ or $$$a_i - x$$$ (depending on the selected transition) should be added to the dynamic programming value itself.
So, we got a solution in $$$O(nk)$$$.