問題一覧 > 通常問題

No.2139 K Consecutive Sushi

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 : ShirotsumeShirotsume / テスター : AngrySadEightAngrySadEight
4 ProblemId : 8521 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-02 09:55:02

問題文

Shirotsume は回転寿司店に来ました。いまから、Shirotsume のいるカウンターに $N$ 皿の寿司が順番に流れてきます。 $i$ $(1 \leq i \leq N)$ 番目に流れてくる寿司のおいしさは $A_i$ です。

Shirotsume は流れてくる寿司を好きなだけ取って食べることにしましたが、他のお客さんのことも考えて、$K$ 皿以上連続して寿司を取らないことに決めました。

Shirotsume が食べる寿司のおいしさの総和として考えられる最大値を求めてください。

制約

  • 入力は全て整数
  • $2 \leq K \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9$ $(1 \leq i \leq N)$

入力

入力は標準入力から以下の形式で与えられる。

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

出力

Shirotsume が食べる寿司のおいしさの総和として考えられる最大値を出力せよ。

サンプル

サンプル1
入力
4 2
3 2 4 5
出力
8

$2$ 皿の連続した皿を取ることはできないので、$3$ 番目と $4$ 番目の皿を両方取るような選び方はできません。

$1$ 番目と $4$ 番目を選ぶ選び方でおいしさの総和が $8$ となり、これが最大です。

サンプル2
入力
3 3
2 3 1
出力
5
サンプル3
入力
17 5
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2
出力
71

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。