Cắt hoa (Bài 4 HSG9 Tỉnh Bà Rịa - Vũng Tàu 2025)

Xem PDF



Tác giả:
Dạng bài
Điểm: 1 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Vườn hoa của nhà Minh nở rộ \(N\) khóm hoa đẹp, khóm hoa thứ \(i\)\(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

Vào từ file văn bản FCUT.INP:

  • Dòng đầu tiên chứa \(2\) số nguyên dương \(N\)\(K\).
  • Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) lần lượt là số bông hoa mỗi khóm hoa.

Dữ liệu đảm bảo: \(2 \le K \le N \le 10^5\)\(1 \le A_i \le 10^9\).

Kết quả

Ghi vào file văn bản FCUT.OUT một số nguyên là tổng số bông hoa nhiều nhất có thể cắt được.

Ràng buộc

  • Subtask 1: \(40\%\) số test ứng với \(K = 3\).
  • Subtask 2: \(40\%\) số test ứng với \(2 \le K \le N \le 10^3\).
  • Subtask 3: \(20\%\) số test không có ràng buộc gì thêm.

Ví dụ

Giải thích

Test 1

Input
7 3
2 4 1 5 3 1 6
Output
20
Note
  • Trong ví dụ \(1\): 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.

Test 2

Input
5 2
10 4 7 3 4
Output
21
Note
  • Trong ví dụ \(2\): 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\)\(5\). Tổng số bông hoa cắt được là \(10 + 7 + 4 = 21\) bông hoa.

Bình luận

Không có bình luận nào.