Official

C - ボーナスタイム / Bonus Time Editorial by harurun4635 Editorial for printing


基本スコアは必ず獲得するわけですから、それを除くと「ある長さ \(K\) の substring であって、総和が最大のもの」を求める問題に帰着されます。

これは、差分を更新することで、各 \([i:i+k)\) について求めることができます。


実装例

n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = tmp = sum(a[:k])
for i in range(n - k):
    tmp += a[i+k] - a[i]
    ans = max(ans, tmp)
print(ans + sum(a))

posted:
last update: