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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define UwU cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);

int main() {
	UwU;
    int n, k, t; cin >> n >> k >> t;
    string s; cin >> s;
	vector<ll> 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');
    }
   
	ll ans = -1;
    ll tot1 = P1[n], tot2 = P2[n], tot3 = P3[n];

	if (tot1 <= k) {
        ll r = tot3 + tot1 + min(tot2, k - tot1);
        ans = max(ans, r);
    }

    for (int i = 1; i <= n - 2 * t; i++) {
        for (int j = i + t; j <= n - t; j++) {
            int preL = 1, preR = i - 1;
            int sufL = j + t + 1, sufR = n;
			int p1 = 0, p2 = 0, p3 = 0;
			if(preR >= preL) {
				p1 =  P1[preR] - P1[preL - 1];
				p2 =  P2[preR] - P2[preL - 1];
				p3 =  P3[preR] - P3[preL - 1];
			}
			int s1 = 0, s2 = 0, s3 = 0;
            if(sufL <= sufR) {
				s1 = P1[sufR] - P1[sufL - 1];
				s2 = P2[sufR] - P2[sufL - 1];
				s3 = P3[sufR] - P3[sufL - 1];
			}
            ll cost1 = (P1[i + t - 1] - P1[i - 1]) + (P2[i + t - 1] - P2[i - 1]);
            ll cost2 = (P1[j + t] - P1[j]) + (P2[j + t] - P2[j]);
            
			int trav = cost1 + cost2;
            int mand = p1 + s1;
           
			if (trav + mand > k) continue;

            int add = min(p2 + s2, k - trav - mand);
            ll r = p3 + p1 + s3 + s1 + add;
            ans = max(ans, r);
        }
    }
    cout << ans;
    return 0;
}