APIO '15 P3 - Palembang Bridges - DMOJ: Modern Online Judge

APIO '15 P3 - Palembang Bridges

Points: 20 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem types

The city of Palembang is separated by Musi River into two zones. Let's call them zone $A$ $A$ and zone $B$ $B$ .

Each zone consists of exactly $1\,000\,000\,001$ $1 000 000 001$ buildings along the respective side of the river, conveniently numbered $0$ $0$ through $1\,000\,000\,000$ $1 000 000 000$ . The distance between every pair of adjacent buildings is $1$ $1$ unit of distance. The width of the river is $1$ $1$ unit of distance as well. Building $i$ $i$ in zone $A$ $A$ is located on exactly the opposite side of building $i$ $i$ in zone $B$ $B$ .

$N$ $N$ citizens live and work in the city. Citizen $i$ $i$ 's house is in zone $P_i$ $P_{i}$ , building $S_i$ $S_{i}$ , while his office is in zone $Q_i$ $Q_{i}$ , building $T_i$ $T_{i}$ . If a citizen must cross the river to go from his house to his office, he must take a boat. This has been uncomfortable, so the government has decided to build at most $K$ $K$ bridges over the river, so that the citizens can go to work by driving. Each bridge must be built exactly between two opposite buildings in the two zones. The bridges must be strictly perpendicular to the river. The bridges must not overlap each other.

Let $D_i$ $D_{i}$ be the minimum distance citizen $i$ $i$ has to drive to go from his house to his office, after the government has built at most $K$ $K$ bridges. Help the government build the bridges in such a way that the sum $D_1 + D_2 + \dots + D_N$ $D_{1} + D_{2} + \dots + D_{N}$ is minimized.

Input Specification

The first line contains two integers $K$ $K$ and $N$ $N$ . Each of the next $N$ $N$ lines contains four tokens $P_i$ $P_{i}$ , $S_i$ $S_{i}$ , $Q_i$ $Q_{i}$ , and $T_i$ $T_{i}$ .

Output Specification

A single line containing the minimum sum of the distances.

Sample Input 1

Copy

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

Sample Output 1

Copy

Sample Input 2

Copy

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

Sample Output 2

Copy

Explanation

This is the illustration for both sample inputs.

Here is one possible solution for sample input 1. The pink stripe segment denotes a bridge.

And this is a possible solution for sample input 2:

Subtasks

For each subtask,

$P_i$ $P_{i}$ and $Q_i$ $Q_{i}$ will be either a character A or a character B.
$0 \le S_i, T_i \le 1\,000\,000\,000$ $0 \leq S_{i}, T_{i} \leq 1 000 000 000$
More than one house or office (or combination of both) can be located in the same building.

Subtask 1 (8 points)

$K=1$ $K = 1$
$1 \le N \le 1\,000$ $1 \leq N \leq 1 000$

Subtask 2 (14 points)

$K = 1$ $K = 1$
$1 \le N \le 100\,000$ $1 \leq N \leq 100 000$

Subtask 3 (9 points)

$K=2$ $K = 2$
$1 \le N \le 100$ $1 \leq N \leq 100$

Subtask 4 (32 points)

$K=2$ $K = 2$
$1 \le N \le 1\,000$ $1 \leq N \leq 1 000$

Subtask 5 (37 points)

$K=2$ $K = 2$
$1 \le N \le 100\,000$ $1 \leq N \leq 100 000$

Comments

2

404 commented on June 5, 2022, 9:04 p.m. ← edited →

$K$ $K$ only goes up to $2$ $2$ ... i wasted so much time thinking it went up to $100\,000$ $100 000$