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

int main() {
    int n, k, t;
    cin >> n >> k >> t;
    string s;
    cin >> s;

    vector<int> p1(n + 1, 0), p2(n + 1, 0), p3(n + 1, 0);
    for(int i = 0; i < n; i++) {
        p1[i + 1] = p1[i] + (s[i] == '1');
        p2[i + 1] = p2[i] + (s[i] == '2');
        p3[i + 1] = p3[i] + (s[i] == '3');
    }

    int res = -1;
    if(k >= p1[n]) {
        res = p3[n] + p1[n] + min(k - p1[n], p2[n]);
    }

    for(int i = 0; i <= n - 2 * t; i++) {
        int a1 = p1[i];
        int a2 = p2[i];
        int a3 = p3[i];

        int t1_cost = p1[t + i] - p1[i] + p2[t + i] - p2[i];
        
        for(int j = i + t; j <= n - t; j++) {
            int b1 = p1[n] - p1[j + t];
            int b2 = p2[n] - p2[j + t];
            int b3 = p3[n] - p3[j + t];

            int t2_cost = p1[j + t] - p1[j] + p2[j + t] - p2[j];

            int cost = t1_cost + t2_cost + a1 + b1;
            if(cost > k) continue;
            
            int total = a3 + b3 + a1 + b1 + min(k - cost, a2 + b2);
            
            res = max(res, total);
        }
    }

    cout << res;
}