P14000 [eJOI 2025] Grid

Simona 梦想获得无数财富。她得到一个玩游戏赢取大奖的机会。 Simona 将从一个 $N \times M$ 的网格 $A$ 的格子 $(0, 0)$ 出发，这个网格填充了正整数。她必须到达格子 $(N-1, M-1)$。为此，她可以重复进行如下移动：从当前位置 $(x, y)$ 移动到任意 $(x + d, y)$ 或 $(x, y + d)$，其中 $d > 0$。每次移动时，她将获得奖励硬币 $|A_{x,y} - A_{x',y'}| - C$，其中 $(x', y')$ 是她的新位置，$C$ 是游戏开始前固定的常数代价。注意，如果表达式 $|A_{x,y} - A_{x',y'}| - C$ 的结果为负数，Simona 将失去硬币。注意游戏结束时她可能拥有负数硬币。 请帮助 Simona 确定她最多可以获得多少硬币。 其中，$|a| = a$ 若 $a \geq 0$，否则 $|a| = -a$。 ### 实现细节 你需要实现函数 `max_profit`： ```cpp long long max_profit(int N, int M, int C, std::vector A) ``` - $N, M$：网格的行数和列数； - $C$：固定代价常数； - $A$：大小为 $N \times M$ 的二维数组，表示网格（先行后列索引）。 该函数在每个测试中被调用一次，返回 Simona 在最优策略下结束游戏时最多能获得的硬币数。

输入格式如下： - 第 1 行：三个整数——$N, M, C$。 - 第 $2$ 行到第 $(N+1)$ 行：每行 $M$ 个整数——$A_{i,j}$。

输出格式如下： - 第 1 行：一个整数——函数调用的返回值。

### 示例 考虑如下调用： ```cpp 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$。 ```cpp max_profit(2, 2, 100, {{1, 2}, {3, 4}}) ``` 在这里，函数必须返回 $-197$。注意答案可能为负数。 ### 约束条件 - $1 \leq N, M$ - $N \cdot M \leq 500000$ - $1 \leq A_{i,j} \leq 1000000$，对所有 $0 \leq i < N, 0 \leq j < M$ - $0 \leq C \leq 1000000$ ### 子任务 | 子任务 | 分值 | 依赖子任务 | 附加约束 | | :-: | :-: | :-: | :-: | | 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 50000$ | | 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 50000$ | | 10 | $13$ | $0-9$ | - | 翻译由 ChatGPT-5 完成。