#include <bits/stdc++.h> using std::cin, std::cout; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; const char endl = '\n'; const int MAX_N = 8005; enum state { BEFORE = 0, WORK = 1, AFTER = 2, }; enum task { WORK_MEET = 0, MEET = 1, NONE = 2, }; int best[3][MAX_N][MAX_N]; int main() { std::ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n, k, t; cin >> n >> k >> t; std::string s; cin >> s; int total_jobs = 0; const int START_SCORE = 10000; best[state::BEFORE][0][0] = START_SCORE; for (int i = 0; i < s.size(); i++) { task type = (task)(s[i] - '1'); if (type == MEET or type == WORK_MEET) total_jobs++; // AFTER -> AFTER for (int jobs_done = 0; jobs_done <= n; jobs_done++) { int curr_score = best[state::AFTER][i][jobs_done]; if (curr_score + 1 > best[state::AFTER][i + 1][jobs_done]) best[state::AFTER][i + 1][jobs_done] = curr_score + 1; if (type == MEET) { if (curr_score > best[state::AFTER][i + 1][jobs_done + 1]) best[state::AFTER][i + 1][jobs_done + 1] = curr_score; } } // WORK -> WORK / AFTER for (int jobs_done = 0; jobs_done <= n; jobs_done++) { int curr_score = best[state::WORK][i][jobs_done]; if (i <= n - t) { if (curr_score > best[state::AFTER][i + t][jobs_done]) best[state::AFTER][i + t][jobs_done] = curr_score; } if (curr_score > best[state::WORK][i + 1][jobs_done]) best[state::WORK][i + 1][jobs_done] = curr_score; if (type == MEET or type == WORK_MEET) { if (curr_score > best[state::WORK][i + 1][jobs_done + 1]) best[state::WORK][i + 1][jobs_done + 1] = curr_score; } } // BEFORE -> BEFORE / WORK for (int jobs_done = 0; jobs_done <= n; jobs_done++) { int curr_score = best[state::BEFORE][i][jobs_done]; if (i <= n - t) { if (curr_score > best[state::WORK][i + t][jobs_done]) best[state::WORK][i + t][jobs_done] = curr_score; } if (curr_score + 1 > best[state::BEFORE][i + 1][jobs_done]) best[state::BEFORE][i + 1][jobs_done] = curr_score + 1; if (type == MEET) { if (curr_score > best[state::BEFORE][i + 1][jobs_done + 1]) best[state::BEFORE][i + 1][jobs_done + 1] = curr_score; } } } int max = 0; for (int jobs_done = std::max(0, total_jobs - k); jobs_done <= total_jobs; jobs_done++) { int score = std::max(best[state::AFTER][n][jobs_done], best[state::BEFORE][n][jobs_done]); if (score > max) max = score; } if (max < START_SCORE) cout << -1; else cout << max - START_SCORE; 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 | #include <bits/stdc++.h> using std::cin, std::cout; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; const char endl = '\n'; const int MAX_N = 8005; enum state { BEFORE = 0, WORK = 1, AFTER = 2, }; enum task { WORK_MEET = 0, MEET = 1, NONE = 2, }; int best[3][MAX_N][MAX_N]; int main() { std::ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n, k, t; cin >> n >> k >> t; std::string s; cin >> s; int total_jobs = 0; const int START_SCORE = 10000; best[state::BEFORE][0][0] = START_SCORE; for (int i = 0; i < s.size(); i++) { task type = (task)(s[i] - '1'); if (type == MEET or type == WORK_MEET) total_jobs++; // AFTER -> AFTER for (int jobs_done = 0; jobs_done <= n; jobs_done++) { int curr_score = best[state::AFTER][i][jobs_done]; if (curr_score + 1 > best[state::AFTER][i + 1][jobs_done]) best[state::AFTER][i + 1][jobs_done] = curr_score + 1; if (type == MEET) { if (curr_score > best[state::AFTER][i + 1][jobs_done + 1]) best[state::AFTER][i + 1][jobs_done + 1] = curr_score; } } // WORK -> WORK / AFTER for (int jobs_done = 0; jobs_done <= n; jobs_done++) { int curr_score = best[state::WORK][i][jobs_done]; if (i <= n - t) { if (curr_score > best[state::AFTER][i + t][jobs_done]) best[state::AFTER][i + t][jobs_done] = curr_score; } if (curr_score > best[state::WORK][i + 1][jobs_done]) best[state::WORK][i + 1][jobs_done] = curr_score; if (type == MEET or type == WORK_MEET) { if (curr_score > best[state::WORK][i + 1][jobs_done + 1]) best[state::WORK][i + 1][jobs_done + 1] = curr_score; } } // BEFORE -> BEFORE / WORK for (int jobs_done = 0; jobs_done <= n; jobs_done++) { int curr_score = best[state::BEFORE][i][jobs_done]; if (i <= n - t) { if (curr_score > best[state::WORK][i + t][jobs_done]) best[state::WORK][i + t][jobs_done] = curr_score; } if (curr_score + 1 > best[state::BEFORE][i + 1][jobs_done]) best[state::BEFORE][i + 1][jobs_done] = curr_score + 1; if (type == MEET) { if (curr_score > best[state::BEFORE][i + 1][jobs_done + 1]) best[state::BEFORE][i + 1][jobs_done + 1] = curr_score; } } } int max = 0; for (int jobs_done = std::max(0, total_jobs - k); jobs_done <= total_jobs; jobs_done++) { int score = std::max(best[state::AFTER][n][jobs_done], best[state::BEFORE][n][jobs_done]); if (score > max) max = score; } if (max < START_SCORE) cout << -1; else cout << max - START_SCORE; return 0; } |