Xếp Cột Bò

Đ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$ con bò đứng trên mặt đất. Bạn có thể chọn một tập con bất kỳ các con bò để xếp chồng lên nhau thành một cột. Mỗi con bò có chiều cao $h_{i}$ , cân nặng $w_{i}$ , và sức chịu đựng $s_{i}$ — là tổng cân nặng tối đa mà con bò đó có thể chịu đựng ở phía trên.

Cột hợp lệ khi mọi con bò trong cột đều chịu được tổng cân nặng của tất cả các con bò phía trên nó.

Hệ số an toàn của một cột là lượng cân nặng tối đa có thể thêm vào đỉnh cột mà không làm vượt quá sức chịu đựng của bất kỳ con bò nào.

Cho biết chiều cao mục tiêu $H$ , hãy tìm hệ số an toàn lớn nhất có thể đạt được với một cột hợp lệ có tổng chiều cao $\geq H$ .

Dữ liệu vào

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

$N$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $h_{i}$ , $w_{i}$ , $s_{i}$ — chiều cao, cân nặng, và sức chịu đựng của con bò thứ $i$ .

Dữ liệu ra

Một số nguyên — hệ số an toàn lớn nhất, hoặc Mark is too tall nếu không thể tạo cột hợp lệ có tổng chiều cao $\geq H$ .

Ràng buộc

$2 \leq N \leq 20$
$1 \leq H \leq 10^{9}$
$1 \leq h_{i}, w_{i}, s_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 10 9 4 1 3 3 5 5 5 5 10 4 4	4	Dùng chỉ con bò 4 (h=10≥10). Không có con bò nào phía trên, hệ số an toàn = s₄ = 4.
2 10 5 4 3 8 2 6	2	Phải dùng cả hai (tổng h=13≥10). Xếp bò 2 dưới, bò 1 trên: cân nặng trên bò 2 = 4, slack = 6−4 = 2; cân nặng trên bò 1 = 0, slack = 3. Hệ số an toàn = min(2,3) = 2.
2 100 3 2 5 4 3 4	Mark is too tall	Tổng chiều cao tối đa = 7 < 100.

Bình luận

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