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

int calculateMaxValidMeetings(const std::string& schedule, int n, int k, int t) {
    std::vector<std::vector<int>> left(schedule.length(), std::vector<int>(3, 0));
    std::vector<std::vector<int>> right(schedule.length(), std::vector<int>(3, 0));
    
    // Obliczamy liczniki z lewej strony
    for (int i = 1; i < schedule.length(); i++) {
        left[i] = left[i-1];
        if (schedule[i-1] >= '1' && schedule[i-1] <= '3') {
            left[i][schedule[i-1] - '1']++;
        }
    }
    
    // Obliczamy liczniki z prawej strony
    for (int i = schedule.length()-2; i >= 0; i--) {
        right[i] = right[i+1];
        if (schedule[i+1] >= '1' && schedule[i+1] <= '3') {
            right[i][schedule[i+1] - '1']++;
        }
    }

    std::vector<int> turtle(n, 0);
    int meetingCounter = 0;
    int turtleBegin = 0;
    int turtleEnd = t-1;

    for(int i = 0; i < t; i++) {
        if(schedule[i] == '1' || schedule[i] == '2') {
            meetingCounter++;
        }
    }
    
    turtle[turtleBegin] = meetingCounter;
    turtleEnd++;
    turtleBegin++;

    while(turtleEnd < n) {
        if(schedule[turtleBegin-1] == '1' || schedule[turtleBegin-1] == '2') {
            meetingCounter--;
        }
        if(schedule[turtleEnd] == '1' || schedule[turtleEnd] == '2') {
            meetingCounter++;
        }

        turtle[turtleBegin] = meetingCounter;
        turtleBegin++;
        turtleEnd++;
    }

    int max = -1;

    // Główna logika
    for(int i = 0; i < n; i++) {
        for(int j = i+t; j <= n-t; j++) {
            int validationSum = turtle[i] + turtle[j] + left[i][0] + right[j +t - 1][0];
            if(validationSum > k) {
                continue;
            }

            int result = left[i][0] + right[j +t -1][0] + left[i][2] + right[j +t -1][2];
            int canSkip = k - validationSum;
            int freeCandidates = left[i][1] + right[j +t-1][1];
            int toAdd = freeCandidates > canSkip ? canSkip : freeCandidates;

            if(result + toAdd > max) {
                max = result + toAdd;
            }
        }
    }

    // Sprawdzenie pierwszej pozycji
    if (schedule[0] == '1') right[0][0]++;
    if (schedule[0] == '2') right[0][1]++;
    if (schedule[0] == '3') right[0][2]++;

    int validationSum = right[0][0];
   
    if (validationSum <= k) {
        int result = right[0][0] + right[0][2];
        int canSkip = k - validationSum;
        int freeCandidates = right[0][1];
        int toAdd = freeCandidates > canSkip ? canSkip : freeCandidates;

        if (result + toAdd > max) {
            max = result + toAdd;
        }
    }

    return max;
}

//#if !defined(GTEST_TESTING)
int main() {
    int n, k, t;
    std::cin >> n >> k >> t;
    
    std::string schedule;
    std::cin >> schedule;
    
    std::cout << calculateMaxValidMeetings(schedule, n, k, t);
    return 0;
}
//#endif