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
//#ifdef DEBUG
//#define _GLIBCXX_DEBUG
//#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#else
#define debug(...) 228
#endif

#define pb push_back

typedef long long ll;
typedef long double ld;

const int maxN = 8005;
int dp[maxN][maxN][3];
int n, k, t;
int val[maxN];
inline void umax(int& a, const int b) {
    a = max(a, b);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    auto start = std::chrono::high_resolution_clock::now();
    cin >> n >> k >> t;
    string s;
    cin >> s;
    int meets = 0;
    for (int i = 0; i < n; i++) {
        val[i] = s[i] - '0';
        if (val[i] == 1 || val[i] == 2) meets++;
    }
    const int INF = 1e9;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int z = 0; z < 3; z++) {
                dp[i][j][z] = -INF;
            }
        }
    }
    dp[0][0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int flag = 0; flag < 3; flag++) {
                if (dp[i][j][flag] < 0) continue;
                if (i + t <= n && flag != 2) umax(dp[i + t][j][flag + 1], dp[i][j][flag]);
                if (flag != 1) {
                    umax(dp[i + 1][j][flag], dp[i][j][flag] + 1);
                    if (val[i] == 2) umax(dp[i + 1][j + 1][flag], dp[i][j][flag]);
                }
                else {
                    umax(dp[i + 1][j][flag], dp[i][j][flag]);
                    if (val[i] == 1 || val[i] == 2) umax(dp[i + 1][j + 1][flag], dp[i][j][flag]);
                }
            }
        }
    }
    int best = -1;
    for (int cnt = 0; cnt <= meets; cnt++) {
        if (cnt >= meets - k) umax(best, dp[n][cnt][0]);
        if (cnt >= meets - k) umax(best, dp[n][cnt][2]);
    }
    cout << best << '\n';

    auto end = std::chrono::high_resolution_clock::now();
    std::cerr << "Execution Time: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
              << " ms" << std::endl;

    return 0;
}