#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define st first #define nd second #define fi first #define se second #define vt vector #define FOR(a, b, c) for(int a=b; a<c; ++a) #define all(a) (a).begin(),(a).end() #define sz(a) (int)(a).size() typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; typedef pii PII; typedef pll PLL; constexpr ll nax = 2e5+6969, INF = 1e9+2137; constexpr ld eps = 1e-9; mt19937_64 rng(6969); // mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); inline ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } int n, k, t, ans; int pref[4][nax]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> t; string s; cin >> s; for(int i = 0; i < n; i++) { pref[s[i] - '0'][i+1]++; } for(int i = 1; i <= n; i++) { pref[1][i] += pref[1][i-1]; pref[2][i] += pref[2][i-1]; pref[3][i] += pref[3][i-1]; } ans = -1; if(pref[1][n] <= k) { ans = n - pref[2][n] + min(k - pref[1][n], pref[2][n]); } for(int i = 1; i <= n; i++) { for(int j = i+t; j <= n - t + 1; j++) { int skipped = pref[1][i+t-1] + pref[1][n] - pref[1][j-1]; skipped += pref[2][i+t-1] - pref[2][i-1] + pref[2][j + t - 1] - pref[2][j-1]; if(skipped > k) { continue; } int twos = pref[2][i-1] + pref[2][n] - pref[2][j+t-1]; int cur = i - 1 + (n - (j + t - 1)) - twos; cur += min(k - skipped, twos); ans = max(ans, cur); } } cout << ans << "\n"; 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 | #include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define st first #define nd second #define fi first #define se second #define vt vector #define FOR(a, b, c) for(int a=b; a<c; ++a) #define all(a) (a).begin(),(a).end() #define sz(a) (int)(a).size() typedef long long ll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; typedef pii PII; typedef pll PLL; constexpr ll nax = 2e5+6969, INF = 1e9+2137; constexpr ld eps = 1e-9; mt19937_64 rng(6969); // mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); inline ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } int n, k, t, ans; int pref[4][nax]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> t; string s; cin >> s; for(int i = 0; i < n; i++) { pref[s[i] - '0'][i+1]++; } for(int i = 1; i <= n; i++) { pref[1][i] += pref[1][i-1]; pref[2][i] += pref[2][i-1]; pref[3][i] += pref[3][i-1]; } ans = -1; if(pref[1][n] <= k) { ans = n - pref[2][n] + min(k - pref[1][n], pref[2][n]); } for(int i = 1; i <= n; i++) { for(int j = i+t; j <= n - t + 1; j++) { int skipped = pref[1][i+t-1] + pref[1][n] - pref[1][j-1]; skipped += pref[2][i+t-1] - pref[2][i-1] + pref[2][j + t - 1] - pref[2][j-1]; if(skipped > k) { continue; } int twos = pref[2][i-1] + pref[2][n] - pref[2][j+t-1]; int cur = i - 1 + (n - (j + t - 1)) - twos; cur += min(k - skipped, twos); ans = max(ans, cur); } } cout << ans << "\n"; return 0; } |