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
#include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int min(int a, int b) {
    return (a < b) ? a : b;
}

int get(const std::vector<int>& vec, int index) {
    if (index < 0) {
        return 0;
    }
    return vec[index];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    int k;
    int t;

    cin >> n;
    cin >> k;
    cin >> t;

    vector<int> office_meetings(n, 0);
    vector<int> remote_meetings(n, 0);
    vector<int> free_time(n, 0);

    string v;
    cin >> v;

    for (int i = 0; i < n; i++) {
        office_meetings[i] = get(office_meetings, i - 1);
        remote_meetings[i] = get(remote_meetings, i - 1);
        free_time[i] = get(free_time, i - 1);
        if (v[i] == '1') {
            office_meetings[i] = get(office_meetings, i - 1) + 1;           
        }
        if (v[i] == '2') {
            remote_meetings[i] = get(remote_meetings, i - 1) + 1;
        }
        if (v[i] == '3') {
            free_time[i] = get(free_time, i - 1) + 1;
        }
    }
    
    int max_val = -1;

    // No office trip
    int skipped_meetings = remote_meetings[n - 1] + office_meetings[n - 1];
    if (skipped_meetings > k) {
        max_val = -1;
    } else {
        max_val = free_time[n - 1] + skipped_meetings;
    }

    /*for (int i = 0; i < n; i++) {
        cout << office_meetings[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        cout << remote_meetings[i] << " ";
    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        cout << free_time[i] << " ";
    }
    cout << endl;

    cout << "no office" << max_val << endl;*/

    // One office trip
    for (int i = 0; i <= n - (2 * t + 1); i++) {
        for (int j = i + t + 1; j <= n - t; j++) {
            //cout << "i, j = " << i << " " << j << endl;
            int missed_meetings_during_travel = 
                get(office_meetings, i + t - 1) - get(office_meetings, i - 1) 
                + get(remote_meetings, i + t - 1) - get(remote_meetings, i - 1)
                + get(office_meetings, j + t - 1) - get(office_meetings, j - 1) 
                + get(remote_meetings, j + t - 1) - get(remote_meetings, j - 1);
            //cout << "mm = " << missed_meetings_during_travel << endl;
            if (missed_meetings_during_travel > k) {
                continue;
            } else {
                int missed_office_meetings = get(office_meetings, i - 1) - get(office_meetings, -1) + get(office_meetings, n - 1) - get(office_meetings, j + t -1);
                int missed_remote_meetings = get(remote_meetings, i - 1) - get(remote_meetings, -1) + get(remote_meetings, n - 1) - get(remote_meetings, j + t -1);
                if (missed_office_meetings > k - missed_meetings_during_travel) {
                    continue;
                } else {
                    int f_time = get(free_time, i - 1) - get(free_time, -1) + get(free_time, n - 1) - get(free_time, j + t -1);
                    max_val = max(max_val, f_time + min(missed_office_meetings + missed_remote_meetings, k - missed_meetings_during_travel));
                }
            }
        }
    }

    cout << max_val;

    return 0;
}