페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8608
서브태스크

가방 1s 1024MB

문제

상훈이는 KOI 도시에서 상점을 운영하고 있는 시민이다.

상훈이의 상점은 N개의 물건을 가지고 있으며, 이 중 i번째 물건의 무게는 A_i​이다.

상훈이는 도둑 김기범이 본인의 상점을 노리고 있다는 첩보를 들었고, 이에 대비해 피해를 최소화하려고 한다.

도둑 김기범은 가게에서 K개의 물건을 훔쳐갈 것인데, 물건이 무거울 경우 훔쳐가기 어렵고 경찰한테 걸릴 가능성이 높다.

고로, 도둑 김기범은 훔쳐가는 물건의 무게의 합을 최소화한다.

만약 가게에 있는 물건의 개수가 K개 미만일 경우, 도둑 김기범은 가게에 있는 모든 물건을 훔쳐간다.

상훈이는 도둑 김기범이 가게를 도착하기 전에, 가방에 상점의 물건들을 몇 개 담아서 들고 갈 것이다.

이후, 도둑 김기범은 상훈이가 들고 가지 않은 물건들에 대해 위에 설명한 방식으로 범죄를 저지른다.

상훈이는 가방에 물건을 적당히 담아서 도둑 김기범이 훔쳐가는 물건의 무게 합을 최대화하려고 한다.

상훈이의 가방이 감당할 수 있는 무게는 한정되어 있다. 입력으로 최댓값 C가 주어졌을 때, 모든 x=1,2,…,C에 대해 다음 질문에 답하라:

  • 상훈이가 가방에 담을 수 있는 물건들의 무게 합이 x 이하여야 한다는 조건하에, 도둑 김기범이 훔쳐가는 물건들의 무게 합의 최댓값은 얼마인가?

제약 조건

  • 주어지는 모든 수는 정수이다.

  • 1≤K≤N≤5,000

  • 1≤C≤1,000,000

  • 모든 i (1≤i≤N) 에 대해 1≤A_i≤1,000,000


입력

첫 번째 줄에 N,K,C가 공백으로 구분되어 주어진다.

두 번째 줄에 N 개의 정수 A_1,A_2,…,A_N​이 공백으로 구분되어 주어진다.


출력

C 개의 줄을 출력한다. i 번째 줄에는, x=i일 때 도둑 김기범이 훔쳐가는 물건들의 무게 합의 최댓값을 출력한다.


부분문제

번호 점수 조건
#113점

N≤10,\quad A_i​≤10,000,\quad C≤10,000

#217점

N≤80,\quad A_i​≤10,000,\quad C≤10,000

#323점

A_i​≤10,000,\quad C≤10,000

#416점

K=1

#531점

추가 제약 조건 없음


예제 #1

5 1 6
1 2 3 4 5
2
2
3
3
3
4

예제 #2

5 2 5
2 3 5 7 11
5
8
8
8
12

예제 #3

3 2 3
1 1 7
8
8
8


출처

2025 KOI 2차 중2
로그인해야 코드를 작성할 수 있어요.