AT_abc228_f [ABC228F] 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}$。此外，所有格子初始都被涂成白色。

高桥君有一个高 $h_1$ 行、宽 $w_1$ 列的黑色矩形印章，青木君有一个高 $h_2$ 行、宽 $w_2$ 列的白色矩形印章。
两人将用这些印章和网格进行对战游戏。

首先，高桥君用他的黑色印章在网格上选择一个高 $h_1$ 行、宽 $w_1$ 列的矩形区域，将该区域内的所有格子涂成黑色。
也就是说，他选择一个满足 $1 \leq i \leq H - h_1 + 1$ 且 $1 \leq j \leq W - w_1 + 1$ 的整数对 $(i, j)$，然后将所有满足 $i \leq r \leq i + h_1 - 1$ 且 $j \leq c \leq j + w_1 - 1$ 的格子 $(r, c)$ 涂成黑色。

接着，青木君用他的白色印章在网格上选择一个高 $h_2$ 行、宽 $w_2$ 列的矩形区域，将该区域内的所有格子涂成白色。
也就是说，他选择一个满足 $1 \leq i \leq H - h_2 + 1$ 且 $1 \leq j \leq W - w_2 + 1$ 的整数对 $(i, j)$，然后将所有满足 $i \leq r \leq i + h_2 - 1$ 且 $j \leq c \leq j + w_2 - 1$ 的格子 $(r, c)$ 涂成白色。
此时，如果青木君要涂白的格子已经被高桥君涂黑，则这些格子会被白色覆盖，最终颜色为白色。

如上所述，高桥君和青木君各用一次印章后，所有被涂成黑色的格子上所写整数的总和即为本次游戏的“得分”。高桥君会采取使得分尽可能大的最优策略，青木君会采取使得分尽可能小的最优策略。请你求出最终的游戏得分。

输入格式

输入按以下格式从标准输入给出。

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

输出格式

输出在双方都采取最优策略时，游戏的最终得分。

输入输出样例 #1

输入 #1

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

输出 #1

19

输入输出样例 #2

输入 #2

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

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

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$
• 输入均为整数

样例解释 1

游戏过程如下：

• 开始时，所有格子都是白色。
• 首先，高桥君用 $2$ 行 $3$ 列的黑色印章，将格子 $(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)$ 共 $6$ 个格子涂成黑色。
• 然后，青木君用 $3$ 行 $1$ 列的白色印章，将格子 $(1, 4), (2, 4), (3, 4)$ 涂成白色。
• 最终被涂成黑色的格子为 $(2, 2), (2, 3), (3, 2), (3, 3)$ 共 $4$ 个，因此游戏得分为 $9 + 2 + 3 + 5 = 19$。

样例解释 2

青木君用印章后，所有格子都变成白色，游戏得分为 $0$。

由 ChatGPT 4.1 翻译