[SOLUTION] Two Characters, Two Colors Solution Codeforces

by
G. Two Characters, Two Colors
time limit per test

4 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

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 ri�� coins. If you paint it blue, you get bi�� 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 11 coin.

What is the maximum number of coins you can earn?

Input

The first line of the input contains one integer t� (1≤t≤1041≤�≤104) — the number of test cases.

Each test case consists of four lines:

  • the first line contains one integer n� (1≤n≤4⋅1051≤�≤4⋅105) — 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 r1,r2,…,rn�1,�2,…,�� (1≤ri≤10121≤��≤1012);
  • the fourth line contains n� integers b1,b2,…,bn�1,�2,…,�� (1≤bi≤10121≤��≤1012).

Additional constraint on the input: the sum of values of n� over all test cases does not exceed 4⋅1054⋅105.

Output

For each test case, print one integer — the maximum number of coins you can earn.

Example
input

Copy
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
output

Copy
43
36
76
52
Note

Explanations for the test cases for the example (blue characters are underlined, red ones are not):

  1. 01000–10–01000_10_;
  2. 1011–––11011_1;
  3. 0–100000000–––––––––0_100000000_;
  4. 01–01000001_010000.

SOLUTION

# Function to calculate the maximum coins that can be earned
def max_coins(n, s, r, b):
coins = 0
red_counts = [0] * n
total_reds = 0

# Count the number of reds on the right
for i in range(n – 1, -1, -1):
red_counts[i] = total_reds
if s[i] == ‘1’:
total_reds += 1

# Calculate the coins by checking each character in the string
for i in range(n):
if s[i] == ‘1’:
coins += r[i]
else:
coins += b[i]
coins -= red_counts[i]

return coins

# Read the number of test cases
t = int(input())

# Iterate through each test case
for _ in range(t):
n = int(input())
s = input()
r = list(map(int, input().split()))
b = list(map(int, input().split()))
result = max_coins(n, s, r, b)
print(result)

Leave a Comment