← 返回题目列表

Codeforces · 2154/E

E. 无心思考

中文机器翻译题面 查看原题

给你一个长度为 $$$n$$$ 的正整数数组 $$$a$$$ 和一个正整数 $$$k$$$,你将用它们玩以下游戏:

  • 游戏开始时,您将选择一个 奇数 整数 $$$x$$$ ($$$1 \le x \le n$$$)。
  • 然后执行以下操作 最多 $$$k$$$ 次(可能没有):
    • 选择一个 子序列 长度为 $$$m$$$ 的 的 $$$a$$$ 长度为 $$$x$$$,然后将子序列中的每个值替换为该子序列的中位数$$$^{\text{*}}$$$。更正式地说,选择 $$$x$$$ 整数 $$$i_1,\ldots,i_x$$$ ($$$1 \le i_1 \lt i_2 \lt \ldots \lt i_x \le n$$$)。然后同时对所有 $$$d$$$ ($$$1 \le d \le x$$$) 执行 $$$a_{i_d}$$$:= $$$\mathrm{median}([a_{i_1},a_{i_2},\ldots,a_{i_x}])$$$。

请注意,您选择的整数 $$$x$$$ 不能 操作之间的更改。

确定玩游戏后可获得的 $$$a$$$ 总和的最大值。

$$$^{\text{*}}$$$The 中位数 长度为 $$$n$$$ 的数组 $$$a$$$ 的 (写作 $$$\mathrm{median}(a)$$$)是 $$$\left\lfloor\frac{n + 1}{2}\right\rfloor$$$ - $$$a$$$ 中的第一个最小元素,其中 $$$\left\lfloor x \right\rfloor$$$表示小于或等于$$$x$$$的最大整数。例如,$$$\mathrm{中位数}([4, 3, 1, 2, 5]) = 3$$$ 和 $$$\mathrm{中位数}([4, 3, 5, 3]) = 3$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 2 \cdot 10^5$$$) - 数组 $$$a$$$ 的长度,以及可以执行该操作的最大次数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出玩游戏后可达到的最大和$$$a$$$。

示例

输入
复制

7
5 1
1 1 5 5 5
3 1
10 1 2
6 3
1 1 2 3 1 2
5 1
1 2 2 3 5
3 1
332473521 409066963 155613323
6 6
81 71 90 15 87 36
7 2
4 13 11 19 15 16 10

输出
复制

25
13
13
14
997420563
522
105

注意

在第一个测试用例中实现 $$$25$$$ 的一种方法是选择 $$$x = 5$$$ 然后执行以下操作:

  • $$$[\color{红色}1, \color{红色}1, \color{红色}5, \color{红色}5, \color{红色}5] \rightarrow [5, 5, 5, 5, 5]$$$

在第三个测试用例中实现 $$$13$$$ 的一种方法是选择 $$$x = 3$$$ 然后执行以下操作:

  • $$$[\color{red}1, 1, \color{red}2, 3, 1, \color{red}2] \rightarrow [\color{red}2, 1, \color{red}2, 3, \color{red}1, 2] \rightarrow [2, \color{red}1, \color{red}2, 3, \color{red}2, 2] \rightarrow [2, 2, 2, 3, 2, 2]$$$