AtCoder Beginner Contest 037 C - 総和
問題
長さNの数列{}と1以上N以下の整数が与えられます。この数列には長さKの連続する部分がN-K+1個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。
制約
- は整数である。
考えたこと
すべてのパターンを逐一足し算したのでは間に合わなさそうです。累積和を使うことにしました。
コード
#define _GIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) #define all(v) v.begin(), v.end() using namespace std; using ll = long long; int main(void) { ll N, K; cin >> N >> K; vector<ll> a(N); rep(i, N) cin >> a[i]; vector<ll> s(N + 1, 0); for (int i = 0; i < N; ++i) s[i + 1] = s[i] + a[i]; ll ans = 0; int left = 0; int right = K; while (right <= N) { ans += s[right] - s[left]; ++left; ++right; } cout << ans << endl; return 0; }
解説を読んで
とくにありません。