TopCoder

User's AC Ratio

71.4% (15/21)

Submission's AC Ratio

26.6% (34/128)

Description

你現在有一個由整數構成的序列$\langle D_0,D_1,\cdots ,D_{N-1}\rangle$。但是你覺得一個數列實在是太少了,所以你決定對這個數列切$K-1$刀讓它變成$K$份,並且每份都有數字。
但你又不希望切得太隨便,所以你希望從左邊數過來,切出來的偶數份中所有數字總和減掉奇數份中所有數字總和愈大愈好。
(注意,份數的編號由0開始算起。例如,你如果把$\langle 0,1,-5,7,9,10\rangle$切成$\langle 0\rangle$、$\langle 1,-5\rangle$、$\langle 7,9\rangle$、$\langle 10\rangle$四份,那麼偶數份是$\langle 0\rangle$和$\langle 7,9\rangle$,奇數份是$\langle 1,-5\rangle$和$\langle 10\rangle$。)

然而這麼一來,你發現你沒辦法一眼看出要切哪裡了。所以你決定寫個程式來解決這個問題。

本題滿分為150分。

Input Format

第一行有兩個正整數$N,K$,代表序列長度和你要把數列切成幾份。
第二行有$N$個整數$D_0,D_1,\cdots ,D_{N-1}$,代表你的序列。

對於所有測資,$K\leq 6; K\leq N\leq 10^ 6; |D_i|\leq 10^ 9$。

子任務(測資) 額外限制 分數
1 (0) $K=1$ 1
2 (0~4) $K\leq 2$ 10
3 (0~9) $K\leq 3$ 37
4 (0~14) $K\leq 4$ 12
5 (0~19) $K\leq 5$ 19
6 (20~21) $K=4,N\leq 5000$ 21
7 (19~25) $N\leq 5000$ 14
8 (0~29) 無限制 36

Output Format

輸出$K-1$行,每行包含一個正整數$C_i$,第$i$行代表第$i$刀要切在$D_{C_i-1}$和$D_{C_i}$之間。
不必照順序輸出。若有多種最佳解,你只要輸出其中一種就可以了。

Sample Input

6 3
0 1 -5 7 9 10

Sample Output

3
2

Hints

Problem Source

Problem Set by Yihda Yol
建國中學106學年度校隊選拔:複試pD

Subtasks

For Testdata: 0 ~ 0, Score: 1
For Testdata: 0 ~ 4, Score: 10
For Testdata: 0 ~ 9, Score: 37
For Testdata: 0 ~ 14, Score: 12
For Testdata: 0 ~ 19, Score: 19
For Testdata: 20 ~ 21, Score: 21
For Testdata: 19 ~ 25, Score: 14
For Testdata: 0 ~ 29, Score: 36
No. Time Limit (ms) Memory Limit (KiB)
0 600 131072
1 600 131072
2 600 131072
3 600 131072
4 600 131072
5 600 131072
6 600 131072
7 600 131072
8 600 131072
9 600 131072
10 600 131072
11 600 131072
12 600 131072
13 600 131072
14 600 131072
15 600 131072
16 600 131072
17 600 131072
18 600 131072
19 600 131072
20 600 131072
21 600 131072
22 600 131072
23 600 131072
24 600 131072
25 600 131072
26 600 131072
27 600 131072
28 600 131072
29 600 131072