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
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

int main() {
    int godzin;
    int dozwolonychNieobecnosci;
    int czasPrzejazdu;
    int najwiecejZadan = -1;
    std::string obowiazki;

    std::cin >> godzin >> dozwolonychNieobecnosci >> czasPrzejazdu >> obowiazki;

    std::vector<int> spotkanWBiurze(godzin+1);
    std::vector<int> spotkanZdalnych(godzin+1);

    spotkanWBiurze[0] = 0;
    spotkanZdalnych[0] = 0;

    for (unsigned i = 1; i <= godzin; ++i) {
        spotkanWBiurze[i] = spotkanWBiurze[i-1];
        spotkanZdalnych[i] = spotkanZdalnych[i-1];
        if (obowiazki[i-1] == '1') {
            spotkanWBiurze[i]++;
        } else if (obowiazki[i-1] == '2') {
            spotkanZdalnych[i]++;
        }
    }

    // nie wyjeżdżanie do biura
    if (spotkanWBiurze[godzin] <= dozwolonychNieobecnosci) {
        int spotkan = spotkanZdalnych[godzin] + spotkanWBiurze[godzin];
        spotkan -= std::min(dozwolonychNieobecnosci, spotkan);
        najwiecejZadan = godzin - spotkan;
        std::cout << najwiecejZadan << std::endl;
        return 0;
    }

    for (unsigned wyjazdDoBiura = 0; wyjazdDoBiura <= (godzin-2*czasPrzejazdu-1); ++wyjazdDoBiura) {
        for (unsigned powrotDoDomu = (wyjazdDoBiura+czasPrzejazdu+1) ; powrotDoDomu <= (godzin-czasPrzejazdu); ++powrotDoDomu) {
            int nieobecnosci = 0;
            // spotkania w biurze poza biurem
            nieobecnosci += spotkanWBiurze[wyjazdDoBiura+czasPrzejazdu]; //
            nieobecnosci += spotkanWBiurze[godzin] - spotkanWBiurze[powrotDoDomu];
            // spotkania zdalne podczas jazdy
            nieobecnosci += spotkanZdalnych[wyjazdDoBiura+czasPrzejazdu] - spotkanZdalnych[wyjazdDoBiura];
            nieobecnosci += spotkanZdalnych[powrotDoDomu+czasPrzejazdu] - spotkanZdalnych[powrotDoDomu];
            //
            if (dozwolonychNieobecnosci < nieobecnosci) {
                continue;
            }
            int spotkaniaZdalneZDomu = spotkanZdalnych[wyjazdDoBiura];
            spotkaniaZdalneZDomu += spotkanZdalnych[godzin] - spotkanZdalnych[powrotDoDomu+czasPrzejazdu];
            int zadan =
                    + wyjazdDoBiura
                    + (godzin -  powrotDoDomu - czasPrzejazdu)
                    - spotkaniaZdalneZDomu
                    + std::min(spotkaniaZdalneZDomu, dozwolonychNieobecnosci-nieobecnosci)
            ;
            if (najwiecejZadan < zadan) {
                najwiecejZadan = zadan;
            }
        }
    }

    std::cout << najwiecejZadan << std::endl;
}