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

using namespace std;
const int N=8001;

int ile1[N];
int ile2[N];
int ile3[N];
int ile1po[N];
int ile2po[N];
int ile3po[N];
int main()
{
    //for(int i=0;i<1000;++i)cout<<i<<' ';
    int n,k,t,jed=0,dwoj=0,troj=0;
    string s;
    cin>>n>>k>>t;
    cin>>s;
    int wyn=-1;
    /*
    if(s[0]=='1'){
        ile1[0]++;
    }
    else if(s[0]=='2'){
        ile2[0]++;
    }
    else{
        ile3[0]++;
    }
    */
    for(auto i:s){
        if(i=='1')jed++;
        else if(i=='2')dwoj++;
        else troj++;
    }

    for(int i=1;i<n-1;++i){
        ile1[i]=ile1[i-1];
        ile2[i]=ile2[i-1];
        ile3[i]=ile3[i-1];
        if(s[i-1]=='1'){
            ile1[i]=ile1[i-1]+1;
        }
        else if(s[i-1]=='2'){
            ile2[i]=ile2[i-1]+1;
        }
        else{
            ile3[i]=ile3[i-1]+1;
        }
    }
     for(int i=n-2;i>=0;--i){
        ile1po[i]=ile1po[i+1];
        ile2po[i]=ile2po[i+1];
        ile3po[i]=ile3po[i+1];
        if(s[i+1]=='1'){
            ile1po[i]=ile1po[i+1]+1;
        }
        else if(s[i+1]=='2'){
            ile2po[i]=ile2po[i+1]+1;
        }
        else{
            ile3po[i]=ile3po[i+1]+1;
        }
    }
    if(jed<=k)wyn=troj+min(jed+dwoj,k);//nie pojecha³ do b

   // cout<<jed+dwoj<<endl;
   // cout<<ile1[n-1];
    for(int i=t;i<n-t;++i){
        int wyn_przed=ile3[i-t],kosztb=ile1[i]+ile2[i]-ile2[i-t] ;//1 i 2,-ile1[i-t]
       // if(s[i-t]=='3')wyn_przed--;
        //if(s[i-t]=='1')kosztb++;
        int wyn_po=ile3po[i+t],kosztd=ile1po[i]+ile2po[i]-ile2po[i+t];//po co aaa,-ile1po[i+t]
      //  cout<<"i="<<i<<" "<<kosztb<<' '<<kosztd<<endl;
      ///  if(s[n-1]=='1')kosztd++;
        int koszt=kosztb+kosztd;
        if(koszt<=k){
            wyn=max(wyn,wyn_przed+wyn_po+ile1[i-t]+ile1po[i+t]+min(max(k-koszt,0),dwoj));//min(k-koszt,dwoj+jed-koszt+ile1[i-t]+ile1po[i+t])
            //cout<<"i="<<i<<" "<<kosztb<<' '<<kosztd<<' ';
           // cout<<max(k-(ile1[i]+ile2[i]-ile2[i-t]-ile1[i-t])-(ile1po[i]+ile2po[i]-ile2po[i+t]-ile1po[i+t]),0);
           // cout<<wyn_przed<<' '<<wyn_po<<' '<<wyn<<endl;
            //cout<<"w1="<<wyn<<endl;
            //return 0;
            }
        for(int j=i+1;j<n-t;++j){

            wyn_po=ile3po[j+t];
            kosztd=ile1po[j]+ile2po[j]-ile2po[j+t];//-ile1po[j+t]
            koszt=kosztb+kosztd;
            if(koszt<=k){
                wyn=max(wyn,wyn_przed+wyn_po+ile1[i-t]+ile1po[j+t]+min(max(k-koszt,0),dwoj));
             //   cout<<wyn_przed<<' '<<wyn_po<<' '<<max(k-(ile1[j]+ile2[j]-ile2[j-t]-ile1[j-t])-(ile1po[j]+ile2po[j]-ile2po[j+t]-ile1po[j+t]),0)<<endl;
                       // cout<<wyn_przed<<' '<<wyn_po;
                        // ile1[i-t]-ile1po[j+t]-(ile2po[i]-ile2po[i+t])-()
            }

        }


    }

    cout<<wyn;


    return 0;
}