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
#include <iostream>
#include <algorithm>
using namespace std;

char c;

const int STACJONARNE = 1;
const int ZDALNE = 2;
const int WOLNE = 3;

int main() {
  int n, k, t;
  int best = -1;
  cin >> n >> k >> t;
  
  int seg[n];
  for(int i = 0; i < n; i++) {
        cin >> c;
        seg[i] = c-'0';
  }


  // najpierw przegladamy przypadek calego dnia w domu  
  int cnt[4] = {0, 0, 0, 0};
  for(int i = 0; i < n; i++)
    cnt[seg[i]]++;
  
  if(cnt[STACJONARNE] <= k) {
    best = cnt[WOLNE] + min(k, cnt[STACJONARNE]+cnt[ZDALNE]);
  }
  
  
  // a teraz przejrzymy brutalnie wszystkie przejazdy
  int cnt_jazda1[4] = {0, 0, 0, 0};
  int cnt_jazda2[4] = {0, 0, 0, 0};
  int cnt_dom[4] = {0, 0, 0, 0};
  
  for(int i = 0; i < t; i++)
    cnt_jazda1[seg[i]]++;
  for(int i = 0; i< t; i++)
    cnt_jazda2[seg[n-i-1]]++;
  
  for(int wyjazd = 0; wyjazd +2*t < n; wyjazd++) {
    int cnt_powr[4];
    for(int i = 0; i < 4; i++)
        cnt_powr[i] = cnt_jazda2[i];
    
    int cnt_dom2[] = {0, 0, 0, 0};
    for(int powrot = n-t; wyjazd+t < powrot; powrot--) {
        // ----------
        int ominiete = cnt_jazda1[STACJONARNE] + cnt_jazda1[ZDALNE] + cnt_powr[STACJONARNE] + cnt_powr[ZDALNE] + cnt_dom[STACJONARNE] + cnt_dom2[STACJONARNE];
        if(ominiete <= k) {
          int uczeszcza = cnt_dom[ZDALNE] + cnt_dom2[ZDALNE];
          int aktualne = cnt_dom[WOLNE] + cnt_dom2[WOLNE]
                         + min(k-ominiete, uczeszcza);
          if(aktualne > best)
            best = aktualne;
        }
        // ----------
        cnt_dom2[ seg[powrot+t-1] ] ++;
        cnt_powr[ seg[powrot+t-1] ] --;
        cnt_powr[ seg[powrot-1] ] ++;
    }
  
    cnt_jazda1[seg[wyjazd+t]]++;
    cnt_jazda1[seg[wyjazd]]--;
    cnt_dom[seg[wyjazd]]++;
  }
  
  
  
  cout << best << endl;
  return 0;
}