10682. Hotels along the croatian coast

Along the beautiful Adriatic coast, there are n hotels. Each hotel has its cost in euros. Petr won m euros in the lottery. Now he wants to buy a sequence of consecutive hotels one after another so that the sum of the costs of these consecutive hotels is as large as possible, but does not exceed m. You need to calculate this maximum possible total cost.

Input. The first line contains two integers n and m (1 ≤ n ≤ 300000, 1 ≤ m < 2³¹). The next line contains n positive integers less than 10⁶, representing the costs of the hotels in the order they are located along the coast.

Output. Print the desired maximum cost (it will be greater than 0 in all tests).

Sample input	Sample output
5 12 2 1 3 4 5	12

SOLUTION

two pointers

Algorithm analysis

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] ≤ 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 [0 … 3] because the sum there is equal to 10, while the sum in the interval [0 ... 4] is equal to 15.

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

3. When i = 2, move j forward to the interval [2 … 4].

The maximum value among all good intervals is equal to 12 and is achieved in the interval [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)