P3837 [IOI 2017] Wiring

This is a library problem. This problem supports only C++ languages. You do not need to include the header file `wiring.h` when submitting, but you must include the `vector` header and declare the function `long long min_total_length(std::vector r, std::vector b)` at the beginning of your program. Due to an indescribable bug, submitting with C++14 (GCC9) will cause CE. Please do not use it.

Maryam is an electrical engineer. She is designing a wiring plan for a communication tower. There are connectors placed at various heights on this tower. A wire can be used to connect any two connectors. Each connector may be connected to any number of wires. There are two types of connectors: red connectors and blue connectors. For convenience, the tower is regarded as a straight line, and the red and blue connectors are located at some non-negative integer coordinates on this line. The length of a wire is the distance between the two connectors it connects. Your task is to help Maryam find a wiring plan that satisfies the following: 1. Each connector has at least one wire connected to a connector of the opposite color. 2. The total length of the wires is minimized. Implementation details: You need to implement the following subroutine: `long long min_total_length(std::vector r, std::vector b)` - $r$: an array of length $n$, containing the positions of all red connectors in ascending order. - $b$: an array of length $m$, containing the positions of all blue connectors in ascending order. - This subroutine should return the minimal total length of wires among all valid wirings. - Note that the return type of this subroutine is `long long`. Constraints: - $1 \leqslant n,m \leqslant 100000$. - $0 \leqslant r[i] \leqslant 10^9$ (for all $0 \leqslant i \leqslant n-1$). - $0 \leqslant b[i] \leqslant 10^9$ (for all $0 \leqslant i \leqslant m-1$). - The arrays $r$ and $b$ are already sorted in ascending order. - All $n+m$ values in $r$ and $b$ are distinct. Subtasks: 1. ($7$ points) $n,m\leqslant 200$. 2. ($13$ points) All red connector positions are smaller than any blue connector position. 3. ($10$ points) In every $7$ consecutive connectors, there is at least one red connector and one blue connector. 4. ($25$ points) All connectors have distinct positions in the range $[1,n+m]$. 5. ($45$ points) No additional constraints.

You need to implement the subroutine described above.

Return a `long long` value.

Sample function call: `min_total_length([1, 2, 3, 7], [0, 4, 5, 9, 10])` The following figure illustrates the sample data.  - The tower is drawn horizontally. - Because the statement is printed in black and white, red connectors are drawn darker, and blue connectors lighter. - There are $4$ red connectors at positions $1, 2, 3$, and $7$. - There are $5$ blue connectors at positions $0, 4, 5, 9$, and $10$. - The optimal total wire length is $1+2+2+2+3=10$, so the subroutine should return $10$. - Note that there are two wires incident to the connector at position $7$. Translated by ChatGPT 5