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

constexpr char OFFICE = '1';
constexpr char REMOTE = '2';
constexpr char NONE = '3';

int main() {
    int n;
    int k;
    int t;
    std::string in;

    std::cin >> n >> k >> t >> in;

    int missedSoFarL = 0;
    int missedSoFarR = 0;
    for (int i = 0; i < t; ++i) {
        if (in[i] != NONE) {
            ++missedSoFarL;
        }
        if (in[n - 1 - i] != NONE) {
            ++missedSoFarR;
        }
    }

    std::vector<int> remoteL(n/* - 2*t*/ + 1, 0);
    std::vector<int> remoteR(n/* - 2*t*/ + 1, 0);
    std::vector<int> missedL(n/* - 2*t*/, 0);
    std::vector<int> missedR(n/* - 2*t*/, 0);
    for (int i = 0; i < n - 2*t; ++i) {
        missedL[i] = missedSoFarL;
        remoteL[i + 1] = remoteL[i];
        if (in[i + t] != NONE) {
            ++missedSoFarL;
        }
        if (in[i] == REMOTE) {
            --missedSoFarL;
            ++remoteL[i + 1];
        }

        missedR[i] = missedSoFarR;
        remoteR[i + 1] = remoteR[i];
        if (in[n - 1 - (i + t)] != NONE) {
            ++missedSoFarR;
        }
        if (in[n - 1 - i] == REMOTE) {
            --missedSoFarR;
            ++remoteR[i + 1];
        }
    }

    int totalOffice = 0;
    for (int i = 0; i < n; ++i) {
        if (in[i] == OFFICE) {
            ++totalOffice;
        }
    }

    int mostProductive = -1;
    if (totalOffice <= k) {
        int remotes = 2*t <= n? remoteL[n - 2*t] : 0;
        for (int i = std::max(0, n - 2*t); i < n; ++i) {
            if (in[i] == REMOTE) {
                ++remotes;
            }
        }
        mostProductive = n - std::max(0, remotes - (k - totalOffice));
    } else {
        for (int i = 0; i < n - 2*t; ++i) {
            for (int j = 0; j < n - 2*t - i; ++j) {
                int productive = i + j - remoteL[i] - remoteR[j];
                int missed = missedL[i] + missedR[j];
                if (missed <= k && productive > mostProductive) {
                    mostProductive = productive;
                }
            }
        }
    }

    std::cout << mostProductive << std::endl;

    return 0;
}