| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 714 | 270 | 202 | 41.909% |
상훈이는 KOI 도시에서 상점을 운영하고 있는 시민이다. 상훈이의 상점은 $N$개의 물건을 가지고 있으며, 이 중 $i$번째 물건의 무게는 $A_i$이다. 상훈이는 도둑 김기범이 본인의 상점을 노리고 있다는 첩보를 들었고, 이에 대비해 피해를 최소화하려고 한다.
도둑 김기범은 가게에서 $K$개의 물건을 훔쳐갈 것인데, 물건이 무거울 경우 훔쳐가기 어렵고 경찰한테 걸릴 가능성이 높다. 고로, 도둑 김기범은 훔쳐가는 물건의 무게의 합을 최소화한다. 만약 가게에 있는 물건의 개수가 $K$개 미만일 경우, 도둑 김기범은 가게에 있는 모든 물건을 훔쳐간다.
상훈이는 도둑 김기범이 가게를 도착하기 전에, 가방에 상점의 물건들을 몇 개 담아서 들고 갈 것이다. 이후, 도둑 김기범은 상훈이가 들고 가지 않은 물건들에 대해 위에 설명한 방식으로 범죄를 저지른다. 상훈이는 가방에 물건을 적당히 담아서 도둑 김기범이 훔쳐가는 물건의 무게 합을 최대화하려고 한다.
상훈이의 가방이 감당할 수 있는 무게는 한정되어 있다. 입력으로 최댓값 $C$가 주어졌을 때, 모든 $x = 1, 2, \dots , C$에 대해 다음 질문에 답하라:
첫 번째 줄에 $N$, $K$, $C$가 공백으로 구분되어 주어진다.
두 번째 줄에 $N$개의 정수 $A_1 , A_2 , \dots , A_N$이 공백으로 구분되어 주어진다.
$C$개의 줄을 출력한다. $i$번째 줄에는, $x = i$일 때 도둑 김기범이 훔쳐가는 물건들의 무게 합의 최댓값을 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 13 | $N ≤ 10$, $A ≤ 10\, 000$, $C ≤ 10\, 000$ |
| 2 | 17 | $N ≤ 80$, $A ≤ 10\, 000$, $C ≤ 10\, 000$ |
| 3 | 23 | $A_i ≤ 10\, 000$, $C ≤ 10\, 000$ |
| 4 | 16 | $K = 1$ |
| 5 | 31 | 추가 제약 조건 없음 |
5 1 6 1 2 3 4 5
2 2 3 3 3 4
5 2 5 2 3 5 7 11
5 8 8 8 12
3 2 3 1 1 7
8 8 8
Olympiad > 한국정보올림피아드 > KOI 2025 2차대회 > 중등부 2번