QOJ.ac

QOJ

Time Limit: 15 s Memory Limit: 2048 MB Total points: 100

#8860. 海盗宝箱

Statistics

海盗迪克终于厌倦了在公海上的战斗、掠夺、偷窃以及让许多人生活在痛苦之中。于是他决定退休,并找到了一个完美的岛屿来度过余生,前提是他不会花光所有的钱。他现在有很多金币,他想把它们存放在一个箱子里(毕竟他是个海盗)。迪克可以建造一个矩形箱子,其顶部的尺寸不超过指定的上限,高度为任意整数。现在他需要一个地方来隐藏这个箱子。在探索岛屿时,他找到了一个完美的解决方案。

迪克将通过把箱子沉入一个浑浊的池塘来隐藏它。池塘有一个矩形的表面,它完全填满了一个有着高耸垂直岩壁的山谷底部。迪克勘测了池塘,并知道了放置在池塘表面的笛卡尔坐标网格系统中每个方格的深度。当迪克沉下箱子时,它会尽可能地沉下去,直到触及底部。箱子的顶部将保持与池塘表面平行,并且箱子将与网格方格对齐。被沉入的箱子排出的水会抬高池塘表面的水位(即使箱子周围没有空间让排出的水上升,这种情况也会发生)。山谷的岩壁足够高,水永远不会溅出山谷。当然,由于箱子必须是不可见的,它的顶部必须严格低于池塘的表面。你的任务是找到海盗迪克能以这种方式隐藏的箱子的最大体积。

在图 I.1 中,最左侧的图像显示了一个池塘,中间的图像显示了一个体积为 3 的箱子的可能放置方式,最右侧的图像显示了一个体积为 4 的箱子的放置方式,这是可能的最大体积。注意,如果第二个箱子再高一个单位,它的顶部就会可见,因为它将正好与水面齐平。

图 I.1:样例输入 1 的说明。

输入格式

输入包含一组测试用例。测试用例的第一行包含四个整数 $a, b, m$ 和 $n$ ($1 \le a, b, m, n \le 500$)。池塘表面的尺寸为 $m \times n$,箱子顶部(和底部)的最大尺寸为 $a \times b$。此外,$a$ 和 $b$ 足够小,以至于不可能用一个顶部尺寸为 $a \times b$ 的箱子覆盖整个池塘。接下来的 $m$ 行中,每一行包含 $n$ 个整数 $d_{i,j}$,表示池塘在网格方格 $(i, j)$ 处的深度,其中对于每个 $1 \le i \le m$ 和 $1 \le j \le n$,都有 $0 \le d_{i,j} \le 10^9$。

输出格式

输出一个矩形箱子的最大体积,该箱子的尺寸为整数(顶部的一维尺寸不超过 $a$,另一维尺寸不超过 $b$),且可以完全沉没在池塘表面之下。如果池塘中无法隐藏任何箱子,则输出 0。

样例

样例输入 1

3 1 2 3
2 1 1
2 2 1

样例输出 1

4

样例输入 2

4 1 1 5
2 0 2 2 2

样例输出 2

12

样例输入 3

2 3 3 5
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2

样例输出 3

18

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.