책 복사하기2

윤전기의 발명 전에는 책의 사본을 만드는 것이 무척 고통스러운 일이었다.

당시에는 책을 베껴쓰는 사람들 (서기공)이 전문으로 책을 베껴쓰곤 했다.

이 작업은 몹시 지루했는데, 작업을 일찍 끝낼 유일한 방법은 더 많은 서기공을 고용하는 것 뿐이었다.

당시 극장에서는 유명한 비극을 상연하는 중이었는데,

여러 권으로 나뉜 대본을 배우들에게 주기 위해 서기공들을 고용했다.

대본은 m권으로 나뉘어 있으며, 서기공의 수는 k(k≤m)이다.이 때,

각 서기공마다 한 권 이상씩의 대본을 배정해서 책을 베껴쓰게 하려고 한다.

각 서기공은 연속된 권을 베껴써야 한다. (예를 들어, 1 2 3 권이나 4 5권을 할 수는 있지만, 1 2 4 나 3 5 권을 베껴쓸 수는 없다.

한 권을 두 사람이 나누어서 베낄 수 없다.

이 때, 모든 대본이 다 완성되는 시간은 가장 많은 페이지를 베껴써야 하는 서기공의 업무량에 달렸다.

가장 많은 페이지를 맡은 서기공의 페이지 수를 최소화할 수 있도록 책들을 k명의 서기공에게 배분하는 프로그램을 작성하라.

입력

입력의 첫째 줄에는 책의 권수 m과 서기공의 수 k (각각 100,000이하, k≤m)이 주어진다.

그 후 m개의 (1천만 이하의 자연수) 로 각 책의 페이지 수가 주어진다.

출력

입력에 대해서 책들을 k개의 구간으로 쪼개서 출력해야 한다. 출력 형식은 아래의 예제 출력을 참조한다.

만약 답이 두 개 이상 있다면, 첫 번째 서기공이 할 일이 가장 작은 답을 출력한다.

그래도 두 개 이상 있다면, 두 번째 서기공이 할 일이 가장 작은 답을 출력하며,

그래도 두 개 이상 있을 경우 이런 식으로 반복한다.

예제1

예제2

출처

Central Europe 1998, poj 1505

책 복사하기2 1초 32MB