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
//Jakub Nowak University of Wroclaw
#include<bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0);
#define int long long
#define vi vector<int>
#define pb push_back
const int inf = (int)(1e18)+7;

void solve() {
    int n, k, t;
    cin >> n >> k >> t;
    string Schedule;
    cin >> Schedule;

    function<bool(char&)> working = [&](char &hour) {return hour == '1' || hour == '2';};

    int allworkinghours = 0;
    for(auto &hour : Schedule) allworkinghours += working(hour);

    int minwork = max((int)(0), allworkinghours - k);

    /*function<bool(int&, int&)> enoughwork(int &i, int &j) {
        return (ile2(0, i) + ile2(i+t, j-1) + ile1(i+t, j-1) + ile2(j+t, n-1)) >= k;
    };*/

    vi Pre1(n), Pre2(n);
    for(int i=0; i<n; i++) {
        Pre1[i] = (int)(Schedule[i]=='1') + (int)(i!=0 ? Pre1[i-1] : 0);
        Pre2[i] = (int)(Schedule[i]=='2') + (int)(i!=0 ? Pre2[i-1] : 0);
    }

    function<int(int, int)> ile1 = [&](int a, int b) {
        return Pre1[b] - (a!=0 ? Pre1[a-1] : 0);
    };
    
    function<int(int, int)> ile2 = [&](int a, int b) {
        if(a>b) return (int)(0);
        return Pre2[b] - (a!=0 ? Pre2[a-1] : 0);
    };

    int ans = -1;
    if(ile2(0, n-1) >= minwork) {ans = n - minwork;}

    for(int i=0; i+t-1 < n; i++) for(int j=i+t; j+t-1 < n; j++) {
        int reszta = max(minwork - (ile2(i+t, j-1) + ile1(i+t, j-1)), (int)(0));
        //cout << "Work: (" << i << ", " << j << ") Reszta: " << reszta << "\n";
        if(reszta > (ile2(0, i) + ile2(j+t, n-1))) continue;
        ans = max(ans, i + (n-1) - (j + t - 1) - reszta);
    }

    cout << ans << "\n";
    /*cout << ile1(2, 3) << " " << ile2(2, 3) << "\n";
    for(int i=0; i<n; i++) cout << Pre1[i] << " ";
    cout << "\n";
    int i = 3;
    cout << (i!=0 ? Pre1[i-1] : 0) << " ";*/

    /*

    vi InHomePrefix(n), InHomeSufix(n);
    for(int i=0; i<n; i++) InHomePrefix[i] = (i != 0 ? InHomePrefix[i-1] : 0) + (Schedule[i] == '2');
    for(int i=n-1; i>=0; i--) InHomeSufix[i] = (i != n-1 ? InHomePrefix[i+1] : 0) + (Schedule[i] == '2');

    vi InWorkPrefix(n), InWorkSufix(n);
    for(int i=0; i<n; i++) InWorkPrefix[i] = max((i >= 1 ? InWorkPrefix[i-1] : 0) + working(Schedule[i]), (i >= t ? InHomePrefix[i-t] : (i == t ? 0 : -inf)));
    for(int i=n-1; i>=0; i--) InWorkSufix[i] = max((i < n-1 ? InWorkSufix[i+1] : 0) + working(Schedule[i]), (i < n-t ? InHomeSufix[i+t] : (i == n-1-t ? 0 : -inf)));
    */

    /*function<int(vi&, int)> get = [&](vi &tab, int index) {
        if(index == -1 || index == tab.size()) return (int)(0);
        if(index < -1 || index > tab.size()) return (int)(-inf);
        return (int)(tab[index]);
    };
    
    //Version2
    vi InHomePrefix(n), InHomeSufix(n);
    for(int i=0; i<n; i++) InHomePrefix[i] = get(InHomePrefix, i-1) + (Schedule[i] == '2');
    for(int i=n-1; i>=0; i--) InHomeSufix[i] = get(InHomeSufix, i+1) + (Schedule[i] == '2');

    vi InWorkPrefix(n), InWorkSufix(n);
    for(int i=0; i<n; i++) InWorkPrefix[i] = max(get(InWorkPrefix, i-1) + working(Schedule[i]), get(InHomePrefix, i-t));
    for(int i=n-1; i>=0; i--) InWorkSufix[i] = max(get(InWorkSufix, i+1) + working(Schedule[i]), get(InHomeSufix, i+t));

    function<bool(int)> enoughwork = [&](int hoursworked) {
        return hoursworked >= minwork;
    };

    int ans = enoughwork(InHomePrefix[n-1]) ? n - minwork : -1;
    for(int i=0; i<n; i++) ans = max(ans, enoughwork(get(InWorkPrefix, i) + get(InWorkSufix, i+1)) ? n - minwork - 2*t : -1);

    cout << ans << "\n";
    cout << allworkinghours << "\n";
    cout << enoughwork(InHomePrefix[n-1]) << "\n";

    for(int i=0; i<n; i++) cout << get(InWorkPrefix, i) /*+ get(InWorkSufix, i+1) << " ";*/
}

signed main() {
    boost
    solve();
}