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

#define ll long long
#define fors(u, n, s) for(ll u = (s); u < (n); u++)
#define foru(u, n) fors(u, n, 0)

using namespace std;

const int N = 8100;
int n, k, t;

int chores_goal;

int chores[N];

int remote_chores_prefix[N];
int all_chores_prefix[N];

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

	cin >> n >> k >> t;

	foru(i, n){
		char c; cin >> c; chores[i] = c - '0';
	}

	chores_goal = -k;

	foru(i, n) if (chores[i] != 3) chores_goal ++;

	chores_goal = max(chores_goal, 0);

	remote_chores_prefix[0] = 0;
	all_chores_prefix[0] = 0;

	fors(i, n+1, 1) {
		remote_chores_prefix[i] = remote_chores_prefix[i-1] + (chores[i-1] == 2);
		all_chores_prefix[i] = all_chores_prefix[i-1] + (chores[i-1] != 3);
	}
	
	if(remote_chores_prefix[n] >= chores_goal){
		cout << n-chores_goal;
		return 0;
	}

	int output = -1;

	foru(i, n) fors(j, n, i+2*t) {
		int t_a = i; // first hour of travel
		int t_b = i+t; // first hour of work
		int t_c = j-t; // last hour of work
		int t_d = j; // last hour of travel

		int chores_at_work = all_chores_prefix[t_c + 1] - all_chores_prefix[t_b];
		int chores_at_home = remote_chores_prefix[t_a];
		chores_at_home += remote_chores_prefix[n] - remote_chores_prefix[t_d + 1];

		//cout << "for [" << i << " " << j << "]: chores at work " << chores_at_work << endl;
		//cout << "times " << t_a << " " << t_b << " " << t_c << " " << t_d << endl;
		

		if (chores_at_home + chores_at_work < chores_goal) continue;

		int chore_goal_at_home = chores_goal - chores_at_work;
		int time_at_home = t_a + (n-1-t_d);

		output = max(output, time_at_home - chore_goal_at_home);
	}

	cout << output;

    return 0;
}