#P18791. [KOI2026 二轮] 工厂
[KOI2026 二轮] 工厂
[KOI2026 二轮] 工厂(공장 / Factory)
题目描述
工厂从第 天夜间运行到第 天夜间,按时间先后分为
$$0\text{日夜间},1\text{日白天},1\text{日夜间},\ldots,T\text{日白天},T\text{日夜间}$$共 个时段。白天生产,夜间巡逻。
有 名应聘者。第 人的技能值为 、贡献值为 ,所有人的技能值互不相同。若雇用此人,他将参加第 天夜间、第 天白天、第 天夜间三个时段的工作,并获得基础工资 。基础工资按每名雇员总计支付一次。
每个时段,都将当时工作的所有雇员按技能值从小到大排序,再按排序顺序两两配对:第 人一组,第 人一组,依此类推。
所有工作必须成对进行,因此雇用方案必须使每一个时段的在岗人数都为偶数。允许某个时段没有人,此时不产生任何收益或夜间津贴。
一对雇员 ,若 :
- 白天生产时,产生收益 ,这个数可能为负;
- 夜间巡逻时,两人合计领取津贴 。
初始生产收益为 。总工资等于所雇用者的基础工资总和,加上所有夜间支付的津贴。
求“总生产收益减总工资”的最大值,并输出一组达到最大值的雇员名单。允许一个人也不雇用。
输入格式
第一行两个整数 。
接下来 行,每行四个整数 。
输出格式
第一行输出最大目标值。
第二行输出雇用人数 。
第三行输出 个雇员编号,顺序任意。若 ,可以输出空行,也可以省略第三行。多种最优名单均可接受。
样例 1
6 2
21 0 1 1
13 25 0 2
22 20 3 2
20 5 2 2
4 23 0 2
25 16 8 1
7
4
1 3 4 6
第 天白天的雇员为 ,收益 ;第 天白天的雇员为 ,收益 。三个夜间的津贴分别为 ,基础工资总和为 ,最终为 。注意:第 天白天和第 天夜间的配对可以不同。
样例 2
5 2
40 23 10 1
59 22 2 2
32 7 10 2
52 30 0 1
38 10 3 1
0
0
不雇用任何人即为最优。
样例 3
12 3
6 19 4 2
32 0 1 3
12 0 4 3
25 7 0 2
35 15 5 1
28 25 5 2
19 27 3 3
30 13 3 2
1 24 5 3
20 11 0 2
2 1 5 2
24 28 3 2
20
8
1 3 4 6 7 10 11 12
数据范围与子任务
所有输入均为整数。
- ;
- ;
- ;
- 所有 互不相同。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 13 | |
| 2 | 14 | |
| 3 | 20 | |
| 4 | 22 | 每一天 都至多有 名应聘者满足 |
| 5 | 31 | 无附加限制 |
满分 100 分。时限 1 秒,内存 1024 MiB。使用 SPJ 检查最优值和名单。