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

int n, k, t;
string s;

const int N = 8008, oo = 1e8;
int c[N][3], dp[N][N][3];

int rec(int i, int j, int h) {
    if (i > n || j > k || h > 2) return -oo;
    if (i == n) return h == 1 ? -oo : 0;
    int &res = dp[i][j][h];
    if (res == -1) {
        res = -oo;
        if (h < 2 && i+t <= n) {
            int cost = c[i+t][0]-c[i][0] + c[i+t][1]-c[i][1];
            res = max(res, rec(i+t, j+cost, h+1));
        }
        if (h != 1) {
            res = max(res, 1 + rec(i+1, j + (s[i] != '3'), h));
        }
        res = max(res, rec(i+1, j + (s[i] == '1' && h != 1), h));
    }
    return res;
}

int main() {
    cin >> n >> k >> t >> s;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            c[i+1][j] = c[i][j] + (s[i] == '1'+j);
        }
    }

    memset(dp, -1, sizeof dp);
    int res = rec(0, 0, 0);
    if (res < 0) res = -1;
    cout << res << '\n';
}