시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 612 | 196 | 146 | 39.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일 까지의 각 사람들이 느낀 불쾌함의 총합의 최솟값을 출력하고 두 번째 줄에는 그 때 청소한 날짜를 오름차순으로 출력한다. 정답이 여러 가지인 경우에는 사전 순으로 앞서는 것을 출력한다. 단, 청소는 항상 그 날 학생들이 다 나가고 난 후 저녁에 한다고 한다.
8 2 5 8 6 10 1 15 3 9
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번