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
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 8e3 + 5;
const int inf = 1e9 + 5;

int _3[nmax];
int _2[nmax];
int _1[nmax];

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n, k, t;
   cin >> n >> k >> t;
   
   string s;
   cin >> s;
   for(auto &x : s) if(x != '2') x ^= '1' ^ '3';
   
   s = "$" + s;
   for(int i = 1; i <= n; i++) _1[i] = _1[i - 1] + (s[i] == '1');
   for(int i = 1; i <= n; i++) _2[i] = _2[i - 1] + (s[i] == '2');
   for(int i = 1; i <= n; i++) _3[i] = _3[i - 1] + (s[i] == '3');

   auto get1 = [&](int l, int r) { return _1[r] - _1[l - 1]; };
   auto get2 = [&](int l, int r) { return _2[r] - _2[l - 1]; };
   auto get3 = [&](int l, int r) { return _3[r] - _3[l - 1]; };

   int rez = -inf;
   if(_3[n] <= k)
      rez = _1[n] + _3[n] + min(_2[n], (k - _3[n]));
   
   for(int is = 1; is <= n; is++) {
      for(int jf = is + 2 * t - 1; jf <= n; jf++) {
         int ws = is + t;
         int wf = jf - t;
         
         int miss = get2(is, ws - 1) + get2(wf + 1, jf) + get3(1, ws - 1) + get3(wf + 1, n);
         if(k < miss);
         else {
            rez = max(rez, get1(1, is - 1) + get1(jf + 1, n) + get3(1, is - 1) + get3(jf + 1, n) + min(get2(1, is - 1) + get2(jf + 1, n), k - miss));
         }
      }
   }
   cout << (rez == -inf? -1 : rez) << '\n';
}

/**
      Binecuvanteaza Doamne Ukraina.
--
*/