| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 152 | 53 | 49 | 34.752% |
겨울이 찾아와 하늘이네 부대 앞 도로에 눈이 쌓였다.
도로는 $1$부터 $N$까지의 구역으로 나누어져 있으며, $i$번 구역에는 $A_i$만큼의 눈이 쌓여있다. 하늘이에게 주어진 임무는 제설 도구를 이용해 도로 위 모든 눈을 치우는 것이다!
각 제설도구에는 성능 $X$가 있으며, 성능이 $X$인 제설 도구는 1회 사용 시에 $L$개 이하의 연속한 구역들을 골라 그 안에서 총합 $X$ 이하의 눈을 제거할 수 있다. 이때 고른 구역들에 쌓여 있는 모든 눈을 제거해야 하는 것은 아니라는 점에 유의하자. 모든 제설 도구의 성능 $X$는 자연수이고 성능이 높을 수록 가격이 비싸다. 또한, 모든 제설 도구는 내구도 한계로 인해 최대 $M$회만 사용이 가능하다고 한다.
하늘이는 제한된 예산을 가지고 있기 때문에 최소 비용이 드는 단 하나의 제설 도구로 도로 위 모든 눈을 치우려고 한다. 도로 위 눈을 모두 치우기 위해서 필요한 제설 도구의 성능 $X$의 최솟값을 구하여라.
첫번째 줄에 세 정수 $N$, $M$, $L$이 공백으로 구분되어 주어진다. ($1 \leq L \leq N \leq 10^5$, $1 \leq M \leq 10^{15}$)
두번째 줄에 정수 $A_1$, $A_2$, $\cdots$, $A_N$이 공백으로 구분되어 주어진다. ($0 \leq A_i \leq 10^{10}$, $\Sigma_{i=1}^n A_i > 0$)
모든 입력은 정수이다.
도로 위 눈을 모두 치우기 위해서 필요한 제설 도구의 성능 $X$의 최솟값을 출력한다.
어떤 제설 도구로도 눈을 모두 치울 수 없다면 대신 $-1$을 출력한다.
3 5 2 4 9 5
4
4 4 1 5 1 3 2
5
3 1 2 2 0 1
-1