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
#include <iostream>
using namespace std;

const int inf = 1e9 + 13, mxN = 8013;
int pref1[mxN], pref2[mxN];
int n, k, t;
string s;
void genpref()
{
    pref1[0] = s[0] == '1', pref2[0] = s[0] == '2';
    for(int i = 1; i < n; i++)
        pref1[i] = pref1[i - 1] + (s[i] == '1'), pref2[i] = pref2[i - 1] + (s[i] == '2');
}
int przed(int* tab, int p, int l)
{
    if(l < p)
        return 0;
    if(p == 0)
        return tab[l];
    return tab[l] - tab[p - 1];
}
int spr(int p, int l)
{
    int K = k, ileDom = 0, ileH = n - (l - p + 1);;
    if(p != -1)
    {
        if(l - p + 1 < 2 * t)
            return -1; 
        
        /*for(int i = 0; i < t; i++)
            K -= (s[p + i] != '3');
        for(int i = t - 1; i >= 0; i--)
            K -= s[l - i] != '3';*/
        K -= przed(pref1, p, p + t - 1);
        K -= przed(pref2, p, p + t - 1);
        K -= przed(pref1, l - t + 1, l);
        K -= przed(pref2, l - t + 1, l);
        
    }
    else
        l = -1, ileH = n;

    /*for(int i = 0; i < p; i++)
        K -= s[i] == '1', ileDom += s[i] == '2', ileH++;
    for(int i = l + 1; i < n; i++)
        K -= s[i] == '1', ileDom += s[i] == '2', ileH++;*/
    K -= przed(pref1, 0, p - 1);
    K -= przed(pref1, l + 1, n - 1);
    ileDom += przed(pref2, 0, p - 1);
    ileDom += przed(pref2, l + 1, n - 1);

    if(K < 0)
        return -1;
    return ileH - max(ileDom - K, 0);
    
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k >> t >> s;
    genpref();
    int mn = -1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            mn = max(spr(i, j), mn);
    cout << max(mn, spr(-1, -1)) << '\n';
    
    
}