#include <iostream> #include <cstdio> #include <cstdint> #include <vector> #include <optional> #include <string> enum Responsibles { OFFICE_MEETING = 1, REMOTE_MEETING = 2, FREE = 3 }; struct InputData { uint64_t n; uint64_t max_meetings; uint64_t trip_time; std::vector<uint64_t> segments; } input_data; void parse_input() { std::string segments_string; std::cin >> input_data.n >> input_data.max_meetings >> input_data.trip_time >> segments_string; for (uint64_t i = 0; i < input_data.n; ++i) { char segment = segments_string[i]; input_data.segments.push_back(static_cast<uint64_t>(segment - '0')); } } std::optional<uint64_t> calculate_award(const uint64_t start, const uint64_t end) { if (start + input_data.trip_time >= end || start + input_data.trip_time > input_data.n || end + input_data.trip_time > input_data.n) return std::nullopt; bool at_home = true; uint64_t trip = 0; uint64_t res = 0; auto meetings_left = input_data.max_meetings; uint64_t possible_to_skip = 0; for (uint64_t i = 0; i < input_data.n; ++i) { // std::cerr << "calculate_award " << i << ' ' << res << '\n'; if (i == start) { at_home = false; trip = input_data.trip_time; } else if (i == end) { at_home = true; trip = input_data.trip_time; } if (input_data.segments[i] == OFFICE_MEETING && (trip > 0 || at_home)) { if (meetings_left == 0) return std::nullopt; meetings_left--; if (!trip) res++; } else if (input_data.segments[i] == REMOTE_MEETING) { if (trip > 0) { if (meetings_left == 0) return std::nullopt; meetings_left--; } if (at_home) { possible_to_skip++; } } else if (input_data.segments[i] == FREE && at_home && !trip) res++; if (trip) trip--; } res += possible_to_skip > meetings_left ? meetings_left : possible_to_skip; return res; } std::optional<uint64_t> calculate_award() { uint64_t res = 0; auto meetings_left = input_data.max_meetings; uint64_t possible_to_skip = 0; for (uint64_t i = 0; i < input_data.n; ++i) { if (input_data.segments[i] == OFFICE_MEETING) { if (meetings_left == 0) return std::nullopt; meetings_left--; res++; } else if (input_data.segments[i] == REMOTE_MEETING) { possible_to_skip++; } else if (input_data.segments[i] == FREE) res++; } res += possible_to_skip > meetings_left ? meetings_left : possible_to_skip; return res; } std::optional<uint64_t> solve() { std::optional<uint64_t> res = calculate_award(); // std::cerr << "solve " << res.has_value() << '\n'; for (uint64_t start = 0; start + input_data.trip_time < input_data.n; ++start) { for (uint64_t end = input_data.n - input_data.trip_time; end > start; --end) { const auto current_award = calculate_award(start, end); // std::cerr << "solve " << start << ' ' << end << ' ' << current_award.value_or(2137) << ' ' << res.value_or(2137) << '\n'; if (current_award.has_value() && current_award.value() >= res.value_or(0)) res = current_award; } } return res; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); parse_input(); const auto res = solve(); std::cout << (res.has_value() ? static_cast<int64_t>(res.value()) : -1) << '\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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 | #include <iostream> #include <cstdio> #include <cstdint> #include <vector> #include <optional> #include <string> enum Responsibles { OFFICE_MEETING = 1, REMOTE_MEETING = 2, FREE = 3 }; struct InputData { uint64_t n; uint64_t max_meetings; uint64_t trip_time; std::vector<uint64_t> segments; } input_data; void parse_input() { std::string segments_string; std::cin >> input_data.n >> input_data.max_meetings >> input_data.trip_time >> segments_string; for (uint64_t i = 0; i < input_data.n; ++i) { char segment = segments_string[i]; input_data.segments.push_back(static_cast<uint64_t>(segment - '0')); } } std::optional<uint64_t> calculate_award(const uint64_t start, const uint64_t end) { if (start + input_data.trip_time >= end || start + input_data.trip_time > input_data.n || end + input_data.trip_time > input_data.n) return std::nullopt; bool at_home = true; uint64_t trip = 0; uint64_t res = 0; auto meetings_left = input_data.max_meetings; uint64_t possible_to_skip = 0; for (uint64_t i = 0; i < input_data.n; ++i) { // std::cerr << "calculate_award " << i << ' ' << res << '\n'; if (i == start) { at_home = false; trip = input_data.trip_time; } else if (i == end) { at_home = true; trip = input_data.trip_time; } if (input_data.segments[i] == OFFICE_MEETING && (trip > 0 || at_home)) { if (meetings_left == 0) return std::nullopt; meetings_left--; if (!trip) res++; } else if (input_data.segments[i] == REMOTE_MEETING) { if (trip > 0) { if (meetings_left == 0) return std::nullopt; meetings_left--; } if (at_home) { possible_to_skip++; } } else if (input_data.segments[i] == FREE && at_home && !trip) res++; if (trip) trip--; } res += possible_to_skip > meetings_left ? meetings_left : possible_to_skip; return res; } std::optional<uint64_t> calculate_award() { uint64_t res = 0; auto meetings_left = input_data.max_meetings; uint64_t possible_to_skip = 0; for (uint64_t i = 0; i < input_data.n; ++i) { if (input_data.segments[i] == OFFICE_MEETING) { if (meetings_left == 0) return std::nullopt; meetings_left--; res++; } else if (input_data.segments[i] == REMOTE_MEETING) { possible_to_skip++; } else if (input_data.segments[i] == FREE) res++; } res += possible_to_skip > meetings_left ? meetings_left : possible_to_skip; return res; } std::optional<uint64_t> solve() { std::optional<uint64_t> res = calculate_award(); // std::cerr << "solve " << res.has_value() << '\n'; for (uint64_t start = 0; start + input_data.trip_time < input_data.n; ++start) { for (uint64_t end = input_data.n - input_data.trip_time; end > start; --end) { const auto current_award = calculate_award(start, end); // std::cerr << "solve " << start << ' ' << end << ' ' << current_award.value_or(2137) << ' ' << res.value_or(2137) << '\n'; if (current_award.has_value() && current_award.value() >= res.value_or(0)) res = current_award; } } return res; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); parse_input(); const auto res = solve(); std::cout << (res.has_value() ? static_cast<int64_t>(res.value()) : -1) << '\n'; return 0; } |