Problem : 233 - Oil

Problem Statistics

Solved Member: 14　　Submission: 50　　User Tried: 15

Statement:

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

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

為了避免出現壟斷，政府規定每一個承包商只能承包一個由 K×K 塊相連的土地構成的正方形區域。AoE 石油聯合公司由三個承包商組成，他們想選擇三塊互不相交的 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, AoE 公司可以承包的區域的石油儲量總和為 100,
如果 K = 3, AoE 公司可以承包的區域的石油儲量總和為 208。
AoE 公司雇傭你來寫一個程式，幫助計算出他們可以承包的區域的石油儲量之和的最大值。

Input:Output:

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

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

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

Sample Input:Sample Output:

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

208

Source:

APIO 2009

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	3000ms	131072kb
1	3000ms	131072kb	10
2	3000ms	131072kb	10
3	3000ms	131072kb	10
4	3000ms	131072kb	5
5	3000ms	131072kb	5
6	3000ms	131072kb	5
7	3000ms	131072kb	5
8	3000ms	131072kb	5
9	3000ms	131072kb	5
10	3000ms	131072kb	5
11	3000ms	131072kb	5
12	3000ms	131072kb	5
13	3000ms	131072kb	5
14	3000ms	131072kb	5
15	3000ms	131072kb	5
16	3000ms	131072kb	5
17	3000ms	131072kb	5