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
|
aimbot:
2018-01-09 13:00:19
2 ez |
|
kmkhan_014:
2017-12-18 18:32:04
beauty!!!
|
|
shizukaa:
2017-10-26 17:05:10
Hint on implementation: Use List simply(or you use two pointer but at last you will doing the same thing).
|
|
frozen7:
2017-10-13 17:04:53
Can be solved using binary_search in O(nlogn) or using two pointer technique in O(n) Last edit: 2017-10-13 19:00:19 |
|
hitman007:
2017-09-24 20:45:59
I wrote unexpected number of loops and if-else. Am I doing something wrong ? Although I used sliding window method and AC. |
|
darkdreamofmy1:
2017-09-05 20:59:42
ac in one go LOL |
|
jayu_jd:
2017-07-09 16:59:18
Nice problem!
|
|
anurag_tangri:
2017-07-05 14:10:48
AC IN ONE GO :) prefix sum and two pointers :D |
|
shauryauppal:
2017-07-05 13:43:38
Deque concept O(N) answer
|
|
babur:
2017-06-24 06:46:17
CAKE WALK |
| 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