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

#define MAXN 8000

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int n, k, t;
char S[MAXN];

/* Aux counters */
struct seg {
    int len;
    int m1;
    int m2;
};

void zero(struct seg *s) {
    s->len = 0;
    s->m1 = 0;
    s->m2 = 0;
}

/* add an hour to the counter */
void move(struct seg *from, struct seg *to, int i) 
{
    if (S[i] == '1') {
        to->m1++;
        from->m1--;
    }

    if (S[i] == '2') {
        to->m2++;
        from->m2--;
    }

    to->len++;
    from->len--;
}

int get_value(struct seg *H, struct seg *R, struct seg *O) 
{
    int X = H->m1 + R->m1 + R->m2;

    if (k < X)
        return -1;

    int ret = H->len - (H->m2 - (k - X));
    return ret;
}

int praca()
{
    int best = -1;
    struct seg H, R, O;
    int m1 = 0, m2 = 0;

    /* a) Never go to the office */
    for (int i = 0; i < n; ++i) {
        if (S[i] == '1')
            m1++;
        if (S[i] == '2')
            m2++;
    }

    if (m1 < k) {
        int skipped = MIN(m1 + m2, k);
        return n + MIN(0, k - skipped);
    }

    /* b) We need to go to the office */
    zero(&H);
    zero(&R);
    zero(&O);
    H.m1 = m1;
    H.m2 = m2;
    H.len = n;
    for (int start = t; start < n-1; ++start) {
        zero(&H);
        zero(&R);
        zero(&O);
        H.m1 = m1;
        H.m2 = m2;
        H.len = n;

        /* init with len 1 */
        move(&H, &O, start);
        for (int i = 0; i < t; ++i) {
            int prev = start - i - 1;
            int next = start + i + 1;
            move(&H, &R, prev);
            move(&H, &R, next);
        }

        int value = get_value(&H, &R, &O);
        if (value > best)
            best = value;
    
        for (int end = start + 1; end < n - t; ++end) {
            move(&R, &O, end);
            move(&H, &R, end + t);
            int value = get_value(&H, &R, &O);
            if (value > best)
                best = value;
        }
    }

    return best;
}

int main()
{
    scanf("%d%d%d", &n, &k, &t);
    scanf("%s", S);
    printf("%d\n", praca());

    return 0;
}