← 返回题目列表

Codeforces · 1920/B

B. 求和游戏

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

Alice 和 Bob 正在玩游戏。他们有一个数组 $$$a_1, a_2,\ldots,a_n$$$。游戏分为两个步骤:

- 首先,Alice 将从数组中删除最多 $$$k$$$ 个元素。
- 其次,Bob 最多将数组的 $$$x$$$ 元素乘以 $$$-1$$$。

Alice 想要最大化数组元素的总和,而 Bob 想要最小化它。如果双方都发挥最佳,则在比赛结束后求数组元素之和。

输入

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

每个测试用例的第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq x,k \leq n$$$) — 数组中的元素数量、Alice 可以删除的数组元素数量限制以及限制Bob 可以将 $$$-1$$$ 乘以的数组元素的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — 数组的元素。

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

输出

对于每个测试用例,输出一个整数 - 如果两个玩家都发挥最佳,则游戏结束后数组元素的总和。

示例

输入 #1

8
1 1 1
1
4 1 1
3 1 2 4
6 6 3
1 4 3 2 5 6
6 6 1
3 7 3 3 32 15
8 5 3
5 5 3 3 3 2 9 9
10 6 4
1 8 2 9 3 3 4 5 3 200
2 2 1
4 3
2 1 2
1 3

输出 #1

0
2
0
3
-5
-9
0
-1

注意

在第一个测试用例中,Alice 最好删除数组的唯一元素。那么,游戏结束后,数组元素的总和为$$$0$$$。

在第二个测试用例中,Alice 最好不要删除任何元素。然后 Bob 将 $$$4$$$ 乘以 $$$-1$$$。所以最终数组元素之和为$$$3+1+2-4=2$$$。

在第五个测试用例中,Alice 最好删除 $$$9, 9$$$。然后 Bob 将 $$$5, 5, 3$$$ 乘以 $$$-1$$$。所以数组元素的最终总和是$$$-5-5-3+3+3+2=-5$$$。