Official
B - 売上分析 / Sales Analysis Editorial
by
B - 売上分析 / Sales Analysis Editorial
by
MMNMM
\(T _ i\) の累積和 \(\displaystyle S _ i=\sum _ {j=1} ^ {i-1}T _ j\ (0\le i\le N)\) によって、\(T _ l+T _ {l+1}+\cdots+T _ {l+K-1}=S _ {l+K}-S _ l\) と表すことができます。 よって、累積和を計算しておくことで、\(M _ l\) の値を \(l\) ごとに定数時間で求めることができます。 あとは、これらの最大値を求め、\(\displaystyle\Bigl\lfloor1000\max _ lM _ l\Bigr\rfloor\) を計算すればよいです。
\(M _ l\) の値の比較や \(\lfloor 1000M\rfloor\) の計算においては、\(M _ l\) ではなく \(KM _ l=S _ {l+K}-S _ l\) の値を管理する形で実装を行うのが楽だと思います。
実装例は以下のようになります。
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, K;
cin >> N >> K;
vector<long> T(N);
for (long& t : T) {
cin >> t;
}
// 累積和を求める
for (int i = 1; i < N; ++i) {
T[i] += T[i - 1];
}
T.emplace(begin(T)); // 先頭に 0 を入れておく
long ans = 0;
for (int i = 0; i + K <= N; ++i) {
ans = max(ans, T[i + K] - T[i]); // K 日分の合計の最大値を求める
}
cout << ans * 1000 / K << endl; // 1000 倍して K で割って切り捨て
return 0;
}
N, K = map(int, input().split())
T = [0] + list(map(int, input().split()))
# 累積和を求める
for i in range(1, N + 1):
T[i] += T[i - 1]
ans = 0
for begin, end in zip(T, T[K:]):
ans = max(ans, end - begin) # K 日分の合計の最大値を求める
print(ans * 1000 // K) # 1000 倍して K で割って切り捨て
posted:
last update:
