10682. Отели на хорватском побережье

Вдоль прекрасного Адриатического побережья расположено n отелей. Каждый отель имеет свою стоимость в евро.

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

Вы должны рассчитать эту максимально возможную общую стоимость.

Вход. В первой строке заданы два целых числа n и m (1 ≤ n ≤ 300000, 1 ≤ m < 2³¹). В следующей строке заданы n натуральных чисел меньших 10⁶, представляющих стоимости отелей в том порядке, в котором они расположены вдоль побережья.

Выход. Выведите искомую максимальную стоимость (оно будет больше 0 во всех тестах).

Пример входа	Пример выхода
5 12 2 1 3 4 5	12

РЕШЕНИЕ

два указателя

Анализ алгоритма

Стоимости отелей занесем в массив a. Интервал [i … j] будем называть хорошим, если сумма стоимостей отелей на нем не больше m.

Реализуем скользящее окно при помощи двух индексов i и j и будем его поддерживать так, чтобы текущий рассматриваемый интервал [i … j] был хорошим. Пусть s – сумма стоимостей отелей на интервале [i … j]. Если s + a[j + 1] ≤ m, то расширяем текущий интервал до a[i … j + 1]. Иначе сокращаем его до a[i + 1 … j]. Находим максимум среди стоимостей всех рассматриваемых хороших интервалов.

Пример

Рассмотрим движение указателей для приведенного примера.

1. i = 0, j движется вперед пока сумма чисел на интервале [i … j] не больше m = 12. Остановимся на интервале [0 … 3], так как на нем сумма равна 10, а на интервале [0 … 4] сумма равна 15.

2. i = 1, j подвинуть вперед не можем так как сумма на интервале [1 … 4] равна 13.

3. i = 2, j двигаем вперед до интервала [2 … 4].

Максимальное значение среди всех хороших интервалов равно 12 и достигается на интервале [2 … 4].

Реализация алгоритма

Читаем входные данные.

scanf("%d %lld", &n, &m);

Инициализируем переменные:

· в res вычисляется максимальная стоимость среди стоимостей всех обрабатываемых хороших интервалов;

· в s поддерживается сумма чисел на текущем интервале [i … j]. Все числа текущего интервала [i … j] содержатся в очереди q;

s = res = 0;

Последовательно обрабатываем стоимости отелей.

for (i = 0; i < n; i++)

{

Читаем и добавляем стоимость val текущего отеля в очередь.

scanf("%d", &val);

q.push(val);

Обновляем сумму s на интервале. Все элементы текущего интервала находятся в очереди q.

s += val;

Если сумма чисел на текущем интервале больше s, то удаляем элементы с начала интервала.

while (s > m)

{

s -= q.front();

q.pop();

}

Вычисляем максимальное значение res среди сумм элементов допустимых интервалов (стоимость отелей на которых не превышает m).

if (s > res) res = s;

}

Выводим ответ.

printf("%lld\n", res);

Python реализация

Объявим очередь.

from collections import deque

q = deque()

Читаем входные данные.

n, m = map(int, input().split())

costs = list(map(int, input().split()))

Инициализируем переменные:

· в res вычисляется максимальная стоимость среди стоимостей всех обрабатываемых хороших интервалов;

· в s поддерживается сумма чисел на текущем интервале [i … j]. Все числа текущего интервала [i … j] содержатся в очереди q;

res = s = 0

Последовательно обрабатываем стоимости отелей.

for val in costs:

Добавляем стоимость val текущего отеля в очередь.

q.append(val)

Обновляем сумму s на интервале. Все элементы текущего интервала находятся в очереди q.

s += val

Если сумма чисел на текущем интервале больше s, то удаляем элементы с начала интервала.

while s > m:

s -= q.popleft()

Вычисляем максимальное значение res среди сумм элементов допустимых интервалов (стоимость отелей на которых не превышает m).

if s > res: res = s

Выводим ответ.

print(res)