P2627 [USACO11OPEN] Mowing the Lawn G

After winning the town’s Best Lawn contest a year ago, Farmer John became lazy and hasn’t mowed the lawn since. Now, a new Best Lawn contest is starting, and Farmer John hopes to win again. However, Farmer John’s lawn is a mess, so he can only rely on his cows to do the job. Farmer John has $N$ ($1\le N\le 10^5$) cows in a row, numbered $1\ldots N$. Each cow has a different efficiency; cow $i$ has efficiency $E_i$ ($0\le E_i\le 10^9$). Neighboring cows are very familiar with each other, so if Farmer John schedules more than $K$ ($1\le K\le N$) consecutive cows, they will go on strike to throw a party :). Therefore, Farmer John needs your help to compute the maximum total efficiency he can obtain, with no stretch of more than $K$ consecutive cows.

The first line contains two integers $N$ and $K$ separated by a space. The second to $(N+1)$-th lines: the $(i+1)$-th line contains an integer $E_i$.

Output a single value: the maximum total efficiency that Farmer John can obtain.

Translated by ChatGPT 5