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
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);cin.tie();
	int n,k,t; cin >> n >> k >> t;
	string s; cin >> s;

	int home[n+1],klepanie[n+1];	//home[n] - prefix sum of hours that we will miss;	klepanie[n] - prefix sum of klepanie zadan
	home[0]=0;		home[1] = (s[0]=='1' ? 1 : 0);
	klepanie[0]=0;	klepanie[1] = (s[0]=='3' ? 1 : 0);
	for(int x=2;x<=n;x++){
		home[x] = home[x-1]+(s[x-1]=='1' ? 1 : 0);
		klepanie[x] = klepanie[x-1] + (s[x-1]=='3' ? 1 : 0);
	}

	int drive[n];  //drive[n] - how many hours we will miss when starting to drive at hour n;
	drive[0]=0;		drive[1]=0;
	for(int x=0;x<t;x++){
		if(s[x]!='3')
			drive[1]++;
	}
	for(int x=2;x<=n-t+1;x++){
		drive[x] = drive[x-1] - (s[x-2]!='3' ? 1 : 0) + (s[x+t-2]!='3' ? 1 : 0);
	}


	int res=-1,lhc=0,khc=0,dwojki=0; 		//lhc <-> losthourscount
	for(int x=0;x<n;x++){
		if(s[x]=='1')
			lhc++;
		else if(s[x]=='3')
			khc++;
	}
	khc+=min(n-khc,k);
	if(lhc<=k)
		res=khc;
	
	for(int a=0;a<n-2*t+1;a++){
		for(int b=a+t;b<n-t+1;b++){
			lhc=home[a] + drive[a+1] + 0 + drive[b+1] + (home[n]-home[b+t]);
			khc=klepanie[a] + 						(klepanie[n]-klepanie[b+t]);
			khc += min((a+(n-b-t)-khc),k-drive[a+1]-drive[b+1]);
			/*cout << "MEOW\n" << a << ' ' << b << '\n';
			cout << lhc << ' ' << khc << '\n';*/
			if(lhc <= k)
				res=max(res,khc);
			/*if(lhc <= k && khc==52){
				cout << a << ' ' << b;
			}*/
		}
	}

	cout << res;
	cout << '\n';




	/*cout << "HOME:\n";
	for(int x=0;x<=n;x++){
		cout << home[x] << ' ';
	}
	cout << "\nKlepanie:\n";
	for(int x=0;x<=n;x++){
		cout << klepanie[x] << ' ';
	}
	cout << "\nDrive:\n";
	for(int x=0;x<=n-t+1;x++){
		cout << drive[x] << ' ';
	}*/
}