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
/* 2025
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>

int time;
int max_absences;
int travel_time;
char category[8192];
int remote_meetings[8192];
int office_meetings[8192];

int main(void)
{
    scanf("%d %d %d %s", &time, &max_absences, &travel_time, category);
    for(int t = 1; t <= time; ++t)
    {
        office_meetings[t] = office_meetings[t - 1] + (category[t - 1] == '1');
        remote_meetings[t] = remote_meetings[t - 1] + (category[t - 1] == '2');
    }

    if(office_meetings[time] <= max_absences) // Can "work" at home all day
    {
        printf("%d\n", time - std::max(0, office_meetings[time] + remote_meetings[time] - max_absences));
        return 0;
    }

    // Need to go to work
    int best = -1;
    for(int s = 1; s + travel_time * 2 <= time; ++s)
        for(int e = s + travel_time * 2; e <= time; ++e)
        {
            int missed_meetings =
                // Office meetings before arriving at the office
                office_meetings[s + travel_time - 1] +
                // Remote meetings when travelling to work
                (remote_meetings[s + travel_time - 1] - remote_meetings[s - 1]) +
                // Office meetings after leaving the office
                (office_meetings[time] - office_meetings[e - travel_time]) +
                // Remote meetings when travelling home
                (remote_meetings[e] - remote_meetings[e - travel_time]);

            if(missed_meetings > max_absences)
                continue;

            int absences_left = max_absences - missed_meetings;
            int left_meetings = remote_meetings[s - 1] + remote_meetings[time] - remote_meetings[e];
            best = std::max(best, s + time - e - 1 - std::max(0, left_meetings - absences_left));
        }

    printf("%d\n", best);
    return 0;
}