Elearning CodePath – CTP Online Judge

Khai thác khoáng sản (MINERAL)

302_KHAIT

🟢 Hard #Graph #Deque

## 💻 Đề Bài:

### 📌 **Thông tin chương trình**

---

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

Bản đồ Byteland được mô tả bằng một lưới hình chữ nhật kích thước $M \times N$.
Ký hiệu ô nằm ở hàng $i$, cột $j$ là $A_{i,j}$.

* Nếu ô $A_{i,j}$ có công trình di sản văn hóa, giá trị của nó là $-1$ (không được khai thác).
* Nếu ô $A_{i,j}$ có thể khai thác, giá trị khoáng sản là một số nguyên không âm $V_{i,j}$ ($0 \le V_{i,j} \le 1000$).

Công ty ABC chỉ được phép khai thác trên một **vùng đất hình chữ nhật** có các cạnh song song với cạnh bảng. Vùng này **không được chứa bất kỳ ô nào có công trình văn hóa** (giá trị $-1$).

Hỏi rằng công ty ABC có thể khai thác khoáng sản với **tổng giá trị lớn nhất** là bao nhiêu?

### 📥 **Định dạng Input**

* **Dòng 1:** Ghi hai số nguyên dương $M$ và $N$ ($1 \le M, N \le 400$).
* **$M$ dòng tiếp theo:** Dòng thứ $i$ ghi $N$ số nguyên. Số thứ $j$ là:
    * $-1$ nếu ô $(i, j)$ có công trình văn hóa.
    * $V_{i,j}$ ($0 \le V_{i,j} \le 1000$) nếu ô $(i, j)$ có khoáng sản.

**Giới hạn:**
$$1 \le M, N \le 400$$
$$A_{i,j} \in \{-1, 0, 1, \dots, 1000\}$$

### 📤 **Định dạng Output**

Một số nguyên duy nhất là giá trị khoáng sản có thể khai thác tối đa.

### ✨ **Ví dụ**

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

---

#### **Subtask 1: M, N nhỏ ($M, N \le 50$)**

* Sử dụng **Tổng tiền tố 2D** ($O(MN)$).

#### **Subtask 2: M, N lớn ($M, N \le 400$)**

* Sử dụng **Kỹ thuật "Ghim hai đầu"** kết hợp với **Kadane biến thể** như mô tả ở trên.
* Lặp qua $O(M^2)$ cặp hàng.
* Trong mỗi cặp hàng, tính mảng $B$ và áp dụng Kadane biến thể trong $O(N)$.
* **Độ phức tạp:** $O(M^2 N)$. (Đây là thuật toán hiệu quả nhất cho bài toán này).

✅ Đã AC: 0 / 10 submissions