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

const int MAXN = 8e3+2;

int n, k, t;
string d;

int total_meet_cnt;
int online_meet_sum[MAXN], offline_meet_sum[MAXN];

int meet_cnt_home(int l, int r) {
	if (r < l) return 0;
	return online_meet_sum[r] - online_meet_sum[l - 1];
}

int meet_cnt_work(int l, int r) {
	if (r < l) return 0;
	return offline_meet_sum[r] - offline_meet_sum[l - 1] +
			online_meet_sum[r] - online_meet_sum[l - 1];
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k >> t >> d;
	d = "#" + d;
	
	for (int i = 1; i <= n; i++)
		offline_meet_sum[i] = offline_meet_sum[i - 1] + (d[i] == '1');
	
	for (int i = 1; i <= n; i++)
		online_meet_sum[i] = online_meet_sum[i - 1] + (d[i] == '2');
		
	total_meet_cnt = offline_meet_sum[n] + online_meet_sum[n];
		
	int ans = -1;
	
	//not going to work
	if (total_meet_cnt - online_meet_sum[n] <= k)
		ans = n - max(0, total_meet_cnt - k);
	
	//going to work
	for (int l_work = t + 1; l_work <= n; l_work++) {
		for (int r_work = l_work; r_work <= n - t; r_work++) {
			int at_home, at_work;
			
			at_home = meet_cnt_home(1, l_work - t - 1) + 
						meet_cnt_home(r_work + t + 1, n);
			at_work = meet_cnt_work(l_work, r_work);
								
			if (total_meet_cnt - at_home - at_work > k) continue;
			
			at_home = max(0, total_meet_cnt - k - at_work);
			
			ans = max(ans, max(0, l_work - t - 1) + 
							max(0, n - r_work - t) - at_home);
		}
	}
	
	cout << ans;
}