Elearning CodePath – CTP Online Judge

Cắt Hoa Tối Đa với Ràng Buộc Kề

MAXIMUM_FLOWER

🟢 Easy

### 📌 Thông tin chung

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

Cho một dãy gồm $N$ khóm hoa, khóm hoa thứ $i$ có $A_i$ bông hoa.
Ông Nhân cần chọn một tập hợp con các khóm hoa để cắt, sao cho **tổng số bông hoa** cắt được là lớn nhất.

Ràng buộc: Ông Nhân **không thể** cắt hoa ở $K$ khóm hoa 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} A_i$ lớn nhất có thể.

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

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

* Dòng 1: Hai số nguyên dương $N$ và $K$.
* Dòng 2: $N$ số nguyên dương $A_1, A_2, \dots, A_N$ cách nhau bởi dấu cách.

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

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

Ghi ra file `FLOWER.OUT` một số nguyên không âm duy nhất là tổng số bông hoa lớn nhất có thể cắt.

---
### 🏷 Phân Subtask

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

---

✅ Đã AC: 0 / 0 submissions