| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 64 MB | 0 | 0 | 0 | 0.000% |
You have been hired to build a lift system for a hotel!
The hotel has $k$ lifts, and initially you can choose which floors they are on. During the day there are $n$ requests, each characterized by a pair $(l, r)$. This means someone is on the $l$-th floor and wants to go to the $r$-th floor.
People don’t like waiting around, so we have the requirement to complete the requests sequentially. More formally, request number i must be completed before request number $i + 1$. The lifts are small and must be empty or carrying exactly one passenger at any given time. Also, every request can be completed by any of the lifts.
We want to build a smart system, so we want to minimize the total number of floors when lifts are travelling empty. More precisely, if a lift travels from floor $p$ to floor $q$ without a passenger, then we consider that it has travelled $|p − q|$ floors empty. We should note that the lifts can wait at the same floor for any amount of time, without incurring any additional cost.
Unfortunately, the hotel is old and the machines only have 64 MB of memory! However, we know you’re a great programmer, so this should be no issue for you.
Write a program lifts that, computes the optimal schedule that minimizes the total number of floors that the lifts are travelling empty.
The first line of the standard input contains the numbers $n$ and $k$. The next $n$ lines contain 2ドル$ numbers each - $(l, r)$ for the respective request.
On the single line of the standard output, print the minimum sum of floors where the lifts travel empty.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $n \le 22$ |
| 2 | 20 | $n \le 250$ |
| 3 | 10 | $n \le 600$ |
| 4 | 15 | $n \le 1250$ |
| 5 | 20 | $n \le 2500$ |
| 6 | 30 |
3 2 5 20 8 100 2 80
12
Lift 1ドル$ is initially on floor 5ドル$ and lift 2ドル$ is on floor 8ドル$.
Lift 1ドル$ travels 0ドル$ floors empty and carries the passenger to the 20ドル$th floor.
Lift 1ドル$ travels 12ドル$ floors empty and carries the passenger to the 100ドル$th floor.
Lift 2ドル$ travels 0ドル$ floors empty and carries the passenger to the 80ドル$th floor.
The total number of floors where the lifts travel empty is 0ドル + 12 + 0 = 12$.