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

int binsercz(int maxopu, const vector<int> &v, int tpod, int p)
{
    p++;
    int k = v.size() - tpod;
    if (v[k] > maxopu)
        return -1;
    while (p < k)
    {
        int sr = (p + k) / 2;
        if (v[sr] > maxopu)
        {
            p = sr + 1;
        }
        else
            k = sr;
    }
    return p;
}
int main()
{
    int n, k, tpod;
    string s;
    cin >> n >> k >> tpod >> s;
    vector<int> struktura(n + 1, 0);
    int l1 = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1')
            l1++;
    }
    s = "3" + s;
    struktura[1] = l1;
    for (int i = 1; i < tpod; i++)
    {
        if (s[i] == '2')
        {
            struktura[1]++;
        }
    }
    // cout<<struktura[1]<< " "<<s<<" ";
    for (int i = 1; i <= n - tpod + 1; i++)
    {
        if (i != 1)
            struktura[i] = struktura[i - 1];
        if (s[i + tpod - 1] == '2')
            struktura[i]++;
        if (s[i - 1] != '3')
            struktura[i]--;
    }
    for (int i = 2; i <= n - tpod + 1; i++)
    {
        struktura[i] = min(struktura[i], struktura[i - 1]);
    }
    // for (int i = 1; i <= n; i++)
    // {

    //     cout << i << "|" << struktura[i] << " ";
    // }
    // cout << "\n";
    int lopu = 0;
    for (int i = 1; i < tpod; i++)
    {
        if (s[i] != '3')
            lopu++;
    }
    vector<vector<int>> sumy(n + 1, vector<int>(4, 0));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= 3; j++)
            sumy[i][j] = (int)(s[i] == ('0' + j)) + sumy[i - 1][j];
    }
    int lspb = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '1')
            lspb++;
    }
    if (lspb <= k)
    {
        cout << sumy[n][3] + min(n - sumy[n][3], k);
        return 0;
    }
    int wyn = -1;
    for (int i = tpod; i <= n - tpod; i++)
    {
        lopu += (s[i] != '3') - (s[i - tpod] == '2');
        int indpow = binsercz(k - lopu, struktura, tpod, i);
        if (indpow != -1)
        {
            //cout << "p|" << i << " ";
            if (indpow == i + 1)
            {
                wyn = sumy[n][3] + min(n - sumy[n][3], k);
            }
            int x = sumy[i - tpod][3] + sumy[n][3] - sumy[indpow + tpod - 1][3];
            //cout << x << " lopu " << lopu << " stindpow " << struktura[indpow] << "\n";
            wyn = max(wyn, x + min(k - (sumy[i][2] + sumy[i][1] - sumy[i - tpod][2] - sumy[i - tpod][1] + sumy[indpow + tpod - 1][2] + sumy[indpow + tpod - 1][1] - sumy[indpow-1][2] - sumy[indpow-1][1]), i - tpod + n - (indpow + tpod - 1) - x));
        }
    }
    cout << wyn;
}