시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 2048 MB179746.667%

문제

The North Sea is littered with $N$ pieces of garbage, numbered $1 \dots N$. The $i$'th piece is at position $(x_i, y_i)$ and has a weight of $w_i$. As part of a cleanup effort, all garbage within a rectangular area will be collected. This area has a width of $W$ and a height of $H$, but its location has not yet been decided.

Determine the maximum total weight of garbage that will be collected if the cleanup area is positioned optimally.

입력

The first line contains the integers $N$, $W$ and $H$.

The $i$'th of the next $N$ lines contains the integers $x_i$, $y_i$ and $w_i$.

출력

Print an integer: the maximum total weight of garbage that can be collected.

제한

  • $1 \le N \le 10^5$.
  • $1 \le W, H \le 10^9$.
  • $0 \le x_i, y_i \le 10^9$ for all $i : 1 \le i \le N$.
  • $1 \le w_i \le 10^9$ for all $i : 1 \le i \le N$.

서브태스크

번호배점제한
110

$N \le 400$.

212

$W, H, x_i, y_i \le 2000$ for all $i : 1 \le i \le N$.

315

$N \le 2000$.

422

$H = 10^9$.

523

$W, H, x_i, y_i \le 10^5$ for all $i : 1 \le i \le N$.

618

No additional constraints.

예제 입력 1

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

예제 출력 1

20

The optimal area is the one covering the garbage at $(3,1)$, $(2,1)$ and $(1,0)$ with a total weight of $10 + 5 + 5 = 20$.

출처

Olympiad > Nordic Olympiad in Informatics > 2025 B번

  • 문제를 만든 사람: Sebastian Meineche Falk

채점 및 기타 정보

  • 예제는 채점하지 않는다.