#include <iostream> // #define debug const int MAXN = 8000+2; const int MAXK = 8000+2; int n, K, t; int D[4][MAXN][MAXK]; char M[MAXN]; int S[MAXN]; int sum(int i, int t) { // przegapione spotkania przez jazde samochodem return S[std::min(i+t, n)]-S[std::min(i,n)]; } int DP(int p, int i, int k, bool drive = false) { if (k < 0) return -MAXN*MAXN; if (i == n && drive && p == 3) return 0; if (i >= n && (p < 3 || drive)) return -MAXN*MAXN; if (i >= n && p == 3) return 0; return D[p][i][k]; } int main() { std::ios_base::sync_with_stdio(0); std::cin >> n >> K >> t; std::cin >> M; for (int i = 1;i<=n;++i) { S[i] = S[i-1] + (M[i-1] == '3' ? 0 : 1); } #ifdef debug for (int i = 0;i<n;++i) std::clog << M[i] << " "; std::clog << std::endl; for (int i = 0;i<=n;++i) { std::clog << S[i] << " "; } std::clog << std::endl; for (int i = 0;i<=n;++i) { std::clog << sum(i,t) << " "; } std::clog << std::endl; std::clog << std::endl; #endif for (int p=3;p>=1;--p) { for (int k = 0;k<=K;++k) { for (int i=n-1;i>=0;--i) { if (M[i] == '1') { // Biuro if (p == 1) { // Przed robotą D[p][i][k] = std::max(DP(p, i+1, k-1)+1, DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 2) { // w biurze jest lipa D[p][i][k] = std::max(DP(p, i+1, k), DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 3) { // po robocie ciezko pracowac w biurze xD D[p][i][k] = DP(p, i+1, k-1)+1; } } else if (M[i] == '2') { // Zdalne if (p == 1) { // Przed robotą D[p][i][k] = std::max( std::max(DP(p, i+1, k-1)+1, DP(p, i+1, k)), DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 2) { // w biurze jest lipa albo konczymy D[p][i][k] = std::max(DP(p, i+1, k), DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 3) { // po robocie mozna jeszcze popracowac albo nie D[p][i][k] = std::max(DP(p, i+1, k), DP(p, i+1, k-1)+1); } } else if (M[i] == '3') { // Laba if (p == 1) { // Przed robotą D[p][i][k] = std::max(DP(p, i+1, k)+1, DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 2) { // w biurze nie ma laby D[p][i][k] = std::max(DP(p, i+1, k), DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 3) { // Po fajrancie D[p][i][k] = DP(p, i+1, k)+1; } } else { // WTF? } } } } #ifdef debug for (int p=1;p<=3;++p) { for (int k = 0;k<=K;++k) { for (int i=0;i<n;++i) { std::clog << D[p][i][k] << " "; } std::clog << std::endl; } std::clog << std::endl; } #endif std::cout << std::max(std::max(D[1][0][K], D[3][0][K]), -1) << 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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <iostream> // #define debug const int MAXN = 8000+2; const int MAXK = 8000+2; int n, K, t; int D[4][MAXN][MAXK]; char M[MAXN]; int S[MAXN]; int sum(int i, int t) { // przegapione spotkania przez jazde samochodem return S[std::min(i+t, n)]-S[std::min(i,n)]; } int DP(int p, int i, int k, bool drive = false) { if (k < 0) return -MAXN*MAXN; if (i == n && drive && p == 3) return 0; if (i >= n && (p < 3 || drive)) return -MAXN*MAXN; if (i >= n && p == 3) return 0; return D[p][i][k]; } int main() { std::ios_base::sync_with_stdio(0); std::cin >> n >> K >> t; std::cin >> M; for (int i = 1;i<=n;++i) { S[i] = S[i-1] + (M[i-1] == '3' ? 0 : 1); } #ifdef debug for (int i = 0;i<n;++i) std::clog << M[i] << " "; std::clog << std::endl; for (int i = 0;i<=n;++i) { std::clog << S[i] << " "; } std::clog << std::endl; for (int i = 0;i<=n;++i) { std::clog << sum(i,t) << " "; } std::clog << std::endl; std::clog << std::endl; #endif for (int p=3;p>=1;--p) { for (int k = 0;k<=K;++k) { for (int i=n-1;i>=0;--i) { if (M[i] == '1') { // Biuro if (p == 1) { // Przed robotą D[p][i][k] = std::max(DP(p, i+1, k-1)+1, DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 2) { // w biurze jest lipa D[p][i][k] = std::max(DP(p, i+1, k), DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 3) { // po robocie ciezko pracowac w biurze xD D[p][i][k] = DP(p, i+1, k-1)+1; } } else if (M[i] == '2') { // Zdalne if (p == 1) { // Przed robotą D[p][i][k] = std::max( std::max(DP(p, i+1, k-1)+1, DP(p, i+1, k)), DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 2) { // w biurze jest lipa albo konczymy D[p][i][k] = std::max(DP(p, i+1, k), DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 3) { // po robocie mozna jeszcze popracowac albo nie D[p][i][k] = std::max(DP(p, i+1, k), DP(p, i+1, k-1)+1); } } else if (M[i] == '3') { // Laba if (p == 1) { // Przed robotą D[p][i][k] = std::max(DP(p, i+1, k)+1, DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 2) { // w biurze nie ma laby D[p][i][k] = std::max(DP(p, i+1, k), DP(p+1, i+t, k-sum(i,t), true)); } else if (p == 3) { // Po fajrancie D[p][i][k] = DP(p, i+1, k)+1; } } else { // WTF? } } } } #ifdef debug for (int p=1;p<=3;++p) { for (int k = 0;k<=K;++k) { for (int i=0;i<n;++i) { std::clog << D[p][i][k] << " "; } std::clog << std::endl; } std::clog << std::endl; } #endif std::cout << std::max(std::max(D[1][0][K], D[3][0][K]), -1) << std::endl; return 0; } |