SMARTDOG - Tham ăn
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Tiếp theo chiến lược “quy hoạch động”, Bờm huấn luyện cho chú chó của mình chiến lược “tham ăn” trong một sân chơi được biểu diễn bởi mặt phẳng trực chuẩn . Ban đầu chú chó xuất phát ở điểm (0,0) và nó phải đứng im cho tới khi được gọi. Trò chơi diễn ra trong N lượt, lượt thứ i của trò chơi diễn ra như sau:
Bờm di chuyển đến vị trí (x i ,y i ), cầm c i cái bánh và gọi chú chó. Chú chó có quyền đứng im hoặc di chuyển theo các phương song song theo trục tọa độ để đến chỗ Bờm nếu độ dài quãng đường di chuyển không vượt quá K . Nếu chú chó có thể đi được đến chỗ Bờm và quyết định di chuyển, nó sẽ được thưởng toàn bộ c i cái bánh, ngược lại nó sẽ phải đứng nhìn Bờm ăn hết luôn c i cái bánh đó. Hết lượt chơi này chú chó lại phải đứng im và trò chơi tiếp tục ở lượt i+1.
Yêu cầu: Cho biết trước các tọa độ (x i ,y i ) và số bánh c i tại các lượt chơi, hãy giúp chú chó tội nghiệp của Bờm kiếm được nhiều bánh nhất
Input
- Dòng 1 chứa hai số nguyên dương N , K .
- N dòng tiếp theo, dòng thứ chứa ba số nguyên dương x i ,y i ,c i .
Ràng buộc: N <=10 5 , tất cả các số còn lại trong file dữ liệu đều là số nguyên dương <=10 3 .
Output
- Gồm một số nguyên duy nhất là số bánh chú chó kiếm được trong trò chơi theo phương án của bạn.
Example
Input:8 4
1 2 2
1 5 9
4 3 3
6 4 4
7 7 8
8 2 5
5 1 6
3 2 7 Output:
27
Giải thích: đây là ví dụ với 8 lượt chơi và vị trí của Bờm tại 8 lượt chơi đó lần lượt là A, B, C, D, E, F, G, H. Trong phương án tối ưu chú chó chỉ phải bỏ 9 bánh tại điểm B và 8 bánh tại điểm E.
- Người up: voj
- Nguồn bài: VNOI Marathon 2011 - Problem Setter: Lê Minh Hoàng