P12150 【MX-X11-T4】Surveillance

原题链接：。 --- 「お願い　きみが欲しいの」 「頼り散らしてシックラブ　なんて最高ね」 「分けてくれなきゃ　君の“痛い”感じていたい」 「ねえいいでしょう？　吸い取って　救いたいんだってば」

A **set** pair $(A, B)$ is defined as "good" if and only if $A$ can be transformed into $B$ through a finite number of the following operations: - Choose a number $x$ from $A$, remove $x$ from $A$, then add $x-1$ and $x+1$ to $A$. If duplicates exist, only one copy is retained. Given that the initial value ranges of sets $A$ and $B$ are $[1, n]$ (containing integers), **operations may produce values outside** $[1, n]$. Additionally, you are given the set $B$ and a length-$n$ array $p$. Find a valid $A$ such that $(A, B)$ is good, and minimize the sum $\sum\limits_{i=1}^n [i \in A] \times p_i$.

**Multiple test cases.** The first line contains two integers $c$ and $T$, representing the subtask number and the number of test cases, respectively. Subsequent lines contain the test data. Sample inputs satisfy $c=0$. For each test case: - The first line contains an integer $n$, the initial value range of sets $A$ and $B$. - The second line contains a length-$n$ binary string $s_1 s_2 \cdots s_n$, where $s_i = 1$ indicates $i \in B$, and $s_i = 0$ indicates $i \notin B$. - The third line contains $n$ integers $p_1, p_2, \ldots, p_n$.

For each test case, output a single integer representing the minimal possible sum.

## Explanation #1 For the first test case, $A = \{1, 4, 5, 8, 9\}$ is a valid solution. The cost is $3 + (-3) + 4 + (-3) + (-5) = -4$. For the second test case, $A = \{2, 7\}$ is valid. Operating on $2$ and $7$ transforms $A$ into $\{1, 3, 6, 8\}$, which matches $B$. The cost is $0 + 2 = 2$. ## Constraints For all test data: $1 \le T \le 10$, $1 \le n \le 10^5$, $-10^9 \le p_i \le 10^9$. | Subtask | $n \le$ | Special Property | Points | |:---------:|:---------:|:-------------------:|:--------:| | 1 | 18 | None | 10 | | 2 | $10^5$ | A | 10 | | 3 | $10^5$ | B | 20 | | 4 | $10^5$ | C | 20 | | 5 | $10^5$ | None | 40 | - **Special Property A**: The size of set $B$ does not exceed 10. - **Special Property B**: The binary string $s$ contains no substring `101`. - **Special Property C**: All $p_i$ are equal. Translated by DeepSeek R1