Cây khế
View as PDF
Submit solution
Points:
500.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Cây khế nhà Khánh rất sai quả nên có một con chim to to đến ăn. Ăn xong, chim chở Khánh ra đảo để trả công bằng các viên đá quý. Đảo có N viên đá quý, mỗi viên đá quý có trọng lượng, giá trị và số lượng riêng. Cậu ấy muốn chuyển hết tất cả N viên đá quý của mình về nhà. Nhưng khổ nỗi những viên đá quý này lại có trọng lượng và kích thước khổng lồ. Khánh may gấp rút một cái túi ba trăm gang to đùng nhưng vẫn chưa chắc chứa hết đống đá quý này. Khổ quá đi! Lấy viên nào, bỏ viên nào bây giờ! Các bạn hãy giúp cậu ấy tìm ra một cách chọn đá quý để thu được giá trị lớn nhất và đương nhiên cái túi không bị rách.
Yêu cầu: Hãy chọn các viên đá sao cho tổng giá trị lớn nhất mà túi không bị rách?
Dữ liệu vào:
- Dòng 1: Hai số nguyên: Số viên đá quý N (1 ≤ 𝑁 ≤ 100) và sức chứa của cái túi M (1 ≤ 𝑀 ≤ 10000).
- N dòng tiếp theo: Mỗi dòng ghi 3 số nguyên: Khối lượng ~W_i~, giá trị ~V_i~ và số lượng ~A_i~ của viên đá thứ i (1≤ ~𝑊_𝑖~, ~𝑉_𝑖~, ~𝐴_𝑖~ ≤ 1000). Output:
- Một số nguyên duy nhất là giá trị lớn nhất tìm được.
Example
INPUT
3 4
1 4 2
2 7 2
3 6 1
OUTPUT
15
Comments
ủa? qhd kiểu giống bài cái túi mà vẫn ac ảo z
test xam cu lam trau ma van AC
có hiện tượng copy code :<
iloveamelia