TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

33.3% (5/15)

Tags

Description

千鈞一髮之際,小向解除了光牆,消除了魔法陣。

「看來真的成長了喲,小向!」
「……」小向半點聲音也不出,只是站在原地沉默不語,似乎在思考著什麼。
或許這一切的一切對她造成的衝擊仍在蘊釀。
當然,小向的師父也不會放過任何一瞬間,開始猛力地朝著小向狂施放各種魔法。
小向姑且是張開了防護罩保護了自己和希爾伯特。不過小向的魂如同不在身體裡似的,或許她的精神真的崩潰了。
眼見事情不妙的希爾伯特將魔法道具交給了小向。

「總之…先打倒你的師父再說吧,小向。」
「……說的也是呢…只要打倒就好…」

希爾伯特交給小向的魔法道具名為「裂空魔彈」。本來只是一顆不起眼的小石子,但只要對著裂空魔彈注入魔力便會成為一個殺傷力極大的武器。注入魔力後,裂空魔彈幾本上可以視為是可隨意控制發射角度的子彈。

由於小向的師父的施法相當規律,小向已經知道如何有效率地打倒她的師父。只需要在時刻$T_1, T_2, T_3,\dots, T_N$秒朝著師父發射裂空魔彈即可打敗他。當然,一點點小誤差是可容忍的,而可容忍的最大誤差是$X$秒。也就是說,只要在時刻$T_i-X$秒(含)到時刻$T_i$秒朝著師父發射裂空魔彈即可。

注意到發射裂空魔彈之前,小向必須要對該裂空魔彈注入魔力,而注入魔力所需的時間是1秒。只要注入魔力完畢,該顆裂空魔彈在之後會一直處於可發射的狀態。而小向所剩下來的體力以及魔力只能允許她同時最多做$K$件事。也就是說如果在某一時刻$T$小向對$A$顆裂空魔彈注入魔力並對師父發射$B$顆裂空魔彈,那麼$A+B\leq K$,而且那$B$顆裂空魔彈在時刻$T$以前已注入魔力完畢。

要知道,注入魔力和發射飛彈都不是一件簡單的事,所以在注入魔力或發射飛彈的那秒,小向無法同時支撐著防護罩。雖然希爾伯特會張開暫時的結界,但小向仍希望解開防護罩的時間愈短愈好。假設開始時間是時刻0秒而且小向有足夠多的裂空魔彈,小向解除防護罩的時間最少是幾秒?

例如下面範例測資2中,其中一種最佳策略為在0秒時注入魔力給4顆裂空魔彈,在1秒時注入魔力給最後一顆裂空魔彈,並在1, 3, 9秒發射一顆裂空魔彈,在7秒時發射2顆裂空魔彈。

Input Format

第一行有兩個正整數$N\leq 100, K\leq N$以及一個非負整數$X\leq 10^ 9$,分別代表需要發射的次數,小向同時可以做的事情個數以及誤差容許大小。
第二行有$N$個正整數$T_1, T_2, \dots, T_N\leq 10^ 9$,代表需要發射裂空魔彈的時機。

子任務(測資) 額外限制 分數
1 (0~4) $K=1, N\leq 3, X,T_i\leq 12$ 8
2 (0~14) $K=1$ 16
3 (15~24) $X=0$ 16
4 (25~34) $N\leq 50, X,T_i\leq 2000$ 28
5 (0~44) 32

Output Format

輸入一個正整數,代表解除防護罩的時間總長最小值。如果不存在一種成功的方案,輸出-1。

Sample Input

輸入範例1:
3 2 100
1 1 2

輸入範例2:
5 4 1
3 7 10 8 1

Sample Output

輸出範例1:
-1

輸出範例2:
5

Hints

小向將師父壓制在地,並用計畫中最後一顆裂空魔彈瞄準師父。
師父突然大聲喊道:
「等等!」
小向被驚嚇到而沒發射出這顆裂空魔彈。
「你真的進步了呢,小向。看來你已經通過了我給你的試煉了。」
「…?師父…不是要吸收我的魔力嗎?」
「才不是呢。」小向的師父語氣恢復平常,少了「喲」字,「這一切的一切只是為了讓你進步。仔細想想,你是不是比踏上旅途前,還進步了許多呢?」
「……別胡說了,這一定只是想讓我鬆懈的話術吧。」
「才不是呢。不然你想想,為什麼就算我知道我曾教過你破解紅色果實之術的法術,我還是使用紅色果實吸取你的魔力呢?為什麼我刻意使用市售的防禦道具呢?為什麼希爾伯特身上剛剛好帶著裂空魔彈呢?這一切都是我安排給你的試煉啊…小向!」
「……你別胡扯了!!!!!」
小向大聲一叫,將手上的裂空魔彈朝著師父射了過去。
小向的師父一個不留意,就被裂空魔彈近距離射穿了。
「……是啊,只要打倒師父,師父就不會再背叛我,也不會再胡扯了,我也不會莫名其妙被扯進這一連串的事件裡了……只要打倒…只要打倒就好…」
小向不留情地再拿出好幾顆裂空魔彈朝著師父射過去…
「這樣…應該就…打倒了吧…」
「啊…魔力就這樣留在那邊腐化好像有點浪費,就由我來吸收吧,吶,你說好不好啊,希爾伯特?」
小向把師父的魔力吸得一乾二淨,師父早就一動也不動地躺在地上。希爾伯特也被嚇得動彈不得:這和他一開始見到的小向相去甚遠。
「啊…還是說…乾脆也把你的魔力也吸走好了…」小向手一揮,希爾伯特的魔力也跟著被榨乾了。

於是,吸取了其它時空的自己、師父以及希爾伯特的魔力的小向,成為了魔法少女,或許是最強的魔法少女。為了變得更為強大,小向開始在世界各地旅行,尋找強大的意義。

「我為什麼要變強呢?」
「當然是為了打倒……」
「打倒誰呢?」
~~~~~~~~~~~~~~~~~全劇終~~~~~~~~~~~~~~~~~

Problem Source

Problem Set / Description by Paupière

Subtasks

No. Testdata Range Score
1 0~4 8
2 0~14 16
3 15~24 16
4 25~34 28
5 0~44 32

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 2 5
1 1000 65536 262144 1 2 5
2 1000 65536 262144 1 2 5
3 1000 65536 262144 1 2 5
4 1000 65536 262144 1 2 5
5 1000 65536 262144 2 5
6 1000 65536 262144 2 5
7 1000 65536 262144 2 5
8 1000 65536 262144 2 5
9 1000 65536 262144 2 5
10 1000 65536 262144 2 5
11 1000 65536 262144 2 5
12 1000 65536 262144 2 5
13 1000 65536 262144 2 5
14 1000 65536 262144 2 5
15 1000 65536 262144 3 5
16 1000 65536 262144 3 5
17 1000 65536 262144 3 5
18 1000 65536 262144 3 5
19 1000 65536 262144 3 5
20 1000 65536 262144 3 5
21 1000 65536 262144 3 5
22 1000 65536 262144 3 5
23 1000 65536 262144 3 5
24 1000 65536 262144 3 5
25 1000 65536 262144 4 5
26 1000 65536 262144 4 5
27 1000 65536 262144 4 5
28 1000 65536 262144 4 5
29 1000 65536 262144 4 5
30 1000 65536 262144 4 5
31 1000 65536 262144 4 5
32 1000 65536 262144 4 5
33 1000 65536 262144 4 5
34 1000 65536 262144 4 5
35 1000 65536 262144 5
36 1000 65536 262144 5
37 1000 65536 262144 5
38 1000 65536 262144 5
39 1000 65536 262144 5
40 1000 65536 262144 5
41 1000 65536 262144 5
42 1000 65536 262144 5
43 1000 65536 262144 5
44 1000 65536 262144 5