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
|
shahayush457:
2019-06-18 20:38:17
It's easy !!! Binary search and sliding window both solutions are accepted... |
|
protyush:
2019-04-08 13:27:40
weak test cases |
|
suraj_13:
2019-03-21 17:11:17
Use sliding window, and a variable max to keep track of best solution |
|
f23505106:
2019-01-15 08:14:00
any one AC in python? |
|
yaseenmollik:
2018-12-22 08:23:02
Great use of Two Pointers |
|
markaman:
2018-12-08 07:10:02
LEARN SW CONCEPT THIS WILL HELP U ;) Last edit: 2018-12-08 07:13:06 |
|
inkretbear:
2018-08-27 10:24:33
Should be stronger restrictions, O(N) solution is easy to both make it up and code it.
|
|
fr0zen:
2018-08-13 01:50:51
AC in 2³² go!!! |
|
masterchef2209:
2018-08-09 14:13:17
AC in 1 go :D |
|
bartosz_panek:
2018-07-26 18:43:13
Java - time limit exceeded. Same code in c++ and accepted xD |
| 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