QOJ.ac

QOJ

Süre Sınırı: 15 s Bellek Sınırı: 2048 MB Toplam puan: 100

#8860. 海盜寶箱

İstatistikler

海盜 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.