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
|
papan_97:
2016-04-16 08:49:45
after a few TLEs,,,finally came up with a O(n) solution X) |
|
constant_:
2016-03-16 14:29:27
helped to get back on track ;) |
|
a_b_c12345:
2016-02-04 11:31:22
do not search for any algo on google.. just do it by urself .. AC in 1 go...
|
|
nonushikhar:
2016-01-03 16:54:43
O(n) :) |
|
asshole:
2015-12-23 11:20:47
i think you should change the time limit so that it can be accepted in python too |
|
sharif ullah:
2015-10-19 11:29:39
modified version of KAdane's algorithm!!! |
|
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). :) |
| 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