该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AdditionalFile5464.zip

#5464. 「eJOI2025」网格

标签: 传统 | 时间限制: 300 ms | 内存限制: 256 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "grid.h"。

题目描述

题目译自 eJOI2025 Day1 T2. Grid

Simona 梦想着拥有数不尽的财富。她受邀参加一个赢取大奖的游戏。

Simona 将被放置在一个大小为 $N \times M$、填满正整数的网格 $A$ 的单元格 $(0, 0)$ 处。她必须到达单元格 $(N-1, M-1)$。为此，她可以从当前单元格 $(x, y)$ 重复移动到任何其他单元格 $(x+d, y)$ 或 $(x, y+d)$，其中 $d > 0$。对于每一次这样的移动，Simona 将获得 $|A_{x,y} - A_{x',y'}| - C$ 的奖励金币，其中 $(x', y')$ 是她的新坐标，$C$ 是在旅程开始前固定的一个常数成本。请注意，如果表达式 $|A_{x,y} - A_{x',y'}| - C$ 的结果为负数，Simona 将会失去金币。另请注意，游戏结束时金币数量可能为负。

请帮助 Simona 确定她能以最多的金币数量完成游戏。

请注意，如果 $a \geq 0$，则 $|a|=a$；否则 $|a|=-a$。

实现细节

您必须实现函数 max_profit：

 long long max_profit(int N, int M, int C,
                      std::vector<std::vector<int>> A)

• $N, M$：网格的尺寸；
• $C$：测试点的固定成本常数；
• $A$：一个大小为 $N \times M$ 的整数向量的向量，代表二维网格（按行然后按列索引）。

对于每个测试点，该函数将被调用一次，并且必须返回 Simona 能以最多的金币数量结束游戏。

示例评测程序

输入格式如下：

• 第一行包含三个整数：$N, M, C$ 的值。
• 第 $2$ 到第 $N+1$ 行：每行包含 $M$ 个整数——$A_{i,j}$ 的值。

输出格式如下：

• 第一行包含一个整数：该调用的返回值。

样例 1

考虑以下调用：

 max_profit(5, 6, 4, {{20, 24, 31, 33, 36, 40},
                    {25, 23, 25, 31, 32, 39},
                    {31, 26, 21, 24, 31, 35},
                    {32, 28, 25, 21, 26, 28},
                    {36, 35, 28, 24, 21, 27}})

在这种情况下，最优路径是 $(0,0) \xrightarrow{7} (0, 2) \xrightarrow{2} (1, 2) \xrightarrow{10} (1,5) \xrightarrow{8}(4, 5)$，沿着这条路径获得的金币数量是 $7+2+10+8=27$。您的函数必须返回 $27$。

样例 2

 max_profit(2, 2, 100, {{1, 2}, {3, 4}})

在这种情况下，您的函数必须返回：$-197$。请注意，答案可能是负值。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N, M$
• $N \cdot M \leq 500\ 000$
• 对于 $0 \leq i < N$ 和 $0 \leq j < M$，有 $1 \leq A_{i, j} \leq 1\ 000\ 000$
• $0 \leq C \leq 1\ 000\ 000$

详细子任务附加限制及分值如下表所示。

子任务	分值	子任务依赖	附加限制
$0$	$0$	$-$	样例。
$1$	$9$		$N=1, M \leq 200$
$2$	$5$		$N=1, A_{i,j} \leq A_{i, j+1}$
$3$	$8$		$N=1, C=0$
$4$	$10$	$1$	$N=1, M \leq 50\ 000$
$5$	$7$	$1-4$	$N=1$
$6$	$15$	$1$	$N, M \leq 200$
$7$	$9$	$2$	$A_{i,j} \leq A_{i+1, j}, A_{i, j+1}$
$8$	$12$	$3$	$C=0$
$9$	$12$	$0-1, 4, 6$	$N \cdot M \leq 50\ 000$
$10$	$13$	$0-9$	$-$