TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

87.0% (20/23)

Submission's AC Ratio

35.0% (49/140)

Description

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 Format

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

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

Output Format

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

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

Problem Source

原TIOJ1742 / APIO '09

Subtasks

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 20
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
13 1000 131072 262144
14 1000 131072 262144
15 1000 131072 262144
16 1000 131072 262144