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
#include <iostream>
  #include <stdio.h>
  #include <cstdio>
  using namespace std;


  int OFFICE = 0, REMOTE = 1, FREE = 2;

  int n, k, t;
  int timeline[8000];
  int meetings[3][8001];

  int events(int type, int timeStart, int timeStop) {
    return meetings[type][timeStop] - meetings[type][timeStart];
  }


  int calculateScoreNoDriving() {
    int missedOffice = events(OFFICE, 0, n);
    int remoteAtHome = events(REMOTE, 0, n);
    int freeAtHome = events(FREE, 0, n);

    int margin = k - missedOffice;
    if (margin < 0) {
      return -1;
    }

    return freeAtHome + missedOffice + min(remoteAtHome, margin);
  }

  int calculateScore(int timeLeave, int timeBack) {
    int missedWhileDriving = 0;
    missedWhileDriving += events(OFFICE, timeLeave, timeLeave + t);
    missedWhileDriving += events(REMOTE, timeLeave, timeLeave + t);
    missedWhileDriving += events(OFFICE, timeBack, timeBack + t);
    missedWhileDriving += events(REMOTE, timeBack, timeBack + t);

    int missedWhileHome = 0;
    missedWhileHome += events(OFFICE, 0, timeLeave);
    missedWhileHome += events(OFFICE, timeBack + t, n);

    int margin = k - (missedWhileDriving + missedWhileHome);
    if (margin < 0) {
      return -1;
    }

    int remoteAtHome = 0;
    remoteAtHome += events(REMOTE, 0, timeLeave);
    remoteAtHome += events(REMOTE, timeBack + t, n);

    int freeAtHome = 0;
    freeAtHome += events(FREE, 0, timeLeave);
    freeAtHome += events(FREE, timeBack + t, n);

    int score = freeAtHome + missedWhileHome + min(remoteAtHome, margin);
    return score;
  }

  int main() {
    cin >> n;
    cin >> k;
    cin >> t;
    getchar();
    for (int i = 0; i < n; i++) {
      timeline[i] = getchar() - '1';
    }
    for (int type = 0; type < 3; type++) {
      meetings[type][0] = 0;
      for (int i = 1; i <= n; i++) {
        meetings[type][i] = meetings[type][i - 1];
        if (timeline[i - 1] == type) {
          meetings[type][i]++;
        }
      }
    }

    int bestScore = calculateScoreNoDriving();

    for (int timeLeave = 0; timeLeave <= n - 2 * t; timeLeave++) {
      for (int timeBack = timeLeave + t; timeBack <= n - t; timeBack++) {
        int score = calculateScore(timeLeave, timeBack);
        bestScore = max(score, bestScore);
      }
    }

    cout << bestScore;
    return 0;
  }