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
#include <iostream>

using namespace std;

const int MAX_N = 8000;

int n, k, t;
string s;
int dynamic_sum[MAX_N + 1][3];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k >> t;
	cin >> s;
	dynamic_sum[0][s[0] - '1'] = 1;
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < 3; ++j)
			dynamic_sum[i][j] = dynamic_sum[i - 1][j];
		dynamic_sum[i][s[i] - '1'] = dynamic_sum[i - 1][s[i] - '1'] + 1;
	}

	int max_coding_time = -1;

	if ((k - dynamic_sum[n - 1][0]) >= 0) {
		int remain = k - dynamic_sum[n - 1][0];
		int coding_time = dynamic_sum[n - 1][2] + dynamic_sum[n - 1][0] + min(remain, dynamic_sum[n - 1][1]);
		max_coding_time = max(max_coding_time, coding_time);
	}

	for (int start = 0; start <= n - 2 * t; ++start) {
		for (int end = start + t; end <= n - t; ++end) {
			int meetings_offline_left = dynamic_sum[n-1][0] - (dynamic_sum[end - 1][0] - dynamic_sum[start + t - 1][0]);
			int meetings_online_left = dynamic_sum[end + t - 1][1] - dynamic_sum[end - 1][1];
			if (start > 0)
				meetings_online_left += dynamic_sum[start + t - 1][1] - dynamic_sum[start - 1][1];
			else
				meetings_online_left += dynamic_sum[start + t - 1][1];

			int meetings_offline_at_home = dynamic_sum[n - 1][0];
			int meetings_online_at_home = dynamic_sum[n - 1][1];
			int coding_at_home = dynamic_sum[n - 1][2];
			if (start > 0) {
				meetings_offline_at_home -= (dynamic_sum[end + t - 1][0] - dynamic_sum[start - 1][0]);
				meetings_online_at_home -= (dynamic_sum[end + t - 1][1] - dynamic_sum[start - 1][1]);
				coding_at_home -= (dynamic_sum[end + t - 1][2] - dynamic_sum[start - 1][2]);
			}
			else {
				meetings_offline_at_home -= dynamic_sum[end + t - 1][0];
				meetings_online_at_home -= dynamic_sum[end + t - 1][1];
				coding_at_home -= dynamic_sum[end + t - 1][2];
			}
			
			int remain = k - meetings_online_left - meetings_offline_left;

			if (remain < 0)
				continue;
			int coding_time = coding_at_home + meetings_offline_at_home + min(remain, meetings_online_at_home);
			max_coding_time = max(max_coding_time, coding_time);

			/*cout << start << ", " << end << endl;
			cout << remain << " " << meetings_offline_left << " " << meetings_online_left << " " << meetings_online_at_home << " " << meetings_offline_at_home << " " << coding_at_home << endl;
			cout << coding_time<<endl;
			cout << s << endl;
			for (int x = 0; x < s.size(); ++x) {
				if (x == start || x == end)
					cout << "^";
				else if ((x > start && x < (start + t)) || (x > end && x < (end + t)))
					cout << "+";
				else
					cout << "-";
			}
			cout << endl<<endl;*/
		}
	}
	cout << max_coding_time << endl;
	return 0;
}