2018年1月USACO美国计算机奥赛白金级题1

USACO 2018 January Contest, Platinum Problem 1. Lifeguards

2018年1月USACO美国计算机奥赛白金级题1

Farmer John has opened a swimming pool for his cows, figuring it will help them relax and produce more milk.

To ensure safety, he hires NN cows as lifeguards, each of which has a shift that covers some contiguous interval of time during the day. For simplicity, the pool is open from time 00 until time 109109 on a daily basis, so each shift can be described by two integers, giving the time at which a cow starts and ends her shift. For example, a lifeguard starting at time t=4t=4 and ending at time t=7t=7 covers three units of time (note that the endpoints are “points” in time).

Unfortunately, Farmer John hired KK more lifeguards than he has the funds to support. Given that he must fire exactly KKlifeguards, what is the maximum amount of time that can still be covered by the shifts of the remaining lifeguards? An interval of time is covered if at least one lifeguard is present.

INPUT FORMAT (file lifeguards.in):

The first line of input contains NN and KK (KN100,000,1K100K≤N≤100,000,1≤K≤100). Each of the next NN lines describes a lifeguard in terms of two integers in the range 01090…109, giving the starting and ending point of a lifeguard’s shift. All such endpoints are distinct. Shifts of different lifeguards might overlap.

OUTPUT FORMAT (file lifeguards.out):

Please write a single number, giving the maximum amount of time that can still be covered if Farmer John fires KK lifeguards.

SAMPLE INPUT:

3 2
1 8
7 15
2 14

SAMPLE OUTPUT:

12

In this example, FJ should fire the lifeguards covering 181…8 and 7157…15.

 

USACO辅导资料/课程辅导咨询

翰林学院AP课程辅导AP真题下载

微信 linstitute4