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

constexpr int MAX_N = 8e3;

int n, k, t;
string s;

int pref[MAX_N + 1][3], ans = -1;

int sum(int l, int r, char c) {
    return pref[r][c - '1'] - pref[l - 1][c - '1'];
}

int sum(int l, int r, vector<char> vec) {
    int res = 0;

    for(char c : vec) {
        res += pref[r][c - '1'] - pref[l - 1][c - '1'];
    }

    return res;
}

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

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

    for(int i = 1; i <= n; i++) {
        for(char c : {'1', '2', '3'}) {
            pref[i][c - '1'] = pref[i - 1][c - '1'] + (int)(s[i - 1] == c);
        }
    }

    if(sum(1, n, '1') <= k) {
        int can_miss = k - sum(1, n, '1');
        ans = max(ans, sum(1, n, {'1', '3'}) + min(can_miss, sum(1, n, '2')));
    }

    for(int l = t + 1; l <= n - t; l++) {
        for(int r = l; r <= n - t; r++) {
            int missed = sum(1, l - 1, '1') + sum(r + 1, n, '1') + sum(l - t, l - 1, '2') + sum(r + 1, r + t, '2');

            if(missed <= k) {
                int jeden_skibidi = 
                    sum(1, l - t - 1, {'1', '3'}) + 
                    sum(r + t + 1, n, {'1', '3'});

                int drugi_skibidi = 
                    sum(1, l - t - 1, '2') + 
                    sum(l, r, {'1', '2'}) + 
                    sum(r + t + 1, n, '2');

                ans = max(ans, jeden_skibidi + min(k - missed, drugi_skibidi));
            }
        }
    }

    cout << ans;
}