Advertisement blocking software were detected ;( Please add this webpage to whitelist.

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 5
4 9
7 3 5 6

hide comments
sharif ullah: 2015-10-19 11:29:39

modified version of KAdane's algorithm!!!

Dushyant Singh: 2015-10-06 11:22:01

Weak test cases. One of my AC code gives 10 for first output.

theweblover007: 2015-10-05 12:31:14

The algorithm behind this is kadane's algorithm, no you dont need to learn it, its very intuitive.

shshnk28: 2015-09-28 15:19:07

some times the difference between tle and ac could be just changing the language from Python to c++. With the same logic.

snehil10111995: 2015-09-25 16:51:03

No algo. O(n). :)

rohit gajawada: 2015-09-24 11:47:21

whats up raghu

gullu_mishra: 2015-09-22 18:55:56

50th in spoj ..AC in 1 go...nice problem

topke: 2015-09-03 20:29:11

There is nothing to memoize here. Solution is O(n) , you don't need any algorithm to solve this one.

swapnil1996: 2015-08-22 09:23:58

Nice problem....

Mohammad Nasirifar: 2015-08-13 15:40:06

AC O(nlg(n)) :D

Added by:Adrian Satja Kurdija
Time limit:0.184s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Resource:that would be me