QOJ.ac

QOJ

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

#8860. 海盜寶箱

Statistics

海盜 Dick 終於受夠了在公海上戰鬥、劫掠、偷竊,以及讓許多人生活悲慘的日子。因此他決定退休,並找到了一座完美的島嶼,只要錢沒有花光,就能在那裡度過餘生。他現在有很多金幣,想把它們存放在一個箱子裡(畢竟他是海盜)。Dick 可以製造尺寸皆為整數的長方體箱子,頂面的大小不超過指定的最大尺寸,而高度可以是任意整數。現在他需要一個藏箱子的地方。在探索島嶼時,他找到了完美的辦法。

Dick 將把箱子沉入一個混濁的池塘中藏起來。池塘水面為長方形,完全填滿了一個四周有高聳垂直岩壁的山谷底部。Dick 勘測過池塘,知道在水面上建立的笛卡兒座標網格中,每個方格的水深。當 Dick 將箱子沉入水中時,箱子會盡可能下沉,直到碰到塘底。箱子的頂面將保持與水面平行,箱子與網格方格對齊。箱子浸沒後排開的水會使水面上升(即使箱子周圍沒有空間讓排開的水上升,也會如此)。山谷的岩壁足夠高,水永遠不會濺出山谷。當然,因為箱子必須看不見,它的頂面必須嚴格低於池塘水面。你的任務是找出海盜 Dick 能以此方法藏起來的最大箱子體積。

圖 I.1 中,最左邊的圖顯示一個池塘,中間的圖顯示體積為 3 的箱子的一種可行放法,最右邊的圖顯示體積為 4 的箱子的放法,這也是最大可能體積。注意,如果將第二個箱子加高一個單位,它的頂面就會因為恰好與水面等高而被看見。

problem_8860_6017db924e69d8a91320c93044628e5c.png

圖 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.