Xếp Hộp

View as PDF

Submit solution


Points: 300 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Authors:
Problem types

Hôm nay Roronoa Zoro, thợ săn quỷ mạnh nhất đang đến tiki shop để mua nhận luân kiếm cho trận chiến sống còn với chúa quỷ Muzan sắp tới. Khi Zoro tới thì chủ tiệm là algorit đang loay hoay xếp kiếm, algorit mãi chưa xếp xong kiếm nên đành nhờ Zoro giúp xếp hộ kiếm.

Trong tiệm ~N~ thanh kiếm có trọng lượng , độ dài , độ cao lần lượt là ~C_i , W_i , H_i~ , chiều rộng của mỗi thanh kiếm bằng với chiều rộng của tủ kiếm. Trọng lượng và độ dài của mỗi ngăn mà tủ kiếm có thể chứa là ~P~ và ~Q~ .

Bây giờ algorit muốn nhờ Zoro chia ~N~ hộp thành các đoạn liên tiếp để xếp vào ngăn. Biết độ cao của mỗi ngăn là độ cao của thanh kiếm cao nhất trong các hộp đã được xếp vào ngăn. Nếu Zoro giúp được thì algorit sẽ tặng cho anh ~1~ thanh kiếm Trung Quốc hàng xịn, hãy giúp anh ấy nhé !

  • Yêu cầu : Hãy tính chiều cao tối thiểu của tủ khi xếp các kiếm vào tủ 1 cách tối ưu .
  • Input :
    • Dòng đầu tiên gồm 3 số nguyên dương ~N , P , Q~ . ~(N \le 9999, (P,Q) \le 10^{12})~
    • N dòng tiếp theo gồm 3 số nguyên dương ~C_i , W_i , H_i~ . ~(C_i \le P,W_i \le Q,H_i \le 10^9)~
  • Output :
    • Gồm 1 số nguyên dương duy nhất là kết quả của bài toán .
  • Sample input :
    5 18 16
    5 7 3
    6 5 4
    2 1 9
    8 4 2
    3 2 3
  • Sample output :
    12
  • Giải thích : Chúng ta sẽ chia thanh 2 đoạn ~->~ ~(1,2,3)~ và ~(4,5)~
  • Giới hạn :
    • 40% số điểm tương ứng với : ~N \le 400 , P \le 10^3 , Q \le 10^3 , H_i \le 10^3 .~
    • 60% số điểm còn lại không có ràng buộc gì thêm .

Be the first to comment

Comments

There are no comments at the moment.