#5464. 「eJOI2025」网格

题目描述

题目译自 $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$

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