#P3248. [ioi2013]robots

    ID: 2433 传统题 2000ms 64MiB 尝试: 79 已通过: 30 难度: 7 上传者: 标签>难度分类提高+/省选-排序与序列处理二分答案贪心排序贪心堆贪心交换论证CF2300

[ioi2013]robots

[IOI2013] 机器人 · robots

题目描述

Marita 的弟弟把玩具散落在客厅里。第 ii 个玩具的重量为 WiW_i,体积为 SiS_i,共 TT 个玩具。Marita 有两种机器人。

  • AA 个弱机器人。第 ii 个弱机器人只能拿起重量严格小于 XiX_i 的玩具,玩具的体积不限。
  • BB 个小机器人。第 ii 个小机器人只能拿起体积严格小于 YiY_i 的玩具,玩具的重量不限。

每个机器人每分钟能收拾一个它能拿起的玩具,多个机器人可以同时工作。求收拾完所有玩具的最短时间,或者判断能否完成。

输入格式

第一行包含三个整数 A,B,TA,B,T。第二行包含 AA 个整数,依次给出弱机器人的重量限制 XiX_i。第三行包含 BB 个整数,依次给出小机器人的体积限制 YiY_i。若 A=0A=0 或 B=0B=0,相应的一行为空。

接下来 TT 行,每行两个整数 Wi,SiW_i,S_i,给出一个玩具的重量和体积。

输出格式

输出一个整数,表示收拾完所有玩具所需的最少分钟数。若无法收拾完,输出 -1。

样例 1

3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
3

玩具从 00 开始编号。

玩具编号 0 1 2 3 4 5 6 7 8 9
重量 4 8 2 7 1 5 3 8 7 10
体积 6 5 3 9 8 1 7 6 5

一种三分钟内完成的安排如下。表中的数字为玩具编号,空格表示该机器人当分钟不工作。

分钟 弱机器人 0 弱机器人 1 弱机器人 2 小机器人 0 小机器人 1
1 0 4 1 6 2
2 5 3 8
3 7 9

样例 2

2 1 3
2 5
2
3 1
5 3
2 2
-1
玩具编号 0 1 2
重量 3 5 2
体积 1 3

重量为 55、体积为 33 的玩具没有机器人能拿起。

数据规模与约定

1≤T≤1061\le T\le10^{6},0≤A,B≤500000\le A,B\le50000,1≤A+B1\le A+B,1≤Xi,Yi,Wi,Si≤2⋅1091\le X_i,Y_i,W_i,S_i\le2\cdot10^{9}。

原赛子任务 分值 附加限制
1 14 T=2T=2,A+B=2A+B=2
2 B=0B=0
3 25 T≤50T\le50,A+B≤50A+B\le50
4 37 T≤10000T\le10000,A+B≤1000A+B\le1000
5 10 无附加限制

原赛接口

原赛 C/C++ 提交包含 robots.h 并实现 int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])。四个数组从 00 开始编号,长度分别为 A,B,T,TA,B,T,T。Pascal 提交用 Robots 单元,数组元素及返回值使用 LongInt。函数返回所求的分钟数,无法完成时返回 -1。原赛的本地样例评测器从 robots.in 读取以上格式的数据。

IOI 2013 原赛题面 PDF