MBUS - Xe buýt
Giới hạn- Thời gian: 0.2s
- 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.
Trên mặt phẳng tọa độ cho N điểm là N trạm xe buýt, ở trạm thứ i có tọa độ (xi, yi) và có zi người đang chờ ở đó. Cần đi xe buýt từ (1, 1) đến (X, Y) sao cho đón được nhiều người nhất có thể, biết rằng xe buýt chỉ có thể đi lên trên hoặc sang phải.
Dữ liệu
- Dòng đầu ghi 3 số nguyên dương X, Y, N (X, Y < 1000000001, N < 100001)
- N dòng sau mỗi dòng ghi 3 số xi, yi, zi (xi <= X, yi <= Y, zi < 1000001).
Kết qủa
Ghi trên một dòng số duy nhất là số khách lớn nhất có thể đón được.
Ví dụ
Dữ liệu: 8 7 11 4 3 4 6 2 4 2 3 2 5 6 1 2 5 2 1 5 5 2 1 1 3 1 1 7 7 1 7 4 2 8 6 2
Kết qủa 11
- Người up: tranhaidangfpt
- Nguồn bài: POI 2005