TopCoder

Thumb output jddoia
$\huge 南ことり$
$https://www.ototot.com.tw/TIOJ/ \\我要拿牌、去東京、變紅色,那就努力吧 \\ 確かな今よりも新しい夢つかまえたい$

User's AC Ratio

83.3% (10/12)

Submission's AC Ratio

31.6% (24/76)

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

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1400 65536 65536
1 1400 65536 65536
2 1400 65536 65536
3 1400 65536 65536
4 1400 65536 65536
5 1400 65536 65536
6 1400 65536 65536
7 1400 65536 65536
8 1400 65536 65536
9 1400 65536 65536
10 1400 65536 65536