#include <bits/stdc++.h> using namespace std; using vi = vector<int>; #define all(x) x.begin(), x.end() #define OFFICE '1' #define REMOTE '2' #define FREE_TIME '3' int main() { int n, k, t; cin >> n >> k >> t; string s; cin >> s; int n_off = count(all(s), OFFICE); int n_rem = count(all(s), REMOTE); int must = max(n_off + n_rem - k, 0); if (n_rem >= must) { cout << n - must << '\n'; return 0; } vi lowest(n - t + 1, -1); int current = n_rem - count(s.begin(), s.begin() + t, REMOTE); for (int i = 0; i < current; i++) { lowest[i] = 0; } for (int i = 1; i < n - t + 1; i++) { if (s[i - 1] != FREE_TIME) current++; if (s[i + t - 1] == REMOTE) current--; if (lowest[current] == -1) { lowest[current] = i; } } vi n_cum_meets(n + 1, 0); for (int i = 0; i < n; i++) { n_cum_meets[i + 1] = n_cum_meets[i] + (s[i] != FREE_TIME); } int meets_unavailable = (t - 1) - count(s.begin(), s.begin() + t - 1, FREE_TIME); int max_slack = -1; for (int i = 0; i < n - t + 1; i++) { if (s[i + t - 1] != FREE_TIME) meets_unavailable++; int min_meets = meets_unavailable + must; int j = min_meets >= lowest.size() ? -1 : lowest[min_meets]; if (j != -1) { int n_meets_in_office = n_cum_meets[j] - n_cum_meets[i + t]; int time_in_office = (j + t - i); int meets_outside_office = max(must - n_meets_in_office, 0); int slack = n - time_in_office - meets_outside_office; max_slack = max(max_slack, slack); } if (s[i] == REMOTE) meets_unavailable--; } cout << max_slack << '\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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #define all(x) x.begin(), x.end() #define OFFICE '1' #define REMOTE '2' #define FREE_TIME '3' int main() { int n, k, t; cin >> n >> k >> t; string s; cin >> s; int n_off = count(all(s), OFFICE); int n_rem = count(all(s), REMOTE); int must = max(n_off + n_rem - k, 0); if (n_rem >= must) { cout << n - must << '\n'; return 0; } vi lowest(n - t + 1, -1); int current = n_rem - count(s.begin(), s.begin() + t, REMOTE); for (int i = 0; i < current; i++) { lowest[i] = 0; } for (int i = 1; i < n - t + 1; i++) { if (s[i - 1] != FREE_TIME) current++; if (s[i + t - 1] == REMOTE) current--; if (lowest[current] == -1) { lowest[current] = i; } } vi n_cum_meets(n + 1, 0); for (int i = 0; i < n; i++) { n_cum_meets[i + 1] = n_cum_meets[i] + (s[i] != FREE_TIME); } int meets_unavailable = (t - 1) - count(s.begin(), s.begin() + t - 1, FREE_TIME); int max_slack = -1; for (int i = 0; i < n - t + 1; i++) { if (s[i + t - 1] != FREE_TIME) meets_unavailable++; int min_meets = meets_unavailable + must; int j = min_meets >= lowest.size() ? -1 : lowest[min_meets]; if (j != -1) { int n_meets_in_office = n_cum_meets[j] - n_cum_meets[i + t]; int time_in_office = (j + t - i); int meets_outside_office = max(must - n_meets_in_office, 0); int slack = n - time_in_office - meets_outside_office; max_slack = max(max_slack, slack); } if (s[i] == REMOTE) meets_unavailable--; } cout << max_slack << '\n'; return 0; } |