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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPCON(i, n) for(int i=0; i<=n; i++)
#define LL long long
#define SIMPLEVEC vector<int>

#define OFFICE '1'
#define REMOTE '2'

class BajtazarHardWorking {
    int n, k, t;
    string s;

    SIMPLEVEC forced_skip_home;
    SIMPLEVEC forced_skip_transit;
    SIMPLEVEC tasks_home;
    SIMPLEVEC skip_option_home;

    vector<LL> fsh, fst, th, soh;

public:
    BajtazarHardWorking() {
        cin >> n >> k >> t;
        cin >> s;

        forced_skip_home.resize(n);
        forced_skip_transit.resize(n);
        tasks_home.resize(n);
        skip_option_home.resize(n);

        REP(i,n) {
            char c = s[i];
            if (c == OFFICE) {
                forced_skip_home[i] = 1;
                forced_skip_transit[i] = 1;
                tasks_home[i] = 1;
                skip_option_home[i] = 0;
            } else if (c == REMOTE) {
                forced_skip_home[i] = 0;
                forced_skip_transit[i] = 1;
                tasks_home[i] = 0;
                skip_option_home[i] = 1;
            } else {
                forced_skip_home[i] = 0;
                forced_skip_transit[i] = 0;
                tasks_home[i] = 1;
                skip_option_home[i] = 0;
            }
        }

        fsh.resize(n + 1, 0);
        fst.resize(n + 1, 0);
        th.resize(n + 1, 0);
        soh.resize(n + 1, 0);

        REP(i,n) {
            fsh[i + 1] = fsh[i] + forced_skip_home[i];
            fst[i + 1] = fst[i] + forced_skip_transit[i];
            th[i + 1] = th[i] + tasks_home[i];
            soh[i + 1] = soh[i] + skip_option_home[i];
        }
    }

    LL solve() const {
        auto sum_fsh = [&](int l, int r) {
            return fsh[r] - fsh[l];
        };
        auto sum_fst = [&](int l, int r) {
            return fst[r] - fst[l];
        };
        auto sum_th = [&](int l, int r) {
            return th[r] - th[l];
        };
        auto sum_soh = [&](int l, int r) {
            return soh[r] - soh[l];
        };

        LL ans = -1; {
            LL forced_skip_noTravel = sum_fsh(0, n);
            if (forced_skip_noTravel <= k) {
                LL base_tasks = sum_th(0, n);
                LL can_skip = k - forced_skip_noTravel;
                LL cnt_2 = sum_soh(0, n);
                LL best_tasks = base_tasks + min<LL>(can_skip, cnt_2);
                ans = max(ans, best_tasks);
            }
        }
        
        REPCON(L, n) {
            int minR = L + 2 * t;
            if (minR > n) break; 
            for (int R = minR; R <= n; R++) {
                LL skip_forced = 0;

                skip_forced += sum_fsh(0, L);
                skip_forced += sum_fsh(R, n);
             
                skip_forced += sum_fst(L, L + t);
                skip_forced += sum_fst(R - t, R);

                if (skip_forced > k) continue;

                LL c = k - skip_forced;
                LL base_tasks = sum_th(0, L) + sum_th(R, n);
                LL can_skip_2 = sum_soh(0, L) + sum_soh(R, n);

                LL total = base_tasks + min<LL>(c, can_skip_2);
                ans = max(ans, total);
            }
        }

        return ans;
    }
};


int main() {
    BajtazarHardWorking solver;
    cout << solver.solve() << endl;
    return 0;
}