USACO 2018 - Dec - Gold - Teamwork

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 0.5s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=863
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Vào kì nghỉ yêu thích của mình, người nông dân John muốn gửi tới những người bạn của mình một số món quà. Bởi vì không giỏi gói quà, John đã nhờ những chú bò của mình giúp sức.

~N~ chú bò của nông dân John xếp thành một hàng, đánh số từ ~1...N~. Chú bò thứ ~i~ có kĩ năng gói quà là ~a_{i}~. Vì những chỉ số này không đồng đều nên John muốn chia các chú bò thành từng đội. Mỗi đội gồm tối đa ~K~ chú bò liên tiếp nhau. Mỗi chú bò phải trong chính xác một đội. Bởi vì các chú bò có thể học hỏi lẫn nhau nên kĩ năng gói quà của mỗi chú bò được tăng lên bằng kĩ năng gói quà lớn nhất trong đội.

Hãy giúp nông dân John tìm cách chia đội tối ưu nhất và tìm xem tổng kĩ năng gói quà của các chú bò trong phương án tối ưu nhé!

Input

  • Dòng đầu chứa hai số nguyên dương ~N~ và ~K~ ~(1 \le N \le 10^4, 1 \le K \le 10^3)~.

  • ~N~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~a_{i} (1 \le a_{i} \le 10^5)~ - kĩ năng gói quà của chú bò thứ ~i~.

Output

  • Ghi ra tổng kĩ năng gói quà trong phương án tối ưu.

Sample Input

7 3
1
15
7
9
2
5
10

Sample Output

84

Giải thích

  • Nhóm 3 chú bò đầu, 3 chú bò sau và chú bò giữa 1 nhóm riêng. Tổng kĩ năng là ~15 + 15 + 15 + 9 + 10 + 10 + 10 = 84~

Comments

Please read the guidelines before commenting.


There are no comments at the moment.