#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. */
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. */ |