| 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
|
||||||||||||||
|
2015-06-05 05:58:41 ---@@@----
Nice question.. Done it using Sliding Window concept... :) |
||||||||||||||
|
2015-05-20 17:51:17 sathya_dev
Learnt new way of thinking :) |
||||||||||||||
|
2015-05-19 20:03:45 Vaporeon
My dp solution giving WA ar running judge(7).. My submission id is:14282110 please help :( |
||||||||||||||
|
2015-05-12 08:48:25 pramttl
Time limit is too strict. I submitted a O(n) solution in C++14 (memoized, recursive solution) still got TLE. |
||||||||||||||
|
2015-05-12 05:19:56 Subhashis Bhowmik
My Ans is getting WA, Abeer's case worked, but @Riddhi, the output in your test case shud b 23 as my ans is saying. 6+9+8=23 EDIT: Sorry, didn't see consecutive, sorted the array first. My bad :p Last edit: 2015-05-12 05:46:31 |
||||||||||||||
|
2014-12-07 22:45:55 Abeer Khan
Try this test case, Thanks to pero. 6 12 1 2 3 4 5 1 O/P 12 |
||||||||||||||
|
2014-09-23 10:37:56 Riddhi
Try this test case: 9 23 2 8 18 9 91 6 4 2 1 Output: 18 |
||||||||||||||
|
2012-09-01 17:37:04 AC Srinivas
similar problem ALIEN |
||||||||||||||
RSS