#CF1895G. Two Characters, Two Colors
Two Characters, Two Colors
Description
You are given a string consisting of characters 0 and/or 1. You have to paint every character of this string into one of two colors, red or blue.
If you paint the $i$-th character red, you get $r_i$ coins. If you paint it blue, you get $b_i$ coins.
After coloring the string, you remove every blue character from it, and count the number of inversions in the resulting string (i. e. the number of pairs of characters such that the left character in the pair is 1, and the right character in the pair is 0). For each inversion, you have to pay $1$ coin.
What is the maximum number of coins you can earn?
The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
Each test case consists of four lines:
- the first line contains one integer $n$ ($1 \le n \le 4 \cdot 10^5$) — the length of the string;
- the second line contains $s$ — a string of $n$ characters, where each character is either 0 or 1;
- the third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^{12}$);
- the fourth line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^{12}$).
Additional constraint on the input: the sum of values of $n$ over all test cases does not exceed $4 \cdot 10^5$.
For each test case, print one integer — the maximum number of coins you can earn.
题面翻译
给定一个 01 串，你需要给每个节点涂上红色或是蓝色。
如果你给第 个节点涂上红色，那么你将获得 个金币；若涂上蓝色，将获得 个金币。
之后，你会移除所有被涂上蓝色的字符，并统计剩下字符串中的逆序对个数，并失去逆序对个数个金币。
求出能够得到金币的最大数目。
Input
The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
Each test case consists of four lines:
- the first line contains one integer $n$ ($1 \le n \le 4 \cdot 10^5$) — the length of the string;
- the second line contains $s$ — a string of $n$ characters, where each character is either 0 or 1;
- the third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^{12}$);
- the fourth line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^{12}$).
Additional constraint on the input: the sum of values of $n$ over all test cases does not exceed $4 \cdot 10^5$.
Output
For each test case, print one integer — the maximum number of coins you can earn.
4
7
0100010
6 6 6 7 7 6 6
3 3 5 4 7 6 7
5
10111
9 8 5 7 5
4 4 7 8 4
10
0100000000
7 7 6 5 2 2 5 3 8 3
8 6 9 6 6 8 9 7 7 9
8
01010000
8 7 7 7 8 7 7 8
4 4 4 2 1 4 4 4
43
36
76
52
Note
Explanations for the test cases for the example (blue characters are underlined, red ones are not):
- $0100\underline{0}1\underline{0}$;
- $10\underline{11}1$;
- $\underline{0}1\underline{00000000}$;
- $0\underline{1}010000$.
相关
在下列比赛中: