| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
In this problem, you need to solve a well-known NP problem - the quadratic integer programming problem.
Quadratic integer programming problems have variables: you need to give a length $n$ sequence of integers $(x[1], x[2], \ldots, x[n])$ that satisfies all the conditions below.
Quadratic integer programming problems have constraints: the sequence of integers you give needs to satisfy the following two types of constraints:
The quadratic integer programming problem has an objective function: you are given given $k-2$ weight parameters $v[2], v[3], \ldots , v[k-1]$. Let $c[i]$ be the number of elements in the sequence whose value is $i$, and $G$ be the number of pairs $1 \le i, j \le n$ such that $|p[i] - p[j]| \le 1$ (note that when $i \neq j$, $(i, j)$ and $(j, i)$ are not the same). The weight of a sequence $x[1], x[2], \ldots, x[n]$ is:
$$\displaystyle W(x[1], x[2], \ldots, x[n]) = 10^{6}G + \sum_{i = 2}^{k - 1} c[i] v[i]$$
Your sequence needs to maximize its weight while satisfying the above two constraints.
Quadratic integer programming problems do not necessarily require multiple queries, but we will give $q$ queries, each query giving different weight parameters $v[2], v[3], \ldots, v[k-1]$. For each query, you need find a sequence of maximum weight that satisfies the constraints. To reduce the output, you only need to output the weight of this sequence. The data guarantees that at least one sequence that satisfies the above conditions exists.
There are multiple sets of test data for this question. The first line contains a non-negative integer $C$ and a positive integer $T$, which represent the test case number and the number of data sets, respectively. $C = 0$ indicates that this set of data is a sample.
For each test case:
For each set of queries for each set of data, output a row of integers representing the maximum weight of the sequence.
Assume \sum q is the sum of q of all test data in a single test point. For all test points,
| Case | $T \leq$ | $k=$ | $\sum q \leq$ | Special Property |
|---|---|---|---|---|
| 1 | $10$ | $3$ | $200$ | None |
| 2 | $600$ | $3 \times 10^5$ | ||
| 3 | $10$ | $4$ | $200$ | |
| 4 | $600$ | $3 \times 10^5$ | ||
| 5 | $10$ | $5$ | $300$ | |
| 6 | $15$ | $500$ | ||
| 7 | $25$ | $750$ | ||
| 8 | $50$ | $1000$ | ||
| 9 | $80$ | $1500$ | ||
| 10 | $120$ | $2000$ | ||
| 11 | $200$ | $8000$ | A | |
| 12 | $400$ | $3 \times 10^4$ | ||
| 13 | $600$ | $2 \times 10^5$ | ||
| 14 | $200$ | $8000$ | B | |
| 15 | $400$ | $3 \times 10^4$ | ||
| 16 | $600$ | $2 \times 10^5$ | ||
| 17 | $120$ | $10^5$ | C | |
| 18 | $150$ | $2 \times 10^5$ | ||
| 19 | $180$ | $3 \times 10^5$ | ||
| 20 | $300$ | $5 \times 10^4$ | None | |
| 21 | $450$ | $10^5$ | ||
| 22 | $600$ | $3 \times 10^5$ |
0 5 3 5 2 2 1 1 1 2 2 3 1 3 3 3 1 4 0 2 3 1 0 1000000 3 1 0 1 1 1 0 3 1 0 1 1 1 0 3 1 0 1 1 1 0 3 1 0 1 1 1 0
21000000 23000000 1000000 1000000 1000000 1000000
0 4 4 4 3 2 4 4 1 4 2 3 2 3 1 2 1 1 1 0 3 4 0 0 0 100000000 0 4 1 0 1 1 1 0 0 4 1 0 1 1 1 0 0 4 1 0 1 1 1 0 0
16000000 212000000 1000000 1000000 1000000
0 5 5 5 4 3 1 5 1 3 3 5 3 4 2 3 1 2 1 1 3 1 1 4 1 1 5 1 2000000 2000000 2000000 20000000 2000000 2000000 20000000 2000000 20000000 5 1 0 1 1 1 0 0 0 5 1 0 1 1 1 0 0 0 5 1 0 1 1 1 0 0 0 5 1 0 1 1 1 0 0 0
35000000 89000000 99000000 1000000 1000000 1000000 1000000