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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k, t;
    string s;
    cin >> n >> k >> t;
    cin >> s;
    vector<int> prefiks1(n+1, 0), prefiks2(n+1, 0), prefiks3(n+1, 0);
    for (int i = 1; i <= n; ++i) {
        prefiks1[i] = prefiks1[i-1] + (s[i-1] == '1');
        prefiks2[i] = prefiks2[i-1] + (s[i-1] == '2');
        prefiks3[i] = prefiks3[i-1] + (s[i-1] == '3');
    }
    
    int dom_res = -1;
    int l1_dom = prefiks1[n];
    if (l1_dom <= k) {
        int poz_k = k - l1_dom;
        int l2_dom = prefiks2[n];
        int l3_dom = prefiks3[n];
        dom_res = l3_dom + min(poz_k, l2_dom);
    }
    
    int max_biuro = -1;
    int max_s = n - 2 * t;
    for (int start = 1; start <= max_s; ++start) {
        int min_kon = start + t;
        int max_kon = n - t;
        if (min_kon > max_kon) continue;
        for (int kon = min_kon; kon <= max_kon; ++kon) {
            int start_pod1 = start, end_pod1 = start + t - 1;
            int opusz_pod1 = (prefiks1[end_pod1] - prefiks1[start_pod1-1]) 
                            + (prefiks2[end_pod1] - prefiks2[start_pod1-1]);
            int start_pod2 = kon, end_pod2 = kon + t - 1;
            int opusz_pod2 = (prefiks1[end_pod2] - prefiks1[start_pod2-1]) 
                            + (prefiks2[end_pod2] - prefiks2[start_pod2-1]);
            int opuszczone_pod = opusz_pod1 + opusz_pod2;
            int przed_start = 1, przed_kon = start - 1;
            int l1_przed = 0, l2_przed = 0, l3_przed = 0;
            if (przed_kon >= przed_start) {
                l1_przed = prefiks1[przed_kon] - prefiks1[przed_start-1];
                l2_przed = prefiks2[przed_kon] - prefiks2[przed_start-1];
                l3_przed = prefiks3[przed_kon] - prefiks3[przed_start-1];
            }
            int po_start = kon + t, po_kon = n;
            int l1_po = 0, l2_po = 0, l3_po = 0;
            if (po_start <= po_kon) {
                l1_po = prefiks1[po_kon] - prefiks1[po_start-1];
                l2_po = prefiks2[po_kon] - prefiks2[po_start-1];
                l3_po = prefiks3[po_kon] - prefiks3[po_start-1];
            }
            int opuszczone_dom1 = l1_przed + l1_po;
            int opuszczone = opuszczone_pod + opuszczone_dom1; 
            if (opuszczone > k) continue;
            int poz_k = k - opuszczone;
            if (poz_k < 0) continue;
            int l2_dom = l2_przed + l2_po;
            int pom2 = min(poz_k, l2_dom);
            int time = l3_przed + l3_po + pom2;
            if (time > max_biuro) max_biuro = time;
        }
    }
    
    int res = max(dom_res, max_biuro);
    cout << (res == -1 ? -1 : res) << "\n";
}