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

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

#define OFFICE 0
#define REMOTE 1
#define FREE 2

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, k, t;
    cin >> n >> k >> t;
    vector<int> type(n);
    vector<array<int, 3>> prefSum(n, {0, 0, 0});
    char c;
    rep(i, 0, n) {
        cin >> c, type[i] = c - '1';
        if(i != 0) rep(j, 0, 3) prefSum[i][j] = prefSum[i - 1][j];
        prefSum[i][type[i]]++;
    }
    int ans = -1;
    rep(i, t, n) rep(j, i, max(i, n - t)) {
        int skippedOffice = (i == 0 ? 0 : prefSum[i - 1][OFFICE]) + prefSum[n - 1][OFFICE] - prefSum[j][OFFICE];
        int skippedRemote = (i == 0 ? 0 : prefSum[i - 1][REMOTE]) - (i == t ? 0 : prefSum[i - t - 1][REMOTE]) + prefSum[j + t][REMOTE] - prefSum[j][REMOTE];
        DC << "Going to work from " << i << " to " << j;
        if(skippedOffice + skippedRemote > k) DC << " skips too much" << eol;
        if(skippedOffice + skippedRemote > k) continue;
        int skipableRemote = (i == t ? 0 : prefSum[i - t - 1][REMOTE]) + prefSum[n - 1][REMOTE] - prefSum[j + t][REMOTE];
        int skippedRemote2 = min(skipableRemote, k - skippedRemote - skippedOffice);
        int myAns = n - (j - i + 1 + 2 * t) - skipableRemote + skippedRemote2;
        DC << " gives us " << myAns << eol;
        DC << " ( skipped office " << skippedOffice << "; skipped remote " << skippedRemote << " + " << skippedRemote2 << "; remote at home " << skipableRemote << " - " << skippedRemote2 << " )" << eol;
        ans = max(ans, myAns);
    }
    int skippedOffice = prefSum[n - 1][OFFICE];
    int skippedRemote = 0;
    DC << "Not going to work";
    if(skippedOffice + skippedRemote > k) DC << " skips too much" << eol;
    if(skippedOffice + skippedRemote <= k) {
        int skipableRemote = prefSum[n - 1][REMOTE];
        int skippedRemote2 = min(skipableRemote, k - skippedRemote - skippedOffice);
        int myAns = n - skipableRemote + skippedRemote2;
        DC << " gives us " << myAns << eol;
        DC << " ( skipped office " << skippedOffice << "; skipped remote " << skippedRemote << " + " << skippedRemote2 << "; remote at home " << skipableRemote << " - " << skippedRemote2 << " )" << eol;
        ans = max(ans, myAns);
    }
    cout << ans << '\n';
}