#include<bits/stdc++.h> using namespace std; const int N = 8002; int n,pref1[N],pref2[N],pref3[N],k,t; string s; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> t >> s; for(int i = 1;i <= n;i++){ pref1[i] = pref1[i-1] + (s[i-1] == '1'); pref2[i] = pref2[i-1] + (s[i-1] == '2'); pref3[i] = pref3[i-1] + (s[i-1] == '3'); } int max_res = -1; if(pref1[n] <= k){ max_res = max(max_res,pref3[n] + pref1[n] + min(k - pref1[n],pref2[n])); } for(int i = t+1;i <= n-t;i++){ for(int j = i;j <= n-t;j++){ int pominiete = pref1[n] - pref1[j] + pref1[i-1] + pref2[i-1] - pref2[i-t-1] + pref2[j+t] - pref2[j]; if(pominiete > k)continue; max_res = max(max_res,pref3[n] - pref3[j+t] + pref3[i-t-1] + pref1[n] - pref1[j+t] + pref1[i-t-1] + min(k - pominiete,pref1[j] - pref1[i-1] + pref2[n] - pref2[j+t] + pref2[j] - pref2[i-1] + pref2[i-t-1])); } } cout << max_res << "\n"; //cout << pref1[n] << " " << pref2[n] << " " << pref3[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 | #include<bits/stdc++.h> using namespace std; const int N = 8002; int n,pref1[N],pref2[N],pref3[N],k,t; string s; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k >> t >> s; for(int i = 1;i <= n;i++){ pref1[i] = pref1[i-1] + (s[i-1] == '1'); pref2[i] = pref2[i-1] + (s[i-1] == '2'); pref3[i] = pref3[i-1] + (s[i-1] == '3'); } int max_res = -1; if(pref1[n] <= k){ max_res = max(max_res,pref3[n] + pref1[n] + min(k - pref1[n],pref2[n])); } for(int i = t+1;i <= n-t;i++){ for(int j = i;j <= n-t;j++){ int pominiete = pref1[n] - pref1[j] + pref1[i-1] + pref2[i-1] - pref2[i-t-1] + pref2[j+t] - pref2[j]; if(pominiete > k)continue; max_res = max(max_res,pref3[n] - pref3[j+t] + pref3[i-t-1] + pref1[n] - pref1[j+t] + pref1[i-t-1] + min(k - pominiete,pref1[j] - pref1[i-1] + pref2[n] - pref2[j+t] + pref2[j] - pref2[i-1] + pref2[i-t-1])); } } cout << max_res << "\n"; //cout << pref1[n] << " " << pref2[n] << " " << pref3[n]; } |