Xếp lịch công việc lợi nhuận tối đa
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề bài
Có $N$ công việc, mỗi công việc mất đúng $1$ đơn vị thời gian để hoàn thành. Công việc thứ $i$ có thời hạn $D_i$ (phải hoàn thành tại hoặc trước thời điểm $D_i$, tính từ thời điểm $1$) và mang lại lợi nhuận $P_i$. Tại mỗi đơn vị thời gian chỉ làm được tối đa một công việc. Hãy tìm tổng lợi nhuận lớn nhất có thể đạt được.
Dữ liệu vào
Dòng đầu chứa số nguyên $N$. $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $D_i$ và $P_i$.
Dữ liệu ra
In ra tổng lợi nhuận lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 4 20 1 10 1 40 1 30 |
60 |
Giới hạn
- $1 \le N \le 10^5$.
- $1 \le D_i \le N$, $1 \le P_i \le 10^9$.
Community Discussion