쌀 창고

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

요약

직선 위에 정렬된 밭 위치들과 예산 B가 주어질 때, 총 운송 비용이 B 이하가 되도록 정수 위치에 창고를 세워 모을 수 있는 밭의 최대 개수를 구한다.

난이도: 보통10점 중 7점
유형: 투 포인터, 누적 합, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

'쌀의 길'이라고 불리는 긴 직선 도로를 따라 $R$ 개의 논이 있다. 각 논은 $1$ 이상 $L$ 이하의 정수 좌표에 있으며, 좌표가 감소하지 않는 순서로 주어진다. 즉 $0 \le i < R$ 인 논 $i$ 의 좌표를 $X_i$ 라 하면 $1 \le X_0 \le X_1 \le \dots \le X_{R-1} \le L$ 이다. 여러 논이 같은 좌표에 있을 수도 있다.

수확한 쌀을 저장할 쌀 창고 하나를 세우려고 한다. 창고의 위치 또한 $1$ 이상 $L$ 이하의 정수 좌표여야 하며, 논이 있는 자리를 포함해 어디에든 세울 수 있다.

수확기에 각 논은 정확히 트럭 한 대 분량의 쌀을 생산한다. 쌀을 창고로 옮기려면 트럭 운전사를 고용해야 하는데, 트럭 한 대 분량을 단위 거리만큼 옮길 때마다 1바트가 든다. 즉 어떤 논의 쌀을 창고로 옮기는 비용은 그 논의 좌표와 창고 좌표의 차이(절댓값)와 같다.

올해 예산이 넉넉하지 않아 쌀 수송에는 최대 $B$ 바트까지만 쓸 수 있다. 예산 $B$ 이내에서 창고로 쌀을 모을 수 있는 논의 수가 최대가 되도록 창고 위치를 정하고, 그때 모을 수 있는 논의 최대 개수(트럭 대수)를 구하라.

예산 $B$ 는 매우 클 수 있으므로 계산 과정에서 64비트 정수를 사용하는 것을 권장한다.

입력

첫째 줄에 논의 수 $R$ , 최대 좌표 $L$ , 예산 $B$ 가 공백으로 구분되어 주어진다. 이어지는 $R$ 개의 줄에 각 논의 좌표 $X_i$ 가 감소하지 않는 순서로 한 줄에 하나씩 주어진다.

출력

예산 $B$ 이내에서 한 창고로 쌀을 모을 수 있는 논의 최대 개수를 한 줄에 출력한다.

힌트

위 그림은 $R = 5$ , $L = 20$ , $B = 6$ 이고 논이 좌표 1, 2, 10, 12, 14에 있는 경우이다. 이때 창고를 10 이상 14 이하의 어떤 정수 좌표에 두어도 좌표 10, 12, 14의 세 논에서 쌀을 모을 수 있으며, 총 수송 비용은 6바트 이하이다. 네 개 이상의 논에서 쌀을 모을 수 있는 창고 위치는 존재하지 않으므로 정답은 3이다. 그림은 최적 위치 중 하나를 나타낸다.

예제3

예제 1
입력
```
5 20 6
1
2
10
12
14
```
예상 출력
```
3
```
예제 2
입력
```
1 10 0
5
```
예상 출력
```
1
```
예제 3
입력
```
4 10 0
3
3
3
3
```
예상 출력
```
4
```