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 <cstdio>
#include <cstdlib>
#include <cassert>

#include <algorithm>

char commands[8192];

int remotes_psum[8192];
int onsite_psum[8192];

const char ONSITE_MEETING = '1';
const char REMOTE_MEETING = '2';
const char FOCUS_TIME = '3';

int main() {
    int n, k, t;
    scanf("%d %d %d\n", &n, &k, &t);
    scanf("%s\n", commands);

    remotes_psum[0] = 0;
    onsite_psum[0] = 0;

    for (int i = 0; i < n; i++) {
        switch (commands[i]) {
        case ONSITE_MEETING:
            remotes_psum[i + 1] = remotes_psum[i];
            onsite_psum[i + 1] = onsite_psum[i] + 1;
            break;
        case REMOTE_MEETING:
            remotes_psum[i + 1] = remotes_psum[i] + 1;
            onsite_psum[i + 1] = onsite_psum[i];
            break;
        case FOCUS_TIME:
            remotes_psum[i + 1] = remotes_psum[i];
            onsite_psum[i + 1] = onsite_psum[i];
            break;
        default:
            assert(false);
        };
    }

    int best = -1;

    // Special case: we don't go to work at all
    // We must skip all onsite meetings in that case
    // We can attend all remote meetings in the worst case, though
    if (onsite_psum[n] <= k) {
        // We can also skip some remote meetings, but - combined with skipped
        // onsite meetings - not more than k. We use the remaining time
        // to solve algorithmic tasks.
        best = n - std::max(0, onsite_psum[n] + remotes_psum[n] - k);
    }

    // Leave home at i, arrive back at j
    for (int i = 0; i <= n - 2 * t; i++) {
        for (int j = i + 2 * t; j <= n; j++) {
            // Onsite meetings must be skipped when we are not at work
            const int onsite_mandatorily_skipped = onsite_psum[n] - onsite_psum[j - t] + onsite_psum[i + t];

            // Remote meetings must be skipped while we travel to work
            const int remote_mandatorily_skipped
                    = remotes_psum[j] - remotes_psum[j - t]
                    + remotes_psum[i + t] - remotes_psum[i];
            
            if (onsite_mandatorily_skipped + remote_mandatorily_skipped <= k) {
                const int remaining_skip_budget = k - onsite_mandatorily_skipped - remote_mandatorily_skipped;
                const int remote_meetings_while_at_home = remotes_psum[n] - remotes_psum[j] + remotes_psum[i];

                // No use in skipping meetings at work - they won't increase
                // the available time for solving tasks. It only makes sense
                // to skip remote meetings outside work.
                const int time_for_tasks = n - (j - i) - std::max(0, remote_meetings_while_at_home - remaining_skip_budget);
                // printf("(%d %d): %d (mandatory: %d, voluntarily: %d)\n", i, j, time_for_tasks, onsite_mandatorily_skipped + remote_mandatorily_skipped, std::min(0, remote_meetings_while_at_home - remaining_skip_budget));
                best = std::max(best, time_for_tasks);
            } else {
                // printf("(%d %d): (mandatory: %d)\n", i, j, onsite_mandatorily_skipped + remote_mandatorily_skipped);
            }
        }
    }

    printf("%d\n", best);

    return 0;
}