#include <bits/stdc++.h> using namespace std; int solve() { int n, t, k; char s[8008]; scanf("%d%d%d%s", &n, &k, &t, s); vector<int> s_any(n + 1, 0); vector<int> s_remote(n + 1, 0); for (int i = 0; i < n; i++) { s_any[i + 1] = s_any[i] + (s[i] != '3'); s_remote[i + 1] = s_remote[i] + (s[i] == '2'); } int must_meet = max(s_any[n] - k, 0); if (s_any[n] - s_remote[n] <= k) return n - must_meet; int best = -1; auto check = [&](int i, int j) { int in_office = s_any[j - t] - s_any[i + t]; int can_meet = s_remote[i] + s_remote[n] - s_remote[j] + in_office; if (can_meet >= must_meet) best = max(best, n - j + i + in_office - must_meet); return can_meet >= must_meet; }; for (int i = 0; i <= n - 2 * t; i++) { int l = i + 2 * t, r = n + 1; while (l + 1 < r) { int j = (l + r) / 2; if (check(i, j)) r = j; else l = j; } } return best; } int main() { printf("%d\n", solve()); }
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 | #include <bits/stdc++.h> using namespace std; int solve() { int n, t, k; char s[8008]; scanf("%d%d%d%s", &n, &k, &t, s); vector<int> s_any(n + 1, 0); vector<int> s_remote(n + 1, 0); for (int i = 0; i < n; i++) { s_any[i + 1] = s_any[i] + (s[i] != '3'); s_remote[i + 1] = s_remote[i] + (s[i] == '2'); } int must_meet = max(s_any[n] - k, 0); if (s_any[n] - s_remote[n] <= k) return n - must_meet; int best = -1; auto check = [&](int i, int j) { int in_office = s_any[j - t] - s_any[i + t]; int can_meet = s_remote[i] + s_remote[n] - s_remote[j] + in_office; if (can_meet >= must_meet) best = max(best, n - j + i + in_office - must_meet); return can_meet >= must_meet; }; for (int i = 0; i <= n - 2 * t; i++) { int l = i + 2 * t, r = n + 1; while (l + 1 < r) { int j = (l + r) / 2; if (check(i, j)) r = j; else l = j; } } return best; } int main() { printf("%d\n", solve()); } |