思路
前缀和,由于只有状态为0的数可以被加上,所以只对状态为0的数求前缀和。
接下来枚举区间为k的前缀和的最大值再加上状态为1的总和即可。
时间复杂度:O(n)
AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, k;
int a[N], st[N];
LL res, s[N];
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= n; ++i) {
scanf("%d", &st[i]);
if(st[i]) res += a[i];
}
for(int i = 1; i <= n; ++i)
if(!st[i]) s[i] = s[i - 1] + a[i];
else s[i] = s[i - 1];
LL sum = 0;
for(int i = 0; i <= n; ++i)
if(i + k <= n) sum = max(sum, s[i + k] - s[i]);
cout << sum + res << endl;
return 0;
}