TopCoder

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

User's AC Ratio

92.3% (12/13)

Submission's AC Ratio

21.1% (19/90)

Description

巨港市被穆西河分成兩區。假設這兩區分別是A區和B區,每區分別都有1,000,000,001棟建築分布在河的兩邊,方便起見編號為0到1,000,000,000。任兩棟相鄰的建築距離為1單位。河寬也是1單位。A區中第i棟建築恰好位於B區中第i棟建築的對面。有$N$個市民住在城市中。第i位市民的房子在$P_i$區第$S_i$棟建築,而他的公司在$Q_i$區第$T_i$棟建築。如果某個市民從他房子到他公司必須經過一條河,那麼他就必須要搭船。這非常不方便,所以政府決定要蓋最多$K$座橫跨河面的橋讓市民們可以只要開車不用搭船就可以去工作。每座橋一定要連結兩個在不同側的建築並與河垂直。除此之外,橋之間不能覆蓋彼此。假設$D_i$是第$i$位市民從他家開車到他的公司所需要開的最短距離,請幫助政府建橋使得$D_1+D_2+\dots+D_N$最小。

Input Format

第一行包含兩個整數$K,N$。接下來的$N$行中每一行都有四個代碼$P_i,S_i,Q_i,T_i$。

對於所有測資,$P_i,Q_i$是字元A,B中的一者,$0\leq S_1,T_i\leq 1000,000,000$,且可以有超過一個房子或公司(或兩者)同時在同一棟建築物裡。
第一組測資佔分8分,且$K=1,1\leq N\leq 1,000$。
第二組測資佔分14分,且$K=1,1\leq N\leq 100,000$。
第三組測資佔分9分,且$K=2,1\leq N\leq 100$。
第四組測資佔分32分,且$K=2,1\leq N\leq 1,000$。
第五組測資佔分37分,且$K=2,1\leq N\leq 100,000$。

Output Format

請輸出一行包含距離總和的最小值。

Sample Input

Sample Input 1
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

Sample Input 2
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

Sample Output

Sample Output 1
24

Sample Output 2
22

Hints

第一個範例測資中,在編號4的建築物之間蓋一座橋是其中一個最佳策略。
第二個範例測資中,在編號2和6的建築物之間蓋橋是其中一個最佳策略。

Problem Source

2015 APIO pC.

Subtasks

For Testdata: 0 ~ 10, Score: 8
For Testdata: 11 ~ 20, Score: 14
For Testdata: 21 ~ 32, Score: 9
For Testdata: 33 ~ 44, Score: 32
For Testdata: 45 ~ 56, Score: 37
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 262144 262144
1 2000 262144 262144
2 2000 262144 262144
3 2000 262144 262144
4 2000 262144 262144
5 2000 262144 262144
6 2000 262144 262144
7 2000 262144 262144
8 2000 262144 262144
9 2000 262144 262144
10 2000 262144 262144
11 2000 262144 262144
12 2000 262144 262144
13 2000 262144 262144
14 2000 262144 262144
15 2000 262144 262144
16 2000 262144 262144
17 2000 262144 262144
18 2000 262144 262144
19 2000 262144 262144
20 2000 262144 262144
21 2000 262144 262144
22 2000 262144 262144
23 2000 262144 262144
24 2000 262144 262144
25 2000 262144 262144
26 2000 262144 262144
27 2000 262144 262144
28 2000 262144 262144
29 2000 262144 262144
30 2000 262144 262144
31 2000 262144 262144
32 2000 262144 262144
33 2000 262144 262144
34 2000 262144 262144
35 2000 262144 262144
36 2000 262144 262144
37 2000 262144 262144
38 2000 262144 262144
39 2000 262144 262144
40 2000 262144 262144
41 2000 262144 262144
42 2000 262144 262144
43 2000 262144 262144
44 2000 262144 262144
45 2000 262144 262144
46 2000 262144 262144
47 2000 262144 262144
48 2000 262144 262144
49 2000 262144 262144
50 2000 262144 262144
51 2000 262144 262144
52 2000 262144 262144
53 2000 262144 262144
54 2000 262144 262144
55 2000 262144 262144
56 2000 262144 262144