RiseOJ – 높은 헛간 짓기

설명

농부 존은 $$K$$ 마리의 소들의 도움을 받아 완전히 새로운 $$N$$ 층짜리 헛간을 짓고 있다 ( $1 \leq N \leq K \leq 10^{12}$ , $N \leq 10^5$ ). 최대한 빨리 짓기 위해, 소들에게 일을 어떻게 배분할지 알아내는 데 당신의 도움이 필요하다.

각 소는 헛간의 전체 $$N$$ 개 층 중 정확히 한 층에 배정되어 일해야 하며, 각 층에는 적어도 한 마리의 소가 배정되어야 한다. $$i$$ 번째 층에는 총 $$a_i$$ 단위의 작업이 필요하고, 각 소는 시간당 1 단위의 작업을 완료하므로, $$c$$ 마리의 소가 $$i$$ 번째 층에서 일하면 그 층은 $$a_i / c$$ 단위 시간 만에 완성된다. 안전상의 이유로, $$i$$ 번째 층이 완성되어야 $$i+1$$ 번째 층의 공사를 시작할 수 있다.

소들을 층에 최적으로 배정했을 때 헛간을 완성할 수 있는 최소 총 시간을 계산하시오. 이 수를 가장 가까운 정수로 반올림하여 출력한다. 답은 두 정수 사이의 경계로부터 0.1보다 많이 떨어져 있음이 보장된다.

문제 출처: Yang Liu

제약

문제 출처: Yang Liu

입력 형식

입력의 첫째 줄에 $$N$$ 과 $$K$$ 가 주어진다.

다음 $$N$$ 개의 줄에 $a_1 \ldots a_N$ 이 주어지며, 각각은 $10^{12}$ 이하의 양의 정수이다.

출력 형식

헛간을 짓는 데 필요한 최소 시간을 가장 가까운 정수로 반올림하여 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 tallbarn.in · 출력을 쓸 파일 tallbarn.out

예제 1

입력

2 5
10
4

출력

문제 정보

riseoj 작성

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

올림피아드 > USACO > 2016-2017 > January > Platinum

태그

JudgeUSACO

높은 헛간 짓기

평가 및 의견

풀이 제출