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

using namespace std;

struct sum{
    int offices = 0,
        remotes = 0,
        potyczkas = 0;        
    sum operator+(sum& rhs)
    {
        return sum{offices + rhs.offices,
                   remotes + rhs.remotes,
                   potyczkas + rhs.potyczkas};
    }
    sum operator-(sum& rhs)
    {
        return sum{offices - rhs.offices,
                   remotes - rhs.remotes,
                   potyczkas - rhs.potyczkas};
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, k, t;
    cin>>n>>k>>t;
    string s;
    cin>>s;
    vector<sum> pref(n+1), suf(n+1);
    for(int i=0; i<n; i++)
    {
        pref[i+1] = pref[i];
        if(s[i] == '1')
            pref[i+1].offices++;
        else if(s[i] == '2')
            pref[i+1].remotes++;
        else
            pref[i+1].potyczkas++;
    }
    for(int i=0; i<n; i++)
    {
        suf[n-i-1] = suf[n-i];
        if(s[n-i-1] == '1')
            suf[n-i-1].offices++;
        else if(s[n-i-1] == '2')
            suf[n-i-1].remotes++;
        else
            suf[n-i-1].potyczkas++;
    }
    int sol = -1;
    for(int i=0; i<n-2*t; i++)
    {
        for(int j=i+2*t; j<n; j++)
        {
            //cout<<i<<".."<<j<<"\n";
            sum score = pref[i] + suf[j+1];
            sum travel = pref[i+t] - pref[i] + suf[j+1-t] - suf[j+1];
            int lost = score.offices + travel.offices + travel.remotes;
            if(lost > k)
                continue;
            int skipped = min(score.remotes, k-lost);
            //cout<<score.offices<<" "<<score.remotes<<" "<<score.potyczkas<<"\n";
            //cout<<travel.offices<<" "<<travel.remotes<<" "<<travel.potyczkas<<"\n";
            //cout<<skipped<<"\n";
            //cout<<score.potyczkas + skipped<<";\n";
            sol = max(sol, score.potyczkas + skipped + score.offices);
        }
    }
    sum score = pref[n];
//    cout<<score.offices<<" "<<score.remotes<<" "<<score.potyczkas<<"\n";
    int lost = score.offices;
    if(lost <= k)
    {
        int skipped = min(score.remotes, k-lost);
        sol = max(sol, score.potyczkas + skipped + score.offices);
//        cout<<"T"<<score.potyczkas+skipped+score.offices<<"\n";
    }
    cout<<sol<<"\n";
}