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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 8005;

string s;
int n, k, t, best, dp[3][N][N], i, j, sum[N];

int go(int a, int b, int c) {
	//cout << a << " " << b << " " << c << endl;
	if (dp[a][b][c] != -1) return dp[a][b][c];
	int best = -1;
	if (a == 0 || a == 2) {
		if (s[c - 1] == '1' && b == 0) {
			dp[a][b][c] = -2;
			return -2;
		}
		if (s[c - 1] == '1') best = max(best, go(a, b - 1, c - 1) + 1);
		if (s[c - 1] == '2') {
			best = max(best, go(a, b, c - 1));
			if (b > 0) best = max(best, go(a, b - 1, c - 1) + 1);
		}
		if (s[c - 1] == '3') best = max(best, go(a, b, c - 1) + 1);
	}
	if (a == 1) {
		best = max(best, go(a, b, c - 1));
		if (c >= t && sum[c] - sum[c - t] <= b) best = max(best, go(0, b - (sum[c] - sum[c - t]), c - t));
	}
	if (a == 2) {
		if (c >= t && sum[c] - sum[c - t] <= b) best = max(best, go(1, b - (sum[c] - sum[c - t]), c - t));
	}
	if (best >= 0) dp[a][b][c] = best; else dp[a][b][c] = -2;
	return dp[a][b][c];
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k >> t >> s;
for (j=1;j<=n;j++) if (s[j - 1] == '1' || s[j - 1] == '2') sum[j] = sum[j - 1] + 1; else sum[j] = sum[j - 1];
for (i=0;i<=k;i++) {
	for (j=1;j<=n;j++) dp[0][i][j] = dp[1][i][j] = dp[2][i][j] = -1;
	dp[0][i][0] = dp[1][i][0] = dp[2][i][0] = -2;
}
dp[0][0][0] = 0;
best = -2;
for (i=0;i<=k;i++) {
	go(0, i, n);
	best = max(best, dp[0][i][n]);
	go(2, i, n);
	best = max(best, dp[2][i][n]);
}
if (best < 0) cout << "-1\n"; else cout << best << endl;
return 0;
}