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

const int MAXN = 8e3 + 7;
int pref[3][MAXN];

int main() {
    ios_base::sync_with_stdio(0);
    int n, k, t; cin >> n >> k >> t;
    string s; cin >> s;
    s = '#' + s;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 3; ++j) {
            pref[j][i] = pref[j][i - 1] + (s[i] - '0' - 1 == j);
        }
    }
    if (pref[0][n] <= k) {
        int good = pref[2][n];
        cout << min(good + k, n) << "\n";
        return 0;
    }
    int ans = -1;
    for (int i1 = 1; i1 <= n - t * 2 + 1; ++i1) {
        int nd1 = i1 + t - 1;
        for (int i2 = nd1 + 1; i2 <= n - t + 1; ++i2) {
            int nd2 = i2 + t - 1;
            int missed = pref[0][nd1] + (pref[0][n] - pref[0][i2 - 1]); // type1
            int missed2 = ((pref[1][nd1] - pref[1][i1 - 1]) + (pref[1][nd2] - pref[1][i2 - 1])); // type2
            if (missed + missed2 > k) continue;
            int good = pref[2][i1 - 1] + (pref[2][n] - pref[2][nd2]);
            int office = pref[0][i1 - 1] + (pref[0][n] - pref[0][nd2]);
            int left = (i1 - 1 + (n - nd2)) - good - office;
            ans = max(ans, good + office + min(left, k - missed - missed2));
        }
    }
    cout << ans << "\n";
}