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
#include <iostream>
#include <vector>
#include <array>

#define NUMBER_OF_STATUSES 3
#define MAX_N 8000
#define CACHE_SIZE MAX_N*MAX_N*NUMBER_OF_STATUSES
#define CACHE_INIT_VAL (-10000)


class PraSolver {
  int n{};
  int k{};
  int t{};
  std::string segments;
  std::array<int, MAX_N> cummulativeSumOfOfficeMeetings{};
  std::array<int, MAX_N> cummulativeSumOfRemoteMeetings{};
  std::array<int, MAX_N> cummulativeSumOfBreaks{};

public:
  PraSolver() {
    std::cin >> n >> k >> t >> segments;

    cummulativeSumOfOfficeMeetings[0] = segments[0] == '1' ? 1 : 0;
    for(int i = 1; i < segments.size(); i++) {
      cummulativeSumOfOfficeMeetings[i] = cummulativeSumOfOfficeMeetings[i-1];
      if(segments[i] == '1') {
        cummulativeSumOfOfficeMeetings[i]++;
      }
    }

    cummulativeSumOfRemoteMeetings[0] = segments[0] == '2' ? 1 : 0;
    for(int i = 1; i < segments.size(); i++) {
      cummulativeSumOfRemoteMeetings[i] = cummulativeSumOfRemoteMeetings[i-1];
      if(segments[i] == '2') {
        cummulativeSumOfRemoteMeetings[i]++;
      }
    }

    cummulativeSumOfBreaks[0] = segments[0] == '3' ? 1 : 0;
    for(int i = 1; i < segments.size(); i++) {
      cummulativeSumOfBreaks[i] = cummulativeSumOfBreaks[i-1];
      if(segments[i] == '3') {
        cummulativeSumOfBreaks[i]++;
      }
    }
  }

  int solve() const {
    return std::max(solveFullyRemote(), solveWithOfficeTravel());
  }

private:
  int solveFullyRemote() const {
    int remoteSegments = n;
    int remoteMeetings = getRange(0, n, cummulativeSumOfRemoteMeetings);
    int unavoidableSkippedOfficeMeetings = getRange(0, n, cummulativeSumOfOfficeMeetings);
    int kLeft = k - unavoidableSkippedOfficeMeetings;
    if (kLeft < 0) {
      return -1;
    }
    int meetingFromHomeCount = kLeft >= remoteMeetings ? 0 : remoteMeetings - kLeft;
    return remoteSegments - meetingFromHomeCount;
  }

  int solveWithOfficeTravel() const {
    int best = -1;
    for(int i = 0; i < n - t - t; i++) {
      for(int j = i + t; j < n - t + 1; j++) {
        best = std::max(best, solveWithSpecificOfficeTravel(i, j));
      }
    }
    return best;
  }

  int solveWithSpecificOfficeTravel(int startTravelSegment, int startReturnSegment) const {
    // first home range = 0 --- startTravelSegment
    // second home range = (startReturnSegment + t) --- n
    int remoteSegments = n - t - startReturnSegment + startTravelSegment;
    int remoteMeetings = getRange(0, startTravelSegment, cummulativeSumOfRemoteMeetings) + getRange(startReturnSegment + t, n, cummulativeSumOfRemoteMeetings);
    int unavoidableSkippedOfficeMeetings = getRange(0, startTravelSegment + t, cummulativeSumOfOfficeMeetings) + getRange(startReturnSegment, n, cummulativeSumOfOfficeMeetings);
    int unavoidableSkippedRemoteMeetings = getRange(startTravelSegment, startTravelSegment + t, cummulativeSumOfRemoteMeetings) + getRange(startReturnSegment, startReturnSegment + t, cummulativeSumOfRemoteMeetings);
    int kLeft = k - unavoidableSkippedRemoteMeetings - unavoidableSkippedOfficeMeetings;
    if (kLeft < 0) {
      return -1;
    }
    int meetingFromHomeCount = kLeft >= remoteMeetings ? 0 : remoteMeetings - kLeft;
    return remoteSegments - meetingFromHomeCount;
  }

  int getRange(int startSegment, int exclusiveEnd, const std::array<int, MAX_N>& cummulativeSum) const {
    if(exclusiveEnd <= startSegment) return 0;
    int lowerValue = startSegment == 0 ? 0 : cummulativeSum[startSegment - 1];
    int higherValue = exclusiveEnd - 1  >= n ? cummulativeSum[n - 1] : cummulativeSum[exclusiveEnd - 1];
    return higherValue - lowerValue;
  }
};

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

  PraSolver solver;
  int result = solver.solve();
  std::cout << result;
  return 0;
}