Hotels Along the Croatian Coast (Editorial)

Store the hotel costs in the $a$ array. We’ll call the interval $[i...j]$ good if the sum of hotel costs within it does not exceed $m$.

Let’s implement a sliding window using two indices $i$ and $j$, and maintain it so that the current interval $[i...j]$ is good. Let $s$ be the sum of hotel costs within the interval $[i...j]$. If s + a[j + 1] \le m, then expand the current interval to a[i ... j + 1]. Otherwise, shrink it to a[i + 1 ... j]. Find the maximum among the costs of all considered good intervals.

Example

Consider the movement of pointers for the given example.

1. When i = 0, j moves forward until the sum of numbers in the interval $[i...j]$ does not exceed m = 12. Stop at the interval $[\mathrm{0...3}]$ because the sum there is equal to $10$, while the sum in the interval $[\mathrm{0...4}]$ is equal to $15$.

2. When i = 1, we cannot move $j$ forward because the sum in the interval $[\mathrm{1...4}]$ is equal to $13$.

3. When i = 2 move $j$ forward to the interval $[\mathrm{2...4}]$.

The maximum value among all good intervals is equal to $12$ and is achieved in the interval $[\mathrm{2...4}]$.

Algorithm implementation

Read the input data.

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

Initialize the variables:

• in $res$, the maximum value among the costs of all processed good intervals is computed;

• in $s$, the sum of numbers in the current interval $[i...j]$ is maintained. All the numbers in the current interval $[i...j]$ are stored in the queue $q$;

s = res = 0;

Process the hotel costs sequentially.

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

Read and add the cost $val$ of the current hotel to the queue.

  scanf("%d", &val);
  q.push(val);

Update the sum $s$ within the interval. All elements of the current interval are stored in the queue $q$.

  s += val;

If the sum of numbers in the current interval exceeds $s$, we remove elements from the beginning of the interval.

  while (s > m)
  {
    s -= q.front();
    q.pop();
  }

Compute the maximum value $res$ among the sums of elements in good intervals (where the cost of hotels does not exceed $m$).

  if (s > res) res = s;
}

Print the answer.

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

Python implementation

Declare a queue.

from collections import deque
q = deque()

Read the input data.

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

Initialize the variables:

• in $res$, the maximum value among the costs of all processed good intervals is computed;

• in $s$, the sum of numbers in the current interval $[i...j]$ is maintained. All the numbers in the current interval $[i...j]$ are stored in the queue $q$;

res = s = 0

Process the hotel costs sequentially.

for val in costs:

Add the cost $val$ of the current hotel to the queue.

  q.append(val)

Update the sum $s$ within the interval. All elements of the current interval are stored in the queue $q$.

  s += val

If the sum of numbers in the current interval exceeds $s$, we remove elements from the beginning of the interval.

  while s > m:
    s -= q.popleft()

Compute the maximum value $res$ among the sums of elements in good intervals (where the cost of hotels does not exceed $m$).

  if s > res: res = s

Print the answer.

print(res)