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
#include <bits/stdc++.h>
using namespace std;
#define int long long

constexpr int maxn = 1e6 + 7;
int n, k, d, strata, ans, res, suma, strataprzej, stratabiura, godzwdomu, pracawdomu;
string s;
int plan[maxn];
int pref1[maxn], pref2[maxn];

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> d >> s;
    for(int i = 0; i < n; i++){
        plan[i + 1] = s[i] - '0';
    }
    for(int i = 1; i <= n; i++){
        if(plan[i] == 1) pref1[i] = 1;
        pref1[i] += pref1[i - 1];
        if(plan[i] == 2) pref2[i]++;
        pref2[i] += pref2[i - 1];
    }
    for(int poc = 1; poc <= n; poc++){
        if(poc - d < 1) continue;
        for(int kon = poc; kon <= n; kon++){
            if(kon + d > n) break;
            strataprzej = pref1[poc - 1] - pref1[poc - d - 1] + pref2[poc - 1] - pref2[poc - d - 1] + pref1[kon + d] - pref1[kon] + pref2[kon + d] - pref2[kon];
            stratabiura = pref1[poc - d - 1] + pref1[n] - pref1[kon + d];
            strata = strataprzej + stratabiura;
            
            if(strata > k) continue;
            ans = 1;
            godzwdomu = poc - d - 1 + n - (kon + d);
            pracawdomu = pref2[poc - d - 1] + pref2[n] - (pref2[kon + d]);
            res = max(res, min(n, godzwdomu - pracawdomu + (k - strata)));
            // cout << res << " " << poc << " " << kon << " " << strataprzej << " " << stratabiura << '\n';
        }
    }
    // cout << res << '\n';
    if(pref1[n] <= k){
        ans = 1;
        res = max(res, n - pref2[n] + min(pref2[n], (k - pref1[n])));
    }
    if(!ans) res = -1;

    cout << res << '\n';
}