Knapsack4
Xem dạng PDFNhân dịp chào mừng kỷ niệm ngày thành lập Quân đội Nhân dân Việt Nam, Liên đội đã lên kế hoạch tổ chức Hội thi kéo co giữa các lớp trong toàn trường. Theo quy định của Ban tổ chức, số lượng thành viên của mỗi đội thi là không hạn chế và tổng cân nặng của các thành viên tham gia mỗi đội không vượt quá K kilogam. Là lớp trưởng lớp 9A, Tý cũng rất háo hức để chuẩn bị cho đội thi của lớp mình nên đã tìm hiểu rất kỹ về Hội thi. Sau khi tham khảo kinh nghiệm từ các thầy cô, cậu biết được rằng đội nào có tổng chiều cao các thành viên lớn nhất thì thường là đội vô địch. Do đó, Tý cũng rất muốn chọn ra đội thi của lớp mình sao cho tổng chiều cao các thành viên trong đội là lớn nhất.
Lớp của Tý có N học sinh được đánh số từ 1 đến N. Cân nặng tương ứng của các thành viên là ~a_1, a_2, ..., a_N~ và chiều cao tương ứng của các thành viên là ~b_1, b_2, ..., b_N~.
Yêu cầu: Hãy lập trình giúp Tý chọn được các thành viên của đội sao cho tổng chiều cao của đội là lớn nhất mà vẫn đảm bảo quy định của Ban tổ chức.
Dữ liệu vào:
Cho trong tệp văn bản KNAPSACK4.INP có cấu trúc như sau:
- Dòng 1: Ghi 2 số nguyên dương N, K (~1 ≤ N ≤ 150, 1 ≤ K ≤ 10^9~).
- Dòng 2: Ghi N số nguyên dương ~a_1, a_2, ... a_N~. (~1 ≤ i ≤ N, 1 ≤ a_i ≤ 10^9~).
- Dòng 3: Ghi N số nguyên dương ~b_1, b_2, ... b_N~. (~1 ≤ i ≤ N, 1 ≤ b_i ≤ 10^3~). Các số trên cùng một dòng được ghi cách nhau một dấu cách.
Dữ liệu ra:
Ghi ra tệp văn bản KNAPSACK4.OUT theo cấu trúc như sau:
- Dòng 1: Ghi một số nguyên dương t duy nhất là tổng chiều cao lớn nhất có thể của đội thi.
Ví dụ:
Input
5 140
44 50 30 35 46
130 150 120 150 140
Output
440
Giới hạn:
- Có 70% số test tương ứng với 70% số điểm của câu có (~1 ≤ N ≤ 20, 10^5 ≤ K ≤ 10^9~)
- Có 30% số test tương ứng với 30% số điểm của câu có (~100 < N ≤ 150, 1 ≤ K ≤ 10^4~)
Bình luận
kết hợp 2 câu của phamducminh :)))))))
Test ni là test chính thức các em nhé
áp dụng quay lui + qhd nhé tui tạch rồi :((
giới hạn ra cũng sai, chán cái đề, nhìn vào n <= 100 thg nào liều ms làm quay lui để ăn test...
đề kiểu: bất ngờ chưa thằng già :))
test này test chính thức à mn
test keo co
ý t là test của tỉnh á chứ ko phải bài đó:))
Test của tỉnh là N<=20 hết á =))
=)) đề chi mà sai tùm lum tùm la ri
có giải không các người ae
cs giai skibidi dop dop yes yes
:///
:///
thua m 0,25:(
:DDD
hoàng e vẫn có giải đỏ
.