IOI 2008 day2 2- 피라미드 부지(Pyramid Base) > 문제은행 : 정보올림피아드&알고리즘




2673 : 피라미드 부지(Pyramid Base)

제한시간
5000 ms   
메모리제한
256 MB   
해결횟수
1 회   
시도횟수
2 회   

문제

당신은 피라미드를 새로 짓기에 적합한 가장 넓은 부지를 찾아 달라는 요청을 받았다. 

 

작업 수행을 위해 먼저 땅 전체를 M×N 크기의 정사각형 격자로 나누어 측량해 두었다.

피라미드를 짓는 영역은 이 격자에 평행한 정사각형 형태여야 한다.

 

조사한 바에 따르면 이 땅에는 P개의 장애물이 존재하는데, 이들은 격자에 평행한 직사각형 형태이며 일부 영역이 다른 장애물과 겹칠 수도 있다. 

 

피라미드를 지으려면 피라미드가 차지하는 모든 칸에 장애물이 하나도 없어야 한다. i째 장애물을 제거하는 데 드는 비용은 Ci로 표현된다.

한 장애물은 이 비용을 모두 들여서 완전히 제거하는 것만 가능하며 장애물의 일부 영역만을 부분적으로 제거할 수는 없다. 또한 한 장애물을 제거하더라도 그 장애물과 겹치는 영역이 존재하는 다른 장애물은 영향을 받지 않는다.

땅의 크기인 M과 N, P개의 장애물들의 위치와 이들 각각의 제거 비용, 내게 있는 자금 B를 입력 받아서 이 땅에서 이 자금 한도로 만들 수 있는 피라미드의 가장 큰 크기를 구하는 프로그램을 작성하시오.

 


입력형식

첫째 줄에는 M과 N의 값이 공백을 사이에 두고 들어있다. (1≤M, N≤1,000,000)

둘째 줄에는 장애물 제거를 위해 쓸 수 있는 자금 B가 들어있다. 그리고 셋째 줄에는 이 땅에 존재하는 장애물의 개수 P가 들어있다.

다음 P개의 줄에는 각 장애물에 대한 정보가 들어있다. Xi1, Yi1, Xi2, Yi2, Ci가 차례대로 공백으로 구분되어 있는데, 각각 장애물을 구성하는 직사각형의 좌측 하단 좌표와 우측 상단 좌표이며 끝으로 이 장애물의 제거 비용이 있다. 최좌측 최하단 좌표는 (1, 1)이며 최우측 최상단 좌표는 (M, N)이다. (1≤Xi1 ≤ Xi2≤M, 1≤Yi1 ≤ Yi2≤N이며 1≤Ci≤7,000)

테스트 케이스 중 전체의 35점에 해당하는 첫 그룹은 B=0이며, 1≤P≤1,000이다. 즉, 장애물의 개수는 1000개 이내이며 자금이 전혀 없기 때문에 장애물을 제거하는 경우는 고려할 필요가 없다는 뜻이다.
테스트 케이스 중 또 다른 35점에 해당하는 둘째 그룹은 0<B≤2,000,000,000이며 1≤P≤30,000이다.
테스트 케이스 중 나머지 30점에 해당하는 마지막 그룹은 다시 B=0이며 1≤P≤400,000이다.


출력형식

이 환경에서 지을 수 있는 피라미드의 최대 크기를 나타내는 정수 하나를 출력한다.
피라미드를 전혀 지을 수 없다면 0을 출력한다.


입력 예

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

출력 예

4

입력 예

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

출력 예

3

Hint!

[입력예 1 설명]

피라미드 부지로 가능한 곳은 두 곳이며, 두 곳 모두 한 변의 길이는 4이다.


 

 

[입력에 2 설명]

피라미드 부지로 가능한 곳은 한 곳이며, 한 변의 길이는 3이다.​

 




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP