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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <cstdio>
#include <tuple>
#include <vector>

using namespace std;
using range = pair<int, int>;

int get_count(int start, int end, vector<int> &v) {
  // <start, end>
  return v[end] - v[start];
}

int main() {
  int n, k, t;

  scanf("%d %d %d", &n, &k, &t);

  char *segments = new char[n + 2];
  vector<int> opc(n + 1);
  vector<int> rpc(n + 1);
  vector<int> fpc(n + 1);

  scanf("%s", segments);

  opc[0] = 0;
  rpc[0] = 0;

  for (int i = 1; i < n + 1; i++) {
    opc[i] = opc[i - 1] + (segments[i - 1] == '1' ? 1 : 0);
    rpc[i] = rpc[i - 1] + (segments[i - 1] == '2' ? 1 : 0);
    fpc[i] = fpc[i - 1] + (segments[i - 1] == '3' ? 1 : 0);
  }

  if (get_count(0, n, opc) <= k) {
    int skipped_meetings = get_count(0, n, opc);
    int skippable_remote_meetings = k - get_count(0, n, opc);

    skipped_meetings += min(skippable_remote_meetings, get_count(0, n, rpc));

    printf("%d", get_count(0, n, fpc) + skipped_meetings);

    return 0;
  }

  int result = -1;

  for (int office_start = t; office_start <= n - t; office_start++) {
    for (int office_end = office_start; office_end <= n - t; office_end++) {
      range pre_office({0, office_start - t});
      range pre_office_travel({office_start - t, office_start});
      range office_hours({office_start, office_end});
      range post_office_travel({office_end, office_end + t});
      range post_office({office_end + t, n});

      int travel_skipped_meetings =
          get_count(pre_office_travel.first, pre_office_travel.second, opc) +
          get_count(pre_office_travel.first, pre_office_travel.second, rpc) +
          get_count(post_office_travel.first, post_office_travel.second, opc) +
          get_count(post_office_travel.first, post_office_travel.second, rpc);

      int skipped_office_meetings =
          get_count(post_office.first, post_office.second, opc) +
          get_count(pre_office.first, pre_office.second, opc);

      int skipped_meetings = travel_skipped_meetings + skipped_office_meetings;

      if (skipped_meetings > k) {
        continue;
      }

      int doing_potyczki =
          skipped_office_meetings +
          (get_count(post_office.first, post_office.second, fpc) +
           get_count(pre_office.first, pre_office.second, fpc));
      int skippable_remote_meetings = k - skipped_meetings;

      doing_potyczki +=
          min(skippable_remote_meetings,
              (get_count(post_office.first, post_office.second, rpc) +
               get_count(pre_office.first, pre_office.second, rpc)));

      // printf("pre_office: %d %d\n", pre_office.first, pre_office.second);
      // printf("pre_office_travel: %d %d\n", pre_office_travel.first,
      //        pre_office_travel.second);
      // printf("office_hours: %d %d\n", office_hours.first, office_hours.second);
      // printf("post_office_travel: %d %d\n", post_office_travel.first,
      //        post_office_travel.second);
      // printf("post_office: %d %d\n", post_office.first, post_office.second);
      // printf("travel_skipped_meetings: %d\n", travel_skipped_meetings);
      // printf("skipped_meetings: %d\n", skipped_meetings);
      // printf("doing_potyczki: %d\n", doing_potyczki);

      result = max(result, doing_potyczki);
    }
  }

  printf("%d", result);

  return 0;
}