시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB61219614639.782%

문제

남규는 동아리 방 관리자이다. 요즘 동아리 방 사용자가 많아지고 동아리 방이 더러워져서 사람들이 불쾌함을 느끼고 있다.

한 사람이 느끼는 불쾌함은 동아리 방의 더러움과 같다. 즉, 동아리 방의 더러움이 3이고 그날 5명이 동아리방에 온다면 5명 모두 불쾌함을 3을 느끼게 되어 그 날 각 사람들이 느낀 불쾌함의 총합은 15가 된다. 그리고 동아리방의 더러움은 사람이 a명 들어오고 나가면 a만큼 증가한다. 그래서 사람들의 불쾌함을 최소로 하기 위해 동아리 방을 청소해야한다.

하지만 남규는 게을러서 총 N일중에 M번만 청소를 하려고 한다. 남규는 최대한 전체 사람들의 불쾌함의 총합이 적도록 청소 계획을 짜려한다.

N일 동안의 들어오는 사람을 미리 알 수 있다고 할 때, 어떻게 청소 하는 것이 불쾌함이 적어질지 남규는 몹시 궁금하다. 처음 시작의 동아리방의 더러움은 0이다.

입력

첫째 줄에는 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ min(10, N))이 주어진다. 그리고 두 번째 줄에는 그 날 출입하는 사람의 수 Pi (1 ≤ Pi ≤ 20)가 N개 주어진다. 

출력

첫째 줄에는 N일 까지의 각 사람들이 느낀 불쾌함의 총합의 최솟값을 출력하고 두 번째 줄에는 그 때 청소한 날짜를 오름차순으로 출력한다. 정답이 여러 가지인 경우에는 사전 순으로 앞서는 것을 출력한다. 단, 청소는 항상 그 날 학생들이 다 나가고 난 후 저녁에 한다고 한다.

예제 입력 1

8 2
5 8 6 10 1 15 3 9

예제 출력 1

320
3 6

힌트

N          1    2    3    4    5    6    7    8
더러움(아침)  0    5    13   0    10   11   0    3
불쾌함(당일)  0    40   78   0    10   165  0    27
불쾌함(누적)  0    40   118  118  128  293  293  320

출처

University > 연세대학교 > 2016 연세대 컴퓨터과학과 프로그래밍 경진대회 B번