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
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const short N = 8001;
short p[4][N];

short max_short(short a, short b){
	if(a < b)return b;
	return a;
}

main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	short n, k, t;
	cin >> n >> k >> t;
	string s;
	cin >> s;
	for(short i = 0; i < n; ++i) { p[0][i] = p[1][i] = p[2][i] = 0;}

	for(short i = 0; i < n; ++i){ p[1][i+1] = (s[i] == '1') + p[1][i]; }
	for(short i = 0; i < n; ++i){ p[2][i+1] = (s[i] == '2') + p[2][i]; }
	for(short i = 0; i < n; ++i){ p[3][i+1] = (s[i] == '3') + p[3][i]; }
	bool pos = 0;
	short maks = 0;
	if(p[1][n] <= k){
		pos = 1;
		short y = k-p[1][n];
		short q = max_short((short)p[2][n] - (short)y, (short)0);
		maks = max_short((short)maks, (short)n - q);
	}
	{
		function <short(short,short,short)> f0 = [](short od, short dokad, short licz){
			return p[licz][dokad] - p[licz][od-1];
			/*if(licz == 1)return p[1][dokad] - p[1][od-1];
			if(licz == 2)return p[2][dokad] - p[2][od-1];
			return p[3][dokad] - p[3][od-1];*/
		};

		function <short(short,short,short)> f = [](short od, short dokad, short licz){
			if(dokad < od)return 0;
			return p[licz][dokad] - p[licz][od-1];
			/*if(licz == 1)return p[1][dokad] - p[1][od-1];
			if(licz == 2)return p[2][dokad] - p[2][od-1];
			return p[3][dokad] - p[3][od-1];*/
		};
		for(short i = 1; i+2*t-2 <= n; ++i){
			short a = f0(i, i+t-1, 1);
			short b = f0(i, i+t-1, 2);
			short c = f(1, i-1, 1);
			short d = f(1, i-1, 2);
			short e = f(1, i-1, 3);
			
			for(short j = i+2*t-2; j <= n; ++j){
				if(i+t-1 >= j-(t-1))continue;
				short missed = 0;
				missed += a;
				missed += b;
				missed += f0(j-(t-1),j, 1);
				missed += f0(j-(t-1),j, 2);
				//can_miss = k-missed;
				short ile1 = c;
				ile1 += f(j+1, n, 1);
				
	
				missed += ile1;

				short can_miss = k - missed;
	
				short ile3 = e;
				ile3 += f(j+1, n, 3);
				
				short ile2 = d;
				ile2 += f(j+1, n, 2);
			
				
				short work_time = ile3 + ile1 + min(ile2, can_miss);
				if(can_miss < 0)continue;
				pos = 1;
				maks = max_short(maks, work_time);
			}
		}
		if(!pos)maks = -1;
		cout << maks << '\n';
	}
}