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
|
Dushyant Singh:
2015-10-06 11:22:01
Weak test cases. One of my AC code gives 10 for first output. |
|
theweblover007:
2015-10-05 12:31:14
The algorithm behind this is kadane's algorithm, no you dont need to learn it, its very intuitive. |
|
shshnk28:
2015-09-28 15:19:07
some times the difference between tle and ac could be just changing the language from Python to c++. With the same logic. |
|
snehil10111995:
2015-09-25 16:51:03
No algo. O(n). :) |
|
rohit gajawada:
2015-09-24 11:47:21
whats up raghu
|
|
topke:
2015-09-03 20:29:11
There is nothing to memoize here. Solution is O(n) , you don't need any algorithm to solve this one. |
|
swapnil1996:
2015-08-22 09:23:58
Nice problem.... |
|
Mohammad Nasirifar:
2015-08-13 15:40:06
AC O(nlg(n)) :D |
|
ROHIT Kumar:
2015-08-11 09:10:27
thnks for the test cases @abeer khan and @ridhi
|
|
Anurag Sharma:
2015-08-01 08:45:44
ac after lot more troubles.... finally did troubleshooting Last edit: 2015-08-11 09:11:09 |
| 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