Elearning CodePath – CTP Online Judge

Bob's Building

COMB001

🟢 Easy #General #Combinatorics #Interval

### 📌 Thông tin chung

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

Vùng đất là một hình chữ nhật kích thước $N \times M$ được chia thành $N \cdot M$ ô vuông. Độ cao của ô vuông ở hàng $i$, cột $j$ là $H_{i, j}$.

Nhà của Bob cần xây dựng có dạng:
1.  Là một **hình chữ nhật** có các cạnh song song với các cạnh của vùng đất.
2.  Tất cả các ô vuông trong vùng đất mà Bob xây nhà phải có **cùng độ cao**.

Yêu cầu: Tính toán số phương án khác nhau mà Bob có thể chọn để xây nhà.
Một phương án là một hình chữ nhật con nằm trong lưới $N \times M$ mà tất cả các ô trong nó có cùng một giá trị độ cao.

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

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

* Dòng đầu tiên: Chứa hai số nguyên dương $N$ và $M$.
* $N$ dòng tiếp theo: Mỗi dòng chứa $M$ số nguyên $H_{i, j}$ mô tả độ cao của các ô vuông tương ứng trên vùng đất.

Giới hạn:
* $1 \le N, M \le 500$.
* $1 \le H_{i, j} \le 10^9$.

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

Ghi ra file `BOB.OUT` một dòng duy nhất chứa số cách chọn vùng đất khác nhau có thể có của Bob.

---
### ✨ Ví dụ

| Input (`BOB.INP`) | Output (`BOB.OUT`) |
| :--- | :--- |
| `5 3` `2 2 2` `2 2 1` `1 1 1` `2 1 2` `1 2 1` | `27` |

Giải thích:
Có thể phân tích theo các độ cao:
* **Độ cao 1:**
$\begin{pmatrix} \cdot & \cdot & \cdot \\ \cdot & \cdot & 1 \\ 1 & 1 & 1 \\ \cdot & 1 & \cdot \\ 1 & \cdot & 1 \end{pmatrix}$
* **Độ cao 2:**
$\begin{pmatrix} 2 & 2 & 2 \\ 2 & 2 & \cdot \\ \cdot & \cdot & \cdot \\ 2 & \cdot & 2 \\ \cdot & 2 & \cdot \end{pmatrix}$
Tổng số hình chữ nhật con (kể cả $1 \times 1$) thỏa mãn điều kiện cùng độ cao là $27$.

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N, M \le 100$ | $20\%$ |
| 2 | $N, M \le 500$ | $80\%$ |

---

✅ Đã AC: 0 / 0 submissions