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

using namespace std;

constexpr int MAX_N = 8e3+7;
constexpr int MAX_K = 8e3+7;
constexpr int INF = INT_MAX;

int n; // liczba segmentów
int k; // liczba spotkań
int t; // czas przejazdu między domem Bajtazara a biurem

string S;

int pref_zdalne[MAX_N];
int pref_biuro[MAX_N];

constexpr int zdalne(int l, int r) {
    if (l > r) return 0;
    return pref_zdalne[r] - pref_zdalne[l-1];
}

constexpr int biuro(int l, int r) {
    if (l > r) return 0;
    return pref_biuro[r] - pref_biuro[l-1];
}

constexpr int wolne(int l, int r) {
    if (l > r) return 0;
    return (r-l+1) - zdalne(l,r) - biuro(l,r);
}

int spr_wyn(int tam=-1, int powrot=-1) {
    if (tam == -1 && powrot == -1) {
        if (biuro(1,n) > k) return -1;
        return wolne(1,n) + min(zdalne(1,n) + biuro(1,n), k);
    }

    /*
     * [1, tam-1]           -> w domu
     * [tam, tam+t-1]       -> droga
     * [tam+t, powrot-1]    -> w biurze
     * [powrot, powrot+t-1] -> droga
     * [powrot+t, n]        -> w domu
     */

    int przymusowo_pominiete = 0;
    int suma_wolne = 0;
    int suma_zdalne = 0;

    suma_wolne += wolne(1,tam-1);
    suma_zdalne += zdalne(1, tam-1);
    przymusowo_pominiete += biuro(1, tam-1);

    przymusowo_pominiete += zdalne(tam, tam+t-1) + biuro(tam, tam+t-1);

    przymusowo_pominiete += zdalne(powrot, powrot+t-1) + biuro(powrot, powrot+t-1);

    suma_wolne += wolne(powrot+t, n);
    suma_zdalne += zdalne(powrot+t, n);
    przymusowo_pominiete += biuro(powrot+t, n);

    if (przymusowo_pominiete > k) return -1;

    int do_pominiecia = k - przymusowo_pominiete;

    return suma_wolne + min(suma_zdalne, do_pominiecia);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> k >> t >> S;
    S = '$' + S;

    for (int i=1; i<=n; i++) {
        pref_zdalne[i] = pref_zdalne[i-1] + (S[i] == '2');
        pref_biuro[i] = pref_biuro[i-1] + (S[i] == '1');
    }

    int odp = spr_wyn();
//    cout << odp << '\n';

    for (int i=1; i<=n-t*2+1; i++) {
        for (int j=i+t; j<=n-t+1; j++) {
            odp = max(odp, spr_wyn(i,j));
//            cout << "[" << i << "," << i+t-1 << "]  [" << j << "," << j+t-1 << "]  " << odp << '\n';
        }
    }

    cout << odp << '\n';
}