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

No. Testdata Range Score
1 0~10 8
2 11~20 14
3 21~32 9
4 33~44 32
5 45~56 37

Testdata and Limits

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