给定一个长度为 n 的正整数数列 $ a_1,a_2,…,a_n $ 。

初始时，数列中的每个元素要么处于可选状态，要么处于不可选状态。

你可以选择一个长度恰好为 k 的区间 $[i, i + k-1]$ ,使得 $ a_i∼a_{i+k−1 }$ 这 k 个元素的状态全部变为可选。

请问，在经过此操作后，所有处于可选状态的元素之和最大是多少。

输入格式

第一行包含两个整数 n 和 k 。

第二行包含 n 个整数 $ a_i $。

第三行包含一个长度为 n 的 01 序列，如果第 i 个数为 1 ，表示 ai 的初始状态为可选，如果第 i 个数为 0，表示 ai 的初始状态为不可选。

输出格式

一行一个整数，表示答案。

数据范围

对于 30% 的数据，$ 1≤k≤n≤1000 $ 对于 100% 的数据，$ 1≤k≤n≤10^5,1≤ai≤10^5 $

输入样例1：

1
2
3

3 1
2 5 4
0 0 1

输出样例1：

1

9

输入样例2：

1
2
3

4 3
10 5 4 7
0 1 1 0

输出样例2：

1

19

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include<bits/stdc++.h>
using namespace std;
int n,k;
const int N = 1e5+7;
int a[N];
bool b[N];
int main()
{
    #define ll long long
    cin>>n>>k;
    for (int i = 0; i < n; i ++ ) cin>>a[i];
    for (int i = 0; i < n; i ++ ) cin>>b[i];
     
    ll sum = 0, win = 0;
    for(int i=0;i<n;++i) {
        if(b[i]) sum += a[i];
    }
    ll s= 0;
    for(int j=0;j<n;++j) {
        if(b[j] == 0) win+= a[j];
        if(j>= k && (b[j - k] == 0)) {
            win -= a[j-k];
        }
        s = max(win, s );
    }
    cout << sum + s  <<endl;
    
    
    return 0;
}

前缀和写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,k;
const int N = 1e5+7;
int a[N];
bool b[N];
ll s1[N],s2[N];
int main()
{
    
    cin>>n>>k;
    for (int i = 1; i <= n; i ++ ) cin>>a[i];
    for (int i = 1; i <= n; i ++ ) cin>>b[i];
    
    for(int i=1;i<=n;++i) {
        if(b[i]) s1[i] = a[i];
        else s2[i] = a[i];
    }
    for(int i=1;i<=n;++i) {
        s1[i] += s1[i-1];
        s2[i] += s2[i-1];
    }
    ll res = 0;
    ll win = 0;
    for(int i=1;i+k-1<=n;++i) {
        win = s2[i+k - 1] - s2[i-1];
        res = max(res,win);
    }
    cout << res + s1[n] <<endl;
    
    
    
    return 0;
}