#include <bits/stdc++.h> using namespace std; #define st first #define nd second #define pb push_back #define all(x) (x).begin(), (x).end() #define BOOST ios_base::sync_with_stdio(0), cin.tie(0) typedef long long ll; typedef long double ld; typedef pair<int, int> ii; const int N = 8e3 + 5; int pref[N][4]; int main(){ BOOST; int n, k, t; cin >> n >> k >> t; string s; cin >> s; s = '#' + s; for(int i=1; i<=n; i++){ for(int j=1; j<=3; j++){ pref[i][j] = pref[i-1][j]; } pref[i][s[i] - '0']++; } auto seg = [](int i, int a, int b){ // prawy wyłącznie return pref[b-1][i] - pref[a-1][i]; }; auto go = [&](int be, int en){ int res = seg(3, 1, be) + seg(3, en+t, n+1); res += seg(1, 1, be) + seg(1, en+t, n+1); int skip = seg(1, 1, be+t) + seg(1, en, n+1); skip += seg(2, be, be+t) + seg(2, en, en+t); if(skip > k) return -1; int f2 = seg(2, 1, be) + seg(2, en+t, n+1); res += min(f2, k - skip); return res; }; int mx = -1; int res = seg(3, 1, n+1) + seg(1, 1, n+1); int skip = seg(1, 1, n+1); if(skip <= k){ int f2 = seg(2, 1, n+1); res += min(f2, k - skip); mx = res; } for(int i=1; i<=n; i++){ for(int j=i+t; j+t<=n+1; j++){ mx = max(mx, go(i, j)); } } cout << mx << "\n"; }
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 | #include <bits/stdc++.h> using namespace std; #define st first #define nd second #define pb push_back #define all(x) (x).begin(), (x).end() #define BOOST ios_base::sync_with_stdio(0), cin.tie(0) typedef long long ll; typedef long double ld; typedef pair<int, int> ii; const int N = 8e3 + 5; int pref[N][4]; int main(){ BOOST; int n, k, t; cin >> n >> k >> t; string s; cin >> s; s = '#' + s; for(int i=1; i<=n; i++){ for(int j=1; j<=3; j++){ pref[i][j] = pref[i-1][j]; } pref[i][s[i] - '0']++; } auto seg = [](int i, int a, int b){ // prawy wyłącznie return pref[b-1][i] - pref[a-1][i]; }; auto go = [&](int be, int en){ int res = seg(3, 1, be) + seg(3, en+t, n+1); res += seg(1, 1, be) + seg(1, en+t, n+1); int skip = seg(1, 1, be+t) + seg(1, en, n+1); skip += seg(2, be, be+t) + seg(2, en, en+t); if(skip > k) return -1; int f2 = seg(2, 1, be) + seg(2, en+t, n+1); res += min(f2, k - skip); return res; }; int mx = -1; int res = seg(3, 1, n+1) + seg(1, 1, n+1); int skip = seg(1, 1, n+1); if(skip <= k){ int f2 = seg(2, 1, n+1); res += min(f2, k - skip); mx = res; } for(int i=1; i<=n; i++){ for(int j=i+t; j+t<=n+1; j++){ mx = max(mx, go(i, j)); } } cout << mx << "\n"; } |