DMPG '16 S3 - The Faster Way

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

The Toronto Transit Commission is staking their image on being The Faster Way to get around Toronto, with a reputation for speedily getting commuters to their destination.

A particular bus route consisting of N stops starts at station 0 and ends at station N-1. At present, there are M passengers waiting for a bus in station 0, with the i-th commuter wishing to get off at stop S_i. Conveniently, it turns out that each passenger wants to get off at a different station.

As station manager at station 0, your job is to get them to their destinations as quickly as possible.

Two buses have arrived, a regular bus and a Rocket bus. The regular bus will stop at any station on the route as long as a passenger wishes to get off. The Rocket bus will only stop at R of the N stops, and only if someone wishes to disembark. Whenever a bus stops, it spends 1 minute letting people get off. These are also really fast buses we are talking about, such that it takes no time for a bus to move from one station to the next.

You would like to minimize the total amount of time passengers spend riding The Faster Way (lest it be branded The Slower Way) by optimally assigning passengers at station 0 to either the regular bus or the Rocket. How much time will the passengers have spent cumulatively before they reach their destinations, if you do your job properly?


For all cases, 1 \le M \le N and 0 \le R \le N.

Subtask 1 [20%]

1 \le N \le 10

Subtask 2 [30%]

1 \le N \le 20

Subtask 3 [50%]

1 \le N \le 100\,000

Input Specification

The first line of input will contain the integers N, R and M.
The next line of input will contain R integers in the range 0\cdots N-1, representing which of the N stops the Rocket stops at. The stops will be pairwise distinct.
The last line of input will contain M integers, with the i-th representing S_i. These values will be pairwise distinct.

Output Specification

The minimum cumulative time taken by commuters to get to their destinations.

Sample Input

3 2 2
1 2
1 2

Sample Output



Assign the first passenger to the regular bus, and the second to the Rocket bus. The total amount of time they will spend together is 2 minutes, and they will both be off at their stations after 1 minute.


  • 0
    minecraftyugi  commented on April 23, 2017, 12:44 a.m.

    In the input, the stops on the route go up to N, even though the question specifications said it would only be up to N - 1.