TopCoder

Thumb %e6%88%aa%e5%9c%96 2020 07 24 %e4%b8%8b%e5%8d%8812.28.41
8e7
我很喜歡程式設計

User's AC Ratio

80.0% (16/20)

Submission's AC Ratio

36.1% (35/97)

Description

還記得H遊戲密笈(TIOJ 1446)嗎?

你最近又迷上了另一款H遊戲(Heuristic Game,一款能啟發人coding大進步的遊戲)。

但是你最近卡關了,這又讓你覺得很不愉快。

在一次偶然的機會中,你在圖書館發現了一套『H遊戲密笈』,裡面有教你如何破台的方法,因此你迫不及待的想要把那套『H遊戲密笈』借回家。

但不幸的是,那套書是鎮館之寶,是不能外借的,所以你只好靠紙筆把那本『H遊戲密笈』帶回家(抱歉,影印機和打字機都故障了。)。

當然因為全部都自己抄,實在是太累了,你就請了 k 個人來幫你抄,而你自己則在一旁休息。

這套書總共有 m 本,要抄完每一本書所需的時間都不大一樣,而抄書者只能抄連續編號的書。當然,這k個人是可以同時抄的。

請問你要怎麼安排,才能在最短時間內將這套『H遊戲密笈』帶回家呢?

Input Format

本題有多筆測試資料:

第一行有一個數字 T ,代表有 T 筆測試資料

每一筆測試資料有兩行。第一行有兩個正整數 m, k,代表有 m 本書和 k 個人 ( 1 <= k <= m <= 500 )。

第二行有 m 個正整數ai,代表編號 i 的書抄完需要多少時間。( 0 < ai <= 10,000,000)

Output Format

對於每一組測試資料,請輸出一行,為將a1到am分割為k個部分的一個序列,每個部分為一個抄書者所要抄的書。

如果有多種可能的話,請輸出使第一個抄書者抄最少的解,如果相同的話再比較第二個......

但要特別注意的是,如果有人被請來幫忙,卻沒有事情可以做的話,他會很不高興,所以每個人都至少要抄到一本書。

Sample Input

2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100

Sample Output

100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100

Hints

Problem Source

原TIOJ1465 / 建中校內培訓第四次模擬考試。
Problem Setter:hallogameboy、peter50216
(Adapt From:CEOI 1998)

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1400 65536 262144 1
1 1400 65536 262144 2
2 1400 65536 262144 3
3 1400 65536 262144 4
4 1400 65536 262144 5
5 1400 65536 262144 6
6 1400 65536 262144 7
7 1400 65536 262144 8
8 1400 65536 262144 9
9 1400 65536 262144 10
10 1400 65536 262144 11