#include <algorithm> #include <iomanip> #include <iostream> #include <sstream> #include <vector> constexpr int N = 8000; enum meeting { onsite, remote, none, }; struct state { int score; int home_meetings; int office_meetings; }; void add_meeting(state &out, meeting meeting, bool in_office) { switch (meeting) { case onsite: out.office_meetings += in_office; out.score += !in_office; break; case remote: out.office_meetings += in_office; out.home_meetings += !in_office; break; case none: out.score += !in_office; break; } } void sub_meeting(state &out, meeting meeting, bool in_office) { switch (meeting) { case onsite: out.office_meetings -= in_office; out.score -= !in_office; break; case remote: out.office_meetings -= in_office; out.home_meetings -= !in_office; break; case none: out.score -= !in_office; break; } } std::ostream &operator<<(std::ostream &os, state const &s) { return os << s.score << '@' << s.home_meetings << '/' << s.office_meetings; } meeting tasks[N]; int n, k, t; int total_meetings; int main() { std::cin.tie(nullptr)->sync_with_stdio(false); std::cin >> n >> k >> t; for (int i = 0; i < n; ++i) { char c; std::cin >> c; if (c == '3') tasks[i] = meeting::none; else if (c == '2') tasks[i] = meeting::remote; else if (c == '1') tasks[i] = meeting::onsite; if (tasks[i] != meeting::none) ++total_meetings; } #ifdef DEBUG #define DEBUGN 100 #define SIMPLE_STRINGIFY(x) #x if (n > DEBUGN) { // clang-format off std::cerr << "the debug build cannot handle n > " SIMPLE_STRINGIFY(DEBUGN) "\n"; // clang-format on return 1; } std::vector<state> states((DEBUGN + 1) * (DEBUGN + 1)); auto at = [&](int a, int b) mutable -> state & { return states[a + b * DEBUGN]; }; #endif int min_meetings = total_meetings - k; int max_score = -1; auto register_attempt = [&max_score, min_meetings](state const &st) { int state_meetings = st.home_meetings + st.office_meetings; if (state_meetings >= min_meetings && st.score > max_score) { int extra_score = std::min(st.home_meetings, state_meetings - min_meetings); max_score = st.score + extra_score; } }; state no_office{}; for (int i = 0; i < n; ++i) add_meeting(no_office, tasks[i], false); #ifdef DEBUG std::cerr << "no_office: " << no_office << '\n'; #endif register_attempt(no_office); state current_empty_state; { state empty_office = no_office; for (int i = n - 1; i >= n - t - t; --i) sub_meeting(empty_office, tasks[i], false); #ifdef DEBUG std::cerr << "empty_office(" << n - t << "): " << empty_office << '\n'; at(n - t - t, n) = empty_office; #endif register_attempt(empty_office); current_empty_state = empty_office; } for (int i = n; i >= 0; --i) { state current = current_empty_state; for (int j = i - t - t - 1; j >= 0; --j) { sub_meeting(current, tasks[j], false); add_meeting(current, tasks[j + t], true); register_attempt(current); #ifdef DEBUG at(j, i) = current; #endif } if (i > t) { state next_empty_state = current_empty_state; sub_meeting(next_empty_state, tasks[i - t - t - 1], false); add_meeting(next_empty_state, tasks[i - 1], false); #ifdef DEBUG std::cerr << "empty_office(" << i - t - 1 << "): " << next_empty_state << '\n'; at(i - t - t - 1, i - 1) = next_empty_state; #endif register_attempt(next_empty_state); current_empty_state = next_empty_state; } } #ifdef DEBUG std::cerr << " "; for (int j = 0; j <= n; ++j) { std::cerr << std::setw(7) << j << ' '; } std::cerr << '\n'; for (int i = 0; i <= n; ++i) { std::cerr << std::setw(2) << i << ' '; for (int j = 0; j <= n; ++j) { std::ostringstream xd; xd << at(i, j); std::cerr << std::setw(7) << xd.str() << ' '; } std::cerr << '\n'; } #endif std::cout << max_score << '\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 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 | #include <algorithm> #include <iomanip> #include <iostream> #include <sstream> #include <vector> constexpr int N = 8000; enum meeting { onsite, remote, none, }; struct state { int score; int home_meetings; int office_meetings; }; void add_meeting(state &out, meeting meeting, bool in_office) { switch (meeting) { case onsite: out.office_meetings += in_office; out.score += !in_office; break; case remote: out.office_meetings += in_office; out.home_meetings += !in_office; break; case none: out.score += !in_office; break; } } void sub_meeting(state &out, meeting meeting, bool in_office) { switch (meeting) { case onsite: out.office_meetings -= in_office; out.score -= !in_office; break; case remote: out.office_meetings -= in_office; out.home_meetings -= !in_office; break; case none: out.score -= !in_office; break; } } std::ostream &operator<<(std::ostream &os, state const &s) { return os << s.score << '@' << s.home_meetings << '/' << s.office_meetings; } meeting tasks[N]; int n, k, t; int total_meetings; int main() { std::cin.tie(nullptr)->sync_with_stdio(false); std::cin >> n >> k >> t; for (int i = 0; i < n; ++i) { char c; std::cin >> c; if (c == '3') tasks[i] = meeting::none; else if (c == '2') tasks[i] = meeting::remote; else if (c == '1') tasks[i] = meeting::onsite; if (tasks[i] != meeting::none) ++total_meetings; } #ifdef DEBUG #define DEBUGN 100 #define SIMPLE_STRINGIFY(x) #x if (n > DEBUGN) { // clang-format off std::cerr << "the debug build cannot handle n > " SIMPLE_STRINGIFY(DEBUGN) "\n"; // clang-format on return 1; } std::vector<state> states((DEBUGN + 1) * (DEBUGN + 1)); auto at = [&](int a, int b) mutable -> state & { return states[a + b * DEBUGN]; }; #endif int min_meetings = total_meetings - k; int max_score = -1; auto register_attempt = [&max_score, min_meetings](state const &st) { int state_meetings = st.home_meetings + st.office_meetings; if (state_meetings >= min_meetings && st.score > max_score) { int extra_score = std::min(st.home_meetings, state_meetings - min_meetings); max_score = st.score + extra_score; } }; state no_office{}; for (int i = 0; i < n; ++i) add_meeting(no_office, tasks[i], false); #ifdef DEBUG std::cerr << "no_office: " << no_office << '\n'; #endif register_attempt(no_office); state current_empty_state; { state empty_office = no_office; for (int i = n - 1; i >= n - t - t; --i) sub_meeting(empty_office, tasks[i], false); #ifdef DEBUG std::cerr << "empty_office(" << n - t << "): " << empty_office << '\n'; at(n - t - t, n) = empty_office; #endif register_attempt(empty_office); current_empty_state = empty_office; } for (int i = n; i >= 0; --i) { state current = current_empty_state; for (int j = i - t - t - 1; j >= 0; --j) { sub_meeting(current, tasks[j], false); add_meeting(current, tasks[j + t], true); register_attempt(current); #ifdef DEBUG at(j, i) = current; #endif } if (i > t) { state next_empty_state = current_empty_state; sub_meeting(next_empty_state, tasks[i - t - t - 1], false); add_meeting(next_empty_state, tasks[i - 1], false); #ifdef DEBUG std::cerr << "empty_office(" << i - t - 1 << "): " << next_empty_state << '\n'; at(i - t - t - 1, i - 1) = next_empty_state; #endif register_attempt(next_empty_state); current_empty_state = next_empty_state; } } #ifdef DEBUG std::cerr << " "; for (int j = 0; j <= n; ++j) { std::cerr << std::setw(7) << j << ' '; } std::cerr << '\n'; for (int i = 0; i <= n; ++i) { std::cerr << std::setw(2) << i << ' '; for (int j = 0; j <= n; ++j) { std::ostringstream xd; xd << at(i, j); std::cerr << std::setw(7) << xd.str() << ' '; } std::cerr << '\n'; } #endif std::cout << max_score << '\n'; return 0; } |