[HSG_BRVT_24] Cắt hoa
Xem dạng PDFVườn hoa của nhà Minh nở rộ ~N~ khóm hoa đẹp, khóm hoa thứ ~i~ có ~A_i~ bông hoa. Do nhu cầu của dịp lễ 8/3 lớn nên người lái buôn muốn mua càng nhiều hoa của vườn càng tốt. Tuy nhiên địa hình vườn nhà Minh không thể cắt hoa của ~K~ khóm hoa liên tiếp, vì vậy Minh cần tìm cách cắt hoa sao cho cắt được tổng số bông hoa là nhiều nhất có thể.
Yêu cầu
Hãy xác định số lượng bông hoa nhiều nhất có thể cắt được.
Dữ liệu đầu vào
Gồm hai dòng:
- Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ ~(2 \le K \le N \le 10^5)~.
- Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, A_3, ..., A_N~ ~(1 \le A_i \le 10^9)~ lần lượt là số bông hoa của mỗi khóm hoa.
Dữ liệu đầu ra
Gồm một số nguyên duy nhất là tổng số bông hoa nhiều nhất có thể cắt được.
Ràng buộc dữ liệu
- 40% số test của bài có ~K = 3~.
- 40% số test tiếp theo có ~N \le 10^3;\ K \le 10^3~.
- 20% số test tiếp theo có ~N \le 10^5;\ K \le 10^5~.
Ví dụ
Ví dụ 1
INPUT
7 3
2 4 1 5 3 1 6
OUTPUT
20
Giải thích: Vì không thể cắt hoa ở ~3~ khóm hoa liên tiếp nên Minh sẽ cắt hoa ở những khóm hoa thứ ~1, 2, 4, 5, 7~. Tổng số bông hoa cắt được là ~2 + 4 + 5 + 3 + 6 = 20~ bông hoa.
Ví dụ 2
INPUT
5 2
10 4 7 3 4
OUTPUT
21
Giải thích: Vì không thể cắt hoa ở ~2~ khóm hoa liên tiếp nên Minh sẽ cắt hoa ở những khóm hoa thứ ~1, 3~ và ~5~. Tổng số bông hoa cắt được là ~10 + 7 + 4 = 21~ bông hoa.
Bình luận
AI ĐI NGANG QUA AC BÀI NÀY, CHO MÌNH XIN SOL VỚI HIHJ THANKS NHIỀU
dùng quy hoạch động mà làm