Разбор

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

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

Пример

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

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

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

3. $i=2,j$ двигаем вперед до интервала $[\mathrm{2...4}]$.

Максимальное значение среди всех хороших интервалов равно $12$ и достигается на интервале $[\mathrm{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)