Bedao Grand Contest 16 - Kim cương
View as PDF
Khoa là một kẻ cuồng với những viên đá quý, đặc biệt là kim cương. Hiện tại Khoa có một danh sách ~N~ mỏ kim cương được đặt ở đâu đó trên trục tọa độ. Khoa muốn khai thác nhiều nhất kim cương từ các mỏ đã biết trước. Phạm vi khai thác của Khoa cũng kì hoặc như cách anh ấy thích kim cương, gọi ~(u, v)~ là tâm điểm của phạm vi mà Khoa khai thác, thì Khoa sẽ khai thác được các ô ~(u - 1, v - 1)~, ~(u - 1, v)~, ~(u - 1, v + 1)~, ~(u, v - 2)~, ~(u, v - 1)~, ~(u, v)~ ~(u, v + 1)~, ~(u, v + 2)~, ~(u + 1, v - 1)~, ~(u + 1, v)~, ~(u + 1, v + 1)~, ~(u + 2, v)~.
Hình minh họa:
Vì toàn ngỗng trong bộ môn hình học giải tích, nên Khoa quyết định nhờ bạn giúp anh ấy thõa sức với đam mê kim cương của mình.
Input
Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^5~) – Số lượng mỏ kim cương.
~N~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~x, y, w~ (~1 \leq x, y, w \leq 10^9~) biểu diễn một mỏ kim cương trên trục tọa độ – ~x, y~ đại diện cho tọa độ của mỏ, ~w~ là số viên kim cương trong mỏ.
Output
Một dòng duy nhất là số lượng kim cương tối đa mà Khoa có thể khai thác được.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~50~ | ~1 \leq x, y \leq 10^3~ |
| 2 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
5
1 1 5
1 2 3
1 3 9
2 3 4
2 2 4
Sample Output 1
25
Notes
Chọn tâm điểm khai thác là ~(2, 2)~, Khoa sẽ khai thác được cả ~5~ mỏ kim cương, lấy được tổng cộng ~25~ kim cương.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.