# PBCRECT

:::info
Cho một bảng hình chữ nhật kích thước $M \cdot N$ chỉ gồm các số $0$ và $1$. Cho phép thực hiện thao tác tráo đổi 2 cột bất kỳ của bảng nhiều lần, hãy tìm hình chữ nhật có diện tích lớn nhất chỉ gồm toàn các số 1 và số thao tác tráo đổi ít nhất cần thực hiện.
:::

## Tìm diện tích

Gọi $A_{i,j}$ là số nằm ở hàng $i$ và cột $j$ của bảng, gọi $R$ là hình chữ nhật tìm được, trước hết, chúng ta giả sử $R$ có đáy ở hàng thứ $i ~ (1 \le i \le M)$ và có bề rộng là $k ~ (1 \le k \le N)$.

Gọi $S=\{j_1,j_2,...,j_k\} ~ (1 \le j_x \le N)$ là tập chỉ số ban đầu của các cột hợp thành $R$ (nghĩa là ta tráo đổi cho các cột này đứng cạnh nhau để hợp thành hình $R$), và gọi $F_j$ là số $T$ lớn nhất sao cho $A_{i-T+1,~j}=A_{i-T+2,~j}= \dots =A_{i,~j}=1$ (tức là dãy số $1$ nằm dọc từ trên xuống dài nhất mà kết thúc ở $A_{i,j}$ nếu có), ta có một số nhận xét sau:
- Chiều cao của $R$ là $\min(F_{j_1},F_{j_2},...,F_{j_k})$, và vì vậy, diện tích của hình này là $k \cdot \min(F_{j_1},F_{j_2},...,F_{j_k})$.
- $F_{j_1},F_{j_2},...,F_{j_k}$ là các giá trị $F$ lớn nhất, bởi lẽ nếu có cột $j'$ không thuộc $S$ mà có $F$ lớn hơn hoặc bằng ít nhất một cột hiện nằm trong $S$ thì ta có thể thêm cột $j'$ vào $S$ và tăng diện tích của hình $R$ lên (vô lý).

Như vậy, để tìm $R$, ta có thể làm như sau:
- Với mỗi hàng $i ~ (1 \le i \le M)$, tính tất cả $N$ giá trị $F$ cho hàng đó. Có thể tính nhanh bằng phương pháp quy hoạch động.
- Sắp xếp các giá trị $F$ lại (chẳng hạn từ lớn đến nhỏ). Có 2 cách:
- Subtask 1: `std::sort`
- Subtask 2: Ta nhận thấy rằng, khi chuyển từ một hàng sang hàng tiếp theo thì một giá trị $F_j$ bất kỳ có hai xu hướng sau: tăng lên $1$ hoặc giảm còn $0$. Vì với các giá trị $F$ tăng lên $1$ thì thứ tự lớn nhỏ của chúng vẫn như cũ nên ta chỉ việc:
- Dựng một vector $V$ rỗng,
- Thêm vào $V$ các chỉ số $j$ có $F_j$ tăng lên $1$,
- Thêm vào $V$ các chỉ số $j$ có $F_j$ giảm còn $0$,
là ta đã có tập các $F$ từ lớn đến nhỏ cho hàng tiếp theo.
- Duyệt $k ~ (1 \le k \le N)$, cập nhật kết quả với hình chữ nhật được tạo thành từ $k$ cột có $F$ lớn nhất.

## Truy vết

Ta nhận thấy rằng, sau khi thực hiện tất cả các thao tác trao đổi, tập $S=\{j_1,j_2,\ldots,j_k\}$ sẽ co cụm về một khoảng $[L,L+k-1] ~ (1 \le L \le N-k+1)$. Vậy ta chỉ việc duyệt tất cả các $L$ rồi tính kết quả, chính là số các $j$ nằm ngoài khoảng $[L,L+k-1]$ (chứng minh xin để lại cho bạn đọc).

## Chú ý

:::warning
Lời giải này chỉ giải quyết trường hợp tập $S$ tìm được là duy nhất (nghĩa là không tồn tại hình chữ nhật nào có diện tích bằng hình $R$).
:::

## Code mẫu

:::success
:::spoiler C++

:::