Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
SMARTDOG - Tham ăn |
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í (xi,yi), cầm ci 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ộ ci cái bánh, ngược lại nó sẽ phải đứng nhìn Bờm ăn hết luôn ci 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 độ (xi,yi) và số bánh ci 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 xi,yi,ci.
Ràng buộc: N<=105, tất cả các số còn lại trong file dữ liệu đều là số nguyên dương <=103.
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.
Được gửi lên bởi: | VOJ Team |
Ngày: | 2011-08-05 |
Thời gian chạy: | 1s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED |
Nguồn bài: | VNOI Marathon 2011 - Problem Setter: Lê Minh Hoàng |
hide comments
|
|||||
2011-08-09 10:15:00 Noyethug
Last edit: 2011-11-13 12:21:00 |
|||||
2011-08-09 03:09:40 1212
Last edit: 2011-08-09 06:21:42 |