No.2139 K Consecutive Sushi
タグ : / 解いたユーザー数 80
作問者 :
Problem Statement
Shirotsume has come to a conveyor belt sushi restaurant. From now on, $N$ plates of sushi will come in order to the counter where Shirotsume is sitting. The deliciousness of the $i$-th $(1 \leq i \leq N)$ sushi to come is $A_i$.
Shirotsume will take and eat as many of the passing sushi as desired, but out of consideration for the other customers, has decided not to take $K$ or more consecutive plates of sushi.
Find the maximum possible total deliciousness of the sushi Shirotsume eats.
Constraints
- All inputs are integers.
- $2 \leq K \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$ $(1 \leq i \leq N)$
Input
The input is given from Standard Input in the following format.
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Output the maximum possible total deliciousness of the sushi Shirotsume eats.
Sample
Sample 1
Input
4 2 3 2 4 5
Output
8
Since $2$ consecutive plates cannot be taken, it is not allowed to choose both the $3$-rd and $4$-th plates.
Choosing the $1$-st and $4$-th plates gives a total deliciousness of $8$, which is the maximum.
Sample 2
Input
3 3 2 3 1
Output
5
Sample 3
Input
17 5 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2
Output
71
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。