A6938. 烦人的游戏
编程题
普及+/提高
知识点
题目描述
你有两个整数数组 $a$ 和 $b$ ，长度均为 $n$ ，以及一个总回合数 $k$ 。
Alice 和 Bob 通过轮流修改数组 $a$ 来玩游戏。Alice 先手。游戏总共进行 $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$ 的最大非空子数组和定义为 $ \max_{1 \leq i \leq j \leq n} S(i, j) $ ，其中 $ S(i, j) = a_{i} + a_{i+1} + \cdots + a_{j} $ 。注意不考虑空子数组。
Alice 和 Bob 通过轮流修改数组 $a$ 来玩游戏。Alice 先手。游戏总共进行 $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$ 的最大非空子数组和定义为 $ \max_{1 \leq i \leq j \leq n} S(i, j) $ ，其中 $ S(i, j) = a_{i} + a_{i+1} + \cdots + a_{j} $ 。注意不考虑空子数组。
输入格式
每个测试包含多个测试用例。第一行包含一个整数 $t$ 表示测试用例的数量。每个测试用例的描述随后给出。
每个测试用例的第一行包含两个整数 $n$ 和 $k$，表示数组的长度和回合总数。
每个测试用例的第二行包含 $n$ 个整数 $a_{1},a_{2},\cdots,a_{n}$，表示数组 $a$ 的元素。
每个测试用例的第三行包含 $n$ 个整数 $b_{1},b_{2},\cdots,b_{n}$，表示数组 $b$ 的元素。
每个测试用例的第一行包含两个整数 $n$ 和 $k$，表示数组的长度和回合总数。
每个测试用例的第二行包含 $n$ 个整数 $a_{1},a_{2},\cdots,a_{n}$，表示数组 $a$ 的元素。
每个测试用例的第三行包含 $n$ 个整数 $b_{1},b_{2},\cdots,b_{n}$，表示数组 $b$ 的元素。
输出格式
对于每个测试用例，输出一个整数，表示在 $k$ 回合后，假设双方都以最优策略进行游戏的最终得分。
输入输出样例
输入 #1
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
输出 #1
11 41 9 3 -1
说明/提示
### 样例解释
对于第一个测试用例：
- 任何操作都不能改变数组 $a$ ，因为 $b$ 中的所有元素都是零。
- 最终数组的最大非空子数组和为 $3 + (-1) + 9 = 11$ 。
对于第二个测试用例，一种可能的最优操作序列是：
- Alice 将 $b_{3}=1$ 加到 $a_{3}$ 。数组 $a$ 变为 $[10, 10, 11, 10]$ 。
- Bob 将 $b_{1}=1$ 从 $a_{1}$ 减去。数组 $a$ 变为 $[9, 10, 11, 10]$ 。
- Alice 将 $b_{3}=1$ 加到 $a_{3}$ 。数组 $a$ 变为 $[9, 10, 12, 10]$ 。
- Bob 将 $b_{1}=1$ 从 $a_{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 将 $b_{2}=11$ 从 $a_{2}$ 减去。数组 $a$ 变为 $[2, -7, 3]$ 。
- 最终数组的最大非空子数组和为 $3$ 。
### 数据范围
$1 \le t \le 10^{4}$
$1 \le n \le 2\times 10^{5}$ ， $1 \le k \le 2\times 10^{5}$
$-10^{9} \le a_{i} \le 10^{9}$
$0 \le b_{i} \le 10^{9}$
保证所有测试用例的 $n$ 之和不超过 $2\times 10^{5}$。
对于第一个测试用例：
- 任何操作都不能改变数组 $a$ ，因为 $b$ 中的所有元素都是零。
- 最终数组的最大非空子数组和为 $3 + (-1) + 9 = 11$ 。
对于第二个测试用例，一种可能的最优操作序列是：
- Alice 将 $b_{3}=1$ 加到 $a_{3}$ 。数组 $a$ 变为 $[10, 10, 11, 10]$ 。
- Bob 将 $b_{1}=1$ 从 $a_{1}$ 减去。数组 $a$ 变为 $[9, 10, 11, 10]$ 。
- Alice 将 $b_{3}=1$ 加到 $a_{3}$ 。数组 $a$ 变为 $[9, 10, 12, 10]$ 。
- Bob 将 $b_{1}=1$ 从 $a_{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 将 $b_{2}=11$ 从 $a_{2}$ 减去。数组 $a$ 变为 $[2, -7, 3]$ 。
- 最终数组的最大非空子数组和为 $3$ 。
### 数据范围
$1 \le t \le 10^{4}$
$1 \le n \le 2\times 10^{5}$ ， $1 \le k \le 2\times 10^{5}$
$-10^{9} \le a_{i} \le 10^{9}$
$0 \le b_{i} \le 10^{9}$
保证所有测试用例的 $n$ 之和不超过 $2\times 10^{5}$。