#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); i++) #define all(x) begin(x), end(x) #define sz(x) int((x).size()) using ll = long long; using pii = pair<int, int>; using vi = vector<int>; #ifdef LOCAL auto operator<<(auto& o, auto x) -> decltype(x.first, o); auto operator<<(auto& o, auto x) -> decltype(x.end(), o) { o << "{"; for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y; return o << "}"; } auto operator<<(auto& o, auto x) -> decltype(x.first, o) { return o << "(" << x.first << ", " << x.second << ")"; } void __print(auto... x) { ((cerr << x << " "), ...) << endl; } #define debug(x...) __print("[" #x "]:", x) #else #define debug(...) 2137 #endif int main() { cin.tie(0)->sync_with_stdio(0); int n, k, t; cin >> n >> k >> t; string s; cin >> s; s = "$" + s; vector pref(n + 1, vector<int>(3)); for(int i = 1; i <= n; i++) { for(int j = 0; j < 3; j++) pref[i][j] += pref[i - 1][j]; pref[i][s[i] - '1']++; } auto get = [&](int l, int r, int i) { if(l < 0) return pref[r][i]; return pref[r][i] - pref[l][i]; }; int res = -1; int skip = get(-1, n, 0); if(skip <= k) { int dist = get(-1, n, 1); res = min(k - skip, dist) + n - dist; } for(int i = 0; i < n; i++) { for(int j = i + t; j + t <= n; j++) { int skip = get(-1, i, 0) + get(j + t, n, 0); skip += get(i, i + t, 0) + get(i, i + t, 1); skip += get(j, j + t, 0) + get(j, j + t, 1); if(skip > k) continue; int tot = i + n - j - t; int dist = get(-1, i, 1) + get(j + t, n, 1); res = max(res, min(k - skip, dist) + tot - dist); } } cout << res << endl; }
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 | #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); i++) #define all(x) begin(x), end(x) #define sz(x) int((x).size()) using ll = long long; using pii = pair<int, int>; using vi = vector<int>; #ifdef LOCAL auto operator<<(auto& o, auto x) -> decltype(x.first, o); auto operator<<(auto& o, auto x) -> decltype(x.end(), o) { o << "{"; for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y; return o << "}"; } auto operator<<(auto& o, auto x) -> decltype(x.first, o) { return o << "(" << x.first << ", " << x.second << ")"; } void __print(auto... x) { ((cerr << x << " "), ...) << endl; } #define debug(x...) __print("[" #x "]:", x) #else #define debug(...) 2137 #endif int main() { cin.tie(0)->sync_with_stdio(0); int n, k, t; cin >> n >> k >> t; string s; cin >> s; s = "$" + s; vector pref(n + 1, vector<int>(3)); for(int i = 1; i <= n; i++) { for(int j = 0; j < 3; j++) pref[i][j] += pref[i - 1][j]; pref[i][s[i] - '1']++; } auto get = [&](int l, int r, int i) { if(l < 0) return pref[r][i]; return pref[r][i] - pref[l][i]; }; int res = -1; int skip = get(-1, n, 0); if(skip <= k) { int dist = get(-1, n, 1); res = min(k - skip, dist) + n - dist; } for(int i = 0; i < n; i++) { for(int j = i + t; j + t <= n; j++) { int skip = get(-1, i, 0) + get(j + t, n, 0); skip += get(i, i + t, 0) + get(i, i + t, 1); skip += get(j, j + t, 0) + get(j, j + t, 1); if(skip > k) continue; int tot = i + n - j - t; int dist = get(-1, i, 1) + get(j + t, n, 1); res = max(res, min(k - skip, dist) + tot - dist); } } cout << res << endl; } |