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
// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever! 
#include <bits/stdc++.h>

using namespace std;

auto range(auto l, auto r) { return views::iota(l,r); }
auto rev=views::reverse;

_GLIBCXX_ALWAYS_INLINE void chmax(auto &a, auto b) { a=max(a,b); }
_GLIBCXX_ALWAYS_INLINE void chmin(auto &a, auto b) { a=min(a,b); }

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
// int T; cin>>T;
int T=1;
while (T--) []{
    int n, k, t;
    cin>>n>>k>>t;
    string a; cin>>a; a=" "+a;
    array<vector<int>,3> f;
    f[0].resize(n+1); f[1].resize(n+1); f[2].resize(n+1);
    for (int i=1; i<=n; ++i) {
        for (auto x: {0,1,2}) f[x][i]=f[x][i-1]+(a[i]=='1'+x);
    }
    int ans=-1;
    if (f[0][n]<=k) {
        int rest=k-f[0][n];
        chmax(ans,f[2][n]+f[0][n]+min(rest,f[1][n]));
    }

    // [i-t,i-1] && [j,j+t-1]
    for (int i=t+1; i+t-1<=n; ++i) // [i,j)
        for (int j=i; j+t-1<=n; ++j) {
            int rest=f[0][i-1]+f[0][n]-f[0][j-1]
                    +f[1][i-1]-f[1][i-t-1]+f[1][j+t-1]-f[1][j-1];
            if (rest>k) continue;
            rest=k-rest;
            // [1,i-t) [j+t,n]
            // cerr<<i<<' '<<j<<' '<<rest<<':'<<f[2][i-t-1]+f[2][n]-f[2][j+t-1]
            // +min(rest, f[1][i-t-1]+f[1][n]-f[1][j+t-1])<<'\n';
            chmax(ans,
                f[2][i-t-1]+f[2][n]-f[2][j+t-1]+
                f[0][i-t-1]+f[0][n]-f[0][j+t-1]+
                +min(rest, f[1][i-t-1]+f[1][n]-f[1][j+t-1]));
        }

    cout<<ans<<'\n';
}();
}