103586: [Atcoder]ABC358 G - AtCoder Tour
Description
Score : $550$ points
Problem Statement
AtCoder Land is represented by a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the cell at the $i$-th row and $j$-th column.
Takahashi starts at cell $(S_i, S_j)$ and repeats the following action $K$ times:
- He either stays in the current cell or moves to an adjacent cell. After this action, if he is in cell $(i, j)$, he gains a fun value of $A_{i, j}$.
Find the maximum total fun value he can gain.
Here, a cell $(x', y')$ is considered adjacent to cell $(x, y)$ if and only if $|x - x'| + |y - y'| = 1$.
Constraints
- $1 \leq H, W \leq 50$
- $1 \leq K \leq 10^9$
- $1 \leq S_i \leq H$
- $1 \leq S_j \leq W$
- $1 \leq A_{i, j} \leq 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$H$ $W$ $K$
$S_i$ $S_j$
$A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W}$
$\vdots$
$A_{H, 1}$ $A_{H, 2}$ $\ldots$ $A_{H, W}$
Output
Print the answer.
Sample Input 1
2 3 3 1 2 2 1 2 3 4 5
Sample Output 1
14
Takahashi can gain a total fun value of $14$ by acting as follows:
- Initially, he is at $(1, 2)$.
- He moves to cell $(2, 2)$. Then, he gains a fun value of $A_{2, 2} = 4$.
- He moves to cell $(2, 3)$. Then, he gains a fun value of $A_{2, 3} = 5$.
- He stays in cell $(2, 3)$. Then, he gains a fun value of $A_{2, 3} = 5$.
He cannot gain a total fun value greater than $14$, so print $14$.
Sample Input 2
2 2 1000000000 2 1 100 100 100 99
Sample Output 2
100000000000
Output
问题描述
AtCoder 乐园是一个有 $H$ 行和 $W$ 列的网格。记 $(i, j)$ 为第 $i$ 行第 $j$ 列的单元格。
Takahashi 从单元格 $(S_i, S_j)$ 开始，重复以下动作 $K$ 次：
- 他要么留在当前单元格，要么移动到相邻的单元格。完成这个动作后，如果他在单元格 $(i, j)$，他将获得乐趣值 $A_{i, j}$。
找出他能获得的最大总乐趣值。
单元格 $(x', y')$ 只有当 $|x - x'| + |y - y'| = 1$ 时才被认为是单元格 $(x, y)$ 的相邻单元格。
限制条件
- $1 \leq H, W \leq 50$
- $1 \leq K \leq 10^9$
- $1 \leq S_i \leq H$
- $1 \leq S_j \leq W$
- $1 \leq A_{i, j} \leq 10^9$
- 所有输入值都是整数。
输入
输入从标准输入以以下格式给出：
$H$ $W$ $K$
$S_i$ $S_j$
$A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W}$
$\vdots$
$A_{H, 1}$ $A_{H, 2}$ $\ldots$ $A_{H, W}$
输出
打印答案。
样例输入 1
2 3 3 1 2 2 1 2 3 4 5
样例输出 1
14
Takahashi 可以通过以下方式获得总乐趣值 $14$：
- 最初，他在 $(1, 2)$。
- 他移动到单元格 $(2, 2)$。然后，他获得了乐趣值 $A_{2, 2} = 4$。
- 他移动到单元格 $(2, 3)$。然后，他获得了乐趣值 $A_{2, 3} = 5$。
- 他留在单元格 $(2, 3)$。然后，他获得了乐趣值 $A_{2, 3} = 5$。
他无法获得总乐趣值大于 $14$，所以打印 $14$。
样例输入 2
2 2 1000000000 2 1 100 100 100 99
样例输出 2
100000000000