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
// Mateusz Kussowski
// PA 2025 day 1 B praca

#include <iostream>
#include <vector>
#include <climits>
#include <iomanip>
using namespace std;

const char on_site = '1';
const char remote = '2';
const char free_time = '3';

inline void inc(int& ptr, int val){
    ptr = max(ptr, val);
}

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

    int n, k, t;
    cin >> n >> k >> t;

    char types[n+1];
    types[0] = -1;
    for(int i = 1; i <= n; ++i){
        cin >> types[i];
    }

    int on_site_pre[n+1], remote_pre[n+1], free_time_pre[n+1];
    on_site_pre[0] = remote_pre[0] = free_time_pre[0] = 0;
    for(int i = 1; i <= n; ++i){
        on_site_pre[i] = on_site_pre[i-1] + (types[i] == on_site);
        remote_pre[i] = remote_pre[i-1] + (types[i] == remote);
        free_time_pre[i] = free_time_pre[i-1] + (types[i] == free_time);
    }

    int best = -1;
    
    //consider not going on site
    if(on_site_pre[n] <= k){
        inc(best, n - max(on_site_pre[n] + remote_pre[n] - k, 0));
    }

    //consider going on site
    for(int work_begin = t; work_begin <= n - t; ++work_begin){
        for(int work_end = work_begin + 1; work_end <= n - t; ++work_end){
            // cout << work_begin << " " << work_end << ": \n";

            int remaining_time = n - (work_end - work_begin);
            int remaining_on_site = on_site_pre[work_begin] + on_site_pre[n] - on_site_pre[work_end];
            int remaining_remote = remote_pre[work_begin] + remote_pre[n] - remote_pre[work_end];

            // cout << "remaining_time: " << remaining_time << endl;
            // cout << "remaining_on_site: " << remaining_on_site << endl;
            // cout << "remaining_remote: " << remaining_remote << endl;

            //wasted for travel
            int wasted_on_site = on_site_pre[work_begin] - on_site_pre[work_begin - t] + on_site_pre[work_end + t] - on_site_pre[work_end];
            int wasted_remote = remote_pre[work_begin] - remote_pre[work_begin - t] + remote_pre[work_end + t] - remote_pre[work_end];

            // cout << "wasted_on_site: " << wasted_on_site << endl;
            // cout << "wasted_remote: " << wasted_remote << endl;

            int remaining_k = k - wasted_on_site - wasted_remote;

            // cout << "remaining_k: " << remaining_k << endl;

            if(remaining_k < 0) continue;

            // cout << "continuing\n";

            remaining_on_site -= wasted_on_site;
            remaining_remote -= wasted_remote;
            remaining_time -= 2 * t;

            if(remaining_k < remaining_on_site) continue;

            remaining_k -= remaining_on_site;
            remaining_on_site = 0;

            // cout << "remaining_on_site: " << remaining_on_site << endl;
            // cout << "remaining_remote: " << remaining_remote << endl;
            // cout << "remaining_time: " << remaining_time << endl;

            int max_free_time = remaining_time - max(0, remaining_on_site + remaining_remote - remaining_k);

            // cout << "max_free_time: " << max_free_time << endl;

            inc(best, max_free_time);
        }
    }

    cout << best << endl;
}