상훈이는 KOI 도시에서 상점을 운영하고 있는 시민이다. 상훈이의 상점은 \(N\)개의 물건을 가지고 있으며, 이 중 \(i\)번째 물건의 무게는 \(A_i\)이다. 상훈이는 도둑 김기범이 본인의 상점을 노리고 있다는 첩보를 들었고, 이에 대비해 피해를 최소화하려고 한다.

도둑 김기범은 가게에서 \(K\)개의 물건을 훔쳐갈 것인데, 물건이 무거울 경우 훔쳐가기 어렵고 경찰한테 걸릴 가능성이 높다. 고로, 도둑 김기범은 훔쳐가는 물건의 무게의 합을 최소화한다. 만약 가게에 있는 물건의 개수가 \(K\)개 미만일 경우, 도둑 김기범은 가게에 있는 모든 물건을 훔쳐간다.

상훈이는 도둑 김기범이 가게를 도착하기 전에, 가방에 상점의 물건들을 몇 개 담아서 들고 갈 것이다. 이후, 도둑 김기범은 상훈이가 들고 가지 않은 물건들에 대해 위에 설명한 방식으로 범죄를 저지른다. 상훈이는 가방에 물건을 적당히 담아서 도둑 김기범이 훔쳐가는 물건의 무게 합을 최대화하려고 한다.

상훈이의 가방이 감당할 수 있는 무게는 한정되어 있다. 입력으로 최댓값 \(C\)가 주어졌을 때, 모든 \(x = 1, 2, \dots , 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 , \dots , A_N\)이 공백으로 구분되어 주어진다.

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

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 2차 대회 > 중등부 2번