Lập lịch hội thảo có thời gian nghỉ
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ đồ vật, đồ vật thứ $i$ có trọng lượng $w_i$ và giá trị $v_i$. Bạn có một chiếc túi có sức chứa tối đa $W$. Mỗi đồ vật chỉ được chọn tối đa $1$ lần. Hãy tìm tổng giá trị lớn nhất có thể mang theo mà tổng trọng lượng không vượt quá $W$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, W$.lt; E_i$).
Sau khi tham dự xong một buổi hội thảo kết thúc ở thời điểm $E$, bạn cần ít nhất $K$ đơn vị thời gian nghỉ ngơi trước khi bắt đầu buổi tiếp theo (tức là buổi tiếp theo phải có $S_{next} \ge E + K$).
Hãy tìm số lượng buổi hội thảo nhiều nhất có thể tham dự.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, K$.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $S_i, E_i$.
Dữ liệu ra
In ra một số nguyên duy nhất là số buổi hội thảo nhiều nhất có thể tham dự.
Ví dụ
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i, v_i$.
Dữ liệu ra
In ra một số nguyên duy nhất là tổng giá trị lớn nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 2 1 3 4 6 5 8 9 11 |
2 |
Giới hạn
$1 \le N \le 2 \cdot 10^5$, $0 \le K \le 10^9$, $0 \le S_i < E_i \le 10^9$.
Community Discussion