Problem : 396 - Rabbit Rush

Problem Statistics

Solved Member: 15　　Submission: 90　　User Tried: 16

Statement:

你玩過 Rabbit Rush 嗎？這是一個輕鬆有趣的解謎遊戲。某天你受到了這個遊戲第一個關卡的啟發，也決定來做一個類似的遊戲。

遊戲由 N 個房子組成，分別由 1 標號到 N，並且第 i 個房子裡住著 C_i 隻兔子。玩家可以用滑鼠在房子之間拖曳來讓兔子移動到別的房子；每次滑鼠拖曳可以經過很多個房子，並且你用一個特殊的方法來計算每次拖曳的得分。

例如玩家用滑鼠依序經過兔子數量 1,9,3,7 的房子，那麼前面房子裡的兔子(共 1+9+3=13 隻)會移動到原本 7 隻兔子的房子。而這一次移動的得分為這個數列兩相鄰數字差的總和，即 |1-9| + |9-3| + |3-7| = 18。

但對如此簡單的遊戲你仍然不滿足，於是你又增加了幾條規則：
● 玩家總共要做 K 次拖曳的動作，並且這 K 次的拖曳必須包含所有房子，而這場遊戲的總得分就是每次拖曳的得分總和
● 一場遊戲中，如果一個房子之前被滑鼠拖過，那麼之後的拖曳就不會包含這個房子
● 每場玩完後會開啟一場新的遊戲，這場遊戲會比上一場遊戲少恰好一間房子，且其他房子兔子數量相同

你想知道每一場遊戲裡，玩家根據上面的規則玩至少會得到幾分？

Input:Output:

每筆測資第一行有三個數字 N,K,Q，依序代表房子數目、拖曳的次數，以及會有幾個房子消失。
第二行有 N 個整數 C₁, C₂, ..., C_N，分別代表每個房子的兔子數量。
接下來有 Q 行，每行一個整數 X_i，代表這場遊戲兔子隻數 X_i 的房子消失了。

0 ≤ C_i ≤ 200000
1 ≤ N,K ≤ 200000
0 ≤ Q ≤ 200000
K ≤ N-Q
任意兩間房子的兔子數量都不相等，並且每個房子最多被刪除一次，不會刪除不存在的房子

30%的測試資料： K = 1, Q = 0
50%的測試資料： Q ≤ 2

第一行請輸出一個數字，代表最剛開始的遊戲最小得分。
接下來請輸出 Q 行，每行一個數字，依序代表每一間房子消失以後的最小得分。

Sample Input:Sample Output:

SAMPLE 1：
5 4 0
1 9 3 7 4

SAMPLE 2：
4 2 2
6 5 10 2
10
6

SAMPLE 1：
1

SAMPLE 2：
4
1
0

HINT:

SAMPLE 2的解釋：

第一場遊戲每間房子的兔子數量為 6,5,10,2
第一次移動依序經過 2,5,6，第二次移動只經過 10。得分為 |2-5|+|5-6|=4。

第二場少了 10 隻兔子的房子，剩下的房子兔子數量為 2,5,6。
第一次移動依序經過 6,5，第二次移動經過 2。得分為 |5-6| = 1。

第三場少了 6 隻兔子的房子，剩下的房子兔子數量為 2,5。
第一次移動經過 2，第二次移動經過 5，得分為 0。

Source:

104資奧校內初選

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	500ms	262144kb
0-2	500ms	262144kb
1-1	500ms	262144kb	10
1-2	500ms	262144kb
1-3	500ms	262144kb
1-4	500ms	262144kb
1-5	500ms	262144kb
2-1	500ms	262144kb	10
2-2	500ms	262144kb
2-3	500ms	262144kb
2-4	500ms	262144kb
2-5	500ms	262144kb
3-1	500ms	262144kb	10
3-2	500ms	262144kb
3-3	500ms	262144kb
3-4	500ms	262144kb
3-5	500ms	262144kb
4-1	500ms	262144kb	10
4-2	500ms	262144kb
4-3	500ms	262144kb
4-4	500ms	262144kb
4-5	500ms	262144kb
5-1	500ms	262144kb	10
5-2	500ms	262144kb
5-3	500ms	262144kb
5-4	500ms	262144kb
5-5	500ms	262144kb
6-1	500ms	262144kb	10
6-2	500ms	262144kb
6-3	500ms	262144kb
6-4	2000ms	262144kb
6-5	2000ms	262144kb
7-1	500ms	262144kb	10
7-2	500ms	262144kb
7-3	500ms	262144kb
7-4	2000ms	262144kb
7-5	2000ms	262144kb
8-1	500ms	262144kb	10
8-2	500ms	262144kb
8-3	500ms	262144kb
8-4	2000ms	262144kb
8-5	2000ms	262144kb
9-1	500ms	262144kb	10
9-2	500ms	262144kb
9-3	500ms	262144kb
9-4	2000ms	262144kb
9-5	2000ms	262144kb
10-1	500ms	262144kb	10
10-2	500ms	262144kb
10-3	500ms	262144kb
10-4	2000ms	262144kb
10-5	2000ms	262144kb