Official

B - 果物の収穫 / Fruit Harvest Editorial by sounansya


\(\displaystyle B_i=\sum_{j=1}^i A_j\) とします。

左から \(l\) 番目から \(l+K-1\) 番目までの \(K\) 本の木になっている果物の個数の総和は \(\displaystyle \sum_{i=l}^{l+K-1} A_i=A_{l+K-1}-A_{l-1}\) と表せます。したがって、累積和 \(B\) を計算し、 \(B_{i+K}-A_i\) の最大値を計算すれば良いです。

実装例(Python3)

n, k = map(int, input().split())
a = list(map(int, input().split()))
r = [0]
for v in a:
    r.append(r[-1] + v)
ans = 0
for i in range(k, n + 1):
    ans = max(ans, r[i] - r[i - k])
print(ans)

posted:
last update: