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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <cstdio>
#include <cstdint>
#include <vector>
#include <optional>
#include <string>

enum Responsibles {
    OFFICE_MEETING = 1,
    REMOTE_MEETING = 2,
    FREE = 3
};

struct InputData {
    uint64_t n;
    uint64_t max_meetings;
    uint64_t trip_time;
    std::vector<uint64_t> segments;
} input_data;

void parse_input() {
    std::string segments_string;
    std::cin >> input_data.n >> input_data.max_meetings >> input_data.trip_time >> segments_string;  

    for (uint64_t i = 0; i < input_data.n; ++i) {
        char segment = segments_string[i];
        input_data.segments.push_back(static_cast<uint64_t>(segment - '0'));
    }
}

std::optional<uint64_t> calculate_award(const uint64_t start, const uint64_t end) {
    if (start + input_data.trip_time >= end || start + input_data.trip_time > input_data.n || end + input_data.trip_time > input_data.n)
        return std::nullopt;
    bool at_home = true;
    uint64_t trip = 0;
    uint64_t res = 0;
    auto meetings_left = input_data.max_meetings;
    uint64_t possible_to_skip = 0;
    for (uint64_t i = 0; i < input_data.n; ++i) {
        // std::cerr << "calculate_award " << i << ' ' << res << '\n';
        if (i == start) {
            at_home = false;
            trip = input_data.trip_time;
        }
        else if (i == end) {
            at_home = true;
            trip = input_data.trip_time;
        }
        if (input_data.segments[i] == OFFICE_MEETING && (trip > 0 || at_home)) {
            if (meetings_left == 0) return std::nullopt;
            meetings_left--;
            if (!trip) res++;
        }
        else if (input_data.segments[i] == REMOTE_MEETING) {
            if (trip > 0) {
                if (meetings_left == 0) return std::nullopt;
                meetings_left--;
            }
            if (at_home) {
                possible_to_skip++;
            }
        }

        else if (input_data.segments[i] == FREE && at_home && !trip)
            res++;

        if (trip) trip--;
    }
    res += possible_to_skip > meetings_left ? meetings_left : possible_to_skip;
    return res;
}

std::optional<uint64_t> calculate_award() {
    uint64_t res = 0;
    auto meetings_left = input_data.max_meetings;
    uint64_t possible_to_skip = 0;
    for (uint64_t i = 0; i < input_data.n; ++i) {
        if (input_data.segments[i] == OFFICE_MEETING) {
            if (meetings_left == 0) return std::nullopt;
            meetings_left--;
            res++;
        }

        else if (input_data.segments[i] == REMOTE_MEETING) {
            possible_to_skip++;
        }

        else if (input_data.segments[i] == FREE)
            res++;
    }
    res += possible_to_skip > meetings_left ? meetings_left : possible_to_skip;
    return res;
}

std::optional<uint64_t> solve() {
    std::optional<uint64_t> res = calculate_award();
    // std::cerr << "solve " << res.has_value() << '\n';
    for (uint64_t start = 0; start + input_data.trip_time < input_data.n; ++start) {
        for (uint64_t end = input_data.n - input_data.trip_time; end > start; --end) {
            const auto current_award = calculate_award(start, end);
            // std::cerr << "solve " << start << ' ' << end << ' ' << current_award.value_or(2137) << ' ' << res.value_or(2137) << '\n';
            if (current_award.has_value() && current_award.value() >= res.value_or(0))
                res = current_award;
        }
    }
    return res;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    parse_input();
    const auto res = solve();
    std::cout << (res.has_value() ? static_cast<int64_t>(res.value()) : -1) << '\n';

    return 0;
}