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

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

  int n, k, t;
  cin >> n >> k >> t;
  string s;
  cin >> s;

  vector<int> pref1(n + 1, 0), pref2(n + 1, 0), pref3(n + 1, 0),
      prefM(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    char znak = s[i - 1];
    pref1[i] = pref1[i - 1] + (znak == '1');
    pref2[i] = pref2[i - 1] + (znak == '2');
    pref3[i] = pref3[i - 1] + (znak == '3');
    prefM[i] = prefM[i - 1] + ((znak == '1' || znak == '2') ? 1 : 0);
  }

  int wynik = -1;

  if (pref1[n] <= k) {
    int add = k - pref1[n];
    int zad = pref1[n] + pref3[n] + min(pref2[n], add);
    wynik = max(wynik, zad);
  }

  for (int i = 1; i <= n - 2 * t + 1; i++) {
    int przed1 = (i - 1 >= 1 ? pref1[i - 1] : 0);
    int przed2 = (i - 1 >= 1 ? pref2[i - 1] : 0);
    int przed3 = (i - 1 >= 1 ? pref3[i - 1] : 0);
    int tran1 = prefM[i + t - 1] - prefM[i - 1];

    for (int j = i + t; j <= n - t + 1; j++) {
      int po1 = (j + t <= n ? pref1[n] - pref1[j + t - 1] : 0);
      int po2 = (j + t <= n ? pref2[n] - pref2[j + t - 1] : 0);
      int po3 = (j + t <= n ? pref3[n] - pref3[j + t - 1] : 0);

      int d1 = przed1 + po1;
      int d2 = przed2 + po2;
      int d3 = przed3 + po3;

      int tran2 = prefM[j + t - 1] - prefM[j - 1];
      int koszt = d1 + tran1 + tran2;

      if (koszt > k)
        continue;
      int add = k - koszt;
      int zad = d1 + d3 + min(d2, add);
      wynik = max(wynik, zad);
    }
  }

  cout << wynik << '\n';
  return 0;
}