1742 . [APIO '09] Oil

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

73.0% (27/37)

Submission's AC Ratio

27.5% (63/229)

Tags

APIO 2009-APIO

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 1

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 1

208

Hints

Problem Source

原TIOJ1742 / APIO '09

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1
1 1000 131072 262144 2
2 1000 131072 262144 3
3 1000 131072 262144 4
4 1000 131072 262144 5
5 1000 131072 262144 6
6 1000 131072 262144 7
7 1000 131072 262144 8
8 1000 131072 262144 9
9 1000 131072 262144 10
10 1000 131072 262144 11
11 1000 131072 262144 12
12 1000 131072 262144 13
13 1000 131072 262144 14
14 1000 131072 262144 15
15 1000 131072 262144 16
16 1000 131072 262144 17
Submit
Back to Top