Problem 4883. -- CF311 Cats Transport

4883: CF311 Cats Transport

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 4  Solved: 0
[Submit][Status][Web Board]

Description

小S是农场主,他养了M只猫,雇了P位饲养员。农场中有一条笔直的路,路边有N座山,从1到N编号。第 i 座山与
第 i-1 座山之间的距离是 D_i。饲养员都住在1号山。有一天,猫出去玩。第 i 只猫去 H_i 号山玩,玩到时刻 T
_i 停止,然后在原地等饲养员来接。饲养员们必须回收所有的猫。每个饲养员沿着路从1号山走到N号山,把各座
山上已经在等待的猫全部接走。饲养员在路上行走需要时间,速度为1米/单位时间。饲养员在每座山上接猫的时间
可以忽略,可以携带的猫的数量为无穷大。例如有两座相距为1的山,一只猫在2号山玩,玩到时刻3开始等待。如
果饲养员从1号山在时刻2或3出发,那么他可以接到猫,猫的等待时间为0或1。而如果他于时刻1出发,那么他将于
时刻2经过2号山,不能接到当时仍在玩的猫。你的任务是规划每个饲养员从1号山出发的时间,使得所有猫等待时
间的总和尽量小。饲养员出发的时间可以为负。
数据范围:2≤N≤〖10〗^5,1≤M≤〖10〗^5,1≤P≤100。

Input

Output

HINT

请不要提交!

Source

[Submit][Status]