Elearning CodePath – CTP Online Judge

Giá trị Khoáng sản Tối đa

MINERAL

🟢 Easy #Dynamic Programming

### 📌 Thông tin chung

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

Cho một bản đồ là lưới hình chữ nhật kích thước $M \times N$. Mỗi ô $(i, j)$ được gán một giá trị $A_{i, j}$:
* $A_{i, j} = -1$: Ô có công trình văn hóa, không được khai thác.
* $A_{i, j} \ge 0$: Giá trị khoáng sản tại ô đó.

Yêu cầu: Tìm một vùng đất hình chữ nhật con trong lưới sao cho:
1.  Hình chữ nhật con không chứa bất kỳ ô nào có giá trị $-1$ (công trình văn hóa).
2.  Tổng giá trị khoáng sản của các ô trong hình chữ nhật con đó là lớn nhất.

Nếu gọi $R$ là một hình chữ nhật con hợp lệ, mục tiêu là tìm:
$\text{Max Value} = \max_{\text{Hình chữ nhật hợp lệ } R} \left( \sum_{(i, j) \in R} A_{i, j} \right)$

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

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

* Dòng 1: Ghi hai số nguyên dương $M$ (số hàng) và $N$ (số cột).
* $M$ dòng tiếp theo: Dòng thứ $i$ ghi $N$ số nguyên. Số thứ $j$ là $A_{i, j}$.

Giới hạn:
* $1 \le M, N \le 400$.
* $A_{i, j} = -1$ (công trình văn hóa) hoặc $0 \le A_{i, j} \le 10^9$ (giá trị khoáng sản).

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

Ghi ra file `MINERAL.OUT` một số nguyên duy nhất là giá trị khoáng sản tối đa có thể khai thác.

---
### ✨ Ví dụ

| Input (`MINERAL.INP`) | Output (`MINERAL.OUT`) |
| :--- | :--- |
| `4 5` <br> `-1 -1 -1 75 -1` <br> `3 5 2 82 -1` <br> `1 1 1 1 -1` <br> `-1 -1 -1 -1 -1` | `158` |

---
### 🏷 Phân Subtask

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

---

✅ Đã AC: 0 / 0 submissions