#include<iostream> #include<vector> #include<utility> #include<algorithm> #define ll long long using namespace std; vector<vector<int>>tab(4,vector<int>()); int sum_prze(int i, int a, int b){ if(a>b)return 0; if(a==0){ return tab[i][b]; } return tab[i][b]-tab[i][a-1]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int n,k,t; cin>>n>>k>>t; string s; cin>>s; for(int i = 0;i<4;++i){ tab[i].resize(s.size(),0); } for(int i = 0;i<s.size();++i){ if(i>0){ for(int j = 0;j<3;++j){ tab[j+1][i]=tab[j+1][i-1]; } } tab[s[i]-'0'][i]++; } int meet_cnt = sum_prze(1,0,n-1)+sum_prze(2,0,n-1); if(k>=meet_cnt){ cout<<n; return 0; } k = meet_cnt - k; int best = -1; for(int i = 0;i<n;i++){ for(int j = i+2;j<n;++j){ int pocz = i+t; int kon = j-t; if(pocz>kon){ continue; } int cnt = sum_prze(1,pocz,kon)+sum_prze(2,pocz,kon); int remain = k-cnt; int zoom = sum_prze(2,0,i-1)+sum_prze(2,j+1,n-1); int in_home = i+n-1-j; if(remain>zoom){ continue; } if(remain<0){ remain=0; } if(in_home-remain>best){ best=in_home-remain; //cout<<i<<" "<<j<<" "<<best<<endl; } } } int zoom2 = sum_prze(2,0,n-1); if(zoom2>=k && n-1-k>best){ best=n-1-k; //cout<<0<<" "<<n-1<<" "<<best<<endl; } cout<<best; 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 | #include<iostream> #include<vector> #include<utility> #include<algorithm> #define ll long long using namespace std; vector<vector<int>>tab(4,vector<int>()); int sum_prze(int i, int a, int b){ if(a>b)return 0; if(a==0){ return tab[i][b]; } return tab[i][b]-tab[i][a-1]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int n,k,t; cin>>n>>k>>t; string s; cin>>s; for(int i = 0;i<4;++i){ tab[i].resize(s.size(),0); } for(int i = 0;i<s.size();++i){ if(i>0){ for(int j = 0;j<3;++j){ tab[j+1][i]=tab[j+1][i-1]; } } tab[s[i]-'0'][i]++; } int meet_cnt = sum_prze(1,0,n-1)+sum_prze(2,0,n-1); if(k>=meet_cnt){ cout<<n; return 0; } k = meet_cnt - k; int best = -1; for(int i = 0;i<n;i++){ for(int j = i+2;j<n;++j){ int pocz = i+t; int kon = j-t; if(pocz>kon){ continue; } int cnt = sum_prze(1,pocz,kon)+sum_prze(2,pocz,kon); int remain = k-cnt; int zoom = sum_prze(2,0,i-1)+sum_prze(2,j+1,n-1); int in_home = i+n-1-j; if(remain>zoom){ continue; } if(remain<0){ remain=0; } if(in_home-remain>best){ best=in_home-remain; //cout<<i<<" "<<j<<" "<<best<<endl; } } } int zoom2 = sum_prze(2,0,n-1); if(zoom2>=k && n-1-k>best){ best=n-1-k; //cout<<0<<" "<<n-1<<" "<<best<<endl; } cout<<best; return 0; } |