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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
using namespace std;

#ifdef GGDEBUG
#define dbg printf
#else
#define dbg // dbg
#endif

int n, k, t;
char day[8010];

struct Meetings {
    char meeting_type;
    std::vector<int> prefix_sum;

    Meetings(char meeting_type) : meeting_type(meeting_type) {
        calculate_prefix_sum();
    }

    int count(int start, int end) {
        int meetings = 0;
        if (start == 0) {
            meetings = prefix_sum[end - 1];
        } else {
            meetings = prefix_sum[end - 1] - prefix_sum[start - 1];
        }

        return meetings;
    }

    void calculate_prefix_sum() {
        prefix_sum.clear();
        prefix_sum.push_back((day[0] == meeting_type) ? 1 : 0);

        for (int i = 1; i < n; ++i) {
            prefix_sum.push_back(prefix_sum[i - 1] +
                                 ((day[i] == meeting_type) ? 1 : 0));
        }
    }
};

Meetings onsite('1'), remote('2'), freee('3');

int solve(int start, int end) {
    dbg("solve(%d, %d)\n", start, end);
    int home_free = 0;
    int home_meetings = 0;
    int meetings_completed = 0;
    int onsite_while_at_home = 0;

    // from 0 to start - 1 he is at home
    home_free += freee.count(0, start);
    home_meetings += remote.count(0, start);
    onsite_while_at_home += onsite.count(0, start);
    dbg("in home from [%d, %d), home_free = %d\n", 0, start, home_free);

    // from start to start + t - 1 he is in the car

    // from start + t to end - t - 1 he is in the office
    meetings_completed +=
        onsite.count(start + t, end - t) + remote.count(start + t, end - t);
    dbg("in office from [%d, %d), meetings_completed = %d\n", start + t,
        end - t, meetings_completed);

    // from end - t to end he is in the car

    // from end to n - 1 he is at home
    home_free += freee.count(end, n);
    home_meetings += remote.count(end, n);
    onsite_while_at_home += onsite.count(end, n);

    dbg("in home from [%d, %d), home_free = %d\n", end, n, home_free);

    // calculate how many meetings he can skip
    int skipped = 0;
    // calculate onsite skipped
    skipped += onsite.count(0, start + t);
    skipped += onsite.count(end - t, n);
    // calculate remote skipped meating during transit
    skipped += remote.count(start, start + t);
    skipped += remote.count(end - t, end);

    int may_skip = k - skipped;
    dbg("may_skip = %d\n", may_skip);

    if (may_skip < 0) {
        return -1;
    }

    int to_skip = min(may_skip, home_meetings);
    dbg("to_skip = %d\n", to_skip);

    int result = home_free + to_skip + onsite_while_at_home;
    dbg("result = %d\n", result);

    return result;
}

int calculate_without_onsite() {
    dbg("calculate_without_onsite()\n");
    int onsite_meetings = onsite.count(0, n);
    int remote_meetings = remote.count(0, n);
    int result = 0;

    result = onsite_meetings + freee.count(0, n);
    dbg("free time = %d\n", result);
    int may_skip = k - onsite_meetings;
    if (may_skip < 0) {
        return -1;
    }

    int to_skip = min(may_skip, remote_meetings);
    result += to_skip;

    return result;
}

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

    onsite.calculate_prefix_sum();
    remote.calculate_prefix_sum();
    freee.calculate_prefix_sum();

    int res = -1;
    res = calculate_without_onsite();

    dbg("res = %d\n\n", res);

    // check all onsite possibilities
    for (int start = 0; start + 2 * t <= n; ++start) {
        for (int end = start + 2 * t; end <= n; ++end) {
            int now = solve(start, end);
            dbg("\n");
            dbg("start = %d, end = %d, now = %d\n", start, end, now);
            res = max(res, now);
        }
    }

    cout << res << "\n";
}