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

using namespace std;

#define ll long long 
#define ld long double

const int N = 1e4;
int tree[N];

int lsb(int x) {
    return x & (-x);
}

void add(int v, int x) {
    while (v < N) {
        tree[v] = max(tree[v], x);
        v += lsb(v);
    }
}

int query(int v) {
    int ans = -1;
    while (v) {
        ans = max(ans, tree[v]);
        v -= lsb(v);
    }
    return ans;
}
 

int main () {
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);

    for (int i = 0; i < N; i++) tree[i] = -1;

    int n, k, t;
    cin >> n >> k >> t;

    int ans = -1;
    string S;
    cin >> S;
    S = "-" + S;

    vector<vector<int>> pref(4, vector<int>(n + 1, 0));
    for (int k = 1; k < 4; k++) for (int i = 1; i <= n; i++) pref[k][i] = pref[k][i - 1] + (S[i] == ('0' + k) ? 1 : 0);

    for (int j = t + 1; j + t <= n; j++) {
        add(pref[1][j - 1] + pref[2][j - 1] - pref[2][j - t - 1] + 1, j);

        int skipped = pref[1][n] - pref[1][j] + pref[2][j + t] - pref[2][j];
        if (skipped > k) continue;

        int i = query(k - skipped + 1);
        if (i == -1) continue;

        skipped += pref[1][i - 1] + pref[2][i - 1] - pref[2][i - t - 1];

        int A[4];
        for (int k = 2; k <= 3; k++) A[k] = pref[k][i - t - 1] + pref[k][n] - pref[k][j + t];

        int programmed = pref[1][i - t - 1] + pref[1][n] - pref[1][j + t];
        programmed += A[3];
        programmed += min(A[2], k - skipped);

        ans = max(ans, programmed);
    }

    if (pref[1][n] <= k) {
        ans = max(ans, pref[3][n] + pref[1][n] + min(pref[2][n], k - pref[1][n]));
    }

    cout << ans;

    return 0;
}