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
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string s;
    int n, k, t, result;
    cin >> n >> k >> t >> s;
    vector<int> P(n+1,0);
    for(int i=0;i<n;i++) P[i+1] = P[i] + ((s[i]=='1' || s[i]=='2')?1:0);
    vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(3, vector<int>(k+1, -1)));
    dp[0][0][0] = 0;
    for(int i=0;i<=n;i++){
        for(int state=0;state<3;state++){
            for(int miss=0;miss<=k;miss++){
                if(dp[i][state][miss]==-1) continue;
                if(i<n){
                    char duty = s[i];
                    if(state==0 || state==2){
                        if(duty=='1'){
                            if(miss+1<=k)
                                dp[i+1][state][miss+1] = max(dp[i+1][state][miss+1], dp[i][state][miss] + 1);
                        }
                        else if(duty=='2'){
                            dp[i+1][state][miss] = max(dp[i+1][state][miss], dp[i][state][miss]);
                            if(miss+1<=k)
                                dp[i+1][state][miss+1] = max(dp[i+1][state][miss+1], dp[i][state][miss] + 1);
                        }
                        else if(duty=='3'){
                            dp[i+1][state][miss] = max(dp[i+1][state][miss], dp[i][state][miss] + 1);
                        }
                    }
                    else if(state==1){
                        dp[i+1][1][miss] = max(dp[i+1][1][miss], dp[i][1][miss]);
                    }
                }
                if(state==0 && i+t<=n){
                    int cost = P[i+t]-P[i];
                    if(miss+cost<=k)
                        dp[i+t][1][miss+cost] = max(dp[i+t][1][miss+cost], dp[i][0][miss]);
                }
                if(state==1 && i+t<=n){
                    int cost = P[i+t]-P[i];
                    if(miss+cost<=k)
                        dp[i+t][2][miss+cost] = max(dp[i+t][2][miss+cost], dp[i][1][miss]);
                }
            }
        }
    }
    result = -1;
    for(int i=0;i<=k;i++){
        result = max(result, dp[n][0][i]);
        result = max(result, dp[n][2][i]);
    }
    cout << result;
}