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
#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 8000;
int dp[MAX_N + 1][2][MAX_N + 1]; 
char schedule[MAX_N + 1];

int main() {
    int n, k, t;
    cin >> n >> k >> t;
    cin >> schedule;
    
    
    memset(dp, -1, sizeof(dp));
    
   
    dp[0][0][0] = 0;
    
    for (int i = 0; i < n; i++) {
        for (int loc = 0; loc < 2; loc++) {
            for (int missed = 0; missed <= k; missed++) {
                if (dp[i][loc][missed] == -1) continue;
                
                
                if (loc == 0) {
                    
                    if (schedule[i] != '1' || (schedule[i] == '1' && missed + 1 <= k)) {
                        int new_missed = missed + (schedule[i] == '1' || schedule[i] == '2');
                        if (new_missed <= k) {
                            dp[i + 1][0][new_missed] = max(dp[i + 1][0][new_missed], dp[i][0][missed] + 1);
                        }
                    }
                    
                    
                    if (schedule[i] == '2' || schedule[i] == '3') {
                        dp[i + 1][0][missed] = max(dp[i + 1][0][missed], dp[i][0][missed]);
                    }
                    
                   
                    if (i + 2*t <= n && i + t < n) {
                        int new_missed = missed;
                        for (int j = 0; j < t; j++) {
                            if (i + j < n && (schedule[i + j] == '1' || schedule[i + j] == '2')) new_missed++;
                        }
                        if (new_missed <= k) {
                            dp[i + t][1][new_missed] = max(dp[i + t][1][new_missed], dp[i][0][missed]);
                        }
                    }
                }
                
                else if (loc == 1) {
                    
                    if (schedule[i] == '1' || schedule[i] == '2' || schedule[i] == '3') {
                        dp[i + 1][1][missed] = max(dp[i + 1][1][missed], dp[i][1][missed]);
                    }
                    
                    
                    if (i + t <= n) {
                        int new_missed = missed;
                        for (int j = 0; j < t; j++) {
                            if (i + j < n && (schedule[i + j] == '1' || schedule[i + j] == '2')) new_missed++;
                        }
                        if (new_missed <= k) {
                            dp[i + t][0][new_missed] = max(dp[i + t][0][new_missed], dp[i][1][missed]);
                        }
                    }
                }
            }
        }
    }
    
    
    int result = -1;
    for (int missed = 0; missed <= k; missed++) {
        if (dp[n][0][missed] != -1) {
            result = max(result, dp[n][0][missed]);
        }
    }
    
    cout << result << endl;
    
    return 0;
}