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 |
hide comments
|
guru_shreyansh:
2021-09-14 11:37:06
Solved this question with both Sliding Window & Binary Search approach. BUT...
|
|
Waseem Ahmed:
2021-06-26 21:27:19
Ac in one go. Super simple sliding window (two pointer) problem. |
|
princeoftime05:
2021-02-28 04:57:04
AC in one go with binary search UwU |
|
rishikey:
2021-02-26 13:23:54
not an interesting problem.. |
|
deerawat:
2021-01-03 10:41:52
easy one |
|
shreyas_07:
2020-12-08 10:52:33
could have also solved using DP if constraints were small. |
|
varuntumbe:
2020-10-20 08:13:13
beautiful algorithm. creative use of two pointers. |
|
gnomegeek:
2020-08-14 09:12:05
AC in one go. Basic sliding window problem. |
|
justrifat:
2020-07-27 21:32:32
AC in one go :)
|
|
kumar_anubhav:
2020-06-30 13:59:19
AC in one Go!! |
| 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 |
RSS