Elearning CodePath – CTP Online Judge

Tối Đa với Ràng Buộc Kề

Pepsi

🟢 Hard #General #Set / Map

### 📌 Thông tin chung

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

Cho một dãy $N$ chai Pepsi, chai thứ $i$ có dung tích $V_i$.
Khánh cần chọn một tập hợp con các chai để uống, sao cho **tổng dung tích** Pepsi uống được là lớn nhất.

Ràng buộc: Khánh **không được uống** $K$ chai liên tiếp.
Tức là, nếu ta chọn tập chỉ số $I \subset \{1, 2, \dots, N\}$, thì không tồn tại $i$ sao cho $\{i, i+1, \dots, i+K-1\} \subset I$.

Yêu cầu: Tìm tổng $\sum_{i \in I} V_i$ lớn nhất có thể.

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

Dữ liệu vào từ file `Pepsi.inp`:

* Dòng 1: Hai số nguyên $N$ và $K$.
* Dòng 2: $N$ số nguyên $V_1, V_2, \dots, V_N$ cách nhau bởi dấu cách (dung tích của các chai).

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

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

Ghi ra file `Pepsi.out` một số nguyên duy nhất là lượng Pepsi tối đa Khánh có thể uống.

---
### ✨ Ví dụ

| Input (`Pepsi.inp`) | Output (`Pepsi.out`) |
| :--- | :--- |
| `6 3` <br> `6 10 10 13 10 10` | `40` |

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính | 
| :--- | :--- | :--- | 
| 1 | $N \le 1000$ | $30\%$ | 
| 2 | $N \le 10^5, K \le 10^5$ | $70\%$ |

---

✅ Đã AC: 0 / 0 submissions