#include "iostream"
#include "sstream"
#include "vector"
#include "algorithm"
int main() {
int n, k, t;
std::cin >> n >> k >> t;
std::string events;
std::cin >> events;
auto count = std::vector<std::vector<int>>(n+1, std::vector<int>(4, 0));
for (int i = 0; i < n; i++) {
for (int j = 1; j <= 3; j++) {
count[i + 1][j] = count[i][j] + (events[i] -'0' == j);
}
}
// 1: office
// 2: remote
// 3: free
int result = -1;
if (count[n][1] <= k) {
result = count[n][3] + std::min(count[n][1] + count[n][2], k);
}
for (int i = 1; i + t - 1 <= n; i++) {
for (int j = i + t; j + t - 1 <= n; j++) {
int potentially_free = (i - 1) + (n - (j + t - 1));
int travel_missed =
(count[i + t - 1][1] - count[i - 1][1]) +
(count[i + t - 1][2] - count[i - 1][2]) +
(count[j + t - 1][1] - count[j - 1][1]) +
(count[j + t - 1][2] - count[j - 1][2]);
int home_missed =
count[i - 1][1] +
(count[n][1] - count[j + t - 1][1]);
if (home_missed + travel_missed > k) {
continue;
}
int new_k = k - travel_missed - home_missed;
int meetings_possible =
count[i - 1][2] +
(count[n][2] - count[j + t - 1][2]);
result = std::max(result, potentially_free - std::max(meetings_possible - new_k, 0));
}
}
std::cout << result << std::endl;
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 | #include "iostream" #include "sstream" #include "vector" #include "algorithm" int main() { int n, k, t; std::cin >> n >> k >> t; std::string events; std::cin >> events; auto count = std::vector<std::vector<int>>(n+1, std::vector<int>(4, 0)); for (int i = 0; i < n; i++) { for (int j = 1; j <= 3; j++) { count[i + 1][j] = count[i][j] + (events[i] -'0' == j); } } // 1: office // 2: remote // 3: free int result = -1; if (count[n][1] <= k) { result = count[n][3] + std::min(count[n][1] + count[n][2], k); } for (int i = 1; i + t - 1 <= n; i++) { for (int j = i + t; j + t - 1 <= n; j++) { int potentially_free = (i - 1) + (n - (j + t - 1)); int travel_missed = (count[i + t - 1][1] - count[i - 1][1]) + (count[i + t - 1][2] - count[i - 1][2]) + (count[j + t - 1][1] - count[j - 1][1]) + (count[j + t - 1][2] - count[j - 1][2]); int home_missed = count[i - 1][1] + (count[n][1] - count[j + t - 1][1]); if (home_missed + travel_missed > k) { continue; } int new_k = k - travel_missed - home_missed; int meetings_possible = count[i - 1][2] + (count[n][2] - count[j + t - 1][2]); result = std::max(result, potentially_free - std::max(meetings_possible - new_k, 0)); } } std::cout << result << std::endl; return 0; } |
English