← 返回题目列表

Codeforces · 1555/C

C. 硬币行

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

Alice 和 Bob 正在矩阵上玩游戏,该矩阵由 $$$2$$$ 行和 $$$m$$$ 列组成。 $$$j$$$ 列第 $$$i$$$ 行的单元格中包含 $$$a_{i, j}$$$ 硬币。

最初,Alice 和 Bob 都站在牢房 $$$(1, 1)$$$ 中。他们将执行一系列移动以到达单元格 $$$(2, m)$$$。

可能的动作是:

- 向右移动 — 从某个单元格 $$$(x, y)$$$ 到 $$$(x, y + 1)$$$;
- 向下移动 — 从某个单元格 $$$(x, y)$$$ 到 $$$(x + 1, y)$$$。

首先,Alice 进行所有动作,直到达到 $$$(2, m)$$$。她收集她访问的所有单元格(包括起始单元格)中的硬币。

当爱丽丝完成时,鲍勃开始他的旅程。他还执行了到达 $$$(2, m)$$$ 的动作,并收集了他访问过的所有单元格中的硬币,但爱丽丝没有。

游戏的得分是鲍勃收集的硬币总数。

Alice 想要最小化分数。鲍勃想要最大化分数。如果双方都发挥最佳状态,比赛的比分会是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

测试用例的第一行包含一个整数 $$$m$$$ ($$$1 \le m \le 10^5$$$) — 矩阵的列数。

接下来的 $$$2$$$ 行中的第 $$$i$$$ 行包含 $$$m$$$ 整数 $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^4$$$) — 单元格中的硬币数量矩阵第 $$$j$$$ 列中的 $$$i$$$ 行。

所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数——如果两个玩家都发挥最佳的情况下的游戏得分。

示例

输入 #1

3
3
1 3 7
3 5 1
3
1 3 9
3 5 1
1
4
7

输出 #1

7
8
0

注意

测试用例的路径如下图所示。 Alice 的路径用红色表示,Bob 的路径用蓝色表示。