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

ll n, k, t;
string s;

ll bez_pracy() {
	ll odp = 0;
	int opuszczone = 0;
	int naprawic = 0;
	for(int i=0; i<n; ++i) {
		if(s[i]=='3') odp++;
		else if(s[i]=='2') {
			opuszczone++;
			naprawic++;
			odp++;
		} else {
			opuszczone++;
			odp++;
		}
	}
	if(opuszczone-naprawic > k) return -1;
	if(opuszczone > k) odp -= opuszczone-k;
	return odp;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> k >> t >> s;
	ll ans = -1;	
	ans = max(ans, bez_pracy());
	vector<vector<int>> prefix(n+1, vector<int>(4, 0));
	for(int i=1; i<=n; ++i) {
		prefix[i][1] = prefix[i-1][1] + (s[i-1]=='1');
		prefix[i][2] = prefix[i-1][2] + (s[i-1]=='2');
		prefix[i][3] = prefix[i-1][3] + (s[i-1]=='3');
	}
	for(int i=1; i<=n-(2*t)+1; ++i) {
		for(int j=i+t; j<=n-t+1; ++j) {
			ll odp = 0;
			int odpuszcz = 0;
			int napr = 0;
			// W domu 1
			odp += prefix[i-1][1]; odpuszcz += prefix[i-1][1];
			odp += prefix[i-1][2]; odpuszcz += prefix[i-1][2]; napr += prefix[i-1][2];
			odp += prefix[i-1][3];
			//Dojazd
			odpuszcz += prefix[i+t-1][1]-prefix[i-1][1]+prefix[i+t-1][2]-prefix[i-1][2];
			// W pracy - brak
			//Powrot
			odpuszcz += prefix[j+t-1][1]-prefix[j-1][1]+prefix[j+t-1][2]-prefix[j-1][2];
			// W domu 2
			odp += prefix[n][1]-prefix[j+t-1][1]; odpuszcz += prefix[n][1]-prefix[j+t-1][1];
			odp += prefix[n][2]-prefix[j+t-1][2]; odpuszcz += prefix[n][2]-prefix[j+t-1][2]; napr += prefix[n][2]-prefix[j+t-1][2];
			odp += prefix[n][3]-prefix[j+t-1][3];

			if(odpuszcz-napr > k) continue;
			if(odpuszcz > k) odp -= odpuszcz-k;
			ans = max(ans, odp);
		}
	}
	cout << ans << "\n";

	return 0;
}