캠핑장의 전력 이용 기간

문제

한 캠핑장은 앞으로 N일 동안의 공용 전력 사용량을 하루 단위로 예상해 두었다. i일의 예상 사용량 A_i는 0 이상 9 이하의 정수다. 이용객 한 팀이 이 기간 중 연속된 며칠 동안 머무르려고 한다. 도착일과 마지막 이용일은 모두 이용 기간에 포함되며, 중간 날짜를 건너뛰어 선택할 수는 없다. 이 팀은 공용 설비에 부담이 적은 기간을 고르기 위해 두 가지 조건을 정했다. 첫째, 머무르는 모든 날짜의 예상 사용량을 더한 값이 전력 예산 B 이하여야 한다. 둘째, 예상 사용량이 기준 H 이상인 날짜가 이용 기간 안에 K일 이하여야 한다. 기준 H와 정확히 같은 사용량인 날도 두 번째 조건에서 세는 날짜에 포함된다. 사용량이 H보다 작은 날은 첫 번째 조건의 합에는 포함되지만 두 번째 조건의 날짜 수에는 포함되지 않는다. 두 조건은 서로 별개이며, 선택한 기간은 두 조건을 모두 만족해야 한다. 전력 예산이나 날짜 수가 제한과 정확히 같아지는 것은 허용된다. 사용량이 0인 날짜도 하루를 이용한 것으로 세므로 기간의 길이에 포함된다. K가 0이면 사용량이 H 이상인 날짜는 단 하루도 선택한 기간에 들어갈 수 없다. 이 팀은 조건을 만족하는 이용 기간 중 가장 긴 기간을 원한다. 길이가 같은 기간이 여러 개라면 도착일이 가장 빠른 기간을 선택한다. 날짜에는 1부터 N까지 번호가 붙어 있으며, 기간의 길이는 마지막 이용일에서 도착일을 뺀 뒤 1을 더한 값이다. 적어도 하루를 포함하는 기간만 실제 이용 기간으로 인정한다. 선택할 기간의 길이, 도착일, 마지막 이용일을 구한다. 조건을 만족하는 하루짜리 기간조차 없다면 예약할 수 없는 것으로 처리하고 세 값 모두 0을 출력한다. 예상 사용량은 입력된 값 그대로 사용하며 이용 기간을 정한 뒤 사용량을 바꾸거나 일부 날짜의 사용량을 제외할 수 없다.

입력

첫째 줄에 날짜 수 N, 전력 예산 B, 기준 이상 날짜 수의 상한 K, 사용량 기준 H가 공백으로 주어진다. 둘째 줄에 A_1, A_2, ..., A_N이 공백으로 주어진다.
모든 값은 정수이며 1 ≤ N ≤ 180,000, 0 ≤ B ≤ 9N, 0 ≤ K ≤ N, 1 ≤ H ≤ 9, 0 ≤ A_i ≤ 9다.

출력

선택한 기간의 길이, 도착일, 마지막 이용일을 이 순서로 공백으로 구분하여 한 줄에 출력한다. 가장 긴 기간이 여러 개라면 도착일이 가장 빠른 기간을 출력한다. 가능한 이용 기간이 없으면 0 0 0을 출력한다.

8 12 1 5
2 0 5 1 3 6 0 2

5 1 5

3 0 0 1
1 2 3

0 0 0

4 0 0 9
0 0 0 0

4 1 4

출처: Devin.KR 자체 제작