- 基本思路
- 我们使用前缀和数组记录到当前位置时,之前的可选的位置的和,之前的不可选的位置的和。
-
然后两个指针,间距为k,根据上面的不可选的前缀和得出 区间中不可选的位置的和,更新最大值即可
-
欢迎交流想法😁
#include <iostream>
using namespace std;
const int N = 100010;
typedef long long LL;
LL a[N], sumOfOk[N], sumOfNotOk[N];
bool st[N];
int n, k;
int main() {
cin >> n >> k;
for (int i(1); i <= n; ++ i) cin >> a[i];
for (int i(1); i <= n; ++ i) cin >> st[i];
for (int i(1); i <= n; ++ i) {
if (st[i]) {
sumOfOk[i] = sumOfOk[i - 1] + a[i];
sumOfNotOk[i] = sumOfNotOk[i - 1];
} else {
sumOfOk[i] = sumOfOk[i - 1];
sumOfNotOk[i] = sumOfNotOk[i - 1] + a[i];
}
}
LL ans = 0;
for (int i(0); i < n - k; ++ i) {
ans = max(ans, sumOfOk[n] + sumOfNotOk[i + k] - sumOfNotOk[i]);
}
cout << ans;
return 0;
}