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
|
redcenturion:
2018-07-15 22:06:01
@sohailwiiierd you can try this
|
|
anikdutta10:
2018-07-15 20:20:55
Use Deque and Sliding Window!!! |
|
deepak4669:
2018-06-25 19:00:23
Use Fast I/O in java. |
|
captaindavinci:
2018-06-11 19:01:42
you could also use a deque here.
|
|
vivek_dwivedi:
2018-05-26 02:54:10
AC in one go ;) 0.03 sec no idea what sliding window is ..
|
|
a161112225:
2018-05-11 13:04:59
this is my 50'th
|
|
sohailwiiierd:
2018-03-30 20:59:21
O(N) solution but my time is 0.16sec. How to get 0.00 ??? Give me some hint . |
|
imkiller:
2018-03-19 19:05:08
Codes of 15 lines in cpp using SlidingWindow .
|
|
puneethnaik:
2018-02-13 13:32:38
prefix sum + upper_bound(binary search) did it for me.best of luck for others. |
|
satyampnc:
2018-01-11 06:46:06
sliding window... ac in 1 go :) 50th
|
| 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