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

//#define DEBUG
#define PRINT_SOLUTIONS
#define PRINT_NOSOLUTIONS

#ifdef DEBUG
    #undef DEBUG
    #define DEBUG(x) x
#else
    #define DEBUG(x)
#endif


#define WORK_MEETING '1'
#define REMOTE_MEETING '2'
#define NO_DUTY '3'

#define REP(x,n) for(int x=0;x<(n);++x)
#define VAR(x,n) __typeof(n) x = (n)
#define FOREACH(x,c) for(VAR(x, (c).begin()); x != (c).end(); ++x)
#define CONTAINS(x,elem) ((x).find(elem) != (x).end())
#define MAX_N 8002

int workMeetingsSum[MAX_N];
int remoteMeetingsSum[MAX_N];
int noDutySum[MAX_N];


template<typename _T> void printArray(ostream& os, const _T* array, const int length) {
    os << "{ ";
    REP(x,length)
        os << array[x] << " ";
    os << "}" << endl;
}


int inline countMinMissedMeetings(const int n, const string& calendar, const int travelTime) {
    int missed = 0;
    int lastIndex = n-1;
    REP(x,travelTime) {
        if (calendar[x] == WORK_MEETING)
            ++missed;
        if (calendar[lastIndex-x] == WORK_MEETING)
            ++missed;
    }
    return missed;
}

int getSum(const int* array, int startIndex, int endIndex) {
    int result = array[endIndex] - array[startIndex];
    DEBUG(cerr << "sum of " << (array == workMeetingsSum ? "workMeetingSum" : array == remoteMeetingsSum ? "remoteMeetingsSum" : "noDutySum") << "[" << startIndex << ", " << endIndex << "] = " << result << endl;)
    return result;
}

int solve(const int n, const int maxMissedMeetings, const int travelTime, const string& calendar) {
    int minMissedMeetings = countMinMissedMeetings(n, calendar, travelTime);
    if (minMissedMeetings > maxMissedMeetings) {
        return -1;
    }
    REP(x,n+1) {
        workMeetingsSum[x+1] = workMeetingsSum[x] + (calendar[x] == WORK_MEETING);
        remoteMeetingsSum[x+1] = remoteMeetingsSum[x] + (calendar[x] == REMOTE_MEETING);
        noDutySum[x+1] = noDutySum[x] + (calendar[x] == NO_DUTY);
    }
    DEBUG(
        printArray(cerr, workMeetingsSum, n+1);
        printArray(cerr, remoteMeetingsSum, n+1);
        printArray(cerr, noDutySum, n+1);
    )
    if (workMeetingsSum[n] <= maxMissedMeetings) {
        DEBUG(cerr << "can stay at home all day" << endl;)
        return noDutySum[n] + workMeetingsSum[n] + min(maxMissedMeetings - workMeetingsSum[n], remoteMeetingsSum[n]);
    }
    int maxScore = -1;
    int maxLeaveHome = (n-travelTime-travelTime);
    int maxLeaveWork = (n-travelTime);
    ///////// time flow ////////
    // 0 -> day start, Bajtazar is at home
    // [leaveHome-travelTime] -> Bajtazar leaves home
    // [leaveHome] -> Bajtazar starts work after traveling for [travelTime]
    // [leaveWork] -> Bajtazar leaves work
    // [leaveWork+travelTime] -> Bajtazar enters home
    // n -> day end

    //////// time ranges ////////
    // [0, leaveHome) - at home
    // [leaveHome, leaveHome+travelTime) - traveling
    // [leaveHome+travelTime, leaveWork) - working
    // [leaveWork, leaveWork+travelTime) - traveling
    // [leaveWork+travelTime, n) - at home
    for (int leaveHome = 0; leaveHome <= maxLeaveHome; ++leaveHome) {
        for (int leaveWork = leaveHome+travelTime; leaveWork <= maxLeaveWork; ++leaveWork) {
            // missed work meetings - all meetings except those in working hours
            int missedWorkMeetings = workMeetingsSum[n] - getSum(workMeetingsSum, leaveHome+travelTime, leaveWork);
            // missed remote meetings - only during travel time
            int missedRemoteMeetings = getSum(remoteMeetingsSum, leaveHome, leaveHome+travelTime) + getSum(remoteMeetingsSum, leaveWork, leaveWork+travelTime);
            if (missedWorkMeetings + missedRemoteMeetings <= maxMissedMeetings) {
                #ifdef PRINT_SOLUTIONS
                    DEBUG(cerr << "work from " << leaveHome+travelTime << " to " << leaveWork << " results in " << missedWorkMeetings << " missed work meetings and " << missedRemoteMeetings << " missed remote meetings" << endl;
//                        cerr << "remote meetings: " << ( getSum(remoteMeetingsSum, leaveHome-travelTime, leaveHome) ) << " + " << (getSum(remoteMeetingsSum, leaveWork, leaveWork+travelTime)) << endl;
                    )
                #endif
                int remoteMeetingsAtHome = getSum(remoteMeetingsSum, 0, leaveHome) + getSum(remoteMeetingsSum, leaveWork+travelTime, n);
                int workMeetingsAtHome = getSum(workMeetingsSum, 0, leaveHome) + getSum(workMeetingsSum, leaveWork+travelTime, n);
                int contestTime = getSum(noDutySum, 0, leaveHome) + getSum(noDutySum, leaveWork+travelTime, n) + workMeetingsAtHome + min(maxMissedMeetings - missedWorkMeetings - missedRemoteMeetings, remoteMeetingsAtHome);
                DEBUG(cerr << "found score: " << contestTime << endl;)
                if (maxScore < contestTime)
                    maxScore = contestTime;
                break;
            } else {
                #ifdef PRINT_NOSOLUTIONS
                    DEBUG(cerr << "work from " << leaveHome+travelTime << " to " << leaveWork << " results in " << missedWorkMeetings << " missed work meetings and " << missedRemoteMeetings << " missed remote meetings" << endl;)
                #endif
            }
        }
    }
    
    return maxScore;
}

int main() {
    ios_base::sync_with_stdio(0);
    
    int n,maxMissedMeetings,travelTime;
    string calendar;
    {
        cin >> n >> maxMissedMeetings >> travelTime >> calendar;
        cout << solve(n, maxMissedMeetings, travelTime, calendar) << endl;
    }
    return 0;
}