#include <bits/stdc++.h> #define nl '\n' using namespace std; const int MAXN = 8001; int prefix1[MAXN], prefix2[MAXN], prefix3[MAXN]; int n, k, t; int check(int a, int b){ //cerr<<a<<' '<<b<<nl; int skipped1 = prefix1[a+t-1] + prefix1[n] - prefix1[b-1]; int skipped2 = prefix2[a+t-1] - prefix2[a-1] + prefix2[b+t-1] - prefix2[b-1]; int skipped = skipped1 + skipped2; int house = prefix2[a] + prefix2[n] - prefix2[b+t-1]; if(skipped > k) return -1; int res = n - b - t + a - house; int rem = min(k - skipped, house); //cerr<<res<<' '<<skipped<<' '<<house<<' '<<rem<<nl; res +=rem; return res; } int main() { cin.tie(0)->sync_with_stdio(0); cin>>n>>k>>t; string s; cin>>s; for(int i=1; i<=n; i++){ if(s[i-1] == '1'){ prefix1[i]++; } if(s[i-1] == '2'){ prefix2[i]++; } if(s[i-1] == '3'){ prefix3[i]++; } } for(int i=1; i<=n; i++){ prefix1[i] += prefix1[i-1]; prefix2[i] += prefix2[i-1]; prefix3[i] += prefix3[i-1]; } int res = -1; if(prefix1[n] <= k){ //int demand = k - prefix1[n]; cout<<n - max(0, prefix1[n] + prefix2[n] - k)<<nl; return 0; } for(int a=1; a<=n - 2*t; a++){ for(int b = a+t; b+t-1<=n; b++){ res = max(res, check(a, b)); } } cout<<res<<nl; }
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 | #include <bits/stdc++.h> #define nl '\n' using namespace std; const int MAXN = 8001; int prefix1[MAXN], prefix2[MAXN], prefix3[MAXN]; int n, k, t; int check(int a, int b){ //cerr<<a<<' '<<b<<nl; int skipped1 = prefix1[a+t-1] + prefix1[n] - prefix1[b-1]; int skipped2 = prefix2[a+t-1] - prefix2[a-1] + prefix2[b+t-1] - prefix2[b-1]; int skipped = skipped1 + skipped2; int house = prefix2[a] + prefix2[n] - prefix2[b+t-1]; if(skipped > k) return -1; int res = n - b - t + a - house; int rem = min(k - skipped, house); //cerr<<res<<' '<<skipped<<' '<<house<<' '<<rem<<nl; res +=rem; return res; } int main() { cin.tie(0)->sync_with_stdio(0); cin>>n>>k>>t; string s; cin>>s; for(int i=1; i<=n; i++){ if(s[i-1] == '1'){ prefix1[i]++; } if(s[i-1] == '2'){ prefix2[i]++; } if(s[i-1] == '3'){ prefix3[i]++; } } for(int i=1; i<=n; i++){ prefix1[i] += prefix1[i-1]; prefix2[i] += prefix2[i-1]; prefix3[i] += prefix3[i-1]; } int res = -1; if(prefix1[n] <= k){ //int demand = k - prefix1[n]; cout<<n - max(0, prefix1[n] + prefix2[n] - k)<<nl; return 0; } for(int a=1; a<=n - 2*t; a++){ for(int b = a+t; b+t-1<=n; b++){ res = max(res, check(a, b)); } } cout<<res<<nl; } |