問題一覧 > 通常問題

No.2139 K Consecutive Sushi

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 80
作問者 : Shirotsume / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 8521 / 自分の提出
問題文最終更新日: 2022-12-02 09:55:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2022 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。