P14000 [eJOI 2025] Grid

Simona dreams of uncountable riches. She is offered to play a game for a big prize. Simona will be placed in cell $(0, 0)$ of a grid $A$ of size $N \times M$ filled with positive integers. She must reach cell $(N-1, M-1)$. To do this, she is allowed to repeatedly move from her current cell $(x, y)$ to any other cell $(x + d, y)$ or $(x, y + d)$, such that $d > 0$. For each such move, Simona will receive reward coins $|A_{x,y} - A_{x',y'}| - C$, where $x'$, $y'$ are her new coordinates and $C$ is a constant cost fixed before the start of the journey. Note that if the expression $|A_{x,y} - A_{x',y'}| - C$ evaluates to a negative number, Simona will lose coins. Note also that it is possible to end the game with a negative number of coins. Help Simona determine the maximum number of coins she can finish the game with. Note that $|a| = a$ if $a \geq 0$ and $|a| = -a$, otherwise. ### Implementation details You have to implement the function `max_profit`: ```cpp long long max_profit(int N, int M, int C, std::vector A) ``` - $N$, $M$: the dimensions of the grid; - $C$: the fixed cost constant for the test; - $A$: vector of vectors of integers of size $N \times M$, representing the two dimensional grid (indexed by row and then column). This function will be called once for each test and has to return the maximum number of coins Simona can end the game with.

The input format is the following: - line 1: three integers – the values of $N$, $M$ and $C$. - lines $2 - (N + 1)$: $M$ integers – the values of $A_{i,j}$.

The output format is the following: - line 1: one integer – the return value of the call.

### Example Consider the following call: ```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}}) ``` In this case the optimal path is $(0,0) \xrightarrow{7} (0,2) \xrightarrow{2} (1,2) \xrightarrow{10} (1,5) \xrightarrow{8} (4,5)$ and the number of coins achieved by following it is $7 + 2 + 10 + 8 = 27$. Your function must return $27$. ```cpp max_profit(2, 2, 100, {{1, 2}, {3, 4}}) ``` Here your function must return: $-197$. Note that the answer may be negative value. ### Constraints - $1 \leq N, M$ - $N \cdot M \leq 500000$ - $1 \leq A_{i,j} \leq 1000000$ for $0 \leq i < N$ and $0 \leq j < M$ - $0 \leq C \leq 1000000$ ### Subtasks | Subtask | Points | Required subtasks | Additional constraints | | :-: | :-: | :-: | :-: | | 0 | $0$ | - | The example. | | 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$ | - |