← 返回题目列表

AtCoder · pakencamp_2025_day3_q

Q. 荆棘之路

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

配点 : 100 点

致环球杯参赛者

当包含在 Universal Cup 中时,此问题将被删除。因此,当使用 AtCoder 结果进行 Universal Cup 时,我们建议先解决其他问题。 请针对


問題文

T 测试用例解决以下问题。

这片森林是 您可以将其视为 2 行 N 列的网格。每个方格都有一个正整数,称为“脊椎度”,从上往下 i 第几行,从左边 j 选择列中的方块。 (i,j) ,则刺痛程度为 T_{i,j} 。

掌管植物的神圭介,通过使用神力“砍伐”一次,可以进行以下操作。

  • 具有正尖峰的正方形 (a,b)(1 \leq a \leq 2,\ 1 \leq b \leq N)并选择该正方形的刺程度。 1 减少。然而,尖峰程度不能设为负值。

Haruku 当前质量 (1,1) 并移动到右侧或下方的相邻方块以扩展该方块。 我们想要达到 (2,N) 。

此时,通过提前适当砍伐树木,先生。所有可能的路线 对于,路径上的所有方块 ( (包括(1,1) 和 即使增加或减少 (2,N) )是 S 我希望如下。

求 Keisuke 应该使用的最少插条数量来满足这个条件。

制約

  • 1 \le T \le 2 \times 10^5
  • 1 \le N \le 2 \times 10^5
  • 1 \le S \le 2 \times 10^{14}
  • 1 \le T_{i,j} \le 10^9
  • 对于每个测试用例 N 的总和是 2 \times 10^5 以下
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。输入的 1 行具有以下格式。

T

然后,T 测试用例如下。每个测试用例均按以下格式给出。 输出 Keisuke 在第

N S
T_{1,1} T_{1,2} \ldots T_{1,N}
T_{2,1} T_{2,2} \ldots T_{2,N}

出力

T 行。i 行中,i 个测试用例中需要执行的最少“砍伐树木”次数。


入力例 1

3
3 4
1 2 3
4 5 6
6 7
1 1 1 1 1 1
1 1 1 1 1 1
10 31
4 1 5 9 2 6 5 3 5 8
9 7 9 3 2 3 8 4 6 2

出力例 1

13
0
39

该输入包含 包含3 测试用例。

1 第一个测试用例的初始状态如下。

1 2 3
4 5 6

Keisuke 先生对“日志记录”的描述如下。 通过重复 13 次,您可以增加森林方块的尖度。

0 1 3
4 0 0

的事情。

  • 质量 (1,1) 中,加上 1 进行两次砍伐。
  • 质量 (1,2) 中,加上 1 进行两次砍伐。
  • 质量 (2,2) 中,加上 5 进行两次砍伐。
  • 质量 (2,3) 中,加上 6 进行两次砍伐。

此时,重复移动到右侧或下方的相邻方格。 (1,1) 从 (2,3) 的方法中,您经过的方格的尖峰度总值为 4 这满足条件,因为:

12 答案是 13 。