#P3248. [ioi2013]robots
[ioi2013]robots
[IOI2013] 机器人 · robots
题目描述
Marita 的弟弟把玩具散落在客厅里。第 个玩具的重量为 ,体积为 ,共 个玩具。Marita 有两种机器人。
- 个弱机器人。第 个弱机器人只能拿起重量严格小于 的玩具,玩具的体积不限。
- 个小机器人。第 个小机器人只能拿起体积严格小于 的玩具,玩具的重量不限。
每个机器人每分钟能收拾一个它能拿起的玩具,多个机器人可以同时工作。求收拾完所有玩具的最短时间,或者判断能否完成。
输入格式
第一行包含三个整数 。第二行包含 个整数,依次给出弱机器人的重量限制 。第三行包含 个整数,依次给出小机器人的体积限制 。若 或 ,相应的一行为空。
接下来 行,每行两个整数 ,给出一个玩具的重量和体积。
输出格式
输出一个整数,表示收拾完所有玩具所需的最少分钟数。若无法收拾完,输出 -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
玩具从 开始编号。
| 玩具编号 | 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 |
重量为 、体积为 的玩具没有机器人能拿起。
数据规模与约定
,,,。
| 原赛子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 14 | , |
| 2 | ||
| 3 | 25 | , |
| 4 | 37 | , |
| 5 | 10 | 无附加限制 |
原赛接口
原赛 C/C++ 提交包含 robots.h 并实现 int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])。四个数组从 开始编号,长度分别为 。Pascal 提交用 Robots 单元,数组元素及返回值使用 LongInt。函数返回所求的分钟数,无法完成时返回 -1。原赛的本地样例评测器从 robots.in 读取以上格式的数据。