Lập lịch đơn hàng hạn chót
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Một xưởng gia công nhận được $N$ đơn hàng. Đơn hàng thứ $i$ có hạn chót hoàn thành là $d_i$ và mang lại lợi nhuận là $p_i$. Mỗi đơn hàng mất đúng $1$ đơn vị thời gian để thực hiện (bắt đầu từ thời điểm $0$). Tại mỗi thời điểm chỉ có thể thực hiện tối đa một đơn hàng, và đơn hàng phải hoàn thành không quá hạn chót $d_i$. Hãy tính tổng lợi nhuận lớn nhất có thể thu được.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $d_i$ và $p_i$.
Dữ liệu ra
- In ra một số nguyên duy nhất là tổng lợi nhuận lớn nhất.
Ví dụ
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 4 2 100 1 19 2 27 1 25 |
127 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le d_i \le 10^9$
- $1 \le p_i \le 10^9$
Community Discussion