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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k, t;
    cin >> n >> k >> t;
    vector<int> duties(n + 1);
    vector<int> pref1(n + 1);
    vector<int> pref2(n + 1);
    vector<int> pref3(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        char c;
        cin >> c;
        duties[i] = c - '0';
    }

    int best = -1;

    for (int i = 1; i <= n; ++i)
    {
        pref1[i] = pref1[i - 1];
        pref2[i] = pref2[i - 1];
        pref3[i] = pref3[i - 1];

        if (duties[i] == 1) ++pref1[i];
        else if (duties[i] == 2) ++pref2[i];
        else ++pref3[i];
    }

    if (pref1[n] <= k)
    {
        best = pref3[n] + pref1[n] + min(pref2[n], k - pref1[n]);
    }

    for (int l = t + 1; l <= n; ++l)
    {
        for (int r = l; r + t <= n; ++r)
        {
            int skipped = pref1[l - 1] + pref2[l - 1] - pref2[l - t - 1] + pref1[n] - pref1[r] + pref2[r + t] - pref2[r];
            if (skipped > k) continue;

            int left = pref2[l - t - 1] + pref2[n] - pref2[r + t];
            int free = pref3[l - t - 1] + pref3[n] - pref3[r + t] + pref1[l - t - 1] + pref1[n] - pref1[r + t];
            best = max(best, free + min(left, k - skipped));
        }
    }

    cout << best << '\n';
}