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

using namespace std;

int main() {
    int n, k, t;
    cin >> n >> k >> t;
    
    string schedule;
    cin >> schedule;
    
    // Verify we can visit the office within time constraints
    bool canVisitOffice = (2*t < n);
    
    // dp[i][j][l] = max problem solving time:
    // i = current position (0 to n)
    // j = meetings missed so far (0 to k)
    // l = 0 (at home) or 1 (at office)
    vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(k+1, vector<int>(2, -1)));
    
    // Base case: must end at home
    dp[n][0][0] = 0;
    for (int j = 1; j <= k; j++) {
        dp[n][j][0] = 0;
    }
    
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j <= k; j++) {
            // AT HOME
            // 1. Office meeting - must miss it
            if (schedule[i] == '1') {
                if (j < k && dp[i+1][j+1][0] != -1) {
                    // Skip and solve problems
                    dp[i][j][0] = 1 + dp[i+1][j+1][0];
                }
            } 
            // 2. Remote meeting - can attend or miss
            else if (schedule[i] == '2') {
                // Option 1: Attend meeting
                if (dp[i+1][j][0] != -1) {
                    dp[i][j][0] = dp[i+1][j][0];
                }
                // Option 2: Skip meeting and solve problems
                if (j < k && dp[i+1][j+1][0] != -1) {
                    dp[i][j][0] = max(dp[i][j][0], 1 + dp[i+1][j+1][0]);
                }
            } 
            // 3. No obligations - solve problems
            else { 
                if (dp[i+1][j][0] != -1) {
                    dp[i][j][0] = 1 + dp[i+1][j][0];
                }
            }
            
            // Travel to office (if possible)
            if (canVisitOffice && i + 2*t <= n) {
                int missedMeetings = 0;
                bool canTravel = true;
                
                // Count missed meetings during travel
                for (int p = i; p < i+t; p++) {
                    if (p < n && (schedule[p] == '1' || schedule[p] == '2')) {
                        missedMeetings++;
                        if (j + missedMeetings > k) {
                            canTravel = false;
                            break;
                        }
                    }
                }
                
                if (canTravel && j + missedMeetings <= k && dp[i+t][j+missedMeetings][1] != -1) {
                    dp[i][j][0] = max(dp[i][j][0], dp[i+t][j+missedMeetings][1]);
                }
            }
            
            // AT OFFICE
            // 1. Any meeting - can attend or miss
            if (schedule[i] == '1' || schedule[i] == '2') {
                // Option 1: Attend
                if (dp[i+1][j][1] != -1) {
                    dp[i][j][1] = dp[i+1][j][1];
                }
                // Option 2: Skip
                if (j < k && dp[i+1][j+1][1] != -1) {
                    dp[i][j][1] = max(dp[i][j][1], dp[i+1][j+1][1]);
                }
            } 
            // 2. No obligations - must work (no problem solving)
            else {
                if (dp[i+1][j][1] != -1) {
                    dp[i][j][1] = dp[i+1][j][1];
                }
            }
            
            // Travel back home
            if (i + t <= n) {
                int missedMeetings = 0;
                bool canTravel = true;
                
                // Count missed meetings during travel
                for (int p = i; p < i+t; p++) {
                    if (p < n && (schedule[p] == '1' || schedule[p] == '2')) {
                        missedMeetings++;
                        if (j + missedMeetings > k) {
                            canTravel = false;
                            break;
                        }
                    }
                }
                
                if (canTravel && j + missedMeetings <= k && dp[i+t][j+missedMeetings][0] != -1) {
                    dp[i][j][1] = max(dp[i][j][1], dp[i+t][j+missedMeetings][0]);
                }
            }
        }
    }
    
    cout << dp[0][0][0] << endl;
    return 0;
}