TopCoder

User's AC Ratio

82.8% (24/29)

Submission's AC Ratio

18.7% (46/246)

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

No. Testdata Range Score
1 0 1
2 0~4 10
3 0~9 37
4 0~14 12
5 0~19 19
6 20~21 21
7 19~25 14
8 0~29 36

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 600 131072 262144 1 2 3 4 5 8
1 600 131072 262144 2 3 4 5 8
2 600 131072 262144 2 3 4 5 8
3 600 131072 262144 2 3 4 5 8
4 600 131072 262144 2 3 4 5 8
5 600 131072 262144 3 4 5 8
6 600 131072 262144 3 4 5 8
7 600 131072 262144 3 4 5 8
8 600 131072 262144 3 4 5 8
9 600 131072 262144 3 4 5 8
10 600 131072 262144 4 5 8
11 600 131072 262144 4 5 8
12 600 131072 262144 4 5 8
13 600 131072 262144 4 5 8
14 600 131072 262144 4 5 8
15 600 131072 262144 5 8
16 600 131072 262144 5 8
17 600 131072 262144 5 8
18 600 131072 262144 5 8
19 600 131072 262144 5 7 8
20 600 131072 262144 6 7 8
21 600 131072 262144 6 7 8
22 600 131072 262144 7 8
23 600 131072 262144 7 8
24 600 131072 262144 7 8
25 600 131072 262144 7 8
26 600 131072 262144 8
27 600 131072 262144 8
28 600 131072 262144 8
29 600 131072 262144 8