← 返回题目列表

Codeforces · 1716/C

C. 走廊里的机器人

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

有一个网格,由 $$$2$$$ 行和 $$$m$$$ 列组成。行从上到下编号为 $$$1$$$ 到 $$$2$$$。这些列从左到右编号为 $$$1$$$ 到 $$$m$$$。

机器人从 $$$(1, 1)$$$ 单元格开始。在一秒钟内,它可以执行以下两个操作之一:

- 移动到一侧相邻的单元格:上、右、下或左;
- 留在同一个牢房中。

机器人不允许移动到网格之外。

最初,除单元格 $$$(1, 1)$$$ 之外的所有单元格均被锁定。每个单元格 $$$(i, j)$$$ 包含一个值 $$$a_{i,j}$$$ - 该单元格解锁的那一刻。只有在移动之前至少经过 $$$a_{i,j}$$$ 秒,机器人才能移动到单元格 $$$(i, j)$$$ 中。

机器人应访问所有单元格,而不会进入任何单元格两次或更多次(单元格 $$$(1, 1)$$$ 被视为在开始时输入)。它可以在任何单元格中完成。

机器人能达到的最快速度是多少?

输入

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

每个测试用例的第一行包含一个整数 $$$m$$$ ($$$2 \le m \le 2 \cdot 10^5$$$) — 网格的列数。

接下来的 $$$2$$$ 行中的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$0 \le a_{i,j} \le 10^9$$$) - 每个单元格解锁的时刻。 $$$a_{1,1} = 0$$$。如果 $$$a_{i,j} = 0$$$,则单元格 $$$(i, j)$$$ 从一开始就解锁。

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

输出

对于每个测试用例,打印一个整数 - 机器人在不进入任何单元格两次或更多次的情况下访问所有单元格所需的最短秒数。

示例

输入 #1

4
3
0 0 1
4 3 2
5
0 4 8 12 16
2 6 10 14 18
4
0 10 10 10
10 10 10 10
2
0 0
0 0

输出 #1

5
19
17
3