Nguồn: Free Contest

Sắp xếp các mảnh đất theo thứ tự ~B_i - C_i~ giảm dần. Khi đó, với hai mảnh đất ~i < j~, nếu ta xây dựng nhà hàng trên mảnh đất ~i~ và khu vui chơi trên mảnh đất ~j~, ta có thể thay vào đó xây dựng khu vui chơi tại ~i~ và nhà hàng tại ~j~ và lợi nhuận sẽ không giảm.

Nói cách khác, trong lời giải tối ưu, tồn tại một số nguyên ~K~ sao cho:

• Trong ~K~ mảnh đất đầu tiên, sẽ có ~Y~ khu vui chơi và ~K - Y~ trung tâm thương mại.
• Trong các mảnh đất còn lại, sẽ có ~Z~ nhà hàng và ~X + Y - K~ trung tâm thương mại.

Giả sử ~A_i = 0~ (nếu không, ta có thể biến đổi ~(A_i, B_i, C_i)~ thành ~(0, B_i - A_i, C_i - A_i)~ và cộng ~A_i~ vào đáp án). Khi đó, với một số nguyên ~K~ cố định, ta cần tính tổng của hai giá trị sau:

• Tổng của ~Y~ giá trị lớn nhất trong các giá trị ~B_1, B_2, ..., B_K~.
• Tổng của ~Z~ giá trị lớn nhất trong các giá trị ~C_{K+1}, C_{K+2}, ..., C_{X+Y+Z}~.

Việc tính toán các giá trị trên có thể được thực hiện bằng một hàng đợi ưu tiên.

Độ phức tạp: ~O((X+Y+Z).log(X+Y+Z))~