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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll stayingHome(ll totOff, ll totOnl, ll totFree, ll k){
    ll tasks = -1;
    if(totOff <= k){
        ll optional = k - totOff;
        ll solvedFromOnl = min(totOnl, optional);
        tasks = totFree + totOff + solvedFromOnl;
    }
    return tasks;
}

ll goingOffice(ll n, ll k, ll t, vector<ll>& prefOff, vector<ll>& prefOnl, vector<ll>& prefFree){
    ll best = -1;
    for(int L = 1; L <= n - 2*t + 1; L++){
        for(int R = L + t; R <= n - t + 1; R++){
            ll road1_off = prefOff[L + t - 1] - prefOff[L - 1];
            ll road1_onl = prefOnl[L + t - 1] - prefOnl[L - 1];
            ll road1_cost = road1_off + road1_onl;
            ll road2_off = prefOff[R + t - 1] - prefOff[R - 1];
            ll road2_onl = prefOnl[R + t - 1] - prefOnl[R - 1];
            ll road2_cost = road2_off + road2_onl;
            ll roadCost = road1_cost + road2_cost;
            ll home1_off, home1_onl, home1_free;
            if(L - 1 >= 1){
                home1_off = prefOff[L - 1];
                home1_onl = prefOnl[L - 1];
                home1_free = prefFree[L - 1];
            } else{
                home1_off = 0;
                home1_onl = 0;
                home1_free = 0;
            }
            ll home2_off = 0, home2_onl = 0, home2_free = 0;
            if(R + t <= n) {
                home2_off = prefOff[n] - prefOff[R + t - 1];
                home2_onl = prefOnl[n] - prefOnl[R + t - 1];
                home2_free = prefFree[n] - prefFree[R + t - 1];
            }
            ll home_off = home1_off + home2_off;
            ll home_onl = home1_onl + home2_onl;
            ll home_free = home1_free + home2_free;
            ll forcedCost = roadCost + home_off;
            if (forcedCost > k){
                continue;
            }
            ll availableOptional = k - forcedCost;
            ll addFromOnl = min(home_onl, availableOptional);
            ll tasks = home_free + home_off + addFromOnl;
            best = max(best, tasks);
        }
    }
    return best;
}

int main(){
    ll n, k, t;
    cin >> n >> k >> t;
    string s;
    cin >> s;
    vector<ll> off(n + 1, 0), onl(n + 1, 0), free_t(n + 1, 0);
    
    for(int i = 0; i < n; i++){
        char ch = s[i];
        if(ch == '1'){
            off[i + 1] = 1;
        }else if(ch == '2'){
            onl[i + 1] = 1;
        }else{
            free_t[i + 1] = 1;
        }
    }
    vector<ll> prefOff(n + 1, 0), prefOnl(n + 1, 0), prefFree(n + 1, 0);
    for(int i = 1; i <= n; i++){
        prefOff[i] = prefOff[i - 1] + off[i];
        prefOnl[i] = prefOnl[i - 1] + onl[i];
        prefFree[i] = prefFree[i - 1] + free_t[i];
    }
    ll totOff = prefOff[n];
    ll totOnl = prefOnl[n];
    ll totFree = prefFree[n];
    ll best = -1;
    best = max(best, stayingHome(totOff, totOnl, totFree, k));
    best = max(best, goingOffice(n, k, t, prefOff, prefOnl, prefFree));
    cout << best;
}