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

using namespace std;

int result(int budget, int work, int zoom, int free) {
	budget -= work;
	if (budget < 0) return -1;
	int skippaple = min(budget, zoom);
	return (skippaple + work + free);
}

int pref[3][8080];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k, t;
	cin >> n >> k >> t;
	string s;
	cin >> s;
	for(int i = 1; i <= n; i++) {
		if (s[i - 1] == '1') pref[0][i] = 1;
		else if (s[i - 1] == '2') pref[1][i] = 1;
		else if (s[i - 1] == '3') pref[2][i] = 1;
		pref[0][i] = pref[0][i] + pref[0][i - 1];
		pref[1][i] = pref[1][i] + pref[1][i - 1];
		pref[2][i] = pref[2][i] + pref[2][i - 1];
	}
	int res = -1;
	res = max(res, result(k, pref[0][n], pref[1][n], pref[2][n]));
	//cout << k << " " << pref[0][n] << " " << pref[1][n] << " " << pref[2][n] << " " << result(k, pref[0][n], pref[1][n], pref[2][n]) << "\n";
	for(int i = t + 1; i <= n; i++) {
		for(int j = i; j + t <= n; j++) {
			int budget = k;
			budget -= pref[0][i - 1] - pref[0][i - t - 1];
			budget -= pref[1][i - 1] - pref[1][i - t - 1];
			budget -= pref[0][j + t] - pref[0][j];
			budget -= pref[1][j + t] - pref[1][j];
			int work = pref[0][i - t - 1] + pref[0][n] - pref[0][j + t];
			int zoom = pref[1][i - t - 1] + pref[1][n] - pref[1][j + t];
			int free = pref[2][i - t - 1] + pref[2][n] - pref[2][j + t];
			res = max(res, result(budget, work, zoom, free));
			//cout << i << " " << j << " " << budget << " " << work << " " << zoom << " " << free << " " << result(budget, work, zoom, free) << "\n";
		}
	}
	cout << res << "\n";
	return 0;
}