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

int main() {
    int32_t n, k, t;
    std::cin >> n >> k >> t;

    std::string w;
    std::cin >> w;

    int32_t no1 = 0, no2 = 0;
    std::vector<int32_t> pref2(n + 1);
    for (int32_t i = 0; i < n; ++i) {
        pref2[i] = no2;
        if (w[i] == '1') {
            no1 += 1;
        } else if (w[i] == '2') {
            no2 += 1;
        }
    }
    pref2[n] = no2;

    int32_t target = no1 + no2 - k;
    if (target <= 0) {
        std::cout << n << "\n";
        return 0;
    }

    int32_t need1 = target - no2;
    if (need1 <= 0) {
        std::cout << n - target << "\n";
        return 0;
    }

    int32_t best_wait = n + 1;
    for (int32_t i = 0; i + t <= n && best_wait > 0; ++i) {
        int32_t start_miss2 = pref2[i + t] - pref2[i];
        int32_t curr_wait = 0;
        int32_t get1 = 0;
        int32_t pos = i + t;
        for (;;) {
            if (w[pos] == '3') {
                curr_wait += 1;
                if (curr_wait >= best_wait) {
                    break;
                }
            } else if (w[pos] == '1') {
                get1 += 1;
            }

            pos += 1;
            if (pos + t > n) {
                break;
            }
            if (start_miss2 + pref2[pos + t] - pref2[pos] + need1 <= get1) {
                best_wait = curr_wait;
                break;
            }
        }
    }

    if (best_wait > n) {
        std::cout << "-1\n";
    } else {
        std::cout << n - target - 2 * t - best_wait << "\n";
    }
}