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

using namespace std;

#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi; 
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;

const int max_n = 8007;
int arr[max_n];
int pref[max_n][4];

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int n,k,t; cin >> n >> k >> t;
    string s; cin >> s;
    rep(i,1,n){
        arr[i] = int(s[i-1]-'0');
        rep(j,1,3) pref[i][j] = pref[i-1][j];
        pref[i][arr[i]]++;
    }

    int ans = -1;
    rep(i,t,n-t){
        //w momencie i przyjezdzam do biura
        rep(j,i+1,n-t+1){
            //w momencie j wyjezdzam z biura!
            int ile_odp = 0;
            ile_odp += pref[i][2]-pref[i-t][2]+pref[j+t-1][2]-pref[j-1][2]; //trasa
            ile_odp += pref[i][1]-pref[i-t][1]+pref[j+t-1][1]-pref[j-1][1]; //trasa
            ile_odp += pref[i-t][1]+pref[n][1]-pref[j+t-1][1];//spotkania biurowe!
            //cout << "\ni: " << i << " j: " << j << " ile_odp: " << ile_odp << '\n';
            if(ile_odp > k) continue;
            int val = pref[i-t][3]+pref[n][3]-pref[j+t-1][3]+pref[i-t][1]+pref[n][1]-pref[j+t-1][1];
            int ile_z = pref[i-t][2]+pref[n][2]-pref[j+t-1][2];
            val += min(ile_z,k-ile_odp); //ile mozemy sobie odpuscic spotkan
            ans = max(ans,val);
            //cout << "val: " << val << '\n';
        }
    }

    //jeszcze case na brak biura!
    int ile_odp = pref[n][1];
    if(ile_odp <= k) ans = max(ans,pref[n][3]+pref[n][1]+min(pref[n][2],k-ile_odp));

    cout << ans;

    return 0;
}

//g++ -O3 -static -Wall .cpp -std=c++17