P5124 [USACO18DEC] Teamwork G

On Farmer John’s favorite holiday, he wants to give some gifts to his friends. Since he is not very good at wrapping gifts, he wants help from his cows. As you might guess, cows are also not very good at wrapping gifts, and Farmer John is about to learn this lesson. Farmer John has $N$ cows ($1\le N\le 10^4$) standing in a line, numbered $1\dots N$ for convenience. Cow $i$ has a gift-wrapping skill level of $s_i$. Their skill levels may vary a lot, so FJ decides to divide his cows into groups. Each group can contain any number of consecutive cows, as long as it has at most $K$ cows ($1\le K\le 10^3$), and no cow can belong to more than one group. Since the cows learn from each other, every cow in a group will have her skill level changed to the highest skill level within that group. Help FJ find the maximum possible total sum of skill levels, if he groups the cows in the best way.

The first line contains $N$ and $K$. The next $N$ lines give the cows’ skill levels in order. Each skill level is a positive integer not exceeding $10^5$.

Output the maximum total sum of skill levels that FJ can achieve by grouping consecutive cows.

In this example, the best plan is to put the first three cows into one group and the last three cows into another group, with the middle cow alone as a group (note that a group can have fewer than $K$ cows). This effectively increases the 7 cows’ skill levels to $15$, $15$, $15$, $9$, $10$, $10$, $10$, for a total of $84$. Translated by ChatGPT 5