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>
using namespace std;

const int MAX_N = 8005;
int prefix[MAX_N][4];
int n, k, t;
int res = -1;
string s;

int count_on_seg(int type, int l, int r) {
    return prefix[r][type] - prefix[l][type];
}

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

    cin >> n >> k >> t >> s;

    for(int i = 0; i < n; i++) {
        int type = s[i] - '0';

        for(int j = 1; j <= 3; j++) {
            prefix[i + 1][j] = prefix[i][j];
        }

        prefix[i + 1][type]++;
    }

    int ones = count_on_seg(1, 0, n);
    int twos = count_on_seg(2, 0, n);
    int threes = count_on_seg(3, 0, n);

    if(ones <= k) {
        int skip_two = min(twos, k - ones);
        int tasks = ones + threes + skip_two;
        res = max(res, tasks);
    }

    for(int start = 0; start < n - 2 * t + 1; start++) {
        for(int end = start + t; end <= n - t; end++) {

            int skipped = count_on_seg(1, start, start + t) + count_on_seg(2, start, start + t);
            skipped += count_on_seg(1, end, end + t) + count_on_seg(2, end, end + t);

            int ones_home = count_on_seg(1, 0, start) + count_on_seg(1, end + t, n);
            int twos_home = count_on_seg(2, 0, start) + count_on_seg(2, end + t, n);
            int threes_home = count_on_seg(3, 0, start) + count_on_seg(3, end + t, n);

            int left_to_skip = k - ones_home - skipped;

            if(left_to_skip < 0)
                continue;

            int tasks_home = ones_home + threes_home + min(twos_home, left_to_skip);
            res = max(res, tasks_home);
        }
    }

    cout << res << '\n';
}