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 <bits/stdc++.h>

using namespace std;

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k, t, result, meetingSum, y;
    string s;
    int* onlineLeftSum;
    int* onlineRightSum;
    int* localLeftSum;
    int* localRightSum;
    
    cin >> n >> k >> t >> s;
    
    onlineLeftSum = new int[n + 2];
    onlineRightSum = new int[n + 2];
    localLeftSum = new int[n + 2];
    localRightSum = new int[n + 2];
    
    for(int i = 0; i < n; ++i){
        if(s[i] == '1'){
            localLeftSum[i + 1] = 1;
            localRightSum[i + 1] = 1;
            onlineLeftSum[i + 1] = 0;
            onlineRightSum[i + 1] = 0;
        }
        else if(s[i] == '2'){
            onlineLeftSum[i + 1] = 1;
            onlineRightSum[i + 1] = 1;
            localRightSum[i + 1] = 0;
            localLeftSum[i + 1] = 0;
        }
        else{
            localRightSum[i + 1] = 0;
            localLeftSum[i + 1] = 0;
            onlineLeftSum[i + 1] = 0;
            onlineRightSum[i + 1] = 0;
        }
    }
    localRightSum[n + 1] = 0;
    localLeftSum[n + 1] = 0;
    onlineLeftSum[n + 1] = 0;
    onlineRightSum[n + 1] = 0;

    
    for(int i = 1; i < n + 2; ++i){
        localLeftSum[i] += localLeftSum[i - 1];
        onlineLeftSum[i] += onlineLeftSum[i - 1];
    }
    for(int i = n; i >=0; --i){
        localRightSum[i] += localRightSum[i + 1];
        onlineRightSum[i] += onlineRightSum[i + 1];
    }
    
    
    meetingSum = localLeftSum[n + 1] + onlineLeftSum[n + 1];
    
    // cout << n <<' ' << k << ' ' << t << '\n';
    // cout << s << '\n';
    k = max(meetingSum - k, 0);
    
    // for(int i = 0; i < n + 2; ++i){
    //     cout << localLeftSum[i] << ' ';
    // }
    // cout << '\n';
    // for(int i = 0; i < n + 2; ++i){
    //     cout << localRightSum[i] << ' ';
    // }
    // cout << '\n';
    // for(int i = 0; i < n + 2; ++i){
    //     cout << onlineLeftSum[i] << ' ';
    // }
    // cout << '\n';
    // for(int i = 0; i < n + 2; ++i){
    //     cout << onlineRightSum[i] << ' ';
    // }
    // cout << '\n';
    
    result = -1;
    
    if(onlineLeftSum[n + 1] >= k){
        result = n - k;
        // cout << "ASD";
    }
    else{
        
        for(int i = t + 1; i <= n - t; ++i){
            for(int j = i; j <= n - t; ++j){
                y = k - (localLeftSum[j] - localLeftSum[i - 1] + onlineLeftSum[j] - onlineLeftSum[i - 1]);
                // cout << i << ' ' << j << ' ' << y << '\n';
                if(onlineLeftSum[i - t - 1] + onlineRightSum[j + t + 1] >= y){
                    // cout << "ASD: " << i << ' ' << j << '\n';
                    result = max(result, n - (j - i + 1 + t + t) - y);
                }
            }
        }
    }
    
    cout << result << '\n';
    
    return 0;
}