Elearning CodePath – CTP Online Judge

Săn Bắn

111_BIRD

🟢 Hard #General #Binary Search

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho $N$ con chim đậu thành một hàng, con chim thứ $i$ có sức mạnh là $A_i$. BigZero săn bắn theo quy trình lặp đi lặp lại cho đến khi tất cả $N$ con chim bị bắn chết.

**Quy tắc Săn Bắn (Chọn mục tiêu):**
1.  BigZero luôn bắn con chim có **sức mạnh lớn nhất** ($A_{max}$).
2.  Nếu có nhiều con chim cùng có sức mạnh lớn nhất, anh ta sẽ bắn con có **chỉ số (vị trí) nhỏ nhất** (xuất hiện sớm nhất trong hàng).

**Quy tắc Chi phí Năng lượng:**
Giả sử BigZero bắn con chim thứ $i$ (tại vị trí $i$ hiện tại trong hàng).
* Chi phí năng lượng cần dùng để bắn chết con chim $i$ là tổng sức mạnh của ba con chim:
    * Con chim $i$
    * Con chim ngay trước $i$ (gọi là $i-1$, nếu tồn tại)
    * Con chim ngay sau $i$ (gọi là $i+1$, nếu tồn tại)
* **Công thức chi phí:** $Cost(i) = A_i + A_{i-1} + A_{i+1}$ (Với $A_{i-1} = 0$ nếu $i$ là chim đầu hàng, và $A_{i+1} = 0$ nếu $i$ là chim cuối hàng).

**Quy tắc Hàng ngũ sau khi bắn:**
Sau khi con chim $i$ bị bắn chết, nó bị loại khỏi hàng. Các con chim còn lại sẽ xích lại gần nhau, tạo thành một hàng liên tiếp mới với $N-1$ con chim.

**Mục tiêu:** Tính tổng năng lượng tối thiểu BigZero cần dùng để bắn chết tất cả $N$ con chim.

---

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

Dữ liệu vào từ file văn bản `BIRD.INP` gồm:

* **Dòng 1:** Chứa số nguyên dương $N$ – số lượng chim ban đầu.
* **Dòng 2:** Gồm $N$ số nguyên dương $A_1, A_2, \dots, A_N$ biểu thị sức mạnh của các con chim, cách nhau một khoảng trắng.

**Giới hạn (Ràng buộc):**
Giới hạn được cung cấp dưới dạng các Subtask, tuy nhiên vì bài toán yêu cầu một lời giải duy nhất, ta xét ràng buộc tối đa:
*$1 \le N \le 10^5$
*$1 \le A_i \le 10^9$

---

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

Ghi ra file văn bản `BIRD.OUT` một dòng duy nhất ghi tổng năng lượng cần dùng. Tổng năng lượng có thể rất lớn, cần dùng kiểu dữ liệu 64-bit (long long/int64) để lưu trữ.

---

### ✨ Ví dụ

| Input (`BIRD.INP`) | Output (`BIRD.OUT`) |
| :--- | :--- |
| `5` <br> `1 2 3 4 5` | `25` |

---

### 🧪 Subtask

✅ Đã AC: 2 / 5 submissions