TopCoder

User's AC Ratio

66.7% (26/39)

Submission's AC Ratio

11.5% (95/829)

Tags

Description

你聽過希爾伯特的旅館嗎?

希爾伯特最近在他的旅館裡面建造了一個無限長且有無限層的書架,因為他無限的房客離開時常把書忘在房間裡,時間久了就留下了無限難以整理的書。
雖然這些書都已經編號好了,但整理無限本書仍然太累了,所以他決定先把其中的$N$本書放上書架,試試這個書架好不好用。這$N$本書編號為1~$N$,其中編號$i$的書寬度為$A_i$。

具體來說,他希望能把書放進書架上的某些層,使得每一層的書編號都要連續且照順序排。另外,希爾伯特希望一眼就看出這層放了什麼書,因此他要求如果編號$i$和編號$i+1$的書放在同一層,那麼它們之間要放一個寬度為$L_i$的隔板。

因為每一本書的寬度都不同,希爾伯特希望他放書能放整齊一點。具體來說,他希望每一層擺出來的寬度都盡量是$K$。所謂「盡量」的意思,就是如果某一層書擺出來的實際寬度(包含書與隔板的寬度)是$M$,定義這層的「混亂度」就是$|M-K|^ P$(其中$P$是正整數),那他希望總混亂度(有放書的每一層混亂度加起來)最小。

但是,希爾伯特看不出來要怎麼分層會最整齊。所以請你先告訴他,在所有可能的擺書方式中,總混亂度的最小值是多少。

Input Format

第一行有三個正整數$N, K, P$。
第二行有$N$個正整數$A_1, A_2,\cdots ,A_N$。
第三行有$N-1$個非負整數$L_1, L_2,\cdots ,L_{N-1}$。
這些數的意義請參考題目敘述。

對於所有的測資,$N\leq 10^ 6; K\leq 10^ 9; P\leq 20; A_i, L_i\leq 10^ 9$。
保證答案絕對不會超過$10^ {18}$。

子任務(測資) 額外限制 分數
1 (0~3) $N\leq 20$ 37
2 (0~7) $N\leq 300$ 8
3 (0~9) $N\leq 2500$ 34
4 (0~11) $N\leq 12000$ 21
5 (12~15) $N\leq 4\times 10^ 5,K\leq 200$ 33
6 (16~19) $P\leq 2$ 80
7 (16~23) $P\leq 4$ 72
8 (0~27) 無限制 15

Output Format

請輸出一個非負整數,代表所有可能的擺書方式中總混亂度的最小值。

Sample Input 1

8 9 2
3 3 2 1 2 9 5 2
3 5 1 4 6 0 1

Sample Output 1

2

Hints

範例測資中,編號1, 2擺一層(寬度9)、3~5擺一層(寬度10)、6擺一層(寬度9)、7, 8擺一層(寬度8)。此時總混亂度為$0^ 2+1^ 2+0^ 2+1^ 2=2$。

Problem Source

Problem set / Description by Yihda Yol
建國中學105學年度校隊補選pE

題目改編自NOI 2009

Subtasks

No. Testdata Range Score
1 0~3 37
2 0~7 8
3 0~9 34
4 0~11 21
5 12~15 33
6 16~19 80
7 16~23 72
8 0~27 15

Testdata and Limits

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