A22539.工序安排 Job Processing

提高+/省选-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

一家工厂的流水线正在生产一种产品,这需要两步操作:操作机器 AA 和操作机器 BB。每个操作只有一些机器能够完成。


图片解释:第一行为输入容器的内容。第二行为A机器工作方式。第三行为中间容器的内容。第四行为B机器工作方式。第四行输出最终成果。

上图显示了按照下述方式工作的流水线的组织形式。AA 型机器从输入库接受工件,对其施加操作 AA,得到的中间产品存放在缓冲库。BB 型机器从缓冲库接受中间产品,对其施加操作 BB,得到的最终产品存放在输出库。所有的机器平行并且独立地工作,每个库的容量没有限制。每台机器的工作效率可能不同,一台机器完成一次操作需要一定的时间。

给出每台机器完成一次操作的时间,计算完成 AA 操作的时间总和的最小值,和完成 BB 操作的时间总和的最小值。

注:

  1. 机器在一次操作中干掉一个工件;

  2. 时间总和的意思是最晚时间点。

输入格式

第一行:三个用空格分开的整数:NN,工件数量(1N10001\leq N\leq1000);M1M_1AA 型机器的数量(1M1301\leq M_1\leq30);M2M_2BB 型机器的数量 (1M2301\leq M_2\leq30)。

第二行:M1M_1 个整数,表示 AA 型机器完成一次操作的时间;接着是 M2M_2 个整数,BB 型机器完成一次操作的时间。

输出格式

只有一行。输出两个整数:完成所有 AA 操作的时间总和的最小值,和完成所有 BB 操作的时间总和的最小值(AA 操作必须在 BB 操作之前完成)。

输入输出样例

  • 输入#1

    5 2 3
    1 1 3 1 4

    输出#1

    3 5

说明/提示

首页