//#ifdef DEBUG //#define _GLIBCXX_DEBUG //#endif //#pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #else #define debug(...) 228 #endif #define pb push_back typedef long long ll; typedef long double ld; const int maxN = 8005; int dp[maxN][maxN][3]; int n, k, t; int val[maxN]; inline void umax(int& a, const int b) { a = max(a, b); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef DEBUG freopen("input.txt", "r", stdin); #endif auto start = std::chrono::high_resolution_clock::now(); cin >> n >> k >> t; string s; cin >> s; int meets = 0; for (int i = 0; i < n; i++) { val[i] = s[i] - '0'; if (val[i] == 1 || val[i] == 2) meets++; } const int INF = 1e9; for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { for (int z = 0; z < 3; z++) { dp[i][j][z] = -INF; } } } dp[0][0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { for (int flag = 0; flag < 3; flag++) { if (dp[i][j][flag] < 0) continue; if (i + t <= n && flag != 2) umax(dp[i + t][j][flag + 1], dp[i][j][flag]); if (flag != 1) { umax(dp[i + 1][j][flag], dp[i][j][flag] + 1); if (val[i] == 2) umax(dp[i + 1][j + 1][flag], dp[i][j][flag]); } else { umax(dp[i + 1][j][flag], dp[i][j][flag]); if (val[i] == 1 || val[i] == 2) umax(dp[i + 1][j + 1][flag], dp[i][j][flag]); } } } } int best = -1; for (int cnt = 0; cnt <= meets; cnt++) { if (cnt >= meets - k) umax(best, dp[n][cnt][0]); if (cnt >= meets - k) umax(best, dp[n][cnt][2]); } cout << best << '\n'; auto end = std::chrono::high_resolution_clock::now(); std::cerr << "Execution Time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << 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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | //#ifdef DEBUG //#define _GLIBCXX_DEBUG //#endif //#pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #else #define debug(...) 228 #endif #define pb push_back typedef long long ll; typedef long double ld; const int maxN = 8005; int dp[maxN][maxN][3]; int n, k, t; int val[maxN]; inline void umax(int& a, const int b) { a = max(a, b); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); #ifdef DEBUG freopen("input.txt", "r", stdin); #endif auto start = std::chrono::high_resolution_clock::now(); cin >> n >> k >> t; string s; cin >> s; int meets = 0; for (int i = 0; i < n; i++) { val[i] = s[i] - '0'; if (val[i] == 1 || val[i] == 2) meets++; } const int INF = 1e9; for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { for (int z = 0; z < 3; z++) { dp[i][j][z] = -INF; } } } dp[0][0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { for (int flag = 0; flag < 3; flag++) { if (dp[i][j][flag] < 0) continue; if (i + t <= n && flag != 2) umax(dp[i + t][j][flag + 1], dp[i][j][flag]); if (flag != 1) { umax(dp[i + 1][j][flag], dp[i][j][flag] + 1); if (val[i] == 2) umax(dp[i + 1][j + 1][flag], dp[i][j][flag]); } else { umax(dp[i + 1][j][flag], dp[i][j][flag]); if (val[i] == 1 || val[i] == 2) umax(dp[i + 1][j + 1][flag], dp[i][j][flag]); } } } } int best = -1; for (int cnt = 0; cnt <= meets; cnt++) { if (cnt >= meets - k) umax(best, dp[n][cnt][0]); if (cnt >= meets - k) umax(best, dp[n][cnt][2]); } cout << best << '\n'; auto end = std::chrono::high_resolution_clock::now(); std::cerr << "Execution Time: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << std::endl; return 0; } |