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
#include <bits/stdc++.h>

constexpr int N=8000, DEBUG=0, D=8192;
constexpr short INF=SHRT_MAX;
int n, k, t, r=-1; // n - ile godzin, k - ile spotkan mozna opuscic, t - czas dojazdu
char s[N+2]; // 1 - spotkanie w biurze, 2 - spotkanie online, 3 - wolne
short u1[N+2], u2[N+2]; // sumy prefixowe
short tr[2*D];

inline short s1(int a, int b) {
    if (b<a) return 0;
    return u1[b]-u1[a-1];
}
inline short s2(int a, int b) {
    if (b<a) return 0;
    return u2[b]-u2[a-1];
}
inline int calc_missed_surely_right(int q) {
    return s1(q+1, n)+s2(q+1, q+t);
}

// zwraca indeks pierwszego w przedziale <=k lub -1, gdy nie istn.
int query(int w, int a, int b, int l, int r, int k) {
    if ((b<l)||(a>r)) return -1;
    if (tr[w]>k) return -1;
    if (w>=D) return w-D;

    int x=query(2*w, a, b, l, (l+r)/2, k);
    if (x!=-1) return x;
    return query(2*w+1, a, b, (l+r)/2+1, r, k);
}

int main() {
    scanf("%d%d%d", &n, &k, &t);
    scanf("%s", s+1);

    // liczenie sum prefixowych
    for (int i=1; i<=n; ++i) {
        u1[i] = u1[i-1];
        u2[i] = u2[i-1];
        switch (s[i]) {
            case '1':
            ++u1[i];
            break;
            case '2':
            ++u2[i];
            break;
        }
    }

    if (s1(1, n)<=k) r = std::max(r, n-std::max(s2(1, n)-(k-s1(1, n)), 0));
    if (DEBUG) printf("r=%d\n", r);

    for (int i=D; i!=2*D; ++i) tr[i] = INF;
    for (int i=t+1; i<=n-t; ++i) {
        tr[D+i] = calc_missed_surely_right(i);
    }
    for (int i=D-1; i!=0; --i) tr[i] = std::min(tr[2*i], tr[2*i+1]);

    for (int i=t+1; i<=n-t; ++i) {
        short missed_surely_left = s1(1, i-1)+s2(i-t, i-1);
        if (missed_surely_left>k) continue;
        short q = query(1, D+i, D+n-t, D, 2*D-1, k-missed_surely_left);
        if (q==-1) continue;
        r = std::max(r, i-t-1+n-q-t - std::max(s2(1, i-t-1)+s2(q+t+1, n) - (k-missed_surely_left-calc_missed_surely_right(q)), 0));
    }

    printf("%d\n", r);
    return 0;
}