| Submit | All submissions | Best solutions | Back to list |
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 |
| 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 |
hide comments
|
||||||||||||||
|
2016-08-13 23:54:55 vaibhav goyal
try with binary search too apart from two pointer technique....may be you will learn something as applying usual binary search you may caught in an infinite loop :D |
||||||||||||||
|
2016-08-10 14:36:19 Nallagatla Manikanta
O(n) possible :) accepted in one go :) |
||||||||||||||
|
2016-07-04 16:37:39 kartikay singh
try with two pointer techinque |
||||||||||||||
|
2016-07-03 14:38:04
Yes !!! Solved!! Thanks for the hint @Sourabh Goel |
||||||||||||||
|
2016-06-19 08:38:16
Done with BinarySearch.. Should try with Sliding Window. |
||||||||||||||
|
2016-06-17 21:31:35
TLE for O(n^2) in C++ |
||||||||||||||
|
2016-06-16 07:23:41
Both for (no. of hotels<=m) and (no. of hotels<m) the solution gets AC :P |
||||||||||||||
|
2016-04-29 12:11:07 hareesh
got 1 TLE for O(n^2) O(n) AC |
||||||||||||||
|
2016-04-28 09:43:01 Irfan
solvable with prefix sum .. O(nlogn) |
||||||||||||||
|
2016-04-21 11:01:24
O(n) solution. TLE in Java but got AC in C |
||||||||||||||
RSS