1643 . 建築工程規劃
TopCoder
Tags
Description
你是一家建築公司的建築工程師，你被派來做一塊空地的建築策劃工作。
這是一塊矩形的空地，你必須在上面選一塊子矩形當作樓房的地基範圍，而為了增加收益，你老闆希望你能夠盡量讓這塊當作地基的子矩形面積越大越好。
但是基於安全上的考量，你不能讓地基覆蓋的區域的最大「土質硬度差」超過 L，意即在地基範圍內的「最大土質硬度」−「最小土質硬度」必須小於等於 L，
否則所建造的房子在突然搖晃時（如發生地震時）將會有倒塌的危險！
你在事前已經得知了這塊空地的土質硬度分布狀況。為了簡化問題，我們把這塊矩形的空地切格成 N×M 的等大正方形區塊，
並假設其中每一個正方型區塊中的土質硬度都是定值 Fij，而你只能選一個子矩形區塊並且所選的子矩形不得包含不完整的正方形區塊。
確立了這些條件後，請問你到底最大可以選取多大的範圍做為地基呢？
Figure 1. 即範例輸入的內容，答案為選標記灰底的子矩形，A = 3×2 = 6。
Input Format
本題輸入的測試檔只有單筆測試資料，第一行有三個整數 N、M、L。
接下來有 N 行，每一行都有 M 個非負整數代表土質硬度 Fij。
對於所有測試資料，保證1 ≤ N, M ≤ 1000，0 ≤ L ≤ 20，0 ≤ Fij ≤ 109。
Output Format
一個整數 A 代表至多可以在符合安全的條件之下選取多大矩形面積當作地基的範圍。
Sample Input 1
3 3 1
1 1 1
1 2 3
2 1 1
1 1 1
1 2 3
2 1 1
Sample Output 1
6
Hints
Problem Source
原TIOJ1643 / Skyly & Shik Contest II (Problem D)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 8 |
| 2 | 1 | 8 |
| 3 | 2 | 8 |
| 4 | 3 | 8 |
| 5 | 4 | 8 |
| 6 | 5 | 8 |
| 7 | 6 | 8 |
| 8 | 7 | 8 |
| 9 | 8 | 8 |
| 10 | 9 | 8 |
| 11 | 10 | 8 |
| 12 | 11 | 12 |