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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
// PA2025 runda 1B -  https://sio2.mimuw.edu.pl/c/pa-2025-1/p/pra/
//-std=c++20
#include<iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include<list>
#include<cstddef>

#define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))
using namespace std;

u_int32_t n, k, t; // segmenty, ograniczenia, czas podróży
vector<char> desc;


/*
 * 1 - biuro
 * 2 - zdalne
 * 3 - wolne
 */

struct Tram {
    u_int32_t index{0};
    u_int32_t tram_skip{0};
    u_int32_t skip{0};
    u_int32_t points{0};
    int16_t direction{1};
    u_int32_t remotes{0};

    void move() {
        switch (desc[index]) {
            case '1':
                skip++;
                tram_skip--;
                points++;
                break;
            case '2':
                tram_skip--;
                remotes++;
                break;
            case '3':
                points++;
                break;
        }
        switch (desc[index + direction * t]) {
            case '1':
            case '2':
                tram_skip++;
                break;
            case '3':
                break;
        }
        index += direction;
    }

    u_int32_t all_skip() const {
        return skip + tram_skip;
    }

    void init() {
        for (int a = 0; a < t; a++) {
            switch (desc[index + direction * a]) {
                case '1':
                case '2':
                    tram_skip++;
                    break;
                case '3':
                    break;
            }
        }
    }
};

bool valid(const Tram &a, const Tram &b) {
    return (a.all_skip() + b.all_skip()) <= k;
}

int32_t score(const Tram &a, const Tram &b) {
    if (valid(a, b)) {
        auto hard_points = a.points + b.points;
        auto available = k - (a.all_skip() + b.all_skip());
        return hard_points + MIN(available, a.remotes + b.remotes);
    } else {
        return -1;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k >> t;
    desc.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> desc[i];
    }

    u_int32_t offices{0};
    u_int32_t remotes{0};
    u_int32_t slots{0};
    // czy w ogole musi jechac?
    for (char &c: desc) {
        if (c == '1') {
            offices++;
        } else if (c == '2') {
            remotes++;
        } else {
            slots++;
        }
    }
    if (offices <= k) {
        u_int32_t x{0};
        x += slots;
        x += offices;
        x += MIN(remotes, k - offices);
        cout << x;
        return 0;
    }


    // przygotuj tramwaje
    Tram left{0, 0, 0, 0, 1};
    Tram right_end{n - 1, 0, 0, 0, -1};
    left.init();
    right_end.init();

    // iterujemy
    int32_t best_points{-1};
    int32_t points{-1};
    while (left.skip <= k) {
        Tram right = right_end;
        points = score(left, right);
        //cerr << '\n' << left.index << ": " << points << " ";
        best_points = MAX(best_points, points);
        while ((left.skip + right.skip <= k) && (left.index + t < right.index - t)) {
            right.move();
            points = score(left, right);
            //cerr << points << " ";
            best_points = MAX(best_points, points);
        }
        // na koniec przesuń lewy
        left.move();
    }
    cout << best_points;
}