천문대의 연속 관측 묶음

문제

한 천문대에서는 밤새 얻은 관측 기록을 촬영 순서대로 보관하고 있다. 기록에는 1부터 N까지 번호가 붙어 있으며, 각 기록에는 분석에 필요한 정수 단위의 처리량이 적혀 있다. 연구원은 이 기록 중 일부를 하나의 묶음으로 만들어 분석 서버에 보내려 한다. 서버가 한 묶음에 사용할 수 있는 처리량의 한도는 B이다. 연속된 관측 흐름을 유지해야 하므로 하나의 묶음에는 번호가 연속된 기록만 넣을 수 있다. 묶음의 첫 기록이 l번이고 마지막 기록이 r번이면 l번부터 r번까지의 모든 기록을 빠짐없이 포함해야 한다. 중간의 처리량이 큰 기록만 제외하거나 기록의 순서를 바꿀 수 없다. 또한 묶음에는 적어도 하나의 기록이 있어야 하며, 마지막 기록 뒤에서 첫 기록으로 이어지는 순환 구간은 허용하지 않는다. 묶음의 처리량은 포함된 모든 기록의 처리량을 더한 값이다. 이 합이 B 이하이면 서버에 보낼 수 있으며, B와 정확히 같아도 가능하다. 개별 기록의 처리량은 모두 양의 정수이다. 따라서 기록 하나의 처리량이 B보다 크면 그 기록을 포함하는 어떤 묶음도 서버에 보낼 수 없다. 처리량 한도가 0이면 가능한 묶음은 없다. 연구원은 한 번에 가능한 한 많은 기록을 분석하고자 한다. 서버에 보낼 수 있는 묶음 중 포함된 기록 수가 가장 많은 묶음을 선택한다. 기록 수가 같은 묶음이 여러 개이면 첫 기록의 번호가 가장 작은 묶음을 선택한다. 첫 기록 번호와 기록 수가 정해지면 마지막 기록 번호도 하나로 정해지므로, 그 밖의 동점 기준은 필요하지 않다. 선택한 묶음의 기록 수와 첫 기록 번호, 마지막 기록 번호를 구하는 프로그램을 작성한다. 처리량 합 자체를 최대화하는 것이 아니라 기록 수를 최대화해야 한다. 기록 수가 더 많은 묶음은 처리량 합이 더 작더라도 우선한다. 서버에 보낼 수 있는 묶음이 하나도 없으면 세 값으로 0, 0, 0을 출력한다.

입력

첫째 줄에 정수 N과 B가 주어진다. 1≤N≤20,000, 0≤B≤20,000,000,000,000이다.
둘째 줄에 촬영 순서대로 각 기록의 처리량을 나타내는 정수 A1, A2, …, AN이 주어진다. 1≤Ai≤1,000,000,000이다.

출력

선택한 묶음의 기록 수, 첫 기록 번호, 마지막 기록 번호를 한 줄에 공백으로 구분하여 출력한다. 가능한 묶음이 없으면 0 0 0을 출력한다.

7 8
4 2 2 5 1 1 6

3 1 3

4 2
3 7 4 9

0 0 0

6 6
5 1 2 1 2 8

4 2 5

출처: Devin.KR 자체 제작