#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"; } |
English