Elearning CodePath – CTP Online Judge

Diện tích Biển Quảng cáo Lớn nhất

GEN011

🟢 Hard #General

### 📌 Thông tin chung

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

Cho một hàng rào gồm một dãy $N$ tấm gỗ. Mỗi tấm gỗ thứ $i$ có chiều rộng là $1$ đơn vị và chiều cao là $h_i$.

Một tấm quảng cáo có dạng hình chữ nhật được đặt lên hàng rào. Tấm quảng cáo phải nằm hoàn toàn trong giới hạn chiều cao của các tấm gỗ mà nó phủ lên.

Nếu tấm quảng cáo phủ lên các tấm gỗ từ $i$ đến $j$ ($1 \le i \le j \le N$):
* **Chiều rộng** của tấm là $W = j - i + 1$.
* **Chiều cao** tối đa của tấm là $H = \min(h_i, h_{i+1}, \dots, h_j)$.
* **Diện tích** là $Area = W \times H$.

Yêu cầu: Tìm **diện tích lớn nhất** của một tấm quảng cáo hình chữ nhật có thể đặt được.
$$
\text{Max Area} = \max_{1 \le i \le j \le N} \left( (j - i + 1) \times \min_{k=i}^{j} h_k \right)
$$

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

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

* Dòng 1: Ghi số nguyên dương $N$.
* Dòng 2: Ghi $N$ số nguyên dương $h_1, h_2, \dots, h_N$ (chiều cao của các tấm gỗ), cách nhau bởi dấu cách.

Giới hạn:
* $1 \le N \le 10^5$.
* $1 \le h_i \le 10^9$.

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

Ghi ra file `POSTER.OUT` một dòng duy nhất ghi diện tích lớn nhất của một tấm quảng cáo (số nguyên).

---
### ✨ Ví dụ

| Input (`POSTER.INP`) | Output (`POSTER.OUT`) |
| :--- | :--- |
| `4` <br> `3 4 3 1` | `9` |
| `4` <br> `1 2 1 3` | `4` |

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 5000$ | $40\%$ |
| 2 | $N \le 10^5$ | $60\%$ |

---

✅ Đã AC: 3 / 5 submissions