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

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0); cin.tie(0);
	
	int n, k, t; cin>>n>>k>>t;
	string s; cin>>s;

	int best = -1;

	vector<int> rempref(n, 0), pref(n, 0), free(n, 0);
	if(s[0] == '2') rempref[0]++;
	else if(s[0] == '1') pref[0]++;
	else free[0]++;

	for(int i=1; i<n; i++){
		rempref[i] = rempref[i-1];
		pref[i] = pref[i-1];
		free[i] = free[i-1];
		if(s[i] == '2') rempref[i]++;
		if(s[i] == '1') pref[i]++;
		if(s[i] == '3') free[i]++;
	}

	int count = n - free[n-1];

	// 0 jumps
	if(max(0, count - k) <= rempref[n-1]){
		best = max(best, n - max(0, count - k));
	}

	//cout<<best;

	// 1 jump

	for(int i=0; i<=n-2*t; i++){
		for(int j=i+2*t-1; j<n; j++){
			int temp = 0;
			int inhome = 0;
			if(i != 0) temp += rempref[i-1];
			inhome += rempref[n-1] - rempref[j];
			inhome += rempref[j-t] - rempref[i+t-1];
			temp += pref[j-t] - pref[i+t-1];
			temp += inhome;
			
			//cout<<i<<" "<<j<<" "<<temp<<endl;

			if(temp >= count - k){
				int ans = 0;

				if(i != 0){
					ans += free[i-1];
					ans += pref[i-1];
				}

				ans += free[n-1] - free[j] + pref[n-1] - pref[j];

				int diff = temp - max(0, (count - k));
				int plus = min(inhome, diff);

				best = max(best, ans+plus);
			}
		}
	}


	cout<<best;
	return 0;
}