#P18807. [2027年国家集训队互测]双重反转

[2027年国家集训队互测]双重反转

双重反转

给定一个由 nn 个正整数组成的非降序列 aa。Alice 和 Bob 进行 kk 轮游戏,初始得分为 0。

每轮,Alice 先选一个从未选过的位置,其值为 xx;接着 Bob 可选择使用一次翻转技能,把本轮的 xx 变为 −x-x;最后把该值加入得分。Bob 全局最多使用 oo 次技能。一个位置一旦选了就不能再选,即使数值相同,不同位置也分别计数。

双方知道整个序列且采取最优策略:Alice 最大化终局得分,Bob 最小化。求终局得分。

输入格式

第一行三个整数 n,k,on,k,o。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n,按非降序给出。

输出格式

一行一个整数,表示最优策略下的终局得分。

样例 1

3 2 2
1 1 2
-2

Alice 可以选两个 1,保证至少得到 −2-2。Bob 可以把两次选择都翻转,保证得分不超过 −2-2。

样例 2

7 7 2
1 2 3 4 5 6 7
2

每个数都会被选到,Bob 对 6 和 7 使用技能,得分为 1+2+3+4+5−6−7=21+2+3+4+5-6-7=2。

数据范围

1≤k≤n≤2⋅1061\le k\le n\le 2\cdot10^6,1≤o≤21\le o\le2,1≤a1≤⋯≤an≤1091\le a_1\le\cdots\le a_n\le10^9。令 V=max⁡iaiV=\max_i a_i。

数据分组 参考分值 nn 上限 附加限制
1 5 18 无
2 3 2⋅1062\cdot10^6 k≤2k\le2
3 11 100 无
4 15 2000
5 12 2⋅1062\cdot10^6 k≤500k\le500
6 14 V≤1024V\le1024
7 19 5⋅1045\cdot10^4 无
8 21 2⋅1062\cdot10^6

本题评测采用50个测试点,每点2分。

样例附件