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+\mathrm{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 realization

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 realization

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)