소 댄스 공연

몇 달간의 연습 끝에 소들은 연례 댄스 공연을 올릴 준비를 거의 마쳤다. 올해 공연할 작품은 그 유명한 소 발레 "카우펠리아(Cowpelia)"이다.

공연에서 아직 정해지지 않은 유일한 요소는 무대의 크기이다. 크기가 \(K\)인 무대에서는 소 \(K\)마리가 동시에 춤출 수 있다. 무리의 소 \(N\)마리(\(1 \leq N \leq 10,000\))는 춤에 등장해야 하는 순서대로 \(1 \ldots N\)의 번호가 매겨져 있다. 각 소 \(i\)는 정해진 시간 \(d(i)\) 동안 춤을 출 계획이다. 처음에는 소 \(1 \ldots K\)가 무대에 올라 춤을 추기 시작한다. 이들 중 가장 먼저 자기 파트를 끝낸 소가 무대에서 내려가면 소 \(K+1\)이 곧바로 춤을 추기 시작하며, 이후에도 같은 방식으로 항상 \(K\)마리의 소가 춤을 추게 된다(공연 막바지에 소가 부족해지기 전까지). 공연은 마지막 소가 자기 춤 파트를 끝내는 시각 \(T\)에 끝난다.

당연히 \(K\)가 클수록 \(T\)는 작아진다. 공연이 너무 길어지면 안 되므로, \(T\)가 가질 수 있는 최댓값을 지정하는 상한 \(T_{max}\)가 입력으로 주어진다. 이 제약 조건 아래에서 가능한 가장 작은 \(K\) 값을 구하시오.

문제 출제: 델핀(Delphine), 브라이언 딘(Brian Dean)

문제 출제: 델핀(Delphine), 브라이언 딘(Brian Dean)

입력의 첫째 줄에 \(N\)과 \(T_{max}\)가 주어진다. \(T_{max}\)는 100만 이하의 정수이다.

다음 \(N\)개의 줄에는 소 \(1 \ldots N\)의 춤 파트 길이 \(d(1) \ldots d(N)\)이 주어진다. 각 \(d(i)\) 값은 \(1 \ldots 100,000\) 범위의 정수이다.

\(K=N\)이면 공연이 시간 안에 끝나는 것이 보장된다.

댄스 공연이 \(T_{max}\) 시간 단위를 넘지 않도록 하는 가능한 가장 작은 \(K\) 값을 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > January > Silver