311006: CF1920B. Summation Game

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Summation Gametime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alice and Bob are playing a game. They have an array $a_1, a_2,\ldots,a_n$. The game consists of two steps:

  • First, Alice will remove at most $k$ elements from the array.
  • Second, Bob will multiply at most $x$ elements of the array by $-1$.

Alice wants to maximize the sum of elements of the array while Bob wants to minimize it. Find the sum of elements of the array after the game if both players play optimally.

Input

Each test consists of 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 three integers $n$, $k$, and $x$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq x,k \leq n$) — the number of elements in the array, the limit on the number of elements of the array that Alice can remove, and the limit on the number of elements of the array that Bob can multiply $-1$ to.

The second line of each test case contains $n$ integers $a_1, a_2,\ldots, a_n$ ($1 \leq a_i \leq 1000$) — the elements of the array.

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

Output

For each test case, output a single integer — the sum of elements of the array after the game if both players play optimally.

ExampleInput
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
Output
0
2
0
3
-5
-9
0
-1
Note

In the first test case, it is optimal for Alice to remove the only element of the array. Then, the sum of elements of the array is $0$ after the game is over.

In the second test case, it is optimal for Alice to not remove any elements. Bob will then multiply $4$ by $-1$. So the final sum of elements of the array is $3+1+2-4=2$.

In the fifth test case, it is optimal for Alice to remove $9, 9$. Bob will then multiply $5, 5, 3$ by $-1$. So the final sum of elements of the array is $-5-5-3+3+3+2=-5$.

Output

题目大意:
Alice和Bob在玩一个游戏。他们有一个数组a_1, a_2, …, a_n。游戏分为两步:

1. 首先,Alice将最多删除k个元素。
2. 其次,Bob将最多乘以x个元素的-1。

Alice希望最大化数组的元素和,而Bob希望最小化它。如果双方都发挥最佳,求游戏后数组的元素和。

输入数据格式:
每个测试包含多个测试用例。第一行包含一个整数t(1≤t≤10^4)——测试用例的数量。测试用例的描述如下。

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

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

保证所有测试用例的n之和不超过2×10^5。

输出数据格式:
对于每个测试用例,输出一个整数——如果双方都发挥最佳,游戏后数组的元素和。题目大意: Alice和Bob在玩一个游戏。他们有一个数组a_1, a_2, …, a_n。游戏分为两步: 1. 首先,Alice将最多删除k个元素。 2. 其次,Bob将最多乘以x个元素的-1。 Alice希望最大化数组的元素和,而Bob希望最小化它。如果双方都发挥最佳,求游戏后数组的元素和。 输入数据格式: 每个测试包含多个测试用例。第一行包含一个整数t(1≤t≤10^4)——测试用例的数量。测试用例的描述如下。 每个测试用例的第一行包含三个整数n、k和x(1≤n≤2×10^5,1≤x,k≤n)——数组中的元素数量、Alice可以删除的数组元素的限制和Bob可以乘以-1的数组元素的限制。 每个测试用例的第二行包含n个整数a_1, a_2, …, a_n(1≤a_i≤1000)——数组的元素。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式: 对于每个测试用例,输出一个整数——如果双方都发挥最佳,游戏后数组的元素和。

加入题单

上一题 下一题 算法标签: