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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 8e3+7;

int n,k,t;
string s;
int prefB[N];
int prefZ[N];

int sufB[N];
int sufZ[N];

int wyn=-1;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> t;
    cin >> s;

    prefB[0]=0;
    prefZ[0]=0;
    for(int i=0;i<n;i++){
        prefB[i+1]=prefB[i];
        prefZ[i+1]=prefZ[i];
        if(s[i]=='1') prefB[i+1]++;
        if(s[i]=='2') prefZ[i+1]++;
    }

    sufB[n]=0;
    sufZ[n]=0;
    for(int i=n-1;i>=0;i--){
        sufB[i]=sufB[i+1];
        sufZ[i]=sufZ[i+1];
        if(s[i]=='1') sufB[i]++;
        if(s[i]=='2') sufZ[i]++;
    }   


    for(int offset=0;offset<n-(2*t);offset++){
        int missedBefore = prefB[t+offset] + prefZ[t+offset] - prefZ[offset];
        int possibleBefore = prefZ[offset];
        // cout << "off:" << offset << "\n";
        for(int i=t+offset;i<=n-t;i++){
            int missedAfter = sufB[i] + sufZ[i] - sufZ[i+t];
            int possibleAfter = sufZ[i+t];
            if(missedAfter + missedBefore > k)
                continue;
            int actWyn = offset + n-(i+t) - max(0,possibleAfter + possibleBefore - (k-missedAfter-missedBefore));
            wyn = max(actWyn,wyn);
        }
    }

    if(k >= prefB[n]){
        wyn = max(wyn,n-max(0,prefZ[n]-(k-prefB[n])) );
    }
    cout << wyn << "\n";
}