分数: 500 点
问题陈述
有一个网格 H 水平行和 W 垂直列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
对于每对整数 (i, j) 这样 1 \leq i \leq H 和 1 \leq j \leq W, (i, j) 包含正整数 A_{i,j}。此外,每个方块都漆成白色。
高桥有一个长方形的黑色印章,可以覆盖 h_1 行和 w_1 列,青木有一个长方形的白色印章,可以覆盖 h_2 行和 w_2 列。 使用这些印章和网格,他们将互相玩游戏。
首先,高桥按下他的黑色图章,用 h_1 行和 w_1 列黑色。
也就是说,他选择了一对整数 (i, j) 这样 1 \leq i \leq H - h_1 + 1 和 1 \leq j \leq W - w_1 + 1,并将每个方块涂成黑色 (r, c) 这样 i \leq r \leq i + h_1 - 1 和 j \leq c \leq j + w_1 - 1.
其次,青木按下他的白色图章,用 h_2 行和 w_2 列白色。
也就是说,他选择了一对整数 (i, j) 这样 1 \leq i \leq H - h_2 + 1 和 1 \leq j \leq W - w_2 + 1,并将每个方块涂成白色 (r, c) 这样 i \leq r \leq i + h_2 - 1 和 j \leq c \leq j + w_2 - 1.
如果其中一些方块已经被高桥涂成黑色,它们也会变成白色。
游戏的得分定义为高桥和青木如上所述按下印章后涂成黑色的方块上写的整数的总和。 高桥遵循最优策略,使分数尽可能大,而青木则遵循最优策略,使分数尽可能小。 比赛的比分会是多少?
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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
3 4 2 3 3 1 3 1 4 1 5 9 2 6 5 3 5 8
示例输出 1
19
比赛将进行如下。
- 最初,所有方块都漆成白色。
- 首先,高桥按下他的 2 \times 3 黑色图章将以下六个方块涂成黑色: (2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4).
- 其次,青木按下他的 3 \times 1 白色图章将以下三个方块涂成白色: (1, 4), (2, 4), (3, 4).
- 最终,以下四个方块被涂成黑色: (2, 2), (2, 3), (3, 2), (3, 3),分数为 9 + 2 + 3 + 5 = 19.
示例输入 2
3 4 2 3 3 4 3 1 4 1 5 9 2 6 5 3 5 8
示例输出 2
0
青木按下印章后,所有方块都会变成白色,得分为 0.
示例输入 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