Description

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：

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

• $N, M$：网格的行数和列数；
• $C$：固定代价常数；
• $A$：大小为 $N \times M$ 的二维数组，表示网格（先行后列索引）。

该函数在每个测试中被调用一次，返回 Simona 在最优策略下结束游戏时最多能获得的硬币数。

Input Format

输入格式如下：

• 第 1 行：三个整数——$N, M, C$。
• 第 $2$ 行到第 $(N+1)$ 行：每行 $M$ 个整数——$A_{i,j}$。

Output Format

输出格式如下：

• 第 1 行：一个整数——函数调用的返回值。

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

27

2 2 100
1 2
3 4

-197

Hint

示例

考虑如下调用：

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$。

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$

子任务

翻译由 ChatGPT-5 完成。