Лучшая серия по среднему баллу

В электронном дневнике за каждый день стоит число — сколько баллов вы набрали в школьной игре.

Вы хотите выбрать подряд идущую серию дней длиной не меньше K, чтобы средний балл за день был как можно больше. Чтобы не спорить про дроби, договорились считать «средний балл» в тысячных долях и округлять вниз.

То есть нужно найти максимальное значение

floor( (sum / len) * 1000 ),

где sum — сумма баллов на выбранном отрезке, len — его длина, и len >= K.

Важно: промежуточные суммы могут не влезать в 32-битный тип (как на ВсОШ), используйте 64-битную арифметику. В Python это уже поддержано.

Формат ввода

• Первая строка: два целых числа N и K (1 <= K <= N <= 3000).
• Вторая строка: N целых чисел a1, a2, ..., aN (0 <= ai <= 10000).

Формат вывода Выведите одно целое число: floor(max_avg * 1000), где max_avg — максимальное среднее значение по всем отрезкам длины не меньше K.

Ограничения

• 1 <= K <= N <= 50000
• 0 <= ai <= 10000
• Лимит времени: 1 секунда, память: 256 МБ.

Пример Ввод:

3 2
10 0 10

Вывод:

6666

Пояснение: лучший отрезок — все 3 дня, среднее 20/3 = 6.666..., в тысячных это 6666.666..., после округления вниз получаем 6666.

Ключевая мысль: вместо прямого перебора всех отрезков (их много) можно угадывать ответ x (в тысячных) и быстро проверять, бывает ли среднее хотя бы такое.

Если хотим среднее на отрезке sum/len >= x/1000, то перенесём всё в целые числа: sum*1000 - x*len >= 0. Это равносильно тому, что на некотором отрезке сумма значений b[i] = a[i]*1000 - x неотрицательна.

Почему работает бинарный поиск: если для какого-то x существует подходящий отрезок, то для меньших x тоже существует (условие становится легче). Значит, проверка монотонна.

План решения:

• Будем бинарно искать x на диапазоне 0..10000*1000.
• Для фиксированного x строим префиксные суммы pref[i] = pref[i-1] + (a[i]*1000 - x).
• Нужно проверить, есть ли l<r с r-l >= K и pref[r] - pref[l] >= 0.
• Идём r от K до N, поддерживаем минимум pref[l] среди l <= r-K и проверяем pref[r] - min_pref >= 0.
• Если проверка успешна — двигаем бинарный поиск вверх, иначе вниз.

Сложность: проверка за O(N), бинарный поиск по x даёт O(N * log(10000*1000)), при N<=3000 легко проходит.

Частая ошибка: обновлять min_pref не тем индексом — минимум нужно брать только по pref[0..r-K], иначе вы случайно разрешите отрезки короче K.