← 返回题目列表

Codeforces · 2158/C

C. 烦人的游戏

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

给定两个整数数组 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$,总圈数 $$$k$$$。

Alice 和 Bob 通过轮流修改数组 $$$a$$$ 来玩游戏。爱丽丝先走。游戏持续 $$$k$$$ 回合。

在他们的回合中,玩家必须选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 并执行 一 以下操作:

  • 添加: 将 $$$a_i$$$ 增加 $$$b_i$$$,即设置 $$$a_i := a_i + b_i$$$。
  • 减去: 将 $$$a_i$$$ 减少 $$$b_i$$$,即设置 $$$a_i := a_i - b_i$$$。

第 $$$k$$$ 回合结束后,最终得分计算为 最大非空子数组总和 修改后的数组 $$$a$$$ 的 。 Alice的目标是最大化最终得分,而Bob的目标是最小化最终得分。

假设两名选手都以最佳状态发挥各自的目标,则确定最终得分。 $$$a$$$ 的

的 树的 最大非空子数组总和 修改后的数组 $$$a$$$ 的 定义为 $$$\max_{1 \leq i \leq j \leq n} S(i, j)$$$,其中 $$$S(i, j) = a_i + a_{i+1} + \cdots + a_j$$$。请注意,不考虑空子数组。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$1 \le k \le 2\cdot 10^5$$$) - 数组的长度和总圈数。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_{n}$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_{n}$$$ ($$$0 \le b_i \le 10^9$$$) — 数组 $$$b$$$ 的元素。

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

输出

对于每个测试用例,打印一个整数 - $$$k$$$ 回合后的最终分数,假设两个玩家都发挥最佳。

示例

输入
复制

5
5 200000
3 -1 9 -5 4
0 0 0 0 0
4 5
10 10 10 10
1 1 1 1
3 1
2 -7 3
1 11 3
3 2
2 -7 3
1 11 3
1 1
-3
2

输出
复制

11
41
9
3
-1

注意

对于第一个测试用例:

  • 任何移动都无法更改数组 $$$a$$$,因为 $$$b$$$ 中的所有元素均为零。
  • 此最终数组的最大非空子数组和为 $$$3 + (-1) + 9 = 11$$$。

对于第二个测试用例,可能的最佳移动序列之一是:

  • Alice 将 $$$b_3=1$$$ 添加到 $$$a_3$$$。数组 $$$a$$$ 变为 $$$[10, 10, 11, 10]$$$。
  • Bob 从 $$$a_1$$$ 中减去 $$$b_1=1$$$。数组 $$$a$$$ 变为 $$$[9, 10, 11, 10]$$$。
  • Alice 将 $$$b_3=1$$$ 添加到 $$$a_3$$$。数组 $$$a$$$ 变为 $$$[9, 10, 12, 10]$$$。
  • Bob 从 $$$a_1$$$ 中减去 $$$b_1=1$$$。数组 $$$a$$$ 变为 $$$[8, 10, 12, 10]$$$。
  • Alice 将 $$$b_4=1$$$ 添加到 $$$a_4$$$。数组 $$$a$$$ 变为 $$$[8, 10, 12, 11]$$$。
  • 该最终数组的最大非空子数组和为 $$$8+10+12+11 = 41$$$。

对于第三个测试用例,可能的最佳移动顺序之一是:

  • Alice 将 $$$b_2=11$$$ 添加到 $$$a_2$$$。数组 $$$a$$$ 变为 $$$[2, 4, 3]$$$。
  • 该最终数组的最大非空子数组和为 $$$2 + 4 + 3 = 9$$$。

对于第四个测试用例,可能的最佳移动顺序之一是:

  • Alice 将 $$$b_2=11$$$ 添加到 $$$a_2$$$。数组 $$$a$$$ 变为 $$$[2, 4, 3]$$$。
  • Bob 从 $$$a_2$$$ 中减去 $$$b_2=11$$$。数组 $$$a$$$ 变为 $$$[2, -7, 3]$$$。
  • 此最终数组的最大非空子数组和为 $$$3$$$。