Lịch trình bảo trì máy móc
Points
60
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Có $N$ công việc cần thực hiện và $K$ máy giống hệt nhau. Công việc thứ $i$ bắt đầu tại thời điểm $s_i$, kết thúc tại thời điểm $e_i$ ($s_i < e_i$), và mang lại lợi nhuận $r_i$ nếu được hoàn thành.
Mỗi máy chỉ có thể làm tối đa 1 công việc tại một thời điểm, và có thể chuyển sang công việc $j$ ngay sau công việc $i$ nếu $e_i \le s_j$. Một công việc chỉ cần được thực hiện bởi đúng 1 máy (có thể bỏ qua một số 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 hai số nguyên $N, K$ ($1 \le N \le 150, 1 \le K \le 50$).
- $N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $s_i, e_i, r_i$ ($1 \le s_i < e_i \le 10^9, 1 \le r_i \le 10^6$).
Dữ liệu ra
- In ra tổng lợi nhuận lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 1 1 3 5 2 5 8 3 6 4 5 7 6 |
14 |
Giới hạn
- $1 \le N \le 150, 1 \le K \le 50$.
- Thời gian chạy: 3 giây.
Community Discussion