Problem : 251 - Pyramid Base

Problem Statistics

Solved Member: 6　　Submission: 90　　User Tried: 7

Statement:

你要在自己財力許可的範圍內尋找一個盡可能大的地方，以便興建一個新的金字塔。為幫助你作出決定，為你提供了土地測繪圖。為方便起見，該地塊被劃分為由M乘N個小正方形構成的網格。金字塔的地基部份必須是正方形，而且各邊要與這些方格平行。

測繪圖中標出了P個有可能重疊的障礙物，這些障礙物是上述網格上的長方形，其各邊與方格平行。為了建造金字塔，任何塔基所佔方格中的障礙物必須被移走。移除障礙物i需要付出成本Ci。當移除一個障礙物時，需要將障礙物整個地移除，即不能只移除障礙物的一部份。同時，移除一個障礙物對與其重疊的其他障礙物無任何影響。

Task:

任務已知測繪圖中M和N的大小，對P個障礙物的描述，移走每個障礙物的成本以及你的預算B。請寫一個程式，找出在移走障礙物總成本不超過B的前提下金字塔地基的最大邊長。

限制及評分程序用三組不相交的數據進行評測。

Input:Output:

你的程序需要從標準輸入上讀入以下數據：

• 第一行包含兩個以單個空格分隔的整數，分別表示M及N。

• 第二行包含整數B，是你可付出的最大成本（即你的預算）。

• 第三行包含整數P，是測繪圖中標出的障礙物數量。

• 以下P行的每一行表示一個障礙物。其中第i行表示第i個障礙物。每一行包含5個以單個空格分隔的整數X_i1, Y_i1, X_i2, Y_i2和Ci，分別表示障礙物左下角小正方形的座標，右上角小正方形的座標，以及移除這個障礙物的成本。網格左下角的小正方形座標為（1, 1）而其右上角小正方形為（M, N）。

你的程式必須輸出一個整數至標準輸出，此整數為金字塔地基的最大可能邊長。如果無法建造金字塔時，你的程式應輸出數字0。

Sample Input:Sample Output:

Sample #1 :
6 9
42
5
4 1 6 3 12
3 6 5 6 9
1 3 3 8 24
3 8 6 9 21
5 1 6 2 20

Sample #2 :
13 5
0
8
8 4 10 4 1
4 3 4 4 1
10 2 12 2 2
8 2 8 4 3
2 4 6 4 5
10 3 10 4 8
12 3 12 4 13
2 2 4 2 21

Sample #1:
4

Sample #2:
3

HINT:

以下限制適用於所有的測試數據：
1 <= M, N <= 1,000,000 網格的尺寸。
1 <= Ci <= 7,000 移除障礙物i的成本。
對每個障礙物i均有1 <= X_i1 <= X_i2 <= M 並且1 <= Y_i1 <= Y_i2<= N。

第一組測試總分值35分：
B = 0 可以付出的最大成本。 (不可移除任何障礙物)
1<= P <= 1,000 網格中障礙物的數目。

第二組測試總分值35分：
0 < B <= 2,000,000,000 你的預算。
1<= P <= 30,000 網格中障礙物的數目。

第三組測試值30分：
B = 0 你的預算。 (不可以移除任何障礙物)
1<= P <= 400,000 網格中障礙物的數目。

Source:

IOI 2008

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	2000ms	262144kb
0-2	2000ms	262144kb
1	5000ms	262144kb	5
2	5000ms	262144kb	5
3	5000ms	262144kb	5
4	5000ms	262144kb	5
5	5000ms	262144kb	5
6-1	5000ms	262144kb	5
6-2	5000ms	262144kb
7-1	5000ms	262144kb	5
7-2	5000ms	262144kb
8-1	5000ms	262144kb	7
8-2	5000ms	262144kb
8-3	5000ms	262144kb
9-1	5000ms	262144kb	7
9-2	5000ms	262144kb
9-3	5000ms	262144kb
10-1	5000ms	262144kb	7
10-2	5000ms	262144kb
10-3	5000ms	262144kb
10-4	5000ms	262144kb
11-1	8000ms	262144kb	7
11-2	8000ms	262144kb
11-3	8000ms	262144kb
12-1	8000ms	262144kb	7
12-2	8000ms	262144kb
12-3	8000ms	262144kb
12-4	8000ms	262144kb
12-5	8000ms	262144kb
12-6	8000ms	262144kb
13-1	8000ms	262144kb	10
13-2	8000ms	262144kb
14-1	8000ms	262144kb	10
14-2	8000ms	262144kb
14-3	8000ms	262144kb
15-1	8000ms	262144kb	10
15-2	8000ms	262144kb
15-3	8000ms	262144kb
15-4	8000ms	262144kb
15-5	8000ms	262144kb