시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 307 | 99 | 80 | 34.632% |
당신은 칩을 만들기 위해 기판에 N개의 부품을 장착했다. 각각의 부품을 작동시키기 위해서는 전원을 연결해야 하는데, 기판에 연결할 수 있는 전원 선이 K개 밖에 없었다. 당신은 이 K개의 전원 선을 기판의 아래쪽에 연결하고, 기판의 위쪽에서 부품을 연결하여 전원을 나눠 쓰기로 하였다. 이때 다음과 같은 조건을 지켜야 한다.
제일 왼쪽의 예는 기판의 위쪽에 연결한 전선이 꼬이는 경우로 올바르지 않은 경우이다. 두 번째 경우는 올바른 연결이지만 중요도가 최대가 아니다. 세 번째 경우는 올바른 경우이며, 중요도가 4 × 4 + 5 × 5 = 41로 최대가 되는 경우이다.
첫째 줄에 두 정수 N(1 ≤ N ≤ 50), K(1 ≤ K ≤ 20)이 주어진다. 다음 줄에는 N개의 정수로 각 부품의 중요도가 차례로 주어진다. 부품의 중요도는 1,000 이하의 음이 아닌 정수이다.
처음 K개의 줄에는 전원을 연결한 부품의 번호를 출력한다. 사용하지 않은 전원에 대해서는 0을 출력한다. 다음 N개의 줄에는 각 부품이 몇 번 부품과 전원을 공유하는지를 출력한다. 전원을 혼자 사용하는 경우에는 자기 자신을 출력하고, 전원을 사용하지 않는 경우에는 0을 출력한다.
5 2 2 3 4 4 5
4 5 0 0 4 3 5