#include <bits/stdc++.h> using namespace std; typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef long double ldbl; typedef pair<int, int> pii; typedef pair<uint, uint> puu; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<double, double> pdd; typedef vector<int> vi; typedef vector<uint> vu; typedef vector<ll> vll; typedef vector<ull> vull; typedef vector<pii> vpii; typedef vector<puu> vpuu; typedef vector<pll> vpll; typedef vector<pull> vpull; typedef vector<string> vstr; typedef vector<double> vdbl; typedef vector<ldbl> vldbl; #define pb push_back #define ppb pop_back #define pfr push_front #define ppfr pop_front #define emp emplace #define empb emplace_back #define be begin #define rbe rbegin #define all(x) (x).be(), (x).end() #define rall(x) (x).rbe(), (x).rend() #define fir first #define sec second #define mkp make_pair #define brif(cond) if (cond) break #define ctif(cond) if (cond) continue #define retif(cond) if (cond) return void fastio() {ios_base::sync_with_stdio(false);cin.tie(nullptr);} template<typename T> T gcd(T a, T b) {return b ? gcd(b, a%b) : a;} template<typename T> T extgcd(T a, T b, T &x, T &y) { T x0 = 1, y0 = 0, x1 = 0, y1 = 1; while (b) { T q = a/b; a %= b; swap(a, b); x0 -= q*x1; swap(x0, x1); y0 -= q*y1; swap(y0, y1); } x = x0; y = y0; return a; } int ctz(uint x) {return __builtin_ctz(x);} int ctzll(ull x) {return __builtin_ctzll(x);} int clz(uint x) {return __builtin_clz(x);} int clzll(ull x) {return __builtin_clzll(x);} int popcnt(uint x) {return __builtin_popcount(x);} int popcntll(ull x) {return __builtin_popcountll(x);} int bsr(uint x) {return 31^clz(x);} int bsrll(ull x) {return 63^clzll(x);} template<typename T> void umax(T &dst, T src) { dst = max(dst, src); } #define N 8016 char a[N]; int pre[N]; int dp[N][N][3]; int main() { fastio(); int n, k, t; int ans = -1; cin >> n >> k >> t >> a; for (int i = 0; i < n; ++i) pre[i+1] = pre[i]+(a[i]<'3'); for (int i = 0; i <= n; ++i) { for (int j = 0; j <= k; ++j) { for (int w : {0, 1, 2}) dp[i][j][w] = -1; } } dp[0][0][0] = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j <= k; ++j) { for (int w : {0, 1, 2}) { ctif(dp[i][j][w] < 0); /// meeting: if (a[i] == '2' || (a[i] == '1' && w == 1)) umax(dp[i+1][j][w], dp[i][j][w]); /// solve/work/nothing: umax(dp[i+1][j+pre[i+1]-pre[i]][w], dp[i][j][w]+(w!=1)); /// drive: if (w < 2 && i+t <= n) umax(dp[i+t][j+pre[i+t]-pre[i]][w+1], dp[i][j][w]); } } } /*cerr << "DP:\ni\\j"; for (int j = 0; j <= k; ++j) cerr << '\t' << j; cerr << '\n'; for (int i = 0; i <= n; ++i) { cerr << i; for (int j = 0; j <= k; ++j) { cerr << '\t'; for (int w : {0, 1, 2}) { if (w) cerr << ','; if (dp[i][j][w] < 0) cerr << '_'; else cerr << dp[i][j][w]; } } cerr << '\n'; }*/ for (int j = 0; j <= k; ++j) { for (int w : {0, 2}) umax(ans, dp[n][j][w]); } cout << ans << '\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 | #include <bits/stdc++.h> using namespace std; typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef long double ldbl; typedef pair<int, int> pii; typedef pair<uint, uint> puu; typedef pair<ll, ll> pll; typedef pair<ull, ull> pull; typedef pair<double, double> pdd; typedef vector<int> vi; typedef vector<uint> vu; typedef vector<ll> vll; typedef vector<ull> vull; typedef vector<pii> vpii; typedef vector<puu> vpuu; typedef vector<pll> vpll; typedef vector<pull> vpull; typedef vector<string> vstr; typedef vector<double> vdbl; typedef vector<ldbl> vldbl; #define pb push_back #define ppb pop_back #define pfr push_front #define ppfr pop_front #define emp emplace #define empb emplace_back #define be begin #define rbe rbegin #define all(x) (x).be(), (x).end() #define rall(x) (x).rbe(), (x).rend() #define fir first #define sec second #define mkp make_pair #define brif(cond) if (cond) break #define ctif(cond) if (cond) continue #define retif(cond) if (cond) return void fastio() {ios_base::sync_with_stdio(false);cin.tie(nullptr);} template<typename T> T gcd(T a, T b) {return b ? gcd(b, a%b) : a;} template<typename T> T extgcd(T a, T b, T &x, T &y) { T x0 = 1, y0 = 0, x1 = 0, y1 = 1; while (b) { T q = a/b; a %= b; swap(a, b); x0 -= q*x1; swap(x0, x1); y0 -= q*y1; swap(y0, y1); } x = x0; y = y0; return a; } int ctz(uint x) {return __builtin_ctz(x);} int ctzll(ull x) {return __builtin_ctzll(x);} int clz(uint x) {return __builtin_clz(x);} int clzll(ull x) {return __builtin_clzll(x);} int popcnt(uint x) {return __builtin_popcount(x);} int popcntll(ull x) {return __builtin_popcountll(x);} int bsr(uint x) {return 31^clz(x);} int bsrll(ull x) {return 63^clzll(x);} template<typename T> void umax(T &dst, T src) { dst = max(dst, src); } #define N 8016 char a[N]; int pre[N]; int dp[N][N][3]; int main() { fastio(); int n, k, t; int ans = -1; cin >> n >> k >> t >> a; for (int i = 0; i < n; ++i) pre[i+1] = pre[i]+(a[i]<'3'); for (int i = 0; i <= n; ++i) { for (int j = 0; j <= k; ++j) { for (int w : {0, 1, 2}) dp[i][j][w] = -1; } } dp[0][0][0] = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j <= k; ++j) { for (int w : {0, 1, 2}) { ctif(dp[i][j][w] < 0); /// meeting: if (a[i] == '2' || (a[i] == '1' && w == 1)) umax(dp[i+1][j][w], dp[i][j][w]); /// solve/work/nothing: umax(dp[i+1][j+pre[i+1]-pre[i]][w], dp[i][j][w]+(w!=1)); /// drive: if (w < 2 && i+t <= n) umax(dp[i+t][j+pre[i+t]-pre[i]][w+1], dp[i][j][w]); } } } /*cerr << "DP:\ni\\j"; for (int j = 0; j <= k; ++j) cerr << '\t' << j; cerr << '\n'; for (int i = 0; i <= n; ++i) { cerr << i; for (int j = 0; j <= k; ++j) { cerr << '\t'; for (int w : {0, 1, 2}) { if (w) cerr << ','; if (dp[i][j][w] < 0) cerr << '_'; else cerr << dp[i][j][w]; } } cerr << '\n'; }*/ for (int j = 0; j <= k; ++j) { for (int w : {0, 2}) umax(ans, dp[n][j][w]); } cout << ans << '\n'; return 0; } |