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

using namespace std;

const int N = 8e3 + 5;
int czynnosci[N];

int sliding_window(int t, int m, int count_1, int count_2, int czynnosci[N], int n, int k) {
    int ret = -1;

    int bad_1 = 0, bad_2 = 0;
    int inside_2 = 0;
    for (int i = 1; i <= t; i++) {
        // czy tracimy cos w trakcie:
        if (czynnosci[i] == 1){bad_1 += 1;} // dojazdu
        if (czynnosci[i] == 2){bad_2 += 1;} // dojazdu
        if (czynnosci[t+m+i] == 1){bad_1 += 1;} // powrotu
        if (czynnosci[t+m+i] == 2){bad_2 += 1;} // powrotu
    }
    for (int i = t+1; i <= t+m; i++) {
        if (czynnosci[i] == 2){inside_2 += 1;} // zdalne w biurze
    }
    for (int i = t+m+t+1; i <= n; i ++) { //spotkania stacjonarne poza biurem
        if (czynnosci[i] == 1){bad_1 += 1;}
    }
    // cout << bad_1 << " " << bad_2 << endl;
    int opuszczone_z_gory = bad_1 + bad_2;
    int pozostale_spotkania = count_2 - bad_2 - inside_2;
    if (pozostale_spotkania <= k - opuszczone_z_gory) {
        return n - (m + 2*t);
    }
    if (k - opuszczone_z_gory >= 0) {
        ret = max(ret, n - (m + 2*t) - (pozostale_spotkania - (k - opuszczone_z_gory)));
    }
    int left_left = 1;
    int left_right = t;
    int right_left = t+m+1;
    int right_right = m + 2*t;
    while (right_right < n) {
        // cout << bad_1 << " " << bad_2 << endl;
        if (czynnosci[left_left] == 2) {
            opuszczone_z_gory -= 1;
            pozostale_spotkania += 1;
        }
        left_left += 1;

        if (czynnosci[left_right+1] == 1 or czynnosci[left_right+1] == 2) {
            opuszczone_z_gory += 1;
        }
        left_right += 1;

        if (czynnosci[right_left] == 1 or czynnosci[right_left] == 2) {
            opuszczone_z_gory -= 1;
            // pozostale_spotkania -= 1;
        }
        right_left += 1;

        if (czynnosci[right_right+1] == 2) {
            opuszczone_z_gory += 1;
            pozostale_spotkania -= 1;
        }
        right_right += 1;
        // cout << pozostale_spotkania << endl;
        // cout << k - opuszczone_z_gory << endl;
        if (pozostale_spotkania <= k - opuszczone_z_gory) {
            return n - (m + 2*t);
        }
        if (k - opuszczone_z_gory >= 0) {
            ret = max(ret, n - (m + 2*t) - (pozostale_spotkania - (k - opuszczone_z_gory)));
        }
        // cout << ret << endl;
    }
    return ret;
}


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

    char activity;
    int count_1 = 0, count_2 = 0;
    for (int i = 1; i <= n; i++) {
        cin >> activity;
        int int_activity = activity - '0';
        czynnosci[i] = int_activity;
        if (int_activity == 1) {count_1 += 1;}
        if (int_activity == 2) {count_2 += 1;}
    }
    if (count_1 <= k) {
        cout << n;
    }
    else { // linear search po liczbie godzin miedzy dojazdami + sliding window
        int ret = -1;
        int sw;
        for (int m = 0; m <= n-2*t; m++) {
            sw = sliding_window(t, m, count_1, count_2, czynnosci, n, k);
            ret = max(ret, sw);
        }
        cout << ret;
    }
    return 0;
}