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
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,l,r) for(int i = (l); i <= (r); i++)
#define FORD(i,l,r) for(int i = (l); i >= (r); i--)

int pref1[8'018];
int pref2[8'018];
int pref3[8'018];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,maxk,dist;
    cin >> n >> maxk >> dist;
    string s;
    cin >> s;
    pref1[0]=0;
    pref2[0]=0;
    pref3[0]=0;
    FOR(i,1,n){
        pref1[i] = pref1[i-1] + (s[i-1]=='1');
        pref2[i] = pref2[i-1] + (s[i-1]=='2');
        pref3[i] = pref3[i-1] + (s[i-1]=='3');
    }
    pref1[n+1]=pref1[n];
    pref2[n+1]=pref2[n];
    pref3[n+1]=pref3[n];
    pref1[n+2]=pref1[n+1];
    pref2[n+2]=pref2[n+1];
    pref3[n+2]=pref3[n+1];
    pref1[n+3]=pref1[n+2];
    pref2[n+3]=pref2[n+2];
    pref3[n+3]=pref3[n+2];
    pref1[n+4]=pref1[n+3];
    pref2[n+4]=pref2[n+3];
    pref3[n+4]=pref3[n+3];
    int wyn=-1;
    FOR(i,1,n-dist+1){
        FOR(j,i+dist,n-dist+1){
            //cerr << "(" << i << ',' << j << ')' << '\n';
            int i_start = i;
            int i_end = i_start+dist-1;

            int j_start=j;
            int j_end = j_start+dist-1;

            int skipped=0;
            skipped += pref1[j_end]-pref1[j_start-1];
            skipped += pref2[j_end]-pref2[j_start-1];
            skipped += pref1[i_end]-pref1[i_start-1];
            skipped += pref2[i_end]-pref2[i_start-1];
            
            skipped += pref1[i_start-1]-pref1[0];
            skipped += pref1[n]-pref1[j_end];

            int possiblities_now = 0;
            possiblities_now += pref3[i_start-1]-pref3[0];
            possiblities_now += pref3[n]-pref3[j_end];
            possiblities_now += pref1[i_start-1]-pref1[0];
            possiblities_now += pref1[n]-pref1[j_end];

            int works_now = 0;
            works_now += pref2[i_start-1]-pref2[0];
            works_now += pref2[n]-pref2[j_end];

            int max_skips_now = maxk-skipped;
            
            if(max_skips_now < 0) continue;
            int wyn_now = possiblities_now + min(works_now,max_skips_now);
            wyn = max(wyn, wyn_now);
        }
    }

    int skipped= pref1[n]-pref1[0];
    int possiblities_now = pref3[n]-pref3[0] + pref1[n]-pref1[0];
    int works_now = pref2[n]-pref2[0];
    int max_skips_now = maxk-skipped;
    if(max_skips_now >= 0){
        int wyn_now = possiblities_now + min(works_now,max_skips_now);
        wyn = max(wyn, wyn_now);
    }

    cout << wyn;
}