ПУКАНКИ
시간 제한0.2초메모리 제한1024 MB
일렬로 놓인 N개의 팝콘 봉지를 K명이 연속된 구간으로 나누어 가질 때, 가장 많은 양을 받은 사람의 시간(합을 S로 나눈 올림)을 최소로 만드는 값을 구한다.
문제
„Мегамакс“가 팝콘 빨리 먹기 대회를 연다. 대회에는 K명으로 구성된 팀이 참가한다. 대회를 위해 N개의 팝콘 봉지가 탁자 위에 일렬로 놓이고, 각 팀원은 왼쪽부터 순서대로 몇 봉지를 연속으로 가져간다. 이전 팀원이 마지막 봉지를 가져갔다면 아무것도 가져가지 않아도 되며, 가져가는 봉지 수는 얼마든지 가능하다. 마지막 팀원은 남은 봉지를 모두 가져간다. 포장을 바꾸거나 여러 팀원이 한 봉지를 나눠 갖는 것은 안 된다. 팝콘을 나눈 뒤 시작 신호가 울리고 모든 참가자가 자기 팝콘을 먹기 시작한다. 완료 시간은 마지막 팝콘을 먹은 참가자를 기준으로 하며, 정수 초로 반올림한다.
봉지마다 팝콘의 양이 다를 수 있으므로, 먹는 시간이 최소가 되도록 팀원에게 봉지를 나누는 방법이 중요하다. 사람은 1초에 정확히 S개의 팝콘을 먹을 수 있다.
팝콘을 먹는 최소 시간을 구하는 프로그램 popcorn을 작성하시오.
입력
표준 입력의 첫째 줄에 세 정수 N, K, S가 주어진다. N은 팝콘 봉지의 수, K는 팀원의 수, S는 팝콘을 먹는 속도이다.
다음 줄에는 N개의 정수 Pi가 주어진다. Pi는 왼쪽부터 i번째 봉지에 들어 있는 팝콘의 수이다.
출력
표준 출력에 대회 규칙에 따라 팝콘을 먹는 최소 시간을 정수 하나로 출력한다.
제한
- 1 ≤ N ≤ 105
- 1 ≤ K ≤ 105
- 1 ≤ S ≤ 50
- 1 ≤ Pi ≤ 104