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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <vector>

constexpr int N = 8000;

enum meeting {
  onsite,
  remote,
  none,
};

struct state {
  int score;
  int home_meetings;
  int office_meetings;
};

void add_meeting(state &out, meeting meeting, bool in_office) {
  switch (meeting) {
  case onsite:
    out.office_meetings += in_office;
    out.score += !in_office;
    break;
  case remote:
    out.office_meetings += in_office;
    out.home_meetings += !in_office;
    break;
  case none:
    out.score += !in_office;
    break;
  }
}

void sub_meeting(state &out, meeting meeting, bool in_office) {
  switch (meeting) {
  case onsite:
    out.office_meetings -= in_office;
    out.score -= !in_office;
    break;
  case remote:
    out.office_meetings -= in_office;
    out.home_meetings -= !in_office;
    break;
  case none:
    out.score -= !in_office;
    break;
  }
}

std::ostream &operator<<(std::ostream &os, state const &s) {
  return os << s.score << '@' << s.home_meetings << '/' << s.office_meetings;
}

meeting tasks[N];
int n, k, t;
int total_meetings;

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  std::cin >> n >> k >> t;

  for (int i = 0; i < n; ++i) {
    char c;
    std::cin >> c;

    if (c == '3')
      tasks[i] = meeting::none;
    else if (c == '2')
      tasks[i] = meeting::remote;
    else if (c == '1')
      tasks[i] = meeting::onsite;

    if (tasks[i] != meeting::none)
      ++total_meetings;
  }

#ifdef DEBUG
#define DEBUGN 100
#define SIMPLE_STRINGIFY(x) #x
  if (n > DEBUGN) {
    // clang-format off
    std::cerr << "the debug build cannot handle n > " SIMPLE_STRINGIFY(DEBUGN) "\n";
    // clang-format on
    return 1;
  }
  std::vector<state> states((DEBUGN + 1) * (DEBUGN + 1));
  auto at = [&](int a, int b) mutable -> state & {
    return states[a + b * DEBUGN];
  };
#endif

  int min_meetings = total_meetings - k;
  int max_score = -1;

  auto register_attempt = [&max_score, min_meetings](state const &st) {
    int state_meetings = st.home_meetings + st.office_meetings;
    if (state_meetings >= min_meetings && st.score > max_score) {
      int extra_score =
          std::min(st.home_meetings, state_meetings - min_meetings);
      max_score = st.score + extra_score;
    }
  };

  state no_office{};
  for (int i = 0; i < n; ++i)
    add_meeting(no_office, tasks[i], false);

#ifdef DEBUG
  std::cerr << "no_office: " << no_office << '\n';
#endif

  register_attempt(no_office);

  state current_empty_state;
  {
    state empty_office = no_office;

    for (int i = n - 1; i >= n - t - t; --i)
      sub_meeting(empty_office, tasks[i], false);

#ifdef DEBUG
    std::cerr << "empty_office(" << n - t << "): " << empty_office << '\n';
    at(n - t - t, n) = empty_office;
#endif

    register_attempt(empty_office);
    current_empty_state = empty_office;
  }

  for (int i = n; i >= 0; --i) {
    state current = current_empty_state;
    for (int j = i - t - t - 1; j >= 0; --j) {
      sub_meeting(current, tasks[j], false);
      add_meeting(current, tasks[j + t], true);
      register_attempt(current);

#ifdef DEBUG
      at(j, i) = current;
#endif
    }

    if (i > t) {
      state next_empty_state = current_empty_state;
      sub_meeting(next_empty_state, tasks[i - t - t - 1], false);
      add_meeting(next_empty_state, tasks[i - 1], false);

#ifdef DEBUG
      std::cerr << "empty_office(" << i - t - 1 << "): " << next_empty_state
                << '\n';
      at(i - t - t - 1, i - 1) = next_empty_state;
#endif

      register_attempt(next_empty_state);
      current_empty_state = next_empty_state;
    }
  }

#ifdef DEBUG
  std::cerr << "   ";
  for (int j = 0; j <= n; ++j) {
    std::cerr << std::setw(7) << j << ' ';
  }
  std::cerr << '\n';
  for (int i = 0; i <= n; ++i) {
    std::cerr << std::setw(2) << i << ' ';
    for (int j = 0; j <= n; ++j) {
      std::ostringstream xd;
      xd << at(i, j);
      std::cerr << std::setw(7) << xd.str() << ' ';
    }
    std::cerr << '\n';
  }
#endif

  std::cout << max_score << '\n';

  return 0;
}