The Enchanted Forest
Contest: Codeforces Round 796 (Div. 1)
Difficulty rating: 1600
Tags: brute force, greedy

Marisa comes to pick mushrooms in the Enchanted Forest.

The Enchanted forest can be represented by $$$n$$$ points on the $$$X$$$-axis numbered $$$1$$$ through $$$n$$$. Before Marisa started, her friend, Patchouli, used magic to detect the initial number of mushroom on each point, represented by $$$a_1,a_2,\ldots,a_n$$$.

Marisa can start out at any point in the forest on minute $$$0$$$. Each minute, the followings happen in order:

- She moves from point $$$x$$$ to $$$y$$$ ($$$|x-y|\le 1$$$, possibly $$$y=x$$$).
- She collects all mushrooms on point $$$y$$$.
- A new mushroom appears on each point in the forest.

Note that she cannot collect mushrooms on minute $$$0$$$.

Now, Marisa wants to know the maximum number of mushrooms she can pick after $$$k$$$ minutes.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10 ^ 5$$$, $$$1\le k \le 10^9$$$) — the number of positions with mushrooms and the time Marisa has, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the initial number of mushrooms on point $$$1,2,\ldots,n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 5$$$.

Output format:
For each test case, print the maximum number of mushrooms Marisa can pick after $$$k$$$ minutes.

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

Note:
Test case 1:

Marisa can start at $$$x=2$$$. In the first minute, she moves to $$$x=1$$$ and collect $$$5$$$ mushrooms. The number of mushrooms will be $$$[1,7,2,3,4]$$$. In the second minute, she moves to $$$x=2$$$ and collects $$$7$$$ mushrooms. The numbers of mushrooms will be $$$[2,1,3,4,5]$$$. After $$$2$$$ minutes, Marisa collects $$$12$$$ mushrooms.

It can be shown that it is impossible to collect more than $$$12$$$ mushrooms.

Test case 2:

This is one of her possible moving path:

$$$2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$$$

It can be shown that it is impossible to collect more than $$$37$$$ mushrooms.

Example input:
4
5 2
5 6 1 2 3
5 7
5 6 1 2 3
1 2
999999
5 70000
1000000000 1000000000 1000000000 1000000000 1000000000

Example output:
12
37
1000000
5000349985

Editorial:
If $$$k\le n$$$:
- Consider how to maximize the initial mushrooms she collects. Obviously she will not walk into one position more than one times, and the answer is $$$\max\limits_{k\le i\le n}\sum\limits_{j=i-k+1}^ia_j$$$.
- Consider how to maximize the additional mushrooms she collects. Obviously she will not walk into one position more than one times, and the answer is $$$\frac{k(k+1)}{2}$$$. - We can find that maximizing the two parts shares the same strategy. So add up the answers of the two parts.
If $$$k>n$$$:
- Consider how to maximize the initial mushrooms she collects. Obviously she can collect all of them. The answer is $$$\sum\limits_{i=1}^n a_i$$$. - Consider how to maximize the additional mushrooms she collects. Let $$$b_i$$$ be her position on minute $$$k-i$$$ ($$$0\le i< n$$$). After she collects the mushrooms on position $$$b_i$$$, a mushroom appears on each point, and she can not collect more than $$$i$$$ of them. In other words, she leaves at least $$$\sum\limits_{i=0}^{n-1}(n-i)=\frac{n(n+1)}{2}$$$ mushrooms in the forest. Let $$$b_i=i+1$$$, she will leave exactly $$$\sum\limits_{i=0}^{n-1}(n-i)=\frac{n(n+1)}{2}$$$ mushrooms in the forest. - We can find that maximizing the two parts shares the same strategy. So add up the answers of the two parts.