Готелі на хорватському узбережжі (Розбір)

Вартість готелів занесемо у масив $a$. Інтервал $[i...j]$ будемо називати хорошим, якщо сума вартостей готелів на ньому не більше $m$.

Реалізуємо ковзне вікно за допомогою двох індексів $i$ і $j$ та будемо його підтримувати так, щоб поточний розглянутий інтервал $[i...j]$ був хорошим. Нехай $s$ — сума вартостей готелів на інтервалі $[i...j]$. Якщо s + a[j + 1] \le m, то розширюємо поточний інтервал до a[i ... j + 1]. Інакше скорочуємо його до a[i + 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)