TNHWIFI - Cafe WIFI
Giới hạn- Thời gian: 0.461s
- 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.
Trong một thành phố, người ta thấy có M con đường song song theo hướng đông - tây và N con đường song song theo hướng bắc - nam, khoảng cách giữa hai con đường song song với nhau là 1. Tại mỗi giao lộ đều có một quán cafe. K quán cafe trong số này là cafe Wifi, wifi của mỗi quán không giống nhau, wifi của quán cafe thứ i cho phép người dùng có thể truy cập trong phạm vi bán kính R i với tốc độ đường truyền là B i . Bởi vậy người ngồi tại một quán cafe không có wifi vẫn có thể truy cập wifi của quán cafe khác nếu cách quán cafe đó không quá R i .
Giả sử laptop của bạn được trang bị một thiết bị đặt biệt có khả năng kết hợp tốc độ đường truyền của các quán cafe wifi mà chúng phủ sống đến địa điểm của bạn hiện tại, để nhận được đường tuyền có tốc độ bằng tổng tốc độ của các đường truyền wifi của các quán cafe đó.
Hãy xác định tốc độ đường truyền tối đa mà khi ngồi tại một quán cafe nào đó bạn có thể nhận được và đếm số lượng các quán cafe như thế.
Input
- Dòng đầu ghi số nguyên M (1<=M<=30000), là số con đường theo hướng đông - tây.
- Dòng thứ hai ghi số nguyên N (1<=N<=1000), là số con đường theo hướng bắc - nam.
- Dòng thứ ba ghi số nguyên K (1<=K<=1000), là số quán cafe wifi.
- K dòng tiếp theo mỗi dòng chứa thông tin về các quán cafe wifi gồm 4 số nguyên: x, y, R, B. Với x,y lần lượt là số thứ tự của con đường theo hướng bắc - nam, đông - tây của quán cafe wifi, R, B lần lượt là bán kính phủ sống và tốc độ của quán cafe wifi đó. (1<=x<=N, 1<=y<=M, 1<=R<=30000, 1<=B<=10000)
Output
- Dòng thứ nhất là tốc độ đường truyền tối đa mà bạn có thể nhận được.
- Dòng thứ hai là số lượng các quán cafe wifi mà tại đó bạn có thể nhận tốc độ đường truyền tối đa trên.
Example
Input: 3 5 3 1 3 2 5 3 1 2 7 5 1 1 5 Output: 12 5
- Người up: yenthanh132
- Nguồn bài: 2009 Canadian Computing Competition