Moovie Mooving (Gold)

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ bộ phim và thời gian cần lấp đầy là $L$ phút. Mỗi bộ phim $i$ có thời lượng $D_{i}$ phút và $C_{i}$ suất chiếu, mỗi suất bắt đầu vào một thời điểm cho trước. Bessie bắt đầu ở thời điểm $0$ và muốn theo dõi phim liên tục đến thời điểm $L$ .

Quy tắc: khi Bessie đang ở thời điểm $t$ , cô có thể "nhảy vào" bộ phim $i$ đang chiếu nếu có suất chiếu $s \leq t$ với $s + D_{i} > t$ (tức là bộ phim đang phát và chưa kết thúc). Sau đó cô xem đến hết suất đó, kết thúc ở thời điểm $s + D_{i}$ . Mỗi bộ phim chỉ được dùng một lần.

Tìm số bộ phim tối thiểu để Bessie xem từ thời điểm $0$ đến ít nhất thời điểm $L$ , hoặc in $- 1$ nếu không thể.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $L$ .

$N$ dòng tiếp theo, mỗi dòng mô tả một bộ phim: $D_{i}$ (thời lượng), $C_{i}$ (số suất chiếu), rồi $C_{i}$ thời điểm bắt đầu tăng dần.

Dữ liệu ra

Số nguyên là số bộ phim tối thiểu, hoặc $- 1$ .

Ràng buộc

$1 \leq N \leq 20$
$1 \leq L \leq 10^{8}$
$1 \leq D_{i} \leq L$
$1 \leq C_{i} \leq 1000$
Các thời điểm chiếu nằm trong đoạn $[0, L]$

Ví dụ

Input	Output	Giải thích
4 100 50 3 15 30 55 40 2 0 65 30 2 20 90 20 1 0	3	Phim 4 (chiếu lúc 0, kết thúc 20) → Phim 1 (chiếu lúc 15, Bessie nhảy vào lúc 20 không được — phải nhảy vào khi phim đang chạy: phim 1 chiếu lúc 15→65, Bessie ở t=20 nhảy vào xem đến 65) → Phim 2 (chiếu lúc 65→105, xem đến 100≥L). Tổng 3 phim.
7 300 36 30 18 24 31 38 53 65 81 90 97 102 106 116 126 134 146 154 172 173 182 193 202 208 214 230 245 250 252 264 268 286 50 30 0 15 23 42 46 64 75 95 111 117 119 120 128 133 138 158 163 174 175 194 214 222 231 243 253 261 265 278 296 299 64 24 9 23 37 53 64 85 93 100 109 123 135 152 171 181 201 221 222 234 249 263 275 279 287 298 77 29 0 15 17 20 22 25 43 63 69 70 81 100 119 140 142 148 165 179 190 193 201 217 224 237 254 265 269 277 298 33 28 0 7 16 34 52 73 81 95 112 114 115 132 150 160 164 173 174 190 201 207 228 230 238 253 256 259 277 297 78 29 0 11 15 27 46 47 48 52 61 69 89 90 107 123 140 141 161 170 174 189 198 214 230 232 243 244 265 271 287 62 27 18 38 39 53 61 81 98 118 131 138 145 148 163 166 177 178 191 195 207 216 231 243 253 260 266 267 284	5	Cần 5 bộ phim.

Bình luận

Không có bình luận tại thời điểm này.