bzoj#P2385. [Ceoi2011]Hotel
[Ceoi2011]Hotel
题目描述
一个宾馆有 个房间和 个预订,每个房间有住过之后的维护费用 和最大入住人数 ,每个预订有收入 和人数 ,大房间的维护费用不会比小房间的低,问你最多接受 个预订的情况下的最大盈利。
输入格式
输出格式
样例输入
322
150 2
400 3
100 2
200 1
700 3
样例输出
400
数据规模与约定
对于 的数据,有 。
对于所有数据,保证 ,,。
一个宾馆有 n 个房间和 m个预订,每个房间有住过之后的维护费用 c 和最大入住人数 p,每个预订有收入 v 和人数 d,大房间的维护费用不会比小房间的低,问你最多接受 o 个预订的情况下的最大盈利。
322
150 2
400 3
100 2
200 1
700 3
400
对于 40% 的数据,有 n,m≤100。
对于所有数据,保证 1≤n,m≤5×105,1≤o≤min(n,m),1≤ci,pi,vj,dj≤109。