| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1536 MB | 160 | 49 | 29 | 34.118% |
서울의 남부를 잇는 남부순환로 는 $N$ 개의 크기가 같은 블록 으로 나눌 수 있다. $i$번 블록 (1ドル \leq i \leq N$)의 왼쪽에는 $i - 1$ 번 블록이 존재하며 ($i = 1$ 일 때를 제외), 오른쪽에는 $i + 1$ 번 블록이 존재한다 ($i = N$ 일 때를 제외). 이름이 순환로이지만, $N$ 번 블록의 오른쪽에 1ドル$ 번 블록이 인접하지 않음에 유의하라.
남부순환로에는 가로등이 전혀 설치되어 있지 않아서, 밤이 되면 어둡고 이상한 기운이 도는 것으로 악명이 높다. 이 문제를 해결하기 위해, 남부순환로1119길 주민 김준원은 몇 개의 블록에 가로등을 설치하기로 했다.
가로등을 설치할 때, 김준원은 $N$ 개의 블록에 대해서 하나의 가로등을 설치할지 말지를 결정한다. 만약 $i$ 번 블록에 가로등을 설치하기로 결정하였다면, 김준원은 $W_i$ 의 비용을 들여 가로등을 설치한다. 설치하지 않기로 결정하였다면, 비용이 부과되지 않는다. 작업이 끝난 이후, 모든 블록은 가로등이 설치되어 있거나, 왼쪽 / 오른쪽에 인접한 블록에 가로등이 설치되어 있어야 한다. 작업의 전체 비용 은 각 가로등을 설치하는 데 든 비용의 합이다.
김준원이 위 조건을 만족시키면서 가로등을 설치하는 모든 경우를 생각해 보자. 두 경우가 다르다는 것은 어떠한 블록 1ドル \le i \le N$ 이 존재하여 한 경우에는 $i$ 번 블록에 가로등이 있고, 다른 경우에는 가로등이 없음을 뜻한다. (즉, 자신 또는 인접한 블록에 가로등이 설치되어 있어야 한다는 조건을 무시하면 모든 경우는 2ドル^N$ 가지가 있다.) 이 모든 경우를 전체 비용이 감소하지 않는 순서대로 정렬하였을 때, 모든 1ドル \le i \le K$ 에 대해, 정렬된 배열의 $i$ 번째 원소의 전체 비용들을 모두 출력하라. 만약 경우의 수가 $i$ 미만이라면, -1을 출력하라.
첫 번째 줄에 두 정수 $N, K$가 공백으로 구분되어 주어진다. (1ドル \le N, K \le 250,000円$)
두 번째 줄에 $N$ 개의 정수 $W_1, W_2 \cdots W_N$가 공백으로 구분되어 주어진다. $W_i$ 는 $i$번 블록에 가로등을 설치하는 데 필요한 비용이다. (0ドル \leq W_i \leq 10^9$)
$K$ 개의 줄을 출력한다. 이 중 $i$ 번째 줄에는, 정렬된 배열의 $i$ 번째 원소의 전체 비용을 출력하라. 만약 경우의 수가 $i$ 미만이라면, -1을 출력하라.
5 3 1 3 10 3 1
4 4 5
12 20 317 448 258 208 284 248 315 367 562 500 426 390
1525 1566 1602 1616 1633 1652 1697 1725 1730 1733 1747 1761 1764 1766 1773 1775 1783 1792 1811 1824
3 9 0 0 0
0 0 0 0 0 -1 -1 -1 -1