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
|
nilabja16180:
2017-02-28 09:41:40
AC in ONE GO!!!
|
|
narutohokage_1:
2017-02-03 20:18:56
No searching on google for a algorithm , instead think and you will get one , was getting WA Because was adding sum again in each cycle , please see that you can use previous sum of hotel price , instead of calculating it again from scratch in each cycle. |
|
coder_hsnake:
2017-01-31 01:47:34
ALIENS = CODEFURY =HOTELS-(without considering number of hotels just focus on max sum)
|
|
epsilonalpha:
2017-01-29 17:06:00
A/C in one go! No algorithm needed, simple two pointer technique. :) |
|
hasan356:
2016-12-30 07:53:58
used deque!! |
|
kira28:
2016-12-16 21:42:46
try this->
|
|
davidgalehouse:
2016-09-21 05:48:40
Thought it was a little annoying dealing with single hotels that might cost more than the cost limit. Try:
|
|
akshayvenkat:
2016-09-15 17:25:31
Deque ftw :D |
|
Shantanu Banerjee:
2016-09-14 18:37:09
simple O(N). AC in one go! :) |
|
jasbir_220b2:
2016-08-17 12:19:04
O(n) solution.... simple but good one |
| 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