Xếp gạch 2
Xem PDF
Điểm:
400 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
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 \(a_i>a_j\) và \(b_i>b_j\)
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.
Input
- Dòng đầu tiên chứa một số nguyên dương \(N\) (\(N\le 2 \times 10^5\)) là số viên gạch
- \(N\) dòng tiếp theo mỗi dòng chứa 3 số \(a_i, b_i, h_i\). (\(a_i,b_i,h_i \le 10^9\))
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
Scoring
- Subtask \(1\) (\(40\%\) số điểm): \(n \le 5.10^3\).
- Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.
Example
Test 1
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 2Output
5 30
Bình luận
bị 20/50 là lỗi gì vậy ạ , giúp e với
Mình đã cập nhật test , xin lỗi các bạn rất nhiều :"< ❤️
😃 ?
ỏ :V
tui nhầm pair ,
đáng lẽ pair <long long,int> mà tui ghi pair<int,long long> @@
nghi vấn test sai, giới hạn 1e9 mà ông sinh test kết quả loại 2 lại để int thì sai r, tui sài long long sai phải chuyển sang int AC nè :))