TopCoder

User's AC Ratio

82.4% (14/17)

Submission's AC Ratio

26.4% (24/91)

Tags

Description

果茶政府決定將石油資源豐富的小藍省的土地拍賣給私人承包商以建立油井。被拍賣的整塊土地為一個矩形區域,被劃分為 M×N 個小塊。

果茶地質調查局有關於小藍土地石油儲量的估測資料。這些資料表示為 M×N 個正整數,即對每一小塊土地石油儲量的估計值。

為了避免出現壟斷,政府規定每一個承包商只能承包一個由 K×K 塊相連的土地構成的正方形區域。SAO石油聯合公司由三個承包商組成,他們想選擇三塊互不相交的 K×K 的區域使得總的收益最大。

例如,假設石油儲量的估計值如下:

1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9

如果 K = 2, SAO公司可以承包的區域的石油儲量總和為 100,
如果 K = 3, SAO公司可以承包的區域的石油儲量總和為 208。
SAO公司雇傭你來寫一個程式,幫助計算出他們可以承包的區域的石油儲量之和的最大值。

Input Format

輸入第一行包含三個整數 M, N, K,
其中 M 和 N 是矩形區域的行數和列數,K 是每一個承包商承包的正方形的大小(邊長的塊數)。
接下來 M 行,每行有 N個正整數表示這一行每一小塊土地的石油儲量的估計值。

資料保證 K≤M 且 K≤N 並且至少有三個 K×K 的互不相交的正方形區域。
所有的輸入資料, M, N≤ 1500。
每一小塊土地的石油儲量的估計值是整數且絕對值≤ 500。

Output Format

輸出只包含一個正整數,表示 SAO 公司可以承包的區域的石油儲量之和的最大值。

Sample Input

9 9 3
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9

Sample Output

208

Hints

因為一定要挖三個油田,但是三個油田都挖到負的,所以果茶賠光了所有的錢=w=

Problem Source

Subtasks

For Testdata: 0 ~ 12, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 262144
1 1000 131072 262144
2 1000 131072 262144
3 1000 131072 262144
4 1000 131072 262144
5 1000 131072 262144
6 1000 131072 262144
7 1000 131072 262144
8 1000 131072 262144
9 1000 131072 262144
10 1000 131072 262144
11 1000 131072 262144
12 1000 131072 262144