| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 2048 MB | 17 | 9 | 7 | 46.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 | 10 | $N \le 400$. |
| 2 | 12 | $W, H, x_i, y_i \le 2000$ for all $i : 1 \le i \le N$. |
| 3 | 15 | $N \le 2000$. |
| 4 | 22 | $H = 10^9$. |
| 5 | 23 | $W, H, x_i, y_i \le 10^5$ for all $i : 1 \le i \le N$. |
| 6 | 18 | No additional constraints. |
5 3 2 3 1 10 2 1 5 1 0 5 0 2 10 1 3 5
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번