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
#include <iostream>
using namespace std;

int tab[8'007];
int dp[8'007][8'007][3];
int pref[8007];

int main()
{
    //freopen("cash.txt","r",stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    int n, k, t, odp=-1;
    cin>>n>>k>>t;
    cin>>s;
    for(int a=1; a<=n; a++)
        tab[a-1]=s[a-1]-'0';
    for(int a=1; a<=n; a++){
        pref[a]=pref[a-1];
        if(tab[a-1]!=3)
            pref[a]++;
    }
    for(int a=0; a<=n; a++)
        for(int i=0; i<=n*2; i++)
            for(int o=0; o<3; o++)
                dp[a][i][o]=-1'000'000'007;
    dp[0][0][0]=0;
    for(int a=0; a<n; a++){
        for(int i=0; i<=k; i++){
            if(a+t<=n && i+pref[a+t]-pref[a]<=k){
                dp[a+t][i+pref[a+t]-pref[a]][1]=max(dp[a][i][0],dp[a+t][i+pref[a+t]-pref[a]][1]);
                dp[a+t][i+pref[a+t]-pref[a]][2]=max(dp[a][i][1],dp[a+t][i+pref[a+t]-pref[a]][2]);
            }
            if(tab[a]==3){
                dp[a+1][i][0]=max(dp[a][i][0]+1,dp[a+1][i][0]);
                dp[a+1][i][1]=max(dp[a][i][1],dp[a+1][i][1]);
                dp[a+1][i][2]=max(dp[a][i][2]+1,dp[a+1][i][2]);
            }
            if(tab[a]!=3){
                dp[a+1][i+1][0]=max(dp[a][i][0]+1,dp[a+1][i+1][0]);
                dp[a+1][i][1]=max(dp[a][i][1],dp[a+1][i][1]);
                dp[a+1][i+1][2]=max(dp[a][i][2]+1,dp[a+1][i+1][2]);
            }
            if(tab[a]==2)
                for(int o=0; o<3; o++)
                    dp[a+1][i][o]=max(dp[a][i][o],dp[a+1][i][o]);
            if(tab[a]==1)
                dp[a+1][i][1]=max(dp[a][i][1],dp[a+1][i][1]);
        }
        //cout<<a<<"\n";
        if(1)
            continue;
        for(int i=0; i<=7; i++)
            cout<<dp[a][i][2]<<" ";
        cout<<endl;
    }
    //cout<<"XD";
    /*for(int i=0; i<=7; i++)
        cout<<dp[n][i][2]<<" ";
    cout<<endl;*/
    for(int a=0; a<=k; a++)
        odp=max(odp,max(dp[n][a][0],dp[n][a][2]));
    cout<<odp;
}