P2034 Choosing Numbers

Given a sequence of $n$ non-negative integers $a_1 ,\cdots, a_n$. You may choose some of them, but no more than $k$ consecutive numbers can be chosen. Your task is to maximize the sum of the chosen numbers.

The first line contains two integers $n,k$. The following $n$ lines each contain one integer, representing $a_i$.

Output a single value representing the answer.

For $20\%$ of the testdata, $n \le 10$. For another $20\%$ of the testdata, $k=1$. For $60\%$ of the testdata, $n \le 10^3$. For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le k \le n$, $0 \le a_i \le 10^9$. Time limit: 500 ms. Translated by ChatGPT 5