#include <bits/stdc++.h> using namespace std; #define _DEBUG #ifdef _DEBUG template<typename T1, typename T2> auto& operator<<(ostream& o, pair<T1, T2> a) { return o << "(" << a.first << ", " << a.second << ")"; } template<typename T, typename OS> auto& operator<<(OS& o, T a) { o << "{"; for(auto b : a) o << b << ", "; return o << "}"; } #define dbg(x...) cerr << "[" #x "]: ", [](auto... args) { ((cerr << args << ", "),...) << "\n"; }(x) #else #define dbg(...) #endif #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define F first #define S second using ll = long long; using ld = long double; using pll = pair<ll,ll>; using vi = vector<int>; int getSum(const vector<int>& s, int l, int r) { if(r < l) { return 0; } if(l == 0) { return s[r]; } return s[r] - s[l - 1]; } void solve() { int n, k, t; cin >> n >> k >> t; vector<int> o(n); vector<int> r(n); vector<int> f(n); char v; cin >> v; o[0] = (v == '1'); r[0] = (v == '2'); f[0] = (v == '3'); for(int i = 1; i < n; i++) { o[i] = o[i - 1]; r[i] = r[i - 1]; f[i] = f[i - 1]; cin >> v; if(v == '1') { o[i]++; } if(v == '2') { r[i]++; } if(v == '3') { f[i]++; } } int ans = -1; if(o.back() <= k) { ans = n - max(o.back() + r.back() - k, 0); } for(int i = 0; i < n - 2 * t + 1; i++) { for(int j = i + t; j < n - t + 1; j++) { if(getSum(o, 0, i + t - 1) + getSum(o, j, n - 1) + getSum(r, i, i + t - 1) + getSum(r, j, j + t - 1) <= k) { int freeTime = i + n - (j + t); int already = getSum(o, i + t, j - 1) + getSum(r, i + t, j - 1); int needed = max(o.back() + r.back() - k, 0); freeTime -= max(needed - already, 0); ans = max(ans, freeTime); } } } cout << ans; } int main() { cin.tie(0)->sync_with_stdio(0); solve(); return 0; }
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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include <bits/stdc++.h> using namespace std; #define _DEBUG #ifdef _DEBUG template<typename T1, typename T2> auto& operator<<(ostream& o, pair<T1, T2> a) { return o << "(" << a.first << ", " << a.second << ")"; } template<typename T, typename OS> auto& operator<<(OS& o, T a) { o << "{"; for(auto b : a) o << b << ", "; return o << "}"; } #define dbg(x...) cerr << "[" #x "]: ", [](auto... args) { ((cerr << args << ", "),...) << "\n"; }(x) #else #define dbg(...) #endif #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define F first #define S second using ll = long long; using ld = long double; using pll = pair<ll,ll>; using vi = vector<int>; int getSum(const vector<int>& s, int l, int r) { if(r < l) { return 0; } if(l == 0) { return s[r]; } return s[r] - s[l - 1]; } void solve() { int n, k, t; cin >> n >> k >> t; vector<int> o(n); vector<int> r(n); vector<int> f(n); char v; cin >> v; o[0] = (v == '1'); r[0] = (v == '2'); f[0] = (v == '3'); for(int i = 1; i < n; i++) { o[i] = o[i - 1]; r[i] = r[i - 1]; f[i] = f[i - 1]; cin >> v; if(v == '1') { o[i]++; } if(v == '2') { r[i]++; } if(v == '3') { f[i]++; } } int ans = -1; if(o.back() <= k) { ans = n - max(o.back() + r.back() - k, 0); } for(int i = 0; i < n - 2 * t + 1; i++) { for(int j = i + t; j < n - t + 1; j++) { if(getSum(o, 0, i + t - 1) + getSum(o, j, n - 1) + getSum(r, i, i + t - 1) + getSum(r, j, j + t - 1) <= k) { int freeTime = i + n - (j + t); int already = getSum(o, i + t, j - 1) + getSum(r, i + t, j - 1); int needed = max(o.back() + r.back() - k, 0); freeTime -= max(needed - already, 0); ans = max(ans, freeTime); } } } cout << ans; } int main() { cin.tie(0)->sync_with_stdio(0); solve(); return 0; } |