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
#include <bits/stdc++.h>
using namespace std;

struct points {
    int earnings = 0;           //time to write potyczki
    int cost = 0;           //meetings missed
    int potential = 0;          //meetings I can miss ('2' when I'm at home)
    void set(int e, int c, int p) {
        earnings = e;
        cost = c;
        potential = p;
    }
};
bool checkNoTravel(int k, string &tasks) {
    int ones = 0;
    int twos = 0;
    int threes = 0;
    for(char &a : tasks) {
        if(a == '1') {
            ones++;
        }
        else if(a == '2') {
            twos++;
        }
        else if(a == '3') {
            threes++;
        }
    }
    if(ones <= k) {         //good option
        cout << threes + ones + min(k-ones, twos) << "\n";
        return true;
    }
    return false;
}
void calculate(int n, int t, points *prefix, points *suffix, string &tasks) {
    int earnings = 0;
    int cost = 0;
    int potential = 0;
    for(int i=0; i<=t-1; i++) {
        if(tasks[i] == '1' || tasks[i] == '2') {
            cost++;
        }
    }
    prefix[t-1].set(earnings, cost, potential);
    for(int i=t; i<n; i++) {
        if(tasks[i] == '1' || tasks[i] == '2') {
            cost++;
        }
        if(tasks[i-t] == '2') {
            cost--;
            potential++;
        }
        else if(tasks[i-t] == '1' || tasks[i-t] == '3') {
            earnings++;
        }
        prefix[i].set(earnings, cost, potential);
    }
    //the same for suffix
    earnings = 0;
    cost = 0;
    potential = 0;
    for(int i=n-1; i>=n-t; i--) {
        if(tasks[i] == '1' || tasks[i] == '2') {
            cost++;
        }
    }
    suffix[n-t].set(earnings, cost, potential);
    for(int i=n-t-1; i>=0; i--) {
        if(tasks[i] == '1' || tasks[i] == '2') {
            cost++;
        }
        if(tasks[i+t] == '2') {
            cost--;
            potential++;
        }
        else if(tasks[i+t] == '1' || tasks[i+t] == '3') {
            earnings++;
        }
        suffix[i].set(earnings, cost, potential);
    }
}

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

    int n, k, t;            //tasks, skips, travel time
    string tasks;
    cin >> n >> k >> t >> tasks;

    if(checkNoTravel(k, tasks)) {
        return 0;
    }

    points prefix[n];
    points suffix[n];
    calculate(n, t, prefix, suffix, tasks);

    int best = -1;
    for(int i=t-1; i<n; i++) {
        for(int j=i+1; j<n-t+1; j++) {
            int val = k - prefix[i].cost - suffix[j].cost;
            if(val >= 0) {
                best = max(best, prefix[i].earnings + suffix[j].earnings
                    + min(val, prefix[i].potential + suffix[j].potential));
            }
        }
    }
    cout << best << "\n";

    return 0;
}