#P13572. [ICPC 2023 Yokohama R] Task Assignment to Two Employees

    ID: 12772 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-相邻交换确定比较规则贡献法最小割建模Dinic最大流最小割定理当前弧优化

[ICPC 2023 Yokohama R] Task Assignment to Two Employees

题目描述

Hanako 是一家拥有两名员工的小公司的 CEO。目前她有一些任务,希望通过让员工完成任务来赚取利润。员工可以通过任务提升技能,而更高的技能可以从同一任务中获得更大的利润。因此,以适当的顺序将任务分配给合适的员工,对于最大化总利润至关重要。

对于员工 ii 和任务 jj 的每一对组合 (i,j)(i, j),定义了两个非负整数 vi,jv_{i,j} 和 si,js_{i,j}。其中,vi,jv_{i,j} 是任务适配度,si,js_{i,j} 是技能成长量。当技能点为 pp 的员工 ii 完成了任务 jj 时,会获得 p×vi,jp \times v_{i,j} 的利润,并且他的技能点增加至 p+si,jp + s_{i,j}。初始时,两名员工的技能点均为 p0p_0。

注意,技能点是独立的,一名员工完成任务不会改变另一名员工的技能点。每个任务只能由一名员工完成一次。任务的执行顺序可以任意选择。

输入格式

输入由单个测试用例组成,格式如下。

$$\begin{aligned} &n \ p_0\\ &s_{1,1} \ \cdots \ s_{1,n}\\ &s_{2,1} \ \cdots \ s_{2,n}\\ &v_{1,1} \ \cdots \ v_{1,n}\\ &v_{2,1} \ \cdots \ v_{2,n}\\ \end{aligned}$$

所有输入项均为非负整数。任务数量 nn 满足 1≤n≤1001 \leq n \leq 100。初始技能点 p0p_0 满足 0≤p0≤1080 \leq p_0 \leq 10^8。每个 si,js_{i,j} 是员工 ii 完成任务 jj 后的技能成长量,满足 0≤si,j≤1060 \leq s_{i,j} \leq 10^6。每个 vi,jv_{i,j} 是员工 ii 对任务 jj 的任务适配度,满足 0≤vi,j≤1060 \leq v_{i,j} \leq 10^6。

输出格式

在一行中输出可能的最大总利润。

输入输出样例 #1

输入 #1

4 0
10000 1 1 1
1 1 10000 1
1 10000 1 1
1 1 1 10000

输出 #1

200000000

输入输出样例 #2

输入 #2

3 1
1 1 1
2 2 2
2 2 2
1 1 1

输出 #2

12

说明/提示

翻译由 DeepSeek V3 完成