Cho hình chữ nhật, hình thứ có một đỉnh là gốc tọa độ , đỉnh đối có tọa độ và chi phí để chọn nó là . Bạn có thể chọn một tập con bất kỳ của các hình chữ nhật này. Lợi nhuận bạn nhận được là diện tích hợp thành của các hình chữ nhật đó, trừ đi tổng chi phí của các hình chữ nhật đã chọn.
Yêu cầu: Hãy chọn một tập con các hình chữ nhật để đạt lợi nhuận lớn nhất.
Dữ liệu:
Dòng đầu tiên chứa số nguyên ().
dòng tiếp theo, mỗi dòng chứa ba số nguyên ().
Kết quả: In ra lợi nhuận lớn nhất có thể.
Ví dụ:
Dữ liệu:
3
4 4 8
1 5 0
5 2 10
Kết quả:
9
Dữ liệu:
4
6 2 4
1 6 2
2 4 3
5 3 8
Kết quả:
10
Giải thích"
Trong ví dụ đầu, ta chọn hình chữ nhật thứ nhất và thứ hai. Diện tích hợp của chúng là . Tổng chi phí là . Giá trị cuối cùng là .
Trong ví dụ thứ hai, ta chọn hình chữ nhật thứ nhất và thứ hai. Diện tích hợp thành của hai HCN là , chi phí là , do đó lợi nhuận là .
