// https://sio2.mimuw.edu.pl/c/pa-2025-1/p/pra/ #include <bits/stdc++.h> #define st first #define nd second #define pb push_back #define all(x) x.begin(), x.end() #define rep(i, a) for (int i = 0; i < int(a); i++) #define rep1(i, a) for (int i = 1; i <= int(a); i++) #define los(a, b) (rng() % (int)(b - a + 1) + (int)(a)) using namespace std; typedef long long ll; typedef pair<int, int> pi; const int MAXN = 8005; int pref[3][MAXN]; int n, k, t; int ans(int a, int b) { // przedzial w firmie // cerr << "ans " << a << ' ' << b << '\n'; int skip = pref[0][a - 1] + pref[0][n] - pref[0][b]; // cerr << " " << skip << "\n"; skip += pref[1][a - 1] - pref[1][a - t - 1] + pref[1][b + t] - pref[1][b]; // cerr << " " << skip << "\n"; if (skip > k) return -1; // cerr << pref[2][a - t - 1] << "+" << pref[2][n] << "-" << pref[2][b + t] // << " + " // << min(k - skip, pref[0][a - t - 1] + // (pref[0][n] - pref[0][b + t + 1]) + // (pref[0][a - 1] + pref[0][n] - pref[0][b])) // << '\n'; return (pref[2][a - t - 1] + pref[2][n] - pref[2][b + t]) + (pref[0][a - t - 1] + pref[0][n] - pref[0][b + t]) + min(k - skip, pref[1][a - t - 1] + pref[1][n] - pref[1][b + t]); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> k >> t; string s; cin >> s; // cerr << "xd\n"; rep1(i, n) { pref[0][i] = pref[0][i - 1]; pref[1][i] = pref[1][i - 1]; pref[2][i] = pref[2][i - 1]; pref[s[i - 1] - '1'][i]++; } // cerr << "xd\n"; int res = -1; if (k >= pref[0][n]) res = pref[2][n] + min(pref[1][n] + pref[0][n], k); // cerr << "res " << res << '\n'; for (int i = t + 1; i <= n - t; i++) { // cerr << "i: " << i << '\n'; for (int j = i; j <= n - t; j++) { res = max(res, ans(i, j)); } } cout << res << '\n'; // cerr << ans(3, 5) << '\n'; } /* 10 1 2 3233313132 10 1 2 323 33 1 31 32 - - - */
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 | // https://sio2.mimuw.edu.pl/c/pa-2025-1/p/pra/ #include <bits/stdc++.h> #define st first #define nd second #define pb push_back #define all(x) x.begin(), x.end() #define rep(i, a) for (int i = 0; i < int(a); i++) #define rep1(i, a) for (int i = 1; i <= int(a); i++) #define los(a, b) (rng() % (int)(b - a + 1) + (int)(a)) using namespace std; typedef long long ll; typedef pair<int, int> pi; const int MAXN = 8005; int pref[3][MAXN]; int n, k, t; int ans(int a, int b) { // przedzial w firmie // cerr << "ans " << a << ' ' << b << '\n'; int skip = pref[0][a - 1] + pref[0][n] - pref[0][b]; // cerr << " " << skip << "\n"; skip += pref[1][a - 1] - pref[1][a - t - 1] + pref[1][b + t] - pref[1][b]; // cerr << " " << skip << "\n"; if (skip > k) return -1; // cerr << pref[2][a - t - 1] << "+" << pref[2][n] << "-" << pref[2][b + t] // << " + " // << min(k - skip, pref[0][a - t - 1] + // (pref[0][n] - pref[0][b + t + 1]) + // (pref[0][a - 1] + pref[0][n] - pref[0][b])) // << '\n'; return (pref[2][a - t - 1] + pref[2][n] - pref[2][b + t]) + (pref[0][a - t - 1] + pref[0][n] - pref[0][b + t]) + min(k - skip, pref[1][a - t - 1] + pref[1][n] - pref[1][b + t]); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> k >> t; string s; cin >> s; // cerr << "xd\n"; rep1(i, n) { pref[0][i] = pref[0][i - 1]; pref[1][i] = pref[1][i - 1]; pref[2][i] = pref[2][i - 1]; pref[s[i - 1] - '1'][i]++; } // cerr << "xd\n"; int res = -1; if (k >= pref[0][n]) res = pref[2][n] + min(pref[1][n] + pref[0][n], k); // cerr << "res " << res << '\n'; for (int i = t + 1; i <= n - t; i++) { // cerr << "i: " << i << '\n'; for (int j = i; j <= n - t; j++) { res = max(res, ans(i, j)); } } cout << res << '\n'; // cerr << ans(3, 5) << '\n'; } /* 10 1 2 3233313132 10 1 2 323 33 1 31 32 - - - */ |