← 返回题目列表

Codeforces · 2239/B

B. 决策恐惧症

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

有$$$n$$$人参加圆桌聚会,按顺时针顺序编号为$$$1、2、3、\ldots、n$$$。你准备了一些礼物要分发给他们。

每个人 $$$i$$$ 都有一个体重 $$$a_i$$$ 和一个公共视野 $$$d$$$。 $$$i$$$ 人的视野由顺时针坐的 $$$d$$$ 人和逆时针坐的 $$$d$$$ 人组成(总共 $$$2d$$$ 人,不包括 $$$i$$$ 人)。

人$$$i$$$获得的幸福感由以下规则决定:

  • 如果$$$i$$$收到礼物,并且在他们的视野内有$$$x$$$人没有收到礼物,他们会获得$$$x \cdot a_i$$$幸福。
  • 如果$$$i$$$没有收到礼物,并且在他们的视野内有$$$x$$$人收到了礼物,他们会产生$$$-x \cdot a_i$$$幸福。

您希望最大化所有 $$$n$$$ 人的总幸福感。求这个最大值。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le d \lt \frac{n}{2}$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^8$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个人的体重。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出一个表示最大总幸福感的整数。

示例

输入
复制

5
3 1
1 2 3
5 1
1 4 5 2 6
6 2
1 1 4 5 1 4
10 2
230 24 3 42 432 234 934 2389 333 444
3 1
100000000 100000000 100000000

输出
复制

3
15
26
8590
0

注意

在第一个测试用例中,有 3 个人围坐一圈。对于每个人$$$i$$$,视野为$$$d=1$$$,其中包括顺时针坐的1个人和逆时针坐的1个人。如果人 2 收到礼物,他们会从 2 个没有收到礼物的邻居那里获得快乐,从而产生 $$$2 \cdot a_2 = 2 \cdot 2 = 4$$$。然而,人 1 和人 3 却遭受了损失,因为他们没有收到礼物,但有邻居收到了礼物。计算完所有可能性后,最大的总幸福感为3。

在第二个测试用例中,$$$n=5,d=1$$$。最好的方案是给2、3、5号人送礼物,这样可以达到最大的总幸福值15。