페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2618

[고등부] 2025 KOI 2차대회 대비 모의고사 (1회차)

쓰레기 수거
서브태스크
3초 1024MB

문제

공원에 N개의 쓰레기 봉투가 흩어져 있다.

쓰레기 봉투는 1번부터 N번까지 번호가 매겨져 있다.

i번째 쓰레기 봉투는 좌표 (x_i, y_i)에 위치하고 있으며, 무게는 w_i이다.

정올이는 최첨단 쓰레기 수집기를 이용하여 너비가 W이고 높이가 H인 직사각형 영역 내에 있는 모든 쓰레기 봉투를 수거할 수 있다.

직사각형 영역을 최적으로 배치했을 때, 수거할 수 있는 쓰레기 봉투들의 최대 무게 합을 구하라.

같은 좌표 위에 여러 쓰레기 봉투가 있을 수 있음에 유의하라.

[제약 조건]

  • 1 \le N \le 10^5

  • 1 \le W,H \le 10^9

  • 모든 i (1 \le i \le N)에 대해, 0 \le x_i,y_i \lt 10^9

  • 모든 i (1 \le i \le N)에 대해, 1 \le w_i \le 10^9


입력

첫 줄에 세 정수 N, W, H가 공백을 사이에 두고 주어진다.

다음 N개의 줄에 걸쳐 x_i, y_i, w_i가 공백을 사이에 두고 주어진다.


출력

수거할 수 있는 쓰레기 봉투들의 최대 무게 합을 출력한다.


부분문제

번호 점수 조건
#110점

N \le 400

#212점

모든 i (1 \le i \le N)에 대해, W,H,x_i,y_i \le 2000

#315점

N \le 2000

#422점

H = 10^9

#523점

모든 i (1 \le i \le N)에 대해, W,H,x_i,y_i \le 10^5

#618점

추가 제약 조건 없음


예제 

5 3 2
3 1 10
2 1 5
1 0 5
0 2 10
1 3 5
20

(3,1), (2,1), (1,0)에 있는 쓰레기 봉투를 수거하면 10+5+5=20으로, 최적의 방법이다.

로그인해야 코드를 작성할 수 있어요.