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

int n, k, t;
string planS;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> t;
    cin >> planS;

    vector<int> workPrefSum(n + 1);
    workPrefSum[0] = 0;

    vector<int> hostPrefSum(n + 1);
    hostPrefSum[0] = 0;

    vector<int> programPrefSum(n + 1);
    programPrefSum[0] = 0;
    for(int i = 0; i < n; i++)
    {
        workPrefSum[i + 1] = workPrefSum[i] + ((planS[i] == '1'));
        hostPrefSum[i + 1] = hostPrefSum[i] + ((planS[i] == '2'));
        programPrefSum[i + 1] = programPrefSum[i] + ((planS[i] == '3'));
    }
    /* for(int i = 0; i <= n; i++)
    {
        cout << workPrefSum[i] << ' ';
    }
    cout << '\n';
    for(int i = 0; i <= n; i++)
    {
        cout << hostPrefSum[i] << ' ';
    }
    cout << '\n';
    for(int i = 0; i <= n; i++)
    {
        cout << programPrefSum[i] << ' ';
    }
    cout << '\n';
    cout << '\n';
    for(int i = 0; i < n; i++)
    {
        cout << i << ' ';
    }
    cout << '\n';
    for(int i = 1; i <= n; i++)
    {
        cout << i << ' ';
    }
    cout << '\n';
    for(int i = 0; i < n; i++)
    {
        cout << planS[i] << ' ';
    }
    cout << '\n'; */

    int result = -1;
    int skipped = workPrefSum[n];
    //cout << skipped << '\n';
    if(skipped <= k)
    {
        //nie musimy ani razu jechac do pracy
        int currProgram = skipped + programPrefSum[n] + min(k - skipped, hostPrefSum[n]);
        cout << currProgram;
        return 0;
    }

    //od 1 do n
    //workSum[mid] - workSum[mid - lenght]

    //jednak trzeba troche popracowac ;(
    int r = n + 1;
    while((r - (t * 2) - 2) >= 0)
    {
        int mid = r - t; //przed mid
        for(int lenght = 1; mid - lenght - (t + 1) >= 0; lenght++)
        {
            //mid - 1 = ostatnia godzina w pracy
            int notSkipped = workPrefSum[mid - 1] - workPrefSum[mid - 1 - lenght];
            int newSkipped = (hostPrefSum[r - 1] - hostPrefSum[mid - 1]) + (hostPrefSum[mid - 1 - lenght] - hostPrefSum[mid - 1 - lenght - t]);

            int currSkipped = skipped - notSkipped + newSkipped;
            if(currSkipped <= k)
            {
                //dodaj jeszcze te skipniete godziny pracy oraz ile sie da godzin online
                //reszte probojemy dobic na zdalnych jak zostaly nam jeszcze spotkania mozliwe do opuszczenia
                int programHours = programPrefSum[mid - 1 - lenght - t] + (programPrefSum[n] - programPrefSum[r - 1]);
                programHours += workPrefSum[mid - 1 - lenght - t] + (workPrefSum[n] - workPrefSum[r - 1]);
                //jak juz je skipnelismy to programujmy :D
                programHours += min(k - currSkipped, hostPrefSum[mid - 1 - lenght - t] + (hostPrefSum[n] - hostPrefSum[r - 1]));
                
                result = max(result, programHours);
            }
        }
        r--;
    }
    cout << result << '\n';

    //trzeba dodac do not skipped te co sa w pracy oraz odjac '2' gdy przejezdzam

    //sum od r - t do r
    return 0;
}