309484: CF1687A. The Enchanted Forest
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
The Enchanted Forest
题意翻译
> 其实这里被称为魔法森林，基本上就是因为这些有幻觉效果的蘑菇。光是接近这些蘑菇，就好像被施了魔法而产生幻觉。——《东方求闻史纪》 魔理沙来到了魔法森林采摘蘑菇。 魔法森林可以被抽象成一条有着 $n$ 个节点，从 $1$ 到 $n$ 标号的数轴。在魔理沙出发之前，她的好友帕秋莉运用魔法去侦测了每个节点上的蘑菇数量，分别为 $a_1,a_2,\dots,a_n$。 在第 $0$ 分钟的时候，魔理沙可以从任意一个节点出发。在每一分钟的时候，她将会做以下事情： - 她将从节点 $x$ 移动到节点 $y$（$|x-y| \leq 1$，即 $y$ 可能等于 $x$） - 她将会收集节点 $y$ 上的所有蘑菇。 - 魔法森林中每个节点会再生长出一个蘑菇。 注意，她不能在第 $0$ 分钟的时候收集蘑菇。 现在魔理沙希望知道她在前 $k$ 分钟的时候，最多能收集到多少个蘑菇。请你帮帮她。 **输入格式** 第一行输入一个正整数 $t(1 \leq t \leq 10^4)$，表示输入数据组数。 对于每一组测试数据，第一行输入两个正整数 $n,k(1 \leq n \leq 2\times 10^5, 1\leq k \leq 10^9)$，含义如题目所述。 第二行输入 $n$ 个正整数 $a_i$，表示每个节点上起初有的蘑菇数量。 **输出格式** 对于每组测试数据输出一行，表示魔理沙最多能收集到多少个蘑菇。题目描述
The enchanted forest got its name from the magical mushrooms growing here. They may cause illusions and generally should not be approached. —Perfect Memento in Strict Sense 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.输入输出格式
输入格式
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 $ .
输出格式
For each test case, print the maximum number of mushrooms Marisa can pick after $ k $ minutes.
输入输出样例
输入样例 #1
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输出样例 #1
12
37
1000000
5000349985说明
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.Input
题意翻译
> 其实这里被称为魔法森林，基本上就是因为这些有幻觉效果的蘑菇。光是接近这些蘑菇，就好像被施了魔法而产生幻觉。——《东方求闻史纪》 魔理沙来到了魔法森林采摘蘑菇。 魔法森林可以被抽象成一条有着 $n$ 个节点，从 $1$ 到 $n$ 标号的数轴。在魔理沙出发之前，她的好友帕秋莉运用魔法去侦测了每个节点上的蘑菇数量，分别为 $a_1,a_2,\dots,a_n$。 在第 $0$ 分钟的时候，魔理沙可以从任意一个节点出发。在每一分钟的时候，她将会做以下事情： - 她将从节点 $x$ 移动到节点 $y$（$|x-y| \leq 1$，即 $y$ 可能等于 $x$） - 她将会收集节点 $y$ 上的所有蘑菇。 - 魔法森林中每个节点会再生长出一个蘑菇。 注意，她不能在第 $0$ 分钟的时候收集蘑菇。 现在魔理沙希望知道她在前 $k$ 分钟的时候，最多能收集到多少个蘑菇。请你帮帮她。 **输入格式** 第一行输入一个正整数 $t(1 \leq t \leq 10^4)$，表示输入数据组数。 对于每一组测试数据，第一行输入两个正整数 $n,k(1 \leq n \leq 2\times 10^5, 1\leq k \leq 10^9)$，含义如题目所述。 第二行输入 $n$ 个正整数 $a_i$，表示每个节点上起初有的蘑菇数量。 **输出格式** 对于每组测试数据输出一行，表示魔理沙最多能收集到多少个蘑菇。Output
**题意翻译**
《东方求闻史纪》中提到，魔法森林之所以得名，是因为这里生长着能产生幻觉的神奇蘑菇。魔理沙来到魔法森林采摘蘑菇，森林可以看作一条有 $n$ 个节点，从 $1$ 到 $n$ 编号的数轴。在出发前，她的朋友帕秋莉用魔法探测了每个节点上的蘑菇数量，分别是 $a_1, a_2, \ldots, a_n$。魔理沙在第 $0$ 分钟可以从任意节点出发，每分钟她会：
- 从节点 $x$ 移动到节点 $y$（$|x-y| \leq 1$，即 $y$ 可以等于 $x$）
- 收集节点 $y$ 上的所有蘑菇。
- 森林中每个节点会长出一个新蘑菇。
注意，她在第 $0$ 分钟不能收集蘑菇。现在魔理沙想知道在前 $k$ 分钟内，她最多能收集多少蘑菇。
**输入格式**
第一行输入一个正整数 $t(1 \leq t \leq 10^4)$，表示测试数据组数。每组测试数据，第一行输入两个正整数 $n, k(1 \leq n \leq 2 \times 10^5, 1 \leq k \leq 10^9)$，含义如题目所述。第二行输入 $n$ 个正整数 $a_i$，表示每个节点起初的蘑菇数量。
**输出格式**
对于每组测试数据输出一行，表示魔理沙最多能收集到多少个蘑菇。
**题目描述**
《完美记忆的严格意义》中提到，魔法森林因生长着能产生幻觉的神奇蘑菇而得名。魔理沙来到魔法森林采摘蘑菇，森林可以表示为 $n$ 个点在 $X$ 轴上，编号为 $1$ 到 $n$。在魔理沙出发前，她的朋友帕秋莉用魔法探测了每个点上的初始蘑菇数量，表示为 $a_1, a_2, \ldots, a_n$。
魔理沙可以在第 $0$ 分钟从森林中任意点出发。每一分钟，按照以下顺序发生：
- 她从点 $x$ 移动到 $y$（$|x-y|\le 1$，$y$ 可能等于 $x$）。
- 她收集点 $y$ 上的所有蘑菇。
- 森林中每个点会长出一个新蘑菇。
注意，她在第 $0$ 分钟不能收集蘑菇。现在，魔理沙想知道在 $k$ 分钟后，她最多能采摘多少蘑菇。
**输入输出格式**
每个测试包含多个测试用例。第一行包含一个整数 $t(1 \leq t \leq 10^4)$ —— 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $n, k(1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^9)$ —— 有蘑菇的地点数量和魔理沙的时间。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$ —— 点 $1, 2, \ldots, n$ 上的初始蘑菇数量。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
**输出格式**
对于每个测试用例，输出魔理沙在 $k$ 分钟后最多能采摘的蘑菇数量。
**输入输出样例**
**输入样例 #1**
```
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
```
**输出样例 #1**
```
12
37
1000000
5000349985
```
**说明**
测试用例 1:
魔理沙可以从 $x=2$ 开始。第一分钟，她移动到 $x=1$ 并收集 $5$ 个蘑菇。蘑菇的数量变为 $[1,7,2,3,4]$。第二分钟，她移动到 $x=2$ 并收集 $7$ 个蘑菇。蘑菇的数量变为 $[2,1,3,4,5]$。两分钟后，魔理沙共收集了 $12$ 个蘑菇。
可以证明，不可能收集到超过 $12$ 个蘑菇。
测试用例 2:
魔理沙的一种可能的移动路径是：
$2 \**题意翻译** 《东方求闻史纪》中提到，魔法森林之所以得名，是因为这里生长着能产生幻觉的神奇蘑菇。魔理沙来到魔法森林采摘蘑菇，森林可以看作一条有 $n$ 个节点，从 $1$ 到 $n$ 编号的数轴。在出发前，她的朋友帕秋莉用魔法探测了每个节点上的蘑菇数量，分别是 $a_1, a_2, \ldots, a_n$。魔理沙在第 $0$ 分钟可以从任意节点出发，每分钟她会： - 从节点 $x$ 移动到节点 $y$（$|x-y| \leq 1$，即 $y$ 可以等于 $x$） - 收集节点 $y$ 上的所有蘑菇。 - 森林中每个节点会长出一个新蘑菇。 注意，她在第 $0$ 分钟不能收集蘑菇。现在魔理沙想知道在前 $k$ 分钟内，她最多能收集多少蘑菇。 **输入格式** 第一行输入一个正整数 $t(1 \leq t \leq 10^4)$，表示测试数据组数。每组测试数据，第一行输入两个正整数 $n, k(1 \leq n \leq 2 \times 10^5, 1 \leq k \leq 10^9)$，含义如题目所述。第二行输入 $n$ 个正整数 $a_i$，表示每个节点起初的蘑菇数量。 **输出格式** 对于每组测试数据输出一行，表示魔理沙最多能收集到多少个蘑菇。 **题目描述** 《完美记忆的严格意义》中提到，魔法森林因生长着能产生幻觉的神奇蘑菇而得名。魔理沙来到魔法森林采摘蘑菇，森林可以表示为 $n$ 个点在 $X$ 轴上，编号为 $1$ 到 $n$。在魔理沙出发前，她的朋友帕秋莉用魔法探测了每个点上的初始蘑菇数量，表示为 $a_1, a_2, \ldots, a_n$。 魔理沙可以在第 $0$ 分钟从森林中任意点出发。每一分钟，按照以下顺序发生： - 她从点 $x$ 移动到 $y$（$|x-y|\le 1$，$y$ 可能等于 $x$）。 - 她收集点 $y$ 上的所有蘑菇。 - 森林中每个点会长出一个新蘑菇。 注意，她在第 $0$ 分钟不能收集蘑菇。现在，魔理沙想知道在 $k$ 分钟后，她最多能采摘多少蘑菇。 **输入输出格式** 每个测试包含多个测试用例。第一行包含一个整数 $t(1 \leq t \leq 10^4)$ —— 测试用例的数量。测试用例的描述如下。 每个测试用例的第一行包含两个整数 $n, k(1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^9)$ —— 有蘑菇的地点数量和魔理沙的时间。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$ —— 点 $1, 2, \ldots, n$ 上的初始蘑菇数量。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。 **输出格式** 对于每个测试用例，输出魔理沙在 $k$ 分钟后最多能采摘的蘑菇数量。 **输入输出样例** **输入样例 #1** ``` 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 ``` **输出样例 #1** ``` 12 37 1000000 5000349985 ``` **说明** 测试用例 1: 魔理沙可以从 $x=2$ 开始。第一分钟，她移动到 $x=1$ 并收集 $5$ 个蘑菇。蘑菇的数量变为 $[1,7,2,3,4]$。第二分钟，她移动到 $x=2$ 并收集 $7$ 个蘑菇。蘑菇的数量变为 $[2,1,3,4,5]$。两分钟后，魔理沙共收集了 $12$ 个蘑菇。 可以证明，不可能收集到超过 $12$ 个蘑菇。 测试用例 2: 魔理沙的一种可能的移动路径是： $2 \
《东方求闻史纪》中提到，魔法森林之所以得名，是因为这里生长着能产生幻觉的神奇蘑菇。魔理沙来到魔法森林采摘蘑菇，森林可以看作一条有 $n$ 个节点，从 $1$ 到 $n$ 编号的数轴。在出发前，她的朋友帕秋莉用魔法探测了每个节点上的蘑菇数量，分别是 $a_1, a_2, \ldots, a_n$。魔理沙在第 $0$ 分钟可以从任意节点出发，每分钟她会：
- 从节点 $x$ 移动到节点 $y$（$|x-y| \leq 1$，即 $y$ 可以等于 $x$）
- 收集节点 $y$ 上的所有蘑菇。
- 森林中每个节点会长出一个新蘑菇。
注意，她在第 $0$ 分钟不能收集蘑菇。现在魔理沙想知道在前 $k$ 分钟内，她最多能收集多少蘑菇。
**输入格式**
第一行输入一个正整数 $t(1 \leq t \leq 10^4)$，表示测试数据组数。每组测试数据，第一行输入两个正整数 $n, k(1 \leq n \leq 2 \times 10^5, 1 \leq k \leq 10^9)$，含义如题目所述。第二行输入 $n$ 个正整数 $a_i$，表示每个节点起初的蘑菇数量。
**输出格式**
对于每组测试数据输出一行，表示魔理沙最多能收集到多少个蘑菇。
**题目描述**
《完美记忆的严格意义》中提到，魔法森林因生长着能产生幻觉的神奇蘑菇而得名。魔理沙来到魔法森林采摘蘑菇，森林可以表示为 $n$ 个点在 $X$ 轴上，编号为 $1$ 到 $n$。在魔理沙出发前，她的朋友帕秋莉用魔法探测了每个点上的初始蘑菇数量，表示为 $a_1, a_2, \ldots, a_n$。
魔理沙可以在第 $0$ 分钟从森林中任意点出发。每一分钟，按照以下顺序发生：
- 她从点 $x$ 移动到 $y$（$|x-y|\le 1$，$y$ 可能等于 $x$）。
- 她收集点 $y$ 上的所有蘑菇。
- 森林中每个点会长出一个新蘑菇。
注意，她在第 $0$ 分钟不能收集蘑菇。现在，魔理沙想知道在 $k$ 分钟后，她最多能采摘多少蘑菇。
**输入输出格式**
每个测试包含多个测试用例。第一行包含一个整数 $t(1 \leq t \leq 10^4)$ —— 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $n, k(1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^9)$ —— 有蘑菇的地点数量和魔理沙的时间。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$ —— 点 $1, 2, \ldots, n$ 上的初始蘑菇数量。
保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
**输出格式**
对于每个测试用例，输出魔理沙在 $k$ 分钟后最多能采摘的蘑菇数量。
**输入输出样例**
**输入样例 #1**
```
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
```
**输出样例 #1**
```
12
37
1000000
5000349985
```
**说明**
测试用例 1:
魔理沙可以从 $x=2$ 开始。第一分钟，她移动到 $x=1$ 并收集 $5$ 个蘑菇。蘑菇的数量变为 $[1,7,2,3,4]$。第二分钟，她移动到 $x=2$ 并收集 $7$ 个蘑菇。蘑菇的数量变为 $[2,1,3,4,5]$。两分钟后，魔理沙共收集了 $12$ 个蘑菇。
可以证明，不可能收集到超过 $12$ 个蘑菇。
测试用例 2:
魔理沙的一种可能的移动路径是：
$2 \**题意翻译** 《东方求闻史纪》中提到，魔法森林之所以得名，是因为这里生长着能产生幻觉的神奇蘑菇。魔理沙来到魔法森林采摘蘑菇，森林可以看作一条有 $n$ 个节点，从 $1$ 到 $n$ 编号的数轴。在出发前，她的朋友帕秋莉用魔法探测了每个节点上的蘑菇数量，分别是 $a_1, a_2, \ldots, a_n$。魔理沙在第 $0$ 分钟可以从任意节点出发，每分钟她会： - 从节点 $x$ 移动到节点 $y$（$|x-y| \leq 1$，即 $y$ 可以等于 $x$） - 收集节点 $y$ 上的所有蘑菇。 - 森林中每个节点会长出一个新蘑菇。 注意，她在第 $0$ 分钟不能收集蘑菇。现在魔理沙想知道在前 $k$ 分钟内，她最多能收集多少蘑菇。 **输入格式** 第一行输入一个正整数 $t(1 \leq t \leq 10^4)$，表示测试数据组数。每组测试数据，第一行输入两个正整数 $n, k(1 \leq n \leq 2 \times 10^5, 1 \leq k \leq 10^9)$，含义如题目所述。第二行输入 $n$ 个正整数 $a_i$，表示每个节点起初的蘑菇数量。 **输出格式** 对于每组测试数据输出一行，表示魔理沙最多能收集到多少个蘑菇。 **题目描述** 《完美记忆的严格意义》中提到，魔法森林因生长着能产生幻觉的神奇蘑菇而得名。魔理沙来到魔法森林采摘蘑菇，森林可以表示为 $n$ 个点在 $X$ 轴上，编号为 $1$ 到 $n$。在魔理沙出发前，她的朋友帕秋莉用魔法探测了每个点上的初始蘑菇数量，表示为 $a_1, a_2, \ldots, a_n$。 魔理沙可以在第 $0$ 分钟从森林中任意点出发。每一分钟，按照以下顺序发生： - 她从点 $x$ 移动到 $y$（$|x-y|\le 1$，$y$ 可能等于 $x$）。 - 她收集点 $y$ 上的所有蘑菇。 - 森林中每个点会长出一个新蘑菇。 注意，她在第 $0$ 分钟不能收集蘑菇。现在，魔理沙想知道在 $k$ 分钟后，她最多能采摘多少蘑菇。 **输入输出格式** 每个测试包含多个测试用例。第一行包含一个整数 $t(1 \leq t \leq 10^4)$ —— 测试用例的数量。测试用例的描述如下。 每个测试用例的第一行包含两个整数 $n, k(1 \le n \le 2 \cdot 10^5, 1 \le k \le 10^9)$ —— 有蘑菇的地点数量和魔理沙的时间。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$ —— 点 $1, 2, \ldots, n$ 上的初始蘑菇数量。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。 **输出格式** 对于每个测试用例，输出魔理沙在 $k$ 分钟后最多能采摘的蘑菇数量。 **输入输出样例** **输入样例 #1** ``` 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 ``` **输出样例 #1** ``` 12 37 1000000 5000349985 ``` **说明** 测试用例 1: 魔理沙可以从 $x=2$ 开始。第一分钟，她移动到 $x=1$ 并收集 $5$ 个蘑菇。蘑菇的数量变为 $[1,7,2,3,4]$。第二分钟，她移动到 $x=2$ 并收集 $7$ 个蘑菇。蘑菇的数量变为 $[2,1,3,4,5]$。两分钟后，魔理沙共收集了 $12$ 个蘑菇。 可以证明，不可能收集到超过 $12$ 个蘑菇。 测试用例 2: 魔理沙的一种可能的移动路径是： $2 \