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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <cstdint>
#include <string>
#include <vector>

namespace {
    using uint_t = uint_fast32_t;
    using vector_t = std::vector<uint_t>;

    using std::cin, std::cout;
    using std::string;

    constexpr char SWB = '1';
    constexpr char PZ = '2';
    constexpr char BO = '3';

    struct liczniki_t {
        uint_t swb;
        uint_t pz;
        uint_t bo;
    };

    uint_t maksimum_bo(string const & s, vector_t const & seg, uint_t dz, uint_t n, uint_t k, uint_t t) {
        if (dz > seg.size())
            return UINT_FAST32_MAX;

        uint_t prefix_bo = 0, sufix_bo = 0;
        uint_t prefix_swb = 0, sufix_swb = 0;
        uint_t maks = 0;
        bool znaleziono_maks = false;
        uint_t ipocz = 0, ikon = n - 1;
        uint_t opuszczone_spotkania = 0;
        for (uint_t j = 0; j <= seg.size() - dz; ++j) {
            if (seg[j] >= t && seg[j + dz - 1] < n - t) {
                for (uint_t i = ipocz; i < seg[j] - t; ++i)
                    if (s[i] == BO) ++prefix_bo;
                    else if (s[i] == SWB) ++prefix_swb;
                ipocz = seg[j] - t;

                sufix_bo = 0;
                sufix_swb = 0;
                for (uint_t i = ikon; i > seg[j + dz - 1] + t; --i)
                    if (s[i] == BO) ++sufix_bo;
                    else if (s[i] == SWB) ++sufix_swb;
            
                opuszczone_spotkania = prefix_swb + sufix_swb;
                for (uint_t i = 1; i <= t; ++i) {
                    if (s[seg[j] - i] != BO) ++opuszczone_spotkania;
                    if (s[seg[j + dz - 1] + i] != BO) ++opuszczone_spotkania;
                }

                if (opuszczone_spotkania <= k) {
                    znaleziono_maks = true;
                    uint_t mozna_opuscic_w_domu = k - opuszczone_spotkania;
                    uint_t ile_spotkan_w_domu = 0;
                    for (uint_t l = 0; l < seg.size(); ++l) {
                        if (seg[l] <  seg[j] - t || seg[l]  > seg[j + dz - 1] + t)
                            if (s[seg[l]] == PZ)
                                ++ile_spotkan_w_domu;
                    }
                    if (ile_spotkan_w_domu < mozna_opuscic_w_domu)
                        mozna_opuscic_w_domu = ile_spotkan_w_domu;
                    if (prefix_bo + sufix_bo + mozna_opuscic_w_domu + prefix_swb + sufix_swb > maks) {
                        maks = prefix_bo + sufix_bo + mozna_opuscic_w_domu + prefix_swb + sufix_swb;
                    }
                }
            }
        }

        uint_t tmp_maks = maksimum_bo(s, seg, dz + 1, n, k, t);
        if (!znaleziono_maks)
            return tmp_maks;
        else 
            return maks >= tmp_maks || tmp_maks == UINT_FAST32_MAX ? maks : tmp_maks;
    }
}

int main() {
    uint_t n, k, t;
    string s;
    uint_t zadania = 0;
    liczniki_t opuszczone = {0, 0, 0};
    liczniki_t w_prefix_t = {0, 0, 0};
    liczniki_t w_sufix_t = {0, 0, 0};
    vector_t segmenty_spotkan;

    cin >> n >> k >> t >> s;

    for (uint_t i = 0; i < n; ++i) {
        ++zadania;
        if (s[i] == SWB) {
            ++opuszczone.swb;
            if (i < t) ++w_prefix_t.swb;
            else if (i >= n - t) ++w_sufix_t.swb;
            segmenty_spotkan.push_back(i);
        } else if (s[i] == PZ) {
            ++opuszczone.pz;
            if (i < t) ++w_prefix_t.pz;
            else if (i >= n - t) ++w_sufix_t.pz;
            segmenty_spotkan.push_back(i);
        } else {
            if (i < t) ++w_prefix_t.bo;
            else if (i >= n - t) ++w_sufix_t.bo;
        }
    }

    if (opuszczone.swb + opuszczone.pz <= k) {
        cout << zadania << '\n';
    } else if (opuszczone.swb <= k) {
        cout << zadania - (opuszczone.swb + opuszczone.pz - k) << '\n';
    } else {
        uint_t maks_spotkania_w_pracy = opuszczone.swb + opuszczone.pz
                                        - (w_prefix_t.swb + w_sufix_t.swb)
                                        - (w_prefix_t.pz + w_sufix_t.pz);
        uint_t do_zrobienia = opuszczone.swb - k;
        if (do_zrobienia > maks_spotkania_w_pracy) {
            cout << "-1\n";
        } else {
            uint_t maksimum = maksimum_bo(s, segmenty_spotkan, do_zrobienia, n, k, t);
            if (maksimum != UINT_FAST32_MAX)
                cout << maksimum << '\n';
            else
                cout << "-1\n";
        }
    }
}