B - Neutralize
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 個の薬品が横一列に並んでいます。それぞれの薬品には 効用 という整数値が定まっており、左から i 番目の薬品の現在の効用は b_i です。これらの値は正とは限りません。
Kenkoooo さんは、横長の特殊な装置を用いて次の操作を何回でも行えます(行わなくても構いません)。
- 連続して並ぶ K 個の薬品を選ぶ。選ばれた薬品の効用はすべて 0 となる。
なお、薬品を移動させることは危険を伴うためできません。
その後、Kenkoooo さんは N 個の薬品すべてを飲み干します。その前に、N 個の薬品の効用の和を可能な限り大きくしておきたいです。操作後のこの和の最大値を求めてください。
制約
- 1 ≤ K ≤ N ≤ 2 × 10^5
- -10^9 ≤ b_i ≤ 10^9
- 入力中の値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K b_1 : b_N
出力
操作後の N 個の薬品の効用の和の最大値を出力せよ。
入力例 1
9 3 -1 -2 -3 4 5 -6 -7 -8 -9
出力例 1
9
最適な手順の例を示します。
- 1 回目の操作: 左から 1, 2, 3 番目の薬品を選ぶ。
- 2 回目の操作: 左から 6, 7, 8 番目の薬品を選ぶ。
- 3 回目の操作: 左から 7, 8, 9 番目の薬品を選ぶ。
このとき、9 個の薬品の効用の和は 0 + 0 + 0 + 4 + 5 + 0 + 0 + 0 + 0 = 9 となります。
入力例 2
5 4 -1 -1 5 -1 -1
出力例 2
1
何もせずこのまま薬品を飲み干すべきです。
入力例 3
9 5 30 -20 40 60 -90 50 -40 10 70
出力例 3
120
入力例 4
10 1 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000
出力例 4
5000000000