P3749 [Six-Province Joint Exam 2017] Sushi Restaurant

Kiana has recently been dining at a very delicious sushi restaurant. Every evening, the restaurant serves $n$ types of sushi in order. The $i$-th sushi has a code $a_i$ and a deliciousness $d_{i, i}$. Different types of sushi may share the same code. Each type has an unlimited number of servings, and Kiana can take sushi an unlimited number of times; however, in each take she can take at most one serving of each type, and the taken sushi in a single take must form a contiguous segment in the serving order. That is, Kiana may take one serving each of types $1$ and $2$ in one take, or types $2$ and $3$ in one take, but she may not take types $1$ and $3$ together in a single take. Because there are many types and they may interact: salmon and squid together might be great, but together with fruit sushi might cause a stomachache. Therefore, Kiana defines a comprehensive deliciousness $d_{i, j}$ for $i < j$, meaning that if, in a single take, she includes all sushi from the $i$-th to the $j$-th served by the restaurant, then after eating all sushi taken in that take she will gain an extra deliciousness of $d_{i, j}$. Since taking sushi takes some time, we assume that sushi taken in different takes do not interact. Note that when eating sushi from a single take, more than one comprehensive deliciousness will be added. For example, if Kiana takes one serving each of types $1, 2, 3$ in a single take, then besides $d_{1, 3}$, $d_{1, 2}$ and $d_{2, 3}$ will also be added to the total deliciousness. Magically, Kiana’s evaluation of food has memory: whether it is the deliciousness of a single type of sushi or the comprehensive deliciousness of a combination, each will be added to Kiana’s total deliciousness at most once. For example, if Kiana once takes one serving each of types $1$ and $2$, and another time takes one serving each of types $2$ and $3$, then the total deliciousness of these two takes is $d_{1, 1} + d_{2, 2} + d_{3, 3} + d_{1, 2} + d_{2, 3}$, where $d_{2, 2}$ is counted only once. Strangely, the restaurant’s pricing policy is unusual. Specifically, if Kiana has eaten in total $c \ (c > 0)$ kinds of sushi with code $x$, she must pay $m x^2 + c x$ yuan for those sushi, where $m$ is a constant given by the restaurant. Now Kiana wants to know, when eating at this restaurant, what is the maximum value of the total deliciousness (including the deliciousness of all eaten single types and all accumulated comprehensive deliciousness) minus the total amount of money paid. Since she cannot compute it, she asks you to tell her.

The first line contains two positive integers $n, m$, denoting the total number of sushi types served by the restaurant and the constant used in pricing. The second line contains $n$ positive integers, where the $k$-th number $a_k$ is the code of the $k$-th sushi. Then follow $n$ lines. The $i$-th of these lines contains $n - i + 1$ integers, where the $j$-th number is $d_{i, i + j - 1}$, representing the corresponding deliciousness obtained by eating the sushi, as described above.

Output a single line containing a positive integer, which is the maximum value of the total deliciousness Kiana can obtain minus the total amount of money paid.

### Sample Explanation 1 In this sample, the restaurant serves $3$ sushi in total, with codes $a_1 = 2, a_2 = 3, a_3 = 2$, and the constant for pricing is $m = 1$. Under the requirement that each take must yield new deliciousness, Kiana has $14$ distinct ways to eat. Some of them are listed below: 1. Kiana eats nothing. Then her total deliciousness and total payment are both $0$, and their difference is also $0$. 2. Kiana takes sushi exactly once, and only takes the $1$-st sushi, i.e., her takes are $\{[1, 1]\}$. Then the total deliciousness is $5$, the total payment is $1 \times 2^2 + 1 \times 2 = 6$, and the difference is $-1$. 3. Kiana takes sushi twice: the first time the $1$-st and $2$-nd sushi, and the second time the $2$-nd and $3$-rd sushi, i.e., her takes are $\{[1, 2], [2, 3]\}$. Then the total deliciousness is $5 + (-10) + 15 + (-10) + 15 = 15$, the total payment is $(1 \times 2^2 + 2 \times 2) + (1 \times 3^2 + 1 \times 3) = 20$, and the difference is $-5$. 4. Kiana takes sushi twice: the first time the $1$-st sushi, and the second time the $3$-rd sushi, i.e., her takes are $\{[1, 1], [3, 3]\}$. Then the total deliciousness is $5 + 15 = 20$, the total payment is $1 \times 2^2 + 2 \times 2 = 8$, and the difference is $12$. Among the $14$ plans, the unique optimal plan is the last one listed, where the maximum value of total deliciousness minus total payment is $12$. ### Constraints For all testdata, it is guaranteed that $-500 \leq d_{i, j} \leq 500$. Additional special constraints on the data are as follows: | Case # | $n$ | $a_i$ | $m$ | Additional constraint | |:-:|:-:|:-:|:-:|:-:| | 1 | $\leq 2$ | $\leq 30$ | $= 0$ | - | | 2 | $\leq 2$ | $\leq 30$ | $= 1$ | - | | 3 | $\leq 3$ | $\leq 30$ | $= 0$ | - | | 4 | $\leq 3$ | $\leq 30$ | $= 1$ | - | | 5 | $\leq 5$ | $\leq 30$ | $= 0$ | - | | 6 | $\leq 5$ | $\leq 30$ | $= 1$ | - | | 7 | $\leq 10$ | $\leq 30$ | $= 0$ | All $a_i$ are the same | | 8 | $\leq 10$ | $\leq 30$ | $= 1$ | - | | 9 | $\leq 15$ | $\leq 30$ | $= 0$ | All $a_i$ are the same | | 10 | $\leq 15$ | $\leq 30$ | $= 1$ | - | | 11 | $\leq 30$ | $\leq 1000$ | $= 0$ | All $a_i$ are the same | | 12 | $\leq 30$ | $\leq 30$ | $= 0$ | All $a_i$ are the same | | 13 | $\leq 30$ | $\leq 1000$ | $= 0$ | - | | 14 | $\leq 30$ | $\leq 1000$ | $= 1$ | - | | 15 | $\leq 50$ | $\leq 1000$ | $= 0$ | All $a_i$ are the same | | 16 | $\leq 50$ | $\leq 30$ | $= 0$ | All $a_i$ are the same | | 17 | $\leq 50$ | $\leq 1000$ | $= 0$ | - | | 18 | $\leq 50$ | $\leq 1000$ | $= 1$ | - | | 19 | $\leq 100$ | $\leq 1000$ | $= 0$ | - | | 20 | $\leq 100$ | $\leq 1000$ | $= 1$ | - | Translated by ChatGPT 5