#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; #define ll long long #define ull unsigned ll #define pb push_back #define pii pair<int,int> #define pl pair<ll,ll> #define F first #define S second #define pq priority_queue #define all(x) x.begin(), x.end() #define deb(x) cout << #x << " = " << x << '\n'; #define deb2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << '\n'; constexpr int M = 1e9+7; constexpr int N = 8e3+7; constexpr bool debug = 0; int pref[N][3]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, kok, t; cin >> n >> kok >> t; string sus; cin >> sus; for(int i = 0; i < n; ++i){ pref[i+1][0] = pref[i][0]; pref[i+1][1] = pref[i][1]; pref[i+1][2] = pref[i][2]; if(sus[i] == '1') ++pref[i+1][0]; if(sus[i] == '2') ++pref[i+1][1]; if(sus[i] == '3') ++pref[i+1][2]; } int best = -1; if(pref[n][0] <= kok){ best = max(best, pref[n][0]+pref[n][2]+min(kok-pref[n][0], pref[n][1])); } for(int i = 1; i <= n; ++i){ for(int j = i+t; j+t-1 <= n; ++j){ int skipped = pref[i+t-1][0] + pref[n][0]-pref[j-1][0]; skipped += pref[i+t-1][1]-pref[i-1][1] + pref[j+t-1][1]-pref[j-1][1]; if(skipped <= kok){ int remain = pref[i-1][2]+pref[n][2]-pref[j+t-1][2]; remain += pref[i-1][0]+pref[n][0]-pref[j+t-1][0]; int toad = pref[i-1][1]+pref[n][1]-pref[j+t-1][1]; best = max(best, remain + min(kok-skipped, toad)); //deb2(i, j); //deb(best); } } } cout << best << '\n'; 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 | #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; #define ll long long #define ull unsigned ll #define pb push_back #define pii pair<int,int> #define pl pair<ll,ll> #define F first #define S second #define pq priority_queue #define all(x) x.begin(), x.end() #define deb(x) cout << #x << " = " << x << '\n'; #define deb2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << '\n'; constexpr int M = 1e9+7; constexpr int N = 8e3+7; constexpr bool debug = 0; int pref[N][3]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, kok, t; cin >> n >> kok >> t; string sus; cin >> sus; for(int i = 0; i < n; ++i){ pref[i+1][0] = pref[i][0]; pref[i+1][1] = pref[i][1]; pref[i+1][2] = pref[i][2]; if(sus[i] == '1') ++pref[i+1][0]; if(sus[i] == '2') ++pref[i+1][1]; if(sus[i] == '3') ++pref[i+1][2]; } int best = -1; if(pref[n][0] <= kok){ best = max(best, pref[n][0]+pref[n][2]+min(kok-pref[n][0], pref[n][1])); } for(int i = 1; i <= n; ++i){ for(int j = i+t; j+t-1 <= n; ++j){ int skipped = pref[i+t-1][0] + pref[n][0]-pref[j-1][0]; skipped += pref[i+t-1][1]-pref[i-1][1] + pref[j+t-1][1]-pref[j-1][1]; if(skipped <= kok){ int remain = pref[i-1][2]+pref[n][2]-pref[j+t-1][2]; remain += pref[i-1][0]+pref[n][0]-pref[j+t-1][0]; int toad = pref[i-1][1]+pref[n][1]-pref[j+t-1][1]; best = max(best, remain + min(kok-skipped, toad)); //deb2(i, j); //deb(best); } } } cout << best << '\n'; return 0; } |