Lịch trình bảo trì máy móc

Buổi 48 — Min-Cost Max Flow
Points
60
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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.
Draft saved