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
#include<bits/stdc++.h>

int main(){
	using namespace std;
	ios::sync_with_stdio(false), cin.tie(nullptr);
	
	int n, k, t;
	cin >> n >> k >> t;

	vector<char> s(n + 1);
	vector<vector<int>> p(3, vector<int> (n + 1));
	for(int i = 1;i <= n;i++){
		cin >> s[i];
		p[int(s[i] - '1')][i] = 1;
		for(int r = 0;r <= 2;r++) p[r][i] += p[r][i - 1];
	}
	
	auto ileSpotkan = [&](int l, int r, int typ)->int{
		assert(r <= n);
		assert(l >= 1);
		if(l > r) return 0;
		return p[typ][r] - p[typ][l - 1];
	};
	
	int ans = -1;
	
	for(int l = t + 1;l <= n - t;l++){
		for(int r = l;r <= n - t;r++){
			int missed = ileSpotkan(l - t, l - 1, 0) + ileSpotkan(l - t, l - 1, 1) + ileSpotkan(r + 1, r + t, 0) + ileSpotkan(r + 1, r + t, 1);
			missed += ileSpotkan(1, l - t - 1, 0);
			missed += ileSpotkan(r + t + 1, n, 0);
			if(missed > k) continue;
			int delta = ileSpotkan(1, l - t - 1, 0) + ileSpotkan(r + t + 1, n, 0); // bo skoro nie może być w biurze to będzie rozwiązywał
			delta += ileSpotkan(1, l - t - 1, 2) + ileSpotkan(r + t + 1, n, 2);
			delta += min(k - missed, ileSpotkan(1, l - t - 1, 1) + ileSpotkan(r + t + 1, n, 1));
			ans = max(ans, delta);
		}
	}
	
	if(p[0][n] <= k){ // nie trzeba iść do pracy
		ans = max(ans, n - max(0, p[1][n] - k));
	}
	
	cout << ans << '\n';
	
	return 0;
}

/*
UWAGA!

- Do biura może pojechać co najwyżej jeden raz.
- Do domu musi wrócić przed upływem n-tej bajtogodziny.
- Jazda zajmuje mu t bajtogodzin.

Dom: 
  - nie może 1
  - może 2
  - może 3
Droga:
	- nie może nic
Biuro:
	- może 1, 2
	- NIE MOŻE 3

NIE MOŻE OPUSĆIĆ WIĘCEJ NIŻ K SPOTKANIA.
*/