P3644 [APIO2015] Palembang Bridges

An east–west Mu Xi River divides Palembang City into two parts, region $A$ and region $B$. Exactly $1000000001$ buildings are built along each bank. Along each bank, buildings are numbered from $0$ to $1000000000$. Every pair of adjacent buildings is $1$ unit apart, and the river is $1$ unit wide. In region $A$, building $i$ is directly opposite building $i$ in region $B$. There are $N$ residents in the city. The $i$-th resident’s home is at building $S_i$ in region $P_i$, and their office is at building $T_i$ in region $Q_i$. A resident’s home and office may lie on different banks of the river, in which case they must take a boat to commute, which many people find inconvenient. To allow residents to drive to work, the government decides to build at most $K$ bridges across the river. Due to technical reasons, each bridge must connect the two banks exactly, be strictly perpendicular to the river, and no two bridges may intersect. After the government builds at most $K$ bridges, let $D_i$ be the shortest driving distance from the $i$-th resident’s home to their office. Help the government build the bridges to minimize $D_1 + D_2 + \cdots + D_N$.

The first line contains two positive integers $K$ and $N$, the maximum number of bridges and the number of residents. Each of the next $N$ lines contains four parameters: $P_i$, $S_i$, $Q_i$, and $T_i$, meaning that the $i$-th resident’s home is at building $S_i$ in region $P_i$, and their office is at building $T_i$ in region $Q_i$.

Output a single line containing one integer, the minimum value of $D_1 + D_2 + \cdots + D_N$.

Constraints For all testdata, it is guaranteed that $P_i$ and $Q_i$ are one of the characters "A" and "B", $0 \leq S_i, T_i \leq 1000000000$, and there may be more than $1$ home or office (or both) in the same building. Subtask 1 (8 points) $K = 1$ $1 \leq N \leq 1000$. Subtask 2 (14 points) $K = 1$ $1 \leq N \leq 100000$. Subtask 3 (9 points) $K = 2$ $1 \leq N \leq 100$. Subtask 4 (32 points) $K = 2$ $1 \leq N \leq 1000$. Subtask 5 (37 points) $K = 2$ $1 \leq N \leq 100000$. Translated by ChatGPT 5