Editorial for MATRIXA

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Nguồn: Free Contest

Subtask 1

Ta duyệt từng bộ cặp điểm $(x_1, y_1)$ ~(x_1, y_1)~, $(x_2, y_2)$ ~(x_2, y_2)~ là góc trái trên và phải dưới của hình chữ nhật đang xét. Sau đó duyệt tính tổng từng ô trên viền hình chữ nhật đang xét và cập nhật kết quả.

Độ phức tạp: $O(max(m, n)^5)$ ~O(max(m, n)^5)~

Subtask 2

Vẫn tư tưởng như subtask $1$ ~1~ nhưng ta lập thêm các mảng đếm (prefix sum). Cụ thể:

$Row_{i,j} = A_{i,1} + A_{i,2} + ... + A_{i,j}$
$Column_{i,j} = A_{1,j} + A_{2,j} + ... + A_{i,j}$

Khi đó từng bộ cặp điểm $(x_1, y_1)$ ~(x_1, y_1)~ và $(x_2, y_2)$ ~(x_2, y_2)~ là góc trái trên và phải dưới của hình chữ nhật đang xét thì tổng của viền hình chữ nhật được xác định theo công thức :

$S = Row_{x_1,y_2}-Row_{x_1,y_1-1}+Row_{x_2,y_2}-Row_{x_2,y_1-1}+Column_{x_2-1,y_1}-Column_{x_1,y_1}+Column_{x_2-1,y_2}-Column_{x_1,y_2}$

Độ phức tạp: $O(m^2.n^2)$ ~O(m^2.n^2)~

Subtask 3

Ta có thể biến đổi công thức tính $S$ ~S~ ở trên như sau: $S = (Row_{x_1,y_2}+Row_{x_2,y_2}-Column_{x_1,y_2}+Column_{x_2-1,y_2})-(Column_{x_1,y_1}+Row_{x_1,y_1-1}+Row_{x_2,y_1-1}-Column_{x_2-1,y_1})$

Như vậy nếu ta cố định $x_1, x_2$ ~x_1, x_2~ thì với mỗi $y_2$ ~y_2~ ta cần tìm $y_1$ ~y_1~ mà $0 \le y_1 < y_2$ ~0 \le y_1 < y_2~ sao cho $S$ ~S~ lớn nhất. Ta dễ dàng có thể làm được trong $O(n)$ ~O(n)~ với mỗi bộ $x_1, x_2$ ~x_1, x_2~ (có thể sử dụng prefix max).

Độ phức tạp: $O(m^2.n)$ ~O(m^2.n)~