P2488 [SDOI2011] Work Assignment

Your company has received a batch of orders. The orders require your company to provide $n$ types of products, numbered $1 \sim n$, where $C_i$ units of type $i$ are needed. The company has $m$ employees, numbered $1 \sim m$. The types of products that employees can make differ. Each product must be made entirely by a single employee; it is not allowed to have one employee make some parts and then pass it to another employee to continue. We use an $m \times n$ matrix $A$ consisting of $0$ and $1$ to describe which products each employee can make. The rows and columns of the matrix are numbered $1 \sim m$ and $1 \sim n$, respectively. $A_i,j$ being $1$ means employee $i$ can make product $j$, and $0$ means employee $i$ cannot make product $j$. If the company assigns too much work to an employee, the employee will become unhappy. We use an anger value to describe an employee’s mood. A higher anger value means the employee is more unhappy, and a lower anger value means the employee is happier. There is a functional relationship between an employee’s anger value and the number of products assigned to them. Since employees have different endurance, these functions differ between employees. For employee $i$, the function between their anger value and the number of products has $S_i+1$ segments. When they make the $1 \sim T_{i,1}$-th products, each product increases their anger by $W_{i,1}$. When they make the $(T_{i,1}+1) \sim T_{i,2}$-th products, each product increases their anger by $W_{i,2}$, and so on. For convenience, let $T_{i,0}=0, T_{i,s_{i+1}}=+\infty$. Then when they make the $(T_{i,j-1}+1) \sim T_{i,j}$-th products, each product increases their anger by $W_{i,j}$, $1 \le j \le S_i+1$. Your task is to design an assignment plan for the products so that the order requirements are satisfied, and the sum of anger values of all employees is minimized. Since we do not want to use a Special Judge, and to give contestants more time for the other two problems, you only need to output the minimal sum of anger values.

The first line contains two positive integers $m$ and $n$, the number of employees and the number of product types. The second line contains $n$ positive integers, where the $i$-th integer is $C_i$. Each of the next $m$ lines contains $n$ integers describing the matrix $A$. Then there are $m$ sections, where the $i$-th section describes the functional relationship between employee $i$’s anger value and the number of products. Each section consists of three lines: the first line is a non-negative integer $S_i$; the second line contains $S_i$ positive integers, where the $j$-th integer is $T_{i,j}$ (if $S_i=0$, this line does not appear, i.e., the section has only two lines); the third line contains $S_i+1$ positive integers, where the $j$-th integer is $W_{i,j}$.

Output a single integer: the minimal possible sum of anger values.

Constraints - There are $30\%$ of the testdata with $1 \le n, m \le 30$. - About $30\%$ of the testdata satisfy $S_i = 0$. - About $30\%$ of the testdata satisfy $S_i \le 1$ (excluding the above $S_i = 0$ testdata). For all testdata, $1 \le m, n \le 250$, $0 \le S_i \le 5$, $0 \le A_{i, j} \le 1$, $0 < T_{i, j} < T_{i, j + 1}$, $0 < W_{i, j} < W_{i, j + 1}$. All numbers are at most $10^5$. Translated by ChatGPT 5