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

const int MAXN = 8e3 + 5;

int w = -1;
int ile[MAXN][3];

int P(int a, int b, int c){
    if(a > b) return 0;
    return ile[b][c] - ile[a-1][c];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k, t;
    cin >> n >> k >> t;
    string s;
    cin >> s;
    for(int i = 1; i <= n; ++i){
        ile[i][0] = ile[i-1][0];
        ile[i][1] = ile[i-1][1];
        ile[i][2] = ile[i-1][2];
        ile[i][(s[i-1]-'0')-1]++;
        //cout << i << " " << ile[i][0] << " " << ile[i][1] << " " << ile[i][2] << "\n";
    }
    for(int i = 1; i <= n-2*t+1; ++i){
        int c1 = P(1, i - 1, 0);
        int iloscwolnego = P(1, i - 1, 2);
        int ilosczdalnego = P(1, i - 1, 1);
        int iloscmiss = P(i, i + t - 1, 1) + P(i, i + t - 1, 0) + c1;
        int d = c1 + iloscwolnego;
        if(iloscmiss > k) continue;
        for(int j = i + t; j <= n-t+1; ++j){
            int c2 = P(j + t, n, 0);
            int iloscmiss2 = P(j, j + t - 1, 1) + P(j, j + t - 1, 0) + c2;
            int iloscwolnego2 = P(j + t, n, 2);
            int ilosczdalnego2 = P(j + t, n, 1);
            if(iloscmiss2 + iloscmiss > k) continue;
            w = max(w, d + c2 + iloscwolnego2 + min(k - iloscmiss - iloscmiss2, ilosczdalnego2 + ilosczdalnego));
        }
    }
    if(P(1, n, 0) <= k) w = max(w, P(1, n, 2) + min(k, P(1, n, 0) + P(1, n, 1)));
    cout << w << "\n";
    return 0;
}