Lập lịch công việc có hạn chót
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề 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ó hạn chót là $d_i$ (phải hoàn thành không muộn hơn thời điểm $d_i$, tức là có thể thực hiện trong khoảng $[t-1, t]$ với $1 \le t \le d_i$) và mang lại lợi nhuận $p_i$. Tại mỗi đơn vị thời gian chỉ có thể làm tối đa một công việc. Hãy chọn và sắp xếp một tập các công việc để đạt tổng lợi nhuận lớn nhất.
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
Một số nguyên duy nhất là tổng lợi nhuận lớn nhất có thể.
Ví dụ
| Input | Output |
|---|---|
| 4\n4 20\n1 10\n1 40\n1 30 | 60 |
| 5\n2 100\n1 19\n2 27\n1 25\n3 15 | 142 |
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