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
103
104
105
106
107
108
#include <bits/stdc++.h>

using namespace std;

vector<int> meetings1and2;
vector<int> meetings1;
//vector<int> options2and3;
vector<int> options2;

int count_meetings_stationary(int start_stationary, int start_come_back)
{
    return meetings1and2[start_come_back - 1] - meetings1and2[start_stationary - 1];
}

int count_remote_meetings(int start_travel, int come_back_end)
{
    return options2.back() - options2[come_back_end] + options2[start_travel - 1];
}

int count_coding_hours(int start_stationary, int start_come_back, int n, int k, int t)
{
    int meetings_stationary = count_meetings_stationary(start_stationary, start_come_back);

    int obligatory_meetings_left = meetings1and2.back() - k - meetings_stationary;
    obligatory_meetings_left = obligatory_meetings_left < 0 ? 0 : obligatory_meetings_left;

    int start_travel = start_stationary - t;
    int end_come_back = start_come_back + t - 1;

    int remote_possible_meetings = count_remote_meetings(start_travel, end_come_back);

    if(remote_possible_meetings < obligatory_meetings_left) { return -1; } // tu nawet nie chcemy wchodzic, optymalnie zeby ten if sie nie spelnil.. moze?

    return (start_travel - 1) + (n - end_come_back) - obligatory_meetings_left;
}

int main()
{
    char buffer[100], day[8010];
    int n, k, t;

    fgets(buffer, sizeof(buffer), stdin);
    sscanf(buffer, "%d %d %d", &n, &k, &t);

    fgets(day, n + 2, stdin);

    // czyli bajtazar moze pojechać, bedziemy rozwazac ten przypadek gdy sa jakies 1 w ciagu, prawdopodobnie gdy ilosc 1 < k

    // mini optymalizacja - bedziemy rozwazac te jazdy w których sa spotkania jakies we firmie - trzeba wyznaczyc kiedy jest sens rozwazac chociaz
    //
    // moze sie zastanowic kiedy wracac? i jechac, bo pojechac w sumie trzeba gdy jest za mało 2, czyli wiecej 1 niż k
    // czyli jak juz jechac to tak zeby byla sensowna ilosc 1

    // zauwazmy ze powinno byc wiecej spotkan podczas pracy jako 1 niz 2 podczas jazdy, bo inaczej to nie ma sensu.
    // zauwazmy ze podczas jazdy do i z biura nie moze byc wiecej spotkan niz k
    //

    // a -1 bedzie wtedy kiedy nie bedzie takich momentow przyjazdu i odjazu z biura ze zaliczy wystarczajaca ilosc spotkan
    // czyli tu sie moze przydac tablica z sumami prefiksowymi ile bylo dotychczas 1

    // czyli jak mamy okres w biurze to zliczamy 1 i 2 i na bazie tego wyliczamy ile w domu programuje i wynik dla tego sprawdzania jest liczba godzin w domu - pozostale spotkania

    meetings1and2.resize(n+1);
    meetings1.resize(n+1);
    //options2and3.resize(n+1);
    options2.resize(n+1);

    meetings1and2[0] = 0;
    meetings1[0] = 0;
    //options2and3[0] = 0;
    options2[0] = 0;

    for(int i=1; i<=n; i++)
    {
        meetings1and2[i] = meetings1and2[i-1] + (int)(day[i-1] < '3');
        meetings1[i] = meetings1[i-1] + (int)(day[i-1] == '1');
        //options2and3[i] = options2and3[i-1] + (int)(day[i-1] > '1');
        options2[i] = options2[i-1] + (int)(day[i-1] == '2');
    }


    //printf("%d\n", count_meetings_stationary(3, 6));
    //printf("%d\n", count_remote_meetings(1, 7));
    //printf("%d\n", count_coding_hours(3, 6, n, k, t));

    int result = n - max((meetings1and2.back() - k), 0); // przypadek gdy nie jedziemy do biura
    int current_result;

    if(meetings1.back() > k)
    {
        result = -1;
        for(int start=1; start<=n-t-t+1; start++)
        {
            for(int come_back=start+t+1; come_back<=n-t+1; come_back++)
            {
                current_result = count_coding_hours(start+t, come_back, n, k, t);

                //cout << current_result << " " << start+t << " " << come_back << endl;

                if(current_result > result) { result = current_result; }
            }
        }
    }

    printf("%d\n", result);

    return 0;
}