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
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;

int N, K, T;
string S;

// index 0 indicates either an initial timestamp, or the
// hour beginning at the initial timestamp.

vector<int> meetings_after; // when do we begin to return home.
vector<int> meetings_before; // when do we depart to work.

int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> N >> K >> T;
	cin >> S;

	int meetings_value = 0;
	for(int k = T - 1; k < N; k++){
		if(S[k] == '2'){
			meetings_value++;
		}
	}
	for(int j = 0; j <= N - T; j++){
		if(S[j + T - 1] == '2'){
			meetings_value--;
		}
		meetings_after.push_back(meetings_value);
	}

	meetings_value = 0;
	for(int i = 0; i <= N - T; i++){
		meetings_before.push_back(meetings_value);
		if(S[i] == '2'){
			meetings_value++;
		}
	}

	int ANS = -1; // max amount of hours we can spend time productively (i.e. solving PA problems)
	meetings_value = 0; // calculate total amount of meetings in office
	for(int k = 0; k < N; k++){
		if(S[k] == '1'){
			meetings_value++;
		}
	}

	if(meetings_value <= K){
		// now calculate the TOTAL amount of meetings.
		for(int k = 0; k < N; k++){
			if(S[k] == '2'){
				meetings_value++;
			}
		}
		if(meetings_value <= K){
			ANS = N;
		} else {
			ANS = max(ANS, N - (meetings_value - K));
		}
		cout << ANS << endl;
		return 0;
	} else {
		// now calculate the TOTAL amount of meetings (again)
		for(int k = 0; k < N; k++){
			if(S[k] == '2'){
				meetings_value++;
			}
		}
	}
	int total_meetings = meetings_value;

	// and finally, consider all possible times of visiting and departing to/from the office.
	for(int i = 0; i <= N - 2*T; i++){
		int hours_spent_on_meetings_at_home = max(0, total_meetings - K);
		for(int j = i + T; j <= N - T; j++){
			if(meetings_before[i] + meetings_after[j] >= hours_spent_on_meetings_at_home){
				ANS = max(ANS, i + (N - T - j) - hours_spent_on_meetings_at_home);
			}
			if(S[j] != '3' && hours_spent_on_meetings_at_home > 0){
				hours_spent_on_meetings_at_home--;
			}
		}
	}

	// BAM, done.
	cout << ANS << endl;
}