Elearning CodePath – CTP Online Judge

Vị trí Tốt

BPOS

🟢 Easy #Hash #Dynamic Programming

### 📌 Thông tin chung

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

Cho dãy $A = (A_1, A_2, \dots, A_N)$ các số nguyên.

Vị trí $i$ ($1 \le i \le N$) được gọi là một **vị trí tốt** nếu như $A_i$ bằng tổng của **ba giá trị** xuất hiện ở các **vị trí nhỏ hơn $i$** (mỗi giá trị có thể tham gia vào việc tính tổng nhiều lần).
$$
A_i = V_1 + V_2 + V_3
$$
trong đó $V_1, V_2, V_3$ là các giá trị thuộc tập hợp $\{A_j \mid 1 \le j < i\}$.

Yêu cầu: Đếm số lượng vị trí tốt trong dãy $A$.

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

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

* Dòng đầu tiên: Chứa số nguyên dương $N$.
* Dòng thứ hai: Chứa $N$ số nguyên $A_1, A_2, \dots, A_N$.

Giới hạn (Không được cho rõ, giả định theo mức độ phức tạp phổ biến):
* $1 \le N \le 2000$.
* $-10^4 \le A_i \le 10^4$.

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

Ghi ra file `BPOS.OUT` một số nguyên duy nhất là số vị trí tốt tìm được.

---
### ✨ Ví dụ

| Input (`BPOS.INP`) | Output (`BPOS.OUT`) |
| :--- | :--- |
| `2` <br> `1 3` | `1` |
| `6` <br> `1 2 3 5 7 10` | `4` |
| `3` <br> `-1 2 0` | `1` |

---
### 🏷 Phân Subtask

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

---

✅ Đã AC: 0 / 0 submissions