Elearning CodePath – CTP Online Judge

Mảng độ cao

REC01

🟢 Easy #General #Dynamic Programming

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho một lưới hình chữ nhật kích thước $M \times N$. Mỗi ô $(i, j)$ của lưới chứa một giá trị nhị phân ($0$ hoặc $1$).

Yêu cầu: Tìm một **hình chữ nhật con** trên lưới (có các cạnh song song với các cạnh của lưới) thỏa mãn hai điều kiện:
1.  Tất cả các ô vuông trong hình chữ nhật con đều chứa số $1$.
2.  Hình chữ nhật đó có **diện tích (số ô vuông) lớn nhất** có thể.

Diện tích lớn nhất cần tìm là:
${Max Area} = \max_{\text{Hình chữ nhật } R} (\text{Chiều cao}(R) \times \text{Chiều rộng}(R))$
với $R$ chỉ chứa toàn số $1$.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `REC01.INP`:

* Dòng 1: Ghi hai số nguyên $M$ (số hàng) và $N$ (số cột).
* $M$ dòng tiếp theo: Mỗi dòng ghi $N$ số nguyên ($0$ hoặc $1$) mô tả lưới.

Giới hạn:
* $1 \le M, N \le 500$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `REC01.OUT` một số nguyên duy nhất là diện tích lớn nhất của hình chữ nhật chứa toàn số $1$.

---
### ✨ Ví dụ

| Input (`REC01.INP`) | Output (`REC01.OUT`) |
| :--- | :--- |
| `4 5` <br> `0 0 1 1 1` <br> `0 1 1 1 1` <br> `1 1 1 1 1` <br> `0 0 0 0 0` | `9` |

Giải thích: Hình chữ nhật lớn nhất chứa toàn số $1$ có kích thước $3 \times 3$, bắt đầu từ ô $(1, 2)$ và kết thúc tại ô $(3, 4)$ (hoặc $3 \times 3$ nằm ở vị trí khác). Ví dụ:
* Hàng 1: [0, 1, 1]
* Hàng 2: [1, 1, 1]
* Hàng 3: [1, 1, 1]
Hình chữ nhật này có chiều cao 3 và chiều rộng 3, diện tích $3 \times 3 = 9$.

---
### 🏷 Subtask

| Subtask | Ràng buộc | Điểm |
| :--- | :--- | :--- |
| 1 | $M, N \le 100$ | $40\%$ |
| 2 | $M, N \le 500$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions