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.
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.
Print the required number (it will be greater than 0 in all of the test data).
5 12 2 1 3 4 5output
4 9 7 3 5 6output
|Added by:||Adrian Satja Kurdija|
|Cluster:||Cube (Intel Pentium G860 3GHz)|
|Languages:||All except: SCM chicken|
|Resource:||that would be me|
done using variation of KADANAE'S algorithm simple and easy
Amazing problem. But time limit is too strict. Got a TLE in Python but an AC in C++14 :D
Learnt new way of thinking :)
My dp solution giving WA ar running judge(7)..
Time limit is too strict. I submitted a O(n) solution in C++14 (memoized, recursive solution) still got TLE.
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
Try this test case, Thanks to pero.
Try this test case:
similar problem ALIEN