Bedao Grand Contest 17 - Bán vé tháng
Xem dạng PDF
Thành phố H vừa mới mở tuyến đường sắt đô thị (Metro) đầu tiên. Sau ~10^9+7~ năm thi công, người dân rất mong chờ được trải nghiệm loại hình giao thông mới mẻ này.
Là trưởng ban tài chính của công ty Metro mới thành lập, bạn cần đặt giá vé tháng sao cho doanh thu thu về là cao nhất. Thành phố H có ~N~ người, người thứ ~i~ có thu nhập hàng tháng là ~a_i~ vàng và ~b_i~ ngọc (~a_i \ge b_i~).
Bạn cần đặt giá vé tháng là ~x~ vàng / ~y~ ngọc, sao cho ~x \ge y~. Khi đó mỗi người dân sẽ quyết định mua hay không mua vé tháng như sau:
Nếu ~a_i \ge x~, người thứ ~i~ sẽ mua vé tháng với giá ~x~ vàng.
Nếu ~a_i < x~ và ~b_i \ge y~, người thứ ~i~ sẽ mua vé tháng với giá ~y~ ngọc.
Nếu ~a_i < x~ và ~b_i < y~, người thứ ~i~ sẽ không mua vé tháng.
Hãy tìm cách đặt giá vé tháng sao cho doanh thu (bằng tổng số vàng và số ngọc) hàng tháng thu về là cao nhất.
Input
Dòng đầu tiên gồm 1 số nguyên ~N~ (~1 \le N \le 150000~): số người dân ở thành phố H.
~N~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~a_i~ và ~b_i~ (~0 \le b_i \le a_i \le 10^9~) là thu nhập hàng tháng của người thứ i.
Output
In ra 1 số nguyên là doanh thu (bằng tổng số vàng và số ngọc) hàng tháng cao nhất có thể thu về.
Scoring
Subtasks
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~12~ | ~N, A_i, B_i \leq 100~ |
| 2 | ~14~ | ~N \leq 300~ |
| 2 | ~19~ | ~N \leq 3000~ |
| 2 | ~14~ | ~B_i = 0~ |
| 2 | ~19~ | ~A_i = B_i~ |
| 2 | ~11~ | ~N \leq 50000~ |
| 7 | ~11~ | Không có điều kiện gì thêm |
Sample Input 1
5
80 20
60 50
40 40
15 10
70 30
Sample Output 1
220
Sample Input 2
1
50 0
Sample Output 2
50
Bình luận
bai rat la hay
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.