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
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto operator<<(auto&o, auto p)->decltype(p.first, o){return o<<'('<<p.first<<", "<<p.second<<')';}
auto operator<<(auto&o, auto x)->decltype(x.end(), o){o<<'{';int i=2;for (auto e:x)o<<(", ")+i<<e,i=0;return o<<'}';}
#define LOG(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X);
#else
#define LOG(X...)(void)0
#endif

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k, t;
    cin >> n >> k >> t;
    vector<char> values(n);
    for (int i = 0; i < n; i++) {
        cin >> values[i];
        values[i] -= '0';
    }

    vector<int> prefs(n);
    vector<int> prefz(n);
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            prefs[i] = prefs[i - 1];
            prefz[i] = prefz[i - 1];
        }
        if (values[i] == 1)
            prefs[i]++;
        else if (values[i] == 2)
            prefz[i]++;
    }

    auto gps = [&](int l, int r) {
        if (r < 0)
            return 0;
        int ret = prefs[r];
        if (l > 0)
            ret -= prefs[l-1];
        return ret;
    };
    auto gpz = [&](int l, int r) {
        if (r < 0)
            return 0;
        int ret = prefz[r];
        if (l > 0)
            ret -= prefz[l-1];
        return ret;
    };
    auto gpw = [&](int l, int r) {
        if (r < 0)
            return 0;
        int dis = r - l + 1;
        dis -= gps(l, r);
        dis -= gpz(l, r);
        return dis;
    };
    int maxi = -1;
    if (gps(0, n-1) <= k) {
        // nie chcemy jechać :O
        int c2 = 0;
        for (int i = 0; i < n; i++) {
            if (values[i] == 3)
                c2++;
        }
        maxi = max(maxi, c2);
    }

    for (int df = 0; df < n; df++) {
        for (int ds = df + t; ds <= n - t; ds++) {
            int now = gps(0, df + t - 1) + gps(ds, n-1) + gpz(df, df + t - 1) + gpz(ds, ds + t - 1);
            if (now <= k)
                maxi = max(maxi, gpw(0, df - 1) + gpw(ds + t, n-1) + k - now);
        }
    }
    cout << maxi << "\n";
}