#P18791. [KOI2026 二轮] 工厂

[KOI2026 二轮] 工厂

[KOI2026 二轮] 工厂(공장 / Factory)

题目描述

工厂从第 00 天夜间运行到第 TT 天夜间,按时间先后分为

$$0\text{日夜间},1\text{日白天},1\text{日夜间},\ldots,T\text{日白天},T\text{日夜间}$$

共 2T+12T+1 个时段。白天生产,夜间巡逻。

有 NN 名应聘者。第 ii 人的技能值为 AiA_i、贡献值为 BiB_i,所有人的技能值互不相同。若雇用此人,他将参加第 Di−1D_i-1 天夜间、第 DiD_i 天白天、第 DiD_i 天夜间三个时段的工作,并获得基础工资 CiC_i。基础工资按每名雇员总计支付一次。

每个时段,都将当时工作的所有雇员按技能值从小到大排序,再按排序顺序两两配对:第 1,21,2 人一组,第 3,43,4 人一组,依此类推。

所有工作必须成对进行,因此雇用方案必须使每一个时段的在岗人数都为偶数。允许某个时段没有人,此时不产生任何收益或夜间津贴。

一对雇员 x,yx,y,若 Ax>AyA_x>A_y:

  • 白天生产时,产生收益 Bx−ByB_x-B_y,这个数可能为负;
  • 夜间巡逻时,两人合计领取津贴 Ax−AyA_x-A_y。

初始生产收益为 00。总工资等于所雇用者的基础工资总和,加上所有夜间支付的津贴。

求“总生产收益减总工资”的最大值,并输出一组达到最大值的雇员名单。允许一个人也不雇用。

输入格式

第一行两个整数 N,TN,T。

接下来 NN 行,每行四个整数 Ai,Bi,Ci,DiA_i,B_i,C_i,D_i。

输出格式

第一行输出最大目标值。

第二行输出雇用人数 KK。

第三行输出 KK 个雇员编号,顺序任意。若 K=0K=0,可以输出空行,也可以省略第三行。多种最优名单均可接受。

样例 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

第 11 天白天的雇员为 1,61,6,收益 1616;第 22 天白天的雇员为 4,34,3,收益 1515。三个夜间的津贴分别为 4,4,24,4,2,基础工资总和为 1414,最终为 31−10−14=731-10-14=7。注意:第 11 天白天和第 11 天夜间的配对可以不同。

样例 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≤T≤N≤5001\le T\le N\le500;
  • 0≤Ai,Bi,Ci≤10000\le A_i,B_i,C_i\le1000;
  • 1≤Di≤T1\le D_i\le T;
  • 所有 AiA_i 互不相同。
子任务 分值 附加限制
1 13 N≤20N\le20
2 14 T=1T=1
3 20 T≤10T\le10
4 22 每一天 dd 都至多有 88 名应聘者满足 Di=dD_i=d
5 31 无附加限制

满分 100 分。时限 1 秒,内存 1024 MiB。使用 SPJ 检查最优值和名单。