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

const int MAX_DAY_SIZE = 8002;
char schedule[MAX_DAY_SIZE];

const int NO_CAN_DO = -1000000;

int meeting_pref[MAX_DAY_SIZE];

const char OFFICE_MEET = '1';
const char ONLINE_MEET = '2';
const char FREE_TIME = '3';

int best[3][MAX_DAY_SIZE][MAX_DAY_SIZE];

int main() {
    int day_size, miss_limit, travel_time;
    scanf("%d%d%d", &day_size, &miss_limit, &travel_time);
    scanf("%s", schedule + 1);

    int wyn = -1;

    for (int i = 1; i <= day_size; i++) {
        meeting_pref[i] = meeting_pref[i - 1] + (schedule[i] == FREE_TIME ? 0 : 1);
    }

    for (int travel_count = 0; travel_count <= 2; travel_count++) {
        for (int curr_time = 0; curr_time <= day_size; curr_time++) {
            for (int skipped = 0; skipped <= miss_limit; skipped++) {
                best[travel_count][curr_time][skipped] = NO_CAN_DO;
            }
        }
    }
    best[0][0][0] = 0;


    for (int travel_count = 0; travel_count <= 2; travel_count++) {
        for (int curr_time = 1; curr_time <= day_size; curr_time++) {
            for (int skipped = 0; skipped <= miss_limit; skipped++) {
                // Go to meeting
                if (schedule[curr_time] == ONLINE_MEET || (schedule[curr_time] == OFFICE_MEET && travel_count == 1)) {
                    best[travel_count][curr_time][skipped] = max(
                        best[travel_count][curr_time][skipped],
                        best[travel_count][curr_time - 1][skipped]
                    );
                }
                // Have fun or work
                int fun_amount = travel_count == 1 ? 0 : 1;
                if (schedule[curr_time] == FREE_TIME) {
                    best[travel_count][curr_time][skipped] = max(
                        best[travel_count][curr_time][skipped],
                        best[travel_count][curr_time - 1][skipped] + fun_amount
                    );
                } else if (skipped > 0) {
                    best[travel_count][curr_time][skipped] = max(
                        best[travel_count][curr_time][skipped],
                        best[travel_count][curr_time - 1][skipped - 1] + fun_amount
                    );
                }
                // End travel now
                if (travel_count > 0 && curr_time >= travel_time) {
                    int meetings_skipped = meeting_pref[curr_time] - meeting_pref[curr_time - travel_time];
                    if (skipped >= meetings_skipped) {
                        best[travel_count][curr_time][skipped] = max(
                            best[travel_count][curr_time][skipped],
                            best[travel_count - 1][curr_time - travel_time][skipped - meetings_skipped]
                        );
                    }
                }

                // printf("best[%d][%d][%d] = %d\n", travel_count, curr_time, skipped, best[travel_count][curr_time][skipped]);

                if (travel_count != 1 && curr_time == day_size) {
                    wyn = max(wyn, best[travel_count][curr_time][skipped]);
                }
            }
        }
    }

    printf("%d\n", wyn);
}