Stamp Game

题目描述

有一个网格，包含 $H$ $-$ 行（水平方向）和 $W$ 列（垂直方向）。记 $(i, j)$ 为从上数第 $i$ 行、从左数第 $j$ 列的格子。
对于满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$ 的每一对整数 $(i, j)$，格子 $(i, j)$ 上写有一个正整数 $A_{i,j}$。此外，所有格子一开始都被涂成白色。 Takahashi 有一个可以覆盖 $h_1$ 行 $w_1$ 列的矩形黑色印章，Aoki 有一个可以覆盖 $h_2$ 行 $w_2$ 列的矩形白色印章。 他们将使用这些印章在网格上进行对抗游戏。 首先，Takahashi 按下他的黑色印章，将一个 $h_1$ 行 $w_1$ 列的矩形区域涂成黑色。
也就是说，他选择一对整数 $(i, j)$，满足 $1 \leq i \leq H - h_1 + 1$ 且 $1 \leq j \leq W - w_1 + 1$，并将每个满足 $i \leq r \leq i + h_1 - 1$ 且 $j \leq c \leq j + w_1 - 1$ 的格子 $(r, c)$ 涂成黑色。 接着，Aoki 按下他的白色印章，将一个 $h_2$ 行 $w_2$ 列的矩形区域涂成白色。
也就是说，他选择一对整数 $(i, j)$，满足 $1 \leq i \leq H - h_2 + 1$ 且 $1 \leq j \leq W - w_2 + 1$，并将每个满足 $i \leq r \leq i + h_2 - 1$ 且 $j \leq c \leq j + w_2 - 1$ 的格子 $(r, c)$ 涂成白色。
如果其中有些格子已经被 Takahashi 涂成黑色，它们也会变成白色。 游戏的得分定义为在上述 Takahashi 和 Aoki 按下印章之后仍然被涂成黑色的格子上所写整数的总和。 Takahashi 采用最优策略使得得分尽可能大，而 Aoki 采用最优策略使得得分尽可能小。 问这个游戏的得分会是多少？

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $h_1$ $w_1$ $h_2$ $w_2$ $A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, W}$ $A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, W}$ $\vdots$ $A_{H, 1}$ $A_{H, 2}$ $\cdots$ $A_{H, W}$

输出格式

当 Takahashi 采用使得得分尽可能大的最优策略且 Aoki 采用使得得分尽可能小的最优策略时，输出游戏的得分。

3 4 2 3 3 1
3 1 4 1
5 9 2 6
5 3 5 8

19

3 4 2 3 3 4
3 1 4 1
5 9 2 6
5 3 5 8

0

10 10 3 7 2 3
9 7 19 7 10 4 13 9 4 8
10 15 16 3 18 19 17 12 13 2
12 18 4 9 13 13 6 13 5 2
16 12 2 14 18 17 14 7 8 12
12 13 17 12 14 15 19 7 13 15
5 2 16 10 4 6 1 2 7 8
10 14 14 10 9 13 11 4 9 19
16 12 3 19 19 6 2 19 14 20
15 3 19 19 2 10 1 4 3 15
13 20 5 6 19 1 7 17 10 19

180

提示

$2 \leq H, W \leq 1000$ $1 \leq h_1, h_2 \leq H$ $1 \leq w_1, w_2 \leq W$ $1 \leq A_{i, j} \leq 10^9$ 输入中的所有数值都是整数。游戏过程如下。

最初，所有格子均为白色。 首先，Takahashi 按下他的 $2 \times 3$ 黑色印章，将以下六个格子涂成黑色：$(2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4)$。 接着，Aoki 按下他的 $3 \times 1$ 白色印章，将以下三个格子涂成白色：$(1, 4), (2, 4), (3, 4)$。 最终，以下四个格子被涂成黑色：$(2, 2), (2, 3), (3, 2), (3, 3)$，得分为 $9 + 2 + 3 + 5 = 19$。
按下 Aoki 的印章之后，所有格子都会变成白色，得分为 $0$。

标签: AtCoder|abc228F

来源

AtCoder|abc228F