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

using namespace std;

int range(int left, int right, vector<int>& r) {
    if (right < left) return 0;
    if (left == 0) return r[right];
    return r[right] - r[left - 1];
}

int main() {
    int n, k, t;
    cin >> n >> k >> t;
    string schedule;
    cin >> schedule;
    vector<int> r = vector<int>(n);
    vector<int> y = vector<int>(n);
    vector<int> g = vector<int>(n);
    int r_count = 0, y_count = 0, g_count = 0;
    int lost_meetings;
    int remaining_yellows;
    int remaining_greens;
    int remaining_reds;

    for (int i = 0; i < schedule.size(); i++) {
        if (schedule[i] == '1') r_count++;
        if (schedule[i] == '2') y_count++;
        if (schedule[i] == '3') g_count++;
        r[i] = r_count;
        y[i] = y_count;
        g[i] = g_count;
    }

    if (r_count <= k) {
        cout << min(k, y_count + r_count) + g_count;
        return 0;
    }

    // for (int i = 0; i < schedule.size(); i++) {
    //     cout << r[i] << " ";
    // }
    // cout << endl;
    // for (int i = 0; i < schedule.size(); i++) {
    //     cout << y[i] << " ";
    // }
    // cout << endl;
    // for (int i = 0; i < schedule.size(); i++) {
    //     cout << g[i] << " ";
    // }
    // cout << endl;

    int ans = -1;

    for (int s = 0; s < n - (2 * t) + 1; s++) {
        for (int e = s + t; e < n - t + 1; e++) {

            // home time
            // [0; s - 1] + [e + t; n - 1]
            remaining_yellows = range(0, s - 1, y) + range(e + t, n - 1, y);
            remaining_greens = range(0, s - 1, g) + range(e + t, n - 1, g);
            remaining_reds = range(0, s - 1, r) + range(e + t, n - 1, r);

            // lost in transit
            // [s; s + t - 1] + [e; e + t - 1]
            lost_meetings = range(s, s + t - 1, r) + range(s, s + t - 1, y) +
                range(e, e + t - 1, r) + range(e, e + t - 1, y) + remaining_reds;

            // cout << "lm: " << lost_meetings << ", ry: " << remaining_yellows << ", rg: " << remaining_greens <<
            //     ", budget: " << k - lost_meetings << ", skipped meetings: " << min(k - lost_meetings, remaining_yellows + remaining_reds) <<
            //     ", fun time: " << remaining_greens + min(k - lost_meetings, remaining_yellows + remaining_reds) << ", answer "
            //     << (k - lost_meetings < 0 ?
            //         -1 : remaining_greens + min(k - lost_meetings, remaining_yellows)) << endl;

            ans = max(ans, (k - lost_meetings < 0 ?
                -1 : remaining_greens + min(k - lost_meetings, remaining_yellows) + remaining_reds));

        }
    }

    cout << ans << endl;
    return 0;
}