Increase Subarray Sums
Contest: Educational Codeforces Round 123 (Rated for Div. 2)
Difficulty rating: 1400
Tags: brute force, dp, greedy, implementation

You are given an array $$$a_1, a_2, \dots, a_n$$$, consisting of $$$n$$$ integers. You are also given an integer value $$$x$$$.

Let $$$f(k)$$$ be the maximum sum of a contiguous subarray of $$$a$$$ after applying the following operation: add $$$x$$$ to the elements on exactly $$$k$$$ distinct positions. An empty subarray should also be considered, it has sum $$$0$$$.

Note that the subarray doesn't have to include all of the increased elements.

Calculate the maximum value of $$$f(k)$$$ for all $$$k$$$ from $$$0$$$ to $$$n$$$ independently.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of testcases.

The first line of the testcase contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 5000$$$; $$$0 \le x \le 10^5$$$) — the number of elements in the array and the value to add.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^5 \le a_i \le 10^5$$$).

The sum of $$$n$$$ over all testcases doesn't exceed $$$5000$$$.

Output format:
For each testcase, print $$$n + 1$$$ integers — the maximum value of $$$f(k)$$$ for all $$$k$$$ from $$$0$$$ to $$$n$$$ independently.

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

Note:
In the first testcase, it doesn't matter which elements you add $$$x$$$ to. The subarray with the maximum sum will always be the entire array. If you increase $$$k$$$ elements by $$$x$$$, $$$k \cdot x$$$ will be added to the sum.

In the second testcase:

- For $$$k = 0$$$, the empty subarray is the best option.
- For $$$k = 1$$$, it's optimal to increase the element at position $$$3$$$. The best sum becomes $$$-1 + 5 = 4$$$ for a subarray $$$[3, 3]$$$.
- For $$$k = 2$$$, it's optimal to increase the element at position $$$3$$$ and any other element. The best sum is still $$$4$$$ for a subarray $$$[3, 3]$$$.
- For $$$k = 3$$$, you have to increase all elements. The best sum becomes $$$(-2 + 5) + (-7 + 5) + (-1 + 5) = 5$$$ for a subarray $$$[1, 3]$$$.

Example input:
3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4

Example output:
10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8

Editorial:
Consider the naive solution.
Iterate over $$$k$$$. Then iterate over the segment that will have the maximum sum. Let its length be $$$l$$$. Since $$$x$$$ is non-negative, it's always optimal to increase the elements inside the segment. So if $$$k \le l$$$, then the sum of the segment increases by $$$k \cdot x$$$. Otherwise, only the elements inside the segment will affect the sum, thus, it will increase by $$$l \cdot x$$$. That can be written as $$$min(k, l) \cdot x$$$.
Notice that we only care about two parameters for each segment. Its length and its sum. Moreover, if there are several segments with the same length, we only care about the one with the greatest sum.
Thus, the idea of the solution is the following. For each length, find the segment of this length with the greatest sum. Then calculate $$$f(k)$$$ in $$$O(n)$$$ by iterating over the length of the segment.
Overall complexity: $$$O(n^2)$$$ per testcase.