기적의 신약

면접 대비

시간 제한1초메모리 제한256 MB

요약

최근 h시간 중 가장 저렴하고 값이 같으면 가장 늦은 시간에 산 효소를 매시간 사용하고 지정 구간의 시간별 구매량을 출력합니다.

난이도: 보통10점 중 4점
유형: 슬라이딩 윈도우, 큐
정답자: 아직 제출이 없습니다

문제

조는 생물의학 연구자다. 그는 무서운 병의 치료제를 거의 완성했다. 신약을 만들려면 값이 비싸고 일정 시간이 지나면 성질을 잃는 특수 효소가 있어야 한다. 지금은 임상시험 단계라서 매 시각 같은 양의 약을 준비해야 하고, 약 한 번 분량에는 효소가 하나 들어간다.

앞으로 $n$ 시간의 가격이 주어진다. 시각 $i$ 에는 가격 $c_i$ 로 효소를 원하는 만큼 살 수 있다. 효소의 수명은 $h$ 시간이라서 시각 $i$ 에 산 효소는 시각 $i$ 부터 시각 $i + h - 1$ 까지 쓸 수 있다. 시각 $1$ 부터 시각 $n$ 까지 매 시각 효소를 하나씩 쓸 때, 전체 구매 비용이 가장 적은 계획을 구하라.

가격이 같으면 조는 효소를 미리 쌓아 두지 않고 더 신선한 효소를 산다. 그래서 구매 계획은 다음 규칙으로 하나만 정해진다. 시각 $i$ 에 쓸 효소는 구간 $[\max(1,\ i - h + 1),\ i]$ 안에서 가격이 가장 싼 시각에 산다. 가장 싼 시각이 여럿이면 그중 가장 늦은 시각을 고른다.

입력

입력은 데이터 집합 여러 개로 이루어지고 파일 끝에서 끝난다. 각 데이터 집합은 시간의 수 $n$ , 효소의 수명 $h$ , 출력 구간의 시작 시각 $b$ 와 끝 시각 $e$ , 그리고 가격 $c_1, c_2, \dots, c_n$ 을 이 순서로 담는다. 수와 수 사이에는 공백과 줄바꿈이 자유롭게 올 수 있다.

$1 \le n < 10000$
$1 \le h < 10000$
$1 \le b \le e \le n$
$0 \le c_i < 10000$

출력

데이터 집합마다 한 줄씩, 조가 시각 $b$ 부터 시각 $e$ 까지 각 시각에 사는 효소의 개수를 탭 문자로 구분해 줄 맨 앞부터 출력한다.

예제8

예제 1

입력

6	3	1	6
5	4	4	3	5	6
3	3	2	3
9000	9000	9000

예상 출력

1	1	1	3	0	0
1	1

예제 2
입력
```
1 1 1 1
7
```
예상 출력
```
1
```
예제 3
입력
```
5 10 1 5
3 1 1 2 5
```
예상 출력
```
1	1	3	0	0
```
예제 4
입력
```
6 1 1 6
1 2 3 4 5 6
```
예상 출력
```
1	1	1	1	1	1
```
예제 5
입력
```
6 6 1 6
9 8 7 6 5 4
```
예상 출력
```
1	1	1	1	1	1
```
예제 6
입력
```
5 5 1 5
4 4 4 4 4
```
예상 출력
```
1	1	1	1	1
```
예제 7
입력
```
8 4 3 6
7 0 9 9 0 3 3 1
```
예상 출력
```
0	0	4	0
```

예제 8

입력

예상 출력

1	1	1	1
2	0	2
1	1