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
#include <cstdio>
#include <algorithm>
#define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); ++i)
using namespace std;

int n, max_skip, travel_time;
char P[8005];

int result;
int total_office_meetings, office_meetings[8005];
int total_remote_meetings, remote_meetings[8005];

inline int get_office_meetings(int up_to_time) {
    if (up_to_time >= n) return total_office_meetings;
    if (up_to_time < 0) return 0;
    return office_meetings[up_to_time];
}

inline int get_remote_meetings(int up_to_time) {
    if (up_to_time >= n) return total_remote_meetings;
    if (up_to_time < 0) return 0;
    return remote_meetings[up_to_time];
}

int main() {
    scanf("%d %d %d", &n, &max_skip, &travel_time);
    scanf("%s", P);

    // Scan type of meetings
    total_office_meetings = total_remote_meetings = 0;
    FOR(i,0,n) {
        if (P[i] == '1') ++total_office_meetings;
        else if (P[i] == '2') ++total_remote_meetings;
        office_meetings[i] = total_office_meetings;
        remote_meetings[i] = total_remote_meetings;
    }

    result = -1;

    // Case 1 - whole time at home
    if (total_office_meetings <= max_skip)
        result = max(result, n - max(0, total_remote_meetings + total_office_meetings - max_skip));

    // Case 2 - one time in the office (at least for one hour)
    FOR(outside_length, 2*travel_time+1, n+1) {
        int home_lenght = n - outside_length;

        // If there is no possibility to have more free time as currently best result - just stop
        if ((result != -1) && (home_lenght < result)) break;

        // For every segment of lenght 'outside_length'
        FOR(outside_start, 0, n-outside_length+1) {
            int outside_end = outside_start + outside_length - 1;
            int office_start = outside_start + travel_time;
            int office_end = outside_end - travel_time;

            int available_skip = max_skip;
            available_skip -= get_remote_meetings(outside_end) - get_remote_meetings(office_end);
            available_skip -= get_remote_meetings(office_start-1) - get_remote_meetings(outside_start-1);
            available_skip -= total_office_meetings - get_office_meetings(office_end);
            available_skip -= get_office_meetings(office_start-1);
            if (available_skip < 0) continue;

            int home_remote = total_remote_meetings - get_remote_meetings(outside_end) + get_remote_meetings(outside_start-1);
            int local_result = home_lenght - max(0, home_remote - available_skip);
            result = max(result, local_result);
        }
    }

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