¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#8575
Subtarea

쓰레기 수거 3s 1024MB

Problemas

공원에 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


Entrada

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

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


Salida

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


Subtarea

# Puntaje Condición
#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

추가 제약 조건 없음


Ejemplo 

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으로, 최적의 방법이다.



Fuente

NOI 2025
Debes iniciar sesión para escribir código.