| 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
|
||||||||||||
|
2017-07-05 13:43:38
Deque concept O(N) answer 9 63 8 32 1 5 4 9 20 12 30 ans->62 |
||||||||||||
|
2017-06-24 06:46:17
CAKE WALK |
||||||||||||
|
2017-06-01 17:55:01
Awesome. Learn Two pointer.Brute Force will only show you orange TLE. |
||||||||||||
|
2017-05-02 09:47:28 Shubham Jadhav
sliding window is the way to go :) |
||||||||||||
|
2017-04-21 08:58:31
TLE despite going from O(n^2) to O(n). Hopeless. #java |
||||||||||||
|
2017-04-02 22:05:29
got ac in O(N). approach was like bruth force but took help of the previous step's sum to optimize the inner loop and made it O(N) :D |
||||||||||||
|
2017-03-28 17:40:06
Who can help me? So, I summit some times but this return time limit exceeded for me. Because, this is my first solution. I have tested with some case as below: 5 12 2 1 3 4 5 --------- 4 9 7 3 5 6 -------- 6 5 6 7 3 1 8 5 ------------- 8 63 8 32 1 5 4 9 12 3 . The result is correct. Thanks for answer |
||||||||||||
|
2017-03-25 10:56:05
Come on SPOJ, tle in java but AC in CPP. So, many times this happened to me. |
||||||||||||
|
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. |
||||||||||||
|
2017-01-31 01:47:34
ALIENS = CODEFURY =HOTELS-(without considering number of hotels just focus on max sum) TRY OTHER TWO after trying HOTELS |
||||||||||||
RSS