#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; } |