前缀后缀和搞一搞, 然后枚举一下区间, 找出最大值
- #include <iostream>
- #include <algorithm>
- using namespace std;
- const int maxn = 1e5 + 5;
- int a[maxn], f[maxn], b[maxn], c[maxn];
- int main()
- {
- ios::sync_with_stdio(false);
- int n, k;
- cin>> n>> k;
- for (int i = 1; i <= n; i++)
- cin>> a[i];
- for (int i = 1; i <= n; i++)
- cin>> f[i];
- // 前缀和
- for (int i = 1; i <= n; i++)
- if (f[i])b[i] = b[i - 1] + a[i];
- else b[i] = b[i - 1];
- // 后缀和
- for (int i = n; i>0; i--)
- if (f[i])c[i] = c[i + 1] + a[i];
- else c[i] = c[i + 1];
- long long s = 0;
- for (int i = 1; i <= k; i++)s += a[i];
- long long ans = 0;
- for (int i = k; i <= n; i++){
- ans = max(b[i - k] + s + c[i + 1], ans);
- s = s - a[i - k + 1] + a[i + 1];
- }
- cout << ans;
- return 0;
- }
- B. Lecture Sleep( Educational Codeforces Round 41 (Rated for Div. 2))
来源: http://www.bubuko.com/infodetail-2550456.html