(SENIOR) The Math question
All submissions for this problem are available.
Piyush has array a, consisting of n integers a0,a1a2,an-1, and function f(x), taking an integer from 0 to 2n-1 as its single argument. Value f(x) is calculated by formula ,
where bit(i) equals one if the binary representation of number x contains a 1 on the ith position, and zero otherwise.
For example, if n=4 and x=11 (11=20 + 21 + 23), then f(x)= a0 + a1 + a3.
Help Piyush find the miximum of the function f(x) among all x, for which an equality holds: 0 ≤ x ≤ m .
- The first line contains integer T the number of test cases.
- For each test case, the first line contains n the number of array elements. The next line contains n space separated integers a0,a1,a2...an-1 the elements of array a.
- The next line contains a sequence of digits zero and one without spaces s0,s1,...,sn-1 the binary representation of number m. Number m equals .
- For each test case print a single - integer the maximum value of f(x) for all x ∈[0...m].
- 1 ≤ T ≤ 50
- 1 ≤ n ≤ 105
- 0 ≤ ai ≤ 104.
Input: 2 2 3 8 10 5 17 0 10 2 1 11010 Output: 3 27
- In the first test case m=20=1, f(0)=0, f(1)=a0 =3.
- In the second test case m= 20 + 21 + 23 =11, the maximum value of function equals f(5) = a0 + a2 = 17 + 10 =17.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.