codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![](https://espresso.codeforces.com/eba4794e67d3b5ce144adcffa5217705a92db70f.png), 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 ![](https://espresso.codeforces.com/77407fd65d8594ac862f8de69093d5a75e54d3c5.png).
     32 
     33 Output
     34 
     35 Print a single integer — the maximum value of function *f*(*x*) for all ![](https://espresso.codeforces.com/82bfd78b9ec5ce07767875a86696eb7b2eb3031c.png).
     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.