| Submit | All submissions | Best solutions | Back to list |
HOTELS - Hotels Along the Croatian Coast |
There are N hotels along the beautiful Adriatic coast. Each hotel has its value in Euros.
Sroljo has won M Euros on the lottery. Now he wants to buy a sequence of consecutive hotels, such that the sum of the values of these consecutive hotels is as great as possible - but not greater than M.
You are to calculate this greatest possible total value.
Input
In the first line of the input there are integers N and M (1 ≤ N ≤ 300 000, 1 ≤ M < 231).
In the next line there are N natural numbers less than 106, representing the hotel values in the order they lie along the coast.
Output
Print the required number (it will be greater than 0 in all of the test data).
Example
input5 12 2 1 3 4 5output 12 |
 |
input4 9 7 3 5 6output 8 |
| Added by: | Adrian Satja Kurdija |
| Date: | 2011-10-30 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | that would be me |
hide comments
|
||||||||||||||
|
2020-06-23 11:08:51
Spoiler: can be done using Binary search and also by sliding window. hint:use prefix sums for binary search method and you can use dequeue for sliding window. I personally learnt a lot from this question. |
||||||||||||||
|
2020-06-18 19:37:23
can anyone provide binary solution code... |
||||||||||||||
|
2020-04-14 20:16:02
Ac in one go :p |
||||||||||||||
|
2020-04-08 11:32:55
good question Last edit: 2020-04-08 11:35:18 |
||||||||||||||
|
2020-01-29 21:57:30
The wrong Solution got AC! Realized while solving ALIEN. |
||||||||||||||
|
2019-12-21 12:30:04
How can this problem be done using Binary Search ? |
||||||||||||||
|
2019-09-26 22:16:57
weak test cases my wrong sub. got AC. |
||||||||||||||
|
2019-08-14 01:28:52
How to use binary search on this problem? :):) Last edit: 2019-08-14 06:55:45 |
||||||||||||||
|
2019-07-23 23:31:06
i dont know how to do with sliding window. Did it easily with binary search AC in one go :) Last edit: 2019-07-23 23:31:24 |
||||||||||||||
|
2019-06-28 11:09:39
AC in 2 go xD |
||||||||||||||
RSS