P4698 [CEOI2011]Hotel

    • 36通过
    • 71提交
  • 题目提供者 和泉正宗
  • 评测方式 云端评测
  • 标签 2011 高性能
  • 难度 省选/NOI-
  • 时空限制 4000ms / 64MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    你经营着一家旅馆,这家旅馆有 $n$ 个房间,每个房间有维护费用和容量。其中第 $i$ 个房间的维护费用为 $c_i$,容量为 $p_i$ 人。

    现在有 $m$ 个订单,每个订单有两个参数:$v_i,d_i$ ,其中 $v_i$ 表示这个订单支付的租金,$d_i$​​ 表示人数。

    你现在得要合理选择一些订单,并放弃其他订单,使得每个选择的订单被安排在同一间房间内,且人数不超过这个房间的容量限制。当然,两个不同的订单也不能被安排在同一间房间内。

    现在你想要知道,在最多选出 $o$ 个订单时的最大收益。一个方案的收益的定义为,选出的订单的租金和,减去选出的房间的维护费用和。

    输入输出格式

    输入格式:

    第一行三个空格隔开的整数 $n,m,o$ 。

    接下来 $n$ 行,每行两个空格隔开的整数 $c_i,p_i$。

    接下来 $m$ 行,每行两个空格隔开的整数 $v_i,d_i$。

    输出格式:

    一行一个整数表示最大收益。注意答案可能很大。

    输入输出样例

    输入样例#1: 复制
    3 2 2
    150 2
    400 3
    100 2
    200 1
    700 3
    输出样例#1: 复制
    400

    说明

    样例 $1$ 解释

    可以将第一个订单安排至第三个房间,将第二个订单安排至第二个房间。

    数据范围

    对于 $100\%$ 的数据,有 $1\le n,m\le 500\ 000;1\le o\le \min(n,m);1\le c_i,p_i,v_i,d_i\le 10^9$,保证 $\forall 1\le i,j\le n$,若 $p_i\lt p_j$,则 $c_i\le c_j$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。