# Chọn hình chữ nhật [RECT2]

## Tóm tắt bài toán
Cho một lưới kích thước $W \times H$ ô, mỗi ô có giá trị trong khoảng $[0, 100]$. Ta cần tìm một hình chữ nhật có nhiều nhất $N$ ô sao cho tổng giá trị trong hình chữ nhật là lớn nhất.

## Ý tưởng giải quyết bài toán
### 1. **Sử dụng mảng tổng tiền tố 2D để tính tổng nhanh**
Với một hình chữ nhật có góc trái trên tại $(a, b)$ và góc phải dưới tại $(c, d)$, tổng các phần tử trong hình chữ nhật có thể tính nhanh bằng công thức:
$$
\text{sum} = \text{prefix}[c][d] - \text{prefix}[a][d] - \text{prefix}[c][b] + \text{prefix}[a][b].
$$
Với độ phức tạp là $O(1)$.


### 2. **Subtask 1-3: Duyệt tất cả các hình chữ nhật có kích thước hợp lệ**
- Duyệt mọi cặp điểm theo hàng $(a, c)$ để xác định cạnh đứng của hình chữ nhật.
- Duyệt mọi cặp điểm theo cột $(b, d)$ để xác định cạnh ngang của hình chữ nhật.
- Kiểm tra số ô không vượt quá $N$ $((c-a) \cdot (d-b) \leq N)$, nếu hợp lệ thì cập nhật tổng lớn nhất.

Độ phức tạp $O(W^2 \times H^2)$, đủ để đạt **50% số điểm**.

### 3. **Subtask 4: Tối ưu hóa bằng cách xét chiều rộng cố định trước**
- Khi chọn một cạnh dọc cố định từ hàng $a$ đến $c$ với chiều cao là $h = c - a + 1$, do giá trị của các phần tử là không âm nên hình chữ nhật có thể mở rộng ra tối đa vì điều này không làm giảm tổng giá trị. Độ dài cạnh ngang của hình chữ nhật là $w$ phải thoả mãn $(1 \leq w$ và $w\times h \leq N$). Nghĩa là ta có thể trực tiếp xác định $w = \lfloor \frac{N}{h}\rfloor$ và tính được tổng của hình chữ nhật con này trong $O(1)$.
- Bây giờ, chỉ cần duyệt mọi hình chữ nhật với cạnh ngang độ dài $h$ để cập nhật giá trị lớn nhất. Chú ý rằng khi duyệt tới cuối hàng thì có thể chiều rộng sẽ nhở hơn $w$ nên trong trường hợp này cạnh ngang sẽ kéo dài tới cuối hàng.
- Độ phức tạp giảm xuống $O(H^2 \times W)$.

Ví dụ, với bảng


Duyệt đến chiều rộng $w=2$ từ hàng $a=4$ đến hàng $c=5$, nghĩa là ta chỉ quan tâm đến các hình chữ nhật con có chiều cao $2$ trong hai hàng này:

Duyệt trong $O(N)$ các hình chữ nhật con để cập nhật kết quả
**Lưu ý khi duyệt tới cuối hàng:**

### Mã C++

#include <bits/stdc++.h>
using namespace std;

const int N = 255;
int a[N][N], pre[N][N];

int main()
{
    int W, H, N;
    cin >> W >> H >> N;
    for (int i = 1; i <= H; ++i)
        for (int j = 1; j <= W; ++j)
        {
            cin >> a[i][j];
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
        }

    int ans = 0;
    for (int i = 1; i <= H; ++i)
        for (int j = i; j <= min(N + i - 1, H); ++j) // Không duyệt chiều cao lớn hơn N
        {
            int h = j - i + 1;
            for (int k = 1; k <= W; ++k)
            {
                int w = min(N / (h), W - k + 1); // Xử lý cuối hàng
                int y = k + w - 1;
                ans = max(ans, pre[j][y] - pre[j][k - 1] - pre[i - 1][y] + pre[i - 1][k - 1]);
            }
        }

    cout << ans;
}