Lập lịch công việc tối đa lợi nhuận

Buổi 25 — Disjoint Set Union Data-structures greedy
Points
32
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Có $N$ công việc, công việc thứ $i$ cần 1 đơn vị thời gian để hoàn thành, có hạn chót là $d_i$ (phải thực hiện trong một khe thời gian nguyên $t \in [1, d_i]$) và mang lại lợi nhuận $p_i$. Mỗi khe thời gian chỉ thực hiện đượ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 tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $d_i, p_i$ ($1 \le d_i \le 10^5, 1 \le p_i \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là 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, d_i \le 10^5, 1 \le p_i \le 10^9$
Draft saved