Lịch Trình Không Giao Nhau

Buổi 39 — DP + Data Structures Dynamic Programming
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Có $N$ dự án, dự án thứ $i$ diễn ra từ ngày $L_i$ đến ngày $R_i$ (tính cả hai đầu mút) và mang lại lợi nhuận $W_i$.

Bạn có thể chọn thực hiện một tập hợp các dự án sao cho không có hai dự án nào giao nhau về thời gian (tức là nếu chọn dự án $a$ và dự án $b$ với $R_a < R_b$ thì bắt buộc $R_a < L_b$). 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 dương $N$. $N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $L_i, R_i, W_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ụ
Input Output
4
1 3 5
2 5 6
4 6 5
1 6 8
10
3
1 5 10
5 10 10
6 10 10
20
Giới hạn
  • $1 \le N \le 2 \cdot 10^5$
  • $1 \le L_i \le R_i \le 10^9$
  • $1 \le W_i \le 10^9$
Draft saved