1. Идея

Нужно найти минимальный день d, когда можно собрать хотя бы m букетов.

Каждый букет должен состоять из k подряд стоящих цветов, которые уже распустились к дню d, то есть для них должно выполняться a_i <= d. Один цветок нельзя использовать в двух букетах.

Главевая идея задачи — сделать двоичный поиск по ответу:

• если в день d можно собрать m букетов,
• то и в любой день больше d тоже можно, потому что распустившихся цветов станет не меньше.

Значит, ответ обладает монотонностью, а это и есть сигнал к двоичному поиску.

2. Наблюдения

Наблюдение 1. Иногда ответ сразу -1

Если нужно m букетов по k цветов, то всего потребуется m * k цветов.

Если m * k > n, то даже теоретически не хватает цветов, независимо от дней распускания. Тогда ответ -1.

Наблюдение 2. Как проверить фиксированный день

Пусть дан некоторый день day. Нужно понять, можно ли к этому дню собрать хотя бы m букетов.

Идём слева направо по массиву:

• если a[i] <= day, этот цветок уже распустился, увеличиваем длину текущего подряд идущего участка;
• если a[i] > day, участок обрывается, счётчик подряд идущих цветов сбрасывается в 0.

Как только длина текущего участка стала равна k, можно собрать один букет:

• увеличиваем число букетов;
• сбрасываем текущую длину в 0, потому что использованные цветы больше нельзя брать повторно.

Это жадно и правильно: как только есть готовые k подряд, выгодно сразу использовать их в букет.

Наблюдение 3. Монотонность

Если к дню day можно собрать нужное число букетов, то к любому дню day2 >= day тоже можно.

Причина простая: множество распустившихся цветов только расширяется.

Значит, существует некоторый минимальный день, начиная с которого ответ становится истинным. Его и ищем бинарным поиском.

3. Алгоритм

1. Считать n, m, k и массив a.
2. Если m * k > n, вывести -1.
3. Иначе будем искать ответ бинарным поиском по дню:
   • left = min(a)
   • right = max(a)
4. Для середины mid проверяем, можно ли собрать хотя бы m букетов к дню mid.
5. Если можно, запоминаем mid как текущий ответ и пробуем уменьшить день: right = mid - 1.
6. Если нельзя, нужно больше времени: left = mid + 1.
7. После завершения двоичного поиска вывести найденный ответ.

4. Почему это работает

Докажем корректность по частям.

Проверка can_make(day)

Рассмотрим процедуру проверки для фиксированного дня day.

Она просматривает массив слева направо и считает длину текущего блока из цветов, для которых a_i <= day.

• Если встретился ещё один распустившийся цветок, увеличиваем cnt.
• Если встретился нераспустившийся, текущий подряд идущий блок закончился, значит cnt надо сбросить.
• Как только cnt == k, из этих k подряд идущих цветов можно собрать один букет.
• После этого cnt = 0, потому что эти цветы уже использованы и не могут входить в другой букет.

Так мы считаем максимальное число непересекающихся букетов, которые можно собрать из подряд идущих распустившихся цветов.

Почему жадное действие верно?
Потому что любой букет обязан занимать ровно k подряд идущих цветов. Если у нас уже есть k подряд распустившихся цветов, откладывать их использование нет смысла: это не поможет собрать больше букетов позже, а только сдвинет границы. Разбиение каждого подходящего подряд идущего блока длины L на L // k букетов — оптимально.

Значит, can_make(day) действительно правильно отвечает, можно ли к этому дню собрать хотя бы m букетов.

Корректность двоичного поиска

Пусть f(day) — это утверждение «к дню day можно собрать хотя бы m букетов».

Мы уже заметили, что f(day) монотонна:

• если f(day) истинно,
• то f(day + 1) тоже истинно.

Тогда существует минимальный день, для которого f(day) становится истинным. Стандартный двоичный поиск по монотонной функции находит именно этот минимальный день:

• если f(mid) истинно, ответ не больше mid, идём влево;
• если ложно, ответ больше mid, идём вправо.

Следовательно, алгоритм находит минимальный возможный день.

5. Сложность

Пусть R = max(a) - min(a).

• Одна проверка can_make(day) работает за O(n).
• Двоичный поиск делает O(log R) проверок.

Итоговая сложность: O(n log R).

По памяти:

• используется только массив цветов и несколько переменных,
• значит, память O(n).

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool can_make(const vector<int>& a, int m, int k, int day) {
    int bouquets = 0;
    int cnt = 0;

    for (int x : a) {
        if (x <= day) {
            cnt++;
            if (cnt == k) {
                bouquets++;
                cnt = 0;
                if (bouquets >= m) {
                    return true;
                }
            }
        } else {
            cnt = 0;
        }
    }

    return bouquets >= m;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (1LL * m * k > n) {
        cout << -1 << '\n';
        return 0;
    }

    int left = *min_element(a.begin(), a.end());
    int right = *max_element(a.begin(), a.end());
    int answer = right;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (can_make(a, m, k, mid)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << answer << '\n';
    return 0;
}

7. Код на Python 3

n, m, k = map(int, input().split())
a = list(map(int, input().split()))

if m * k > n:
    print(-1)
else:
    def can_make(day):
        bouquets = 0
        cnt = 0
        for x in a:
            if x <= day:
                cnt += 1
                if cnt == k:
                    bouquets += 1
                    cnt = 0
                    if bouquets >= m:
                        return True
            else:
                cnt = 0
        return bouquets >= m

    left = min(a)
    right = max(a)
    answer = right

    while left <= right:
        mid = (left + right) // 2
        if can_make(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    print(answer)