XEPGACH - Xếp gạch
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 3.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: a516 Thánh Ngốc

Cho N viên gạch hình chữ nhật có kích thước là a_i, b_i, h_i lần lượt là chiều dài, chiều rộng, chiều cao của viên gạch thứ i.
Tìm cách xếp các khối gạch thành 1 tháp. Sao cho các cạnh của các viên gạch song song với nhau và hình chữ nhật ở phía trên nằm trọn trong hình chữ nhật phía dưới.
Viên gạch thứ j có thể nằm trên viên gạch thứ i khi ai>aj và bi>bj
Tìm số viên gạch tối đa có thể chồng lên nhau và chiều cao tối đa của tháp.
Dữ liệu:

Input:

-Dòng đầu tiên chứa một số nguyên dương N (n<=5000) là số viên gạch
-N dòng tiếp theo mỗi dòng chứa 3 số ai, bi, hi.

Output:

-gồm 2 số x y lần lượt là số viên gạch tối đa trong 1 tháp và chiều cao tối đa của tháp dựng tự các viên gạch

Ví dụ

  • input
    10
    9 7 1
    10 4 8
    8 5 5
    7 4 10
    7 4 8
    5 1 9
    2 1 10
    3 2 4
    5 4 5
    10 3 2
    output
    5 30
Back to Top