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
70
71
72
73
74
75
76
#include <bits/stdc++.h>

using namespace std;


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

    int n, k, t;
    cin >> n >> k >> t;
    string schedule;
    cin >> schedule;
    
    vector<int> pref_free(n), pref_remote(n), pref_stationary(n);
    vector<int> suff_free(n), suff_remote(n), suff_stationary(n);

    pref_free[0] = (schedule[0] == '3'), pref_remote[0] = (schedule[0] == '2'), pref_stationary[0] = (schedule[0] == '1');
    for (int i = 1; i < n; i++) {
        pref_free[i] = pref_free[i - 1] + (schedule[i] == '3');
        pref_remote[i] = pref_remote[i - 1] + (schedule[i] == '2');
        pref_stationary[i] = pref_stationary[i - 1] + (schedule[i] == '1');
    }

    suff_free[n - 1] = (schedule[n - 1] == '3'), suff_remote[n - 1] = (schedule[n - 1] == '2'), suff_stationary[n - 1] = (schedule[n - 1] == '1');
    for (int i = n - 2; i >= 0; i--) {
        suff_free[i] = suff_free[i + 1] + (schedule[i] == '3');
        suff_remote[i] = suff_remote[i + 1] + (schedule[i] == '2');
        suff_stationary[i] = suff_stationary[i + 1] + (schedule[i] == '1');
    }

    if (suff_stationary[0] <= k) {
        int ans = suff_free[0];
        int temp = suff_remote[0] + suff_stationary[0];
        cout << ans + min(temp, k) << endl;
        return 0;
    }

    int ans = -1, curr, missed;
    for (int i = 2 * t + 1; i <= n; i++) {
        for (int j = 0; j + i - 1 < n; j++) {
            curr = missed = 0;
            if (j != 0) {
                curr += pref_free[j - 1] + pref_stationary[j - 1];
                missed += pref_stationary[j - 1];
            }
            
            if (j + i - 1 != n - 1) {
                curr += suff_free[j + i] + suff_stationary[j + i];
                missed += suff_stationary[j + i];
            }
            

            missed += pref_remote[j + t - 1] + pref_stationary[j + t - 1];
            missed += suff_remote[j + i - t] + suff_stationary[j + i - t];
            
            if (j != 0)
                missed -= pref_remote[j - 1] + pref_stationary[j - 1];
            if (j + i - 1 != n - 1) 
                missed -= suff_remote[j + i] + suff_stationary[j + i];
            
            if (missed <= k) {
                int add = 0;
                if (j != 0)
                    add += pref_remote[j - 1];
                if (j + i - 1 != n - 1)
                    add += suff_remote[j + i];
                add = min(add, k - missed);
                ans = max(ans, curr + add);
            }
        }
    }

    cout << ans << "\n";
}