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
#include <stdio.h>
#include <algorithm>

#define N 8000

int n,k,t;
int ob[N];
char c;
int rozw = -1;

struct wracam {
    int przegapione;
    int zdalnych_po_powrocie;
};

wracam wracam_w_itym[N];

int pom, rozwiazuje, zdalne;

void jade_do_pracy(int idx, int pominiete, int zdalne_w_domu) {
    int i=idx;
    for(; i<idx+t && i<n; i++) {
        if(ob[i]!=3) {
            pominiete++;
        }
    }
    for(;i<n; i++) {
        //wracam w czasie i
        if(wracam_w_itym[i].przegapione == -1) {
            return;
            //za pozno juz mi nic nie pomoże
        }
        pom = pominiete + wracam_w_itym[i].przegapione;
        if(pom > k) {
            continue;
            //za duzo przegapionych
        }
        rozwiazuje = (idx-zdalne_w_domu) + (n-i-t-wracam_w_itym[i].zdalnych_po_powrocie);
        //printf("%d %d %d %d %d %d\n", idx, zdalne_w_domu, n, i, t, wracam_w_itym[i].zdalnych_po_powrocie);
        //jeszcze moge kilka zdalnych ominac, jesli sa
        zdalne = zdalne_w_domu+wracam_w_itym[i].zdalnych_po_powrocie;
        if(k>pom) {
            rozwiazuje+=std::min(k-pom,zdalne);
        }
        if (rozwiazuje > rozw) {
            //printf("%d %d %d\n", idx, i, rozwiazuje);
            //printf("%d %d %d %d %d %d\n", idx, zdalne_w_domu, n, i, t, wracam_w_itym[i].zdalnych_po_powrocie);
            rozw = rozwiazuje;
        }
    }
}

int main() {
    scanf("%d %d %d ", &n, &k, &t);
    for(int i=0; i<n; i++) {
        scanf("%c", &c);
        ob[i]=c-48;
    }

    int przegapione_zdalne = 0;
    int przegapione_biuro = 0;
    int zdalne_po_powrocie = 0;
    for(int i=n-1; i>=0; i--) {
        if(ob[i]==1) {
            przegapione_biuro++;
        } else if(ob[i]==2) {
            przegapione_zdalne++;
        }
        if(i+t>n) {
            wracam_w_itym[i].przegapione = -1;
        } else {
            if(ob[i+t]==2) {
                przegapione_zdalne--;
                zdalne_po_powrocie++;
            }
            wracam_w_itym[i].przegapione = przegapione_biuro + przegapione_zdalne;
            wracam_w_itym[i].zdalnych_po_powrocie = zdalne_po_powrocie;
        }
    }
    if (przegapione_biuro<=k) {
        //nie musze jechac do pracy
        rozwiazuje = n-std::max(0, przegapione_zdalne + przegapione_biuro + zdalne_po_powrocie-k);
        printf("%d\n", rozwiazuje);
        return 0;
    }

    //for (int i=0; i<n; i++) {
    //    printf("%d %d\n", wracam_w_itym[i].przegapione, wracam_w_itym[i].zdalnych_po_powrocie);
    //}


    int pominiete = 0;
    int zdalne_w_domu = 0;
    for(int i=0; i<n; i++) {
        jade_do_pracy(i, pominiete, zdalne_w_domu);
        if(ob[i]==1) {
            pominiete++;
        } else if (ob[i]==2) {
            zdalne_w_domu++;
        }
    }
    printf("%d\n", rozw);

    return 0;
}