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
#include "iostream"
#include "sstream"
#include "vector"
#include "algorithm"

int main() {
    int n, k, t;
    std::cin >> n >> k >> t;

    std::string events;
    std::cin >> events;

    auto count = std::vector<std::vector<int>>(n+1, std::vector<int>(4, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= 3; j++) {
            count[i + 1][j] = count[i][j] + (events[i] -'0' == j);
        }
    }

    // 1: office
    // 2: remote
    // 3: free

    int result = -1;
    if (count[n][1] <= k) {
        result = count[n][3] + std::min(count[n][1] + count[n][2], k);
    }

    for (int i = 1; i + t - 1 <= n; i++) {
        for (int j = i + t; j + t - 1 <= n; j++) {
            int potentially_free = (i - 1) + (n - (j + t - 1));

            int travel_missed = 
                (count[i + t - 1][1] - count[i - 1][1]) + 
                (count[i + t - 1][2] - count[i - 1][2]) +
                (count[j + t - 1][1] - count[j - 1][1]) + 
                (count[j + t - 1][2] - count[j - 1][2]);

            int home_missed = 
                count[i - 1][1] +
                (count[n][1] - count[j + t - 1][1]);

            if (home_missed + travel_missed > k) {
                    continue;
            }
            int new_k = k - travel_missed - home_missed;

            int meetings_possible =
                count[i - 1][2] +
                (count[n][2] - count[j + t - 1][2]);

            result = std::max(result, potentially_free - std::max(meetings_possible - new_k, 0));
        }
    }
    std::cout << result << std::endl;
    return 0;
}