시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 185 | 102 | 89 | 54.268% |
평면에 N(1 ≤ N ≤ 1,000)개의 점들이 있다. 각각의 점들은 정수 값으로 어떤 가중치 S(1 ≤ S ≤ 2,000,000)를 가지고 있다. 또 각각의 점들은 (r, c)의 좌표를 갖는데 이는 (행, 열) 순이다. 또한 1 ≤ r ≤ 2,000,000과 1 ≤ c ≤ 2,000,000가 성립한다.
이제 우리는 세로로 A(1 ≤ A ≤ 2,000,000), 가로로 B(1 ≤ B ≤ 2,000,000)만큼의 직사각형을 쳐서 이 중 몇 개의 점들을 이 사각형 안에 포함시키려고 한다. 이때, 사각형 안에 포함된 점들 중, “S의 최대-S의 최소”가 최대가 되도록 하려 한다.
예를 들어 다음과 같은 경우를 보자.
이는 예제 데이터와 같은 경우고, 회색 부분처럼 선택했을 때, 가중치 최대-가중치 최소가 7이 되고 이 경우가 이 값이 최대가 되는 경우이다.
첫째 줄에 세 정수 N, A, B가 주어진다. 다음 N개의 줄에는 각 점의 r(세로좌표), c(가로좌표), S(가중치)를 나타내는 세 정수가 주어진다. 두 점이 같은 위치를 공유하는 경우는 없다.
첫째 줄에 가중치 최대 - 가중치 최소가 최대가 될 경우의 이 값을 출력한다.
8 4 2 1 4 9 1 5 8 2 10 2 3 2 6 4 6 1 5 15 3 6 4 5 7 9 4
7
Olympiad > USA Computing Olympiad > 2000-2001 Season > USACO Spring 2001 Contest > Green 2번