353C.md (1898B)
1 Source: https://codeforces.com/problemset/problem/353/C 2 3 C. Find Maximum 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Valera has array *a*, consisting of *n* integers *a*0, *a*1, ..., *a**n* - 1, and function *f*(*x*), taking an integer from 0 to 2*n* - 1 as its single argument. Value *f*(*x*) is calculated by formula , where value *bit*(*i*) equals one if the binary representation of number *x* contains a 1 on the *i*-th position, and zero otherwise. 22 23 For example, if *n* = 4 and *x* = 11 (11 = 20 + 21 + 23), then *f*(*x*) = *a*0 + *a*1 + *a*3. 24 25 Help Valera find the maximum of function *f*(*x*) among all *x*, for which an inequality holds: 0 ≤ *x* ≤ *m*. 26 27 Input 28 29 The first line contains integer *n* (1 ≤ *n* ≤ 105) — the number of array elements. The next line contains *n* space-separated integers *a*0, *a*1, ..., *a**n* - 1 (0 ≤ *a**i* ≤ 104) — elements of array *a*. 30 31 The third line contains a sequence of digits zero and one without spaces *s*0*s*1... *s**n* - 1 — the binary representation of number *m*. Number *m* equals . 32 33 Output 34 35 Print a single integer — the maximum value of function *f*(*x*) for all . 36 37 Examples 38 39 Input 40 41 ``` 42 2 43 3 8 44 10 45 ``` 46 47 Output 48 49 ``` 50 3 51 ``` 52 53 Input 54 55 ``` 56 5 57 17 0 10 2 1 58 11010 59 ``` 60 61 Output 62 63 ``` 64 27 65 ``` 66 67 Note 68 69 In the first test case *m* = 20 = 1, *f*(0) = 0, *f*(1) = *a*0 = 3. 70 71 In the second sample *m* = 20 + 21 + 23 = 11, the maximum value of function equals *f*(5) = *a*0 + *a*2 = 17 + 10 = 27.