TOO EASY 쿠키런

면접 대비

시간 제한2초메모리 제한1024 MB

요약

모든 스테이지 난이도에 같은 값 X를 더해 합이 M 이상인 연속 구간이 K개 이상이 되도록 하는 가장 작은 X를 구합니다.

문제

쿠키런은 쿠키 캐릭터가 N개의 스테이지로 이루어진 맵을 달리며 점수를 얻는 인기 게임이다.

쿠키런의 맵 디자이너 수영은 어린이날 패치를 준비하고 있었다. 매력적인 맵을 만들고 패치 하루 전 마지막 테스트를 하던 그녀는 맵이 너무 쉽게 설계되었다는 사실을 깨달았다.

맵은 다음 규칙을 따른다.

각 스테이지에는 난이도 $A\_0, A\_1, A\_2, ..., A\_{N-1}$ 이 주어진다. 난이도가 높을수록 그 스테이지를 통과하기 어렵다.
연속한 스테이지들의 난이도 합이 $M$ 이상이면 그 구간을 흥미로운 구간이라고 한다. 즉 $A\_i + A\_{i+1} + ... + A\_j \geq M$ 이면 구간 $(i, j)$ 는 흥미로운 구간이다.
맵에는 흥미로운 구간이 적어도 $K$ 개 있어야 한다.

이를 다시 말하면, $0 \le i \le j \le N-1$ 이고 $A\_i + ... + A\_j \geq M$ 을 만족하는 쌍 $(i, j)$ 의 개수를 $T$ 라 할 때 $T \geq K$ 여야 한다.

수영은 KAIST RUN 봄 대회 참가자들에게 도움을 요청했다. 그녀가 할 수 있는 일은 모든 스테이지의 난이도에 $X$ 를 한 번에 더해 맵을 어렵게 만드는 것뿐이다. 이 조건을 만족하는 가장 작은 음이 아닌 정수 $X$ 를 구하라.

첫 번째 줄에 공백으로 구분된 세 정수 $N$ , $M$ , $K$ 가 주어진다.

두 번째 줄에 공백으로 구분된 $N$ 개의 정수 $A\_{0}, A\_{1}, \cdots, A\_{N-1}$ 이 주어진다.

조건을 만족하는 가장 작은 $X$ 를 한 줄에 출력한다.

주어진 조건을 만족하는 음이 아닌 정수 $X$ 가 적어도 하나 존재한다고 가정해도 된다.