VM7WC '15 #3 Gold - Pollos

View as PDF

Submit solution

Points: 12
Time limit: 1.4s
Memory limit: 64M

Problem type

Gustavo Fring is a kingpin for the sale and production of math. His restaurant chain, Los Pollos Hermathos is secretly a series of locations in his distribution network. He has N restaurants in his distribution chain, which are arranged along a highway at distinct positions.

Each restaurant has a position on the highway, p_i, which represents its distance from position 0 and a value f_i (f_i \in \{0,1\}). If f_i = 1, the restaurant is said to be fringy. Otherwise it is regular. In addition to the N restaurants, Gus has a math lab at position 0 on the highway.

Gus wants to send a truck from his math lab at position 0 to the last restaurant in his distribution chain. The truck has a fuel capacity F and can only travel a distance of F before it must stop at a restaurant and refuel (assume the truck starts with a full tank of fuel at the beginning). The driver also has the choice to simply drive by a restaurant. However, the truck must stop at all fringy restaurants so the driver can do math. Fring also wants the truck to stop at most K restaurants (including the last restaurant, but not including the math lab) in order to increase the efficiency of his distribution network.

Help Fring calculate the minimum fuel capacity the truck needs so that it will be able to reach the last restaurant while stopping at most K times.

Input Specification

The first line of input will contain two space-separated integers N (1 \le N \le 100\,000) and K (1 \le K \le N).

The next N lines will contain two space-separated integers, p_i (1 \le p_i \le 1\,000\,000\,000) and f_i, describing each restaurant in the chain. The restaurants will be given in increasing order of position. The math lab is at position 0 and will not appear in the input.

Output Specification

Print a single integer, the minimum value of F, the fuel capacity of the truck, so that the truck needs to stop at most K times. If the trip is not possible, print DEA Bust!.

Sample Input 1

5 3
10 0
15 1
19 0
22 0
25 0

Sample Output 1


Explanation for Sample Output 1

With a fuel capacity of 10, the truck can stop at locations 10, 15, and 25, stopping only 3 times, thus satisfying Fring's limit.

Sample Input 2

4 2
1 1
2 1
3 1
4 1

Sample Output 2

DEA Bust!

Explanation for Sample Output 2

The truck must visit all 4 restaurants since they are all fringy, but he is only allowed to stop twice. Therefore there is no solution to this test case.


  • 2
    bobhob314  commented on Jan. 22, 2015, 8:35 p.m.

    ;o I loved your references to everybody's hit zombie (or should I say "walker") show, The Walking Dead! Thanks for another smash hit contest thorthugnasty!