시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB161211417.073%

문제

선생님 정원이는 2023년 수학여행 행사를 계획하고 있다. 정원이는 지난 휴가 때 근사한 시간을 보낸 솔라 아일랜드에 가기로 계획하였다. 정원이의 학교에는 $B$개의 반이 있고, 각 반에는 학생 $P$명이 있어서 학생의 수는 총 $B \times P$명이다.

정원이는 학생들을 모두 수용할 수 있는 리조트를 찾다가 판도라 리조트를 발견하였다. 판도라 리조트는 $N$개의 건물이 일렬로 배치되어 왼쪽에서부터 $i+1$($0 \leq i < N$)번째 건물에는 번호 $i$가 붙어있다. $i$번 건물은 학생 $C_i$명을 수용할 수 있다. 인접한 두 건물 사이 거리는 모두 $1$로 동일하다.

정원이는 버스 $B$대를 확보하여 각 버스에 같은 반 학생 $P$명을 태워서 리조트로 이동하려고 한다. 각 버스는 건물이 있는 위치에 주차할 수 있으며 같은 건물에 여러 버스를 주차할 수 있다.

학생들은 버스에서 내린 후 자신이 머무를 리조트로 이동한다. 학생들의 이동 거리가 너무 길면 학생들을 통제하는 데 노력이 많이 들기 때문에 정원이는 학생 $B \times P$명의 총 이동 거리가 최소화되도록 리조트에 학생들을 배치하고 버스를 주차하려고 한다. 정원이를 도와 학생들의 배치와 버스를 주차하는 위치를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에 리조트의 건물 수 $N$, 버스의 수 $B$, 버스당 인원수 $P$가 주어진다.

두 번째 줄에는 리조트의 각 건물당 수용할 수 있는 인원수 $C_i$에 해당하는 $N$개의 정수가 주어진다.

출력

첫 번째 줄에 정원이가 적절하게 버스와 학생들을 배치했을 때 학생들의 이동 거리의 합을 출력한다.

두 번째 줄부터 $B$개의 줄에는 $P+1$개의 정수를 출력하는데, 각 버스의 위치 $X_i$ ($0 \leq X_i < N$)와 해당 버스에 타는 $P$명의 학생들이 사용할 리조트의 건물 번호 $S_{ij}$ ($0 \leq S_{ij} < N$)를 출력한다.

가능한 정답이 여러 개라면 그중 아무거나 출력한다.

서브태스크

모든 데이터에 대해서, $1 \leq N \leq 250\,000; 0 \leq C_i \leq 250\,000; 1 \leq B \times P \leq \sum_{i=0}^{N-1}C_i \leq 250\,000$ 를 만족한다.

번호배점제한
11

$B = 1$

21

$N, \sum_{i=0}^{N-1}{C_i} ≤ 5\,000$

31

추가 제약조건은 없다.

예제 입력 1

7 3 5
2 6 3 1 1 1 1

예제 출력 1

10
1 0 1 1 1 2
1 0 1 1 1 2
4 2 3 4 5 6

출처

Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 AB번

채점 및 기타 정보

  • 예제는 채점하지 않는다.