页面无法加载？点击这里可能会修复。
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

需要登录才能编写代码。