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
#include<iostream>

using namespace std;

const int maxN=8e3;

string s;
int n, k, t, result=-1;
int officeNum=0, homeNum=0, freeNum=0, ss2[maxN+1]{0}, ssF[maxN+1]{0}, psF[maxN+1]{0}, ps1[maxN+1]{0}, ss1[maxN+1]{0};

int f(int num2 , int mid1, int mid2, int freeTime){
    //cout<<num2<<' '<<mid1<<' '<<mid2<<' '<<freeTime<<endl;
    int calls = officeNum + homeNum - k;
    calls -= mid1+mid2;
    if(calls - num2 > 0)return -1;
    num2 -= calls;
    int result = freeTime+num2;
    result = max(result, -1);
    return result;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k>>t>>s;
    for(char c : s){
        if(c == '1')officeNum++;
        else if(c == '2')homeNum++;
        else freeNum++;
    }
    for(int i=n-1; i>=0; i--){
        ss1[i] = ss1[i+1];
        ss2[i] = ss2[i+1];
        ssF[i] = ssF[i+1];
        if(s[i] == '2')ss2[i]++;
        if(s[i] == '3')ssF[i]++;
        if(s[i] == '1')ss1[i]++;
    }
    for(int i=1; i<=n; i++){
        psF[i] = psF[i-1];
        ps1[i] = ps1[i-1];
        if(s[i-1] == '3')psF[i]++;
        if(s[i-1] == '1')ps1[i]++;
    }
    if(k >= officeNum){
        cout<<freeNum+min(k, officeNum+homeNum);
        return 0;
    }
    //=================================
    //Przypadek liniowy !!!
    int lt2=0, rt2=homeNum, mid2=0, mid1=0;
    for(int i=0; i<2*t; i++)if(s[i] == '2')rt2--;
    for(int i=0; i<=n-2*t; i++){
        for(int j=i+2*t-1; j<n-1; j++){
            result = max(result, f(lt2+rt2, mid1, mid2, psF[i]+ssF[j+1]+ps1[i]+ss1[j+1]));
            if(s[j-t+1] == '1')mid1++;
            else if(s[j-t+1] == '2')mid2++;
            if(s[j+1] == '2')rt2--;
        }
        result = max(result, f(lt2+rt2, mid1, mid2, psF[i]+ps1[i]));
        if(s[i] == '2')lt2++;
        mid1 = mid2 = 0;
        rt2 = ss2[i+2*t+1];
    }
    cout<<result;
    return 0;
}