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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
constexpr int maxn = 8e3 + 7;
using namespace std;
typedef struct{
    int office;
    int remote;
    int solved;
} segm;
segm from_left[maxn];
segm from_right[maxn];
segm get_val(segm l, segm r){
    segm rans;
    rans.office = r.office - l.office;
    rans.remote = r.remote - l.remote;
    rans.solved = r.solved - l.solved;
    return rans;
}
int n,k,t,ans;
string s;
int eval_segm(int l, int r){
   // if(n - t < r){return -1;}
   // if(l < t){return - 1;}
    int L = r - l + 1;
    if(L < 2*t){return -1;}
    segm l_l = get_val(from_left[l-1], from_left[l + t - 1]);
    segm r_r = get_val(from_right[r+1], from_right[r - t + 1]);
    int skipped = l_l.office + l_l.remote + r_r.office + r_r.remote + from_left[l-1].office + from_right[r+1].office;
    if(skipped > k){
        return -1;
    }
    int res = from_left[l-1].solved + from_right[r+1].solved;
    res += from_left[l-1].office + from_right[r+1].office;
    res += min(k-skipped, from_right[r+1].remote+from_left[l-1].remote);
    return res;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k>>t>>s;
    from_left[0].office = 0;
    from_left[0].remote = 0;
    from_left[0].solved = 0;
    from_right[n+1].office = 0;
    from_right[n+1].remote = 0;
    from_right[n+1].solved = 0;
    for(int i = 1; i <= n; i++){
        from_left[i] = from_left[i-1];
        if(s[i-1] == '1'){
            from_left[i].office++;
        }else if(s[i-1] == '2'){
            from_left[i].remote++;
        }else{
            from_left[i].solved++;
        }
    }
    for(int i = n; i >= 1; i--){
        from_right[i] = from_right[i+1];
        if(s[i-1] == '1'){
            from_right[i].office++;
        }else if(s[i-1] == '2'){
            from_right[i].remote++;
        }else{
            from_right[i].solved++;
        }
    }
    // for(char c : s){
    //     cerr<<c<<" ";
    // }
    // cerr<<endl;
    // for(int i = 1; i <= n; i++){
    //     cerr<<from_left[i].office<<" ";
    // }
    // cerr<<endl;
    // for(int i = 1; i <= n; i++){
    //     cerr<<from_left[i].remote<<" ";
    // }
    // cerr<<endl;
    // for(int i = 1; i <= n; i++){
    //     cerr<<from_left[i].solved<<" ";
    // }
     int ANS = -1;
    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            ANS = max(ANS, eval_segm(i,j));
           // cerr<<" i "<<i<<" j "<<j<<endl;
            if(eval_segm(i,j) != -1){
            //cerr<<eval_segm(i,j)<<endl;
            }
        }
    }
    if(from_left[n].office <= k){
        ANS = max(ANS, from_left[n].solved + from_left[n].office + min(k - from_left[n].office,from_left[n].remote));
    }
    // cerr<<endl;
    // cerr<<"s 4 8 : "<<eval_segm(4,8)<<endl;
    // cerr<<"ans: ";
    cout<<ANS<<endl;
    return 0;
}