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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <cstdio>
#include <algorithm>
using namespace std;

// Dla bezpieczeństwa przy n=8000 dajemy tablice minimalnie większe
static const int MAXN = 8000 + 5;

// Słowo z obowiązkami
char s[MAXN];

// Prefix-sumy dla '1', '2', '3'
int ps1[MAXN], ps2[MAXN], ps3[MAXN];

// Pomocniczy makro do pobierania liczby znaków danej kategorii w przedziale [l..r]
#define GET_COUNT(ps, l, r) ( ((l) <= (r)) ? ((ps)[(r)] - (ps)[(l)-1]) : 0 )

int main(){
    int n, k, t;
    scanf("%d %d %d", &n, &k, &t);

    scanf("%s", s+1); 
    // Wczytujemy do s[1..n], żeby indeksowanie było 1‑bazowe
    // (s[0] niewykorzystane;  s[1] to pierwszy znak)

    // Obliczamy prefix-sumy
    // ps1[i] = liczba wystąpień '1' na przedziale [1..i], itd.
    for(int i = 1; i <= n; i++){
        ps1[i] = ps1[i-1];
        ps2[i] = ps2[i-1];
        ps3[i] = ps3[i-1];
        if(s[i] == '1') ps1[i]++;
        if(s[i] == '2') ps2[i]++;
        if(s[i] == '3') ps3[i]++;
    }

    // Zliczamy całkowitą liczbę '1', '2', '3'
    int total1 = ps1[n];
    int total2 = ps2[n];
    int total3 = ps3[n];

    // best - wynik maksymalny (liczba godzin na zadania)
    long long best = -1; 

    // ---------------------------------------------------
    // Przypadek 1: Bajtazar nie jedzie do biura w ogóle
    // ---------------------------------------------------
    {
        // Wszystkie '1' w domu są opuszczone -> forcedSkip_noOffice = total1
        int forcedSkip_noOffice = total1;
        if(forcedSkip_noOffice <= k){
            // tasksBase = liczba '3' + liczba '1'
            long long tasksBase_noOffice = (long long)total3 + total1;
            // Liczba zdalnych '2' w domu, które ewentualnie możemy opuścić
            int optionalSkip2Home_noOffice = total2;
            long long canSkip2 = k - forcedSkip_noOffice;

            long long tasks_noOffice = tasksBase_noOffice 
                                     + min<long long>(optionalSkip2Home_noOffice, canSkip2);
            if(tasks_noOffice > best){
                best = tasks_noOffice;
            }
        }
    }

    // ---------------------------------------------------
    // Przypadek 2: Dokładnie jeden wyjazd do biura
    // ---------------------------------------------------
    // Wybieramy [x..y] - Bajtazar w biurze w tych godzinach
    // Droga "tam": [x-t .. x-1]
    // Droga "z powrotem": [y+1 .. y+t]
    // Warunek: x >= t+1,  y <= n-t,  oraz x <= y
    for(int x = t+1; x <= n - t; x++){
        for(int y = x; y <= n - t; y++){
            // Obliczamy liczbę '1','2' w czasie drogi (T),
            // bo w drodze każdy '1'/'2' jest opuszczany (forced skip).
            // Droga "tam": [x-t .. x-1]
            // Droga "z powrotem": [y+1 .. y+t]
            int count1_T = GET_COUNT(ps1, x-t, x-1) + GET_COUNT(ps1, y+1, y+t);
            int count2_T = GET_COUNT(ps2, x-t, x-1) + GET_COUNT(ps2, y+1, y+t);

            // W biurze [x..y] - tam nie ma skipów, bo można odbyć spotkania.
            int count1_O = GET_COUNT(ps1, x, y);
            int count2_O = GET_COUNT(ps2, x, y);
            // (count3_O nie jest potrzebne do skipów ani do zadań)

            // W domu H = całość - T - O
            // Zliczamy '1','2','3' w H poprzez odjęcie od total.
            int count1_H = total1 - (count1_T + count1_O);
            int count2_H = total2 - (count2_T + count2_O);
            // Możemy również potrzebować count3_H
            int count3_T = GET_COUNT(ps3, x-t, x-1) + GET_COUNT(ps3, y+1, y+t);
            int count3_O = GET_COUNT(ps3, x, y);
            int count3_H = total3 - (count3_T + count3_O);

            // forcedSkip = (wszystkie '1' i '2' w drodze) + (wszystkie '1' w domu)
            int forcedSkip = (count1_T + count2_T) + count1_H;
            if(forcedSkip > k){
                // Zbyt wiele wymuszonych opuszczeń, pomijamy
                continue;
            }

            // tasksBase = liczba '3' w domu + liczba '1' w domu
            // bo '1' w domu też daje 1 godzinę na zadania (choć wymusza skip)
            long long tasksBase = (long long)count3_H + count1_H;

            // optionalSkip2Home = liczba '2' w domu
            // Każde takie '2' możemy albo uczestniczyć, albo pominąć (+1 do skip, +1 do zadań)
            int optionalSkip2Home = count2_H;

            long long canSkip2 = k - forcedSkip; 
            long long tasks = tasksBase + min<long long>(optionalSkip2Home, canSkip2);

            if(tasks > best){
                best = tasks;
            }
        }
    }

    // Jeśli best nadal -1, to znaczy, że nie ma planu mieszczącego się w limicie k
    if(best < 0){
        printf("-1\n");
    } else {
        printf("%lld\n", best);
    }

    return 0;
}