Submit solution
Points:
1.00 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Có ~N~ công việc, công việc thứ ~i~ có thời hạn deadline ~d_i~ và số điểm ~p_i~. Để lấy được số điểm ~p_i~, bạn phải hoàn thành công việc thứ ~i~ ở thời điểm không trễ hơn deadline ~d_i~.
Hãy tìm cách lấy số điểm lớn nhất nếu thực hiện ~k~ công việc đầu tiên với mọi ~k~ từ ~1~ đến ~N~.
Chú ý: Coi thời điểm bắt đầu thực hiện các công việc là thời điểm ~0~ và thời gian hoàn thành mỗi công việc đều là ~1~ đơn vị thời gian.
Input
- Dòng đầu tiên chứa số ~N~ (~N \le 10^5~).
- ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ~2~ số nguyên là ~d_i~ và ~p_i~ cách nhau bởi một dấu cách. (~1 \le d_i, p_i \le 10^6~)
Output
- Ghi ra ~N~ dòng, dòng thứ ~i~ là số điểm lớn nhất có thể lấy được nếu thực hiện ~i~ công việc đầu tiên.
Sample Input
4
4 20
1 10
1 40
1 30
Sample Output
20
30
60
60
Subtask
- ~20\%~ số test có ~N \le 10~
- ~20\%~ số test tiếp theo có ~N \le 1000~
- ~60\%~ số test còn lại không có điều kiện gì thêm
Comments
Theo góp ý của bạn Giangcoder, bọn mình đã cập nhật thêm test 51 cho bài này.