353C Find Maximum （贪心）

Codeforces Round #205 （Div. 2） / 353C Find Maximum （贪心）2014-10-02 synapse7 Valera has array a, consisting of n integers a0,a1,...,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 value bit（i） equals one if the binary representation of number xcontains a 1 on the i-th position, and zero otherwise.

For example, if n=4 and x=11 （11=20+21+23）, then f（x）=a0+a1+a3.

Help Valera find the maximum of function f（x） among all x, for which an inequality holds: 0≤x≤m.

Input

The first line contains integer n （1≤n≤105） — the number of array elements. The next line contains n space-separated integersa0,a1,...,an-1 （0≤ai≤104） — elements of array a.

The third line contains a sequence of digits zero and one without spaces s0s1... sn-1 — the binary representation of number m. Numberm equals

Output

Print a single integer — the maximum value of function f（x） for all

Sample test（s）
input

2
3 8
10

output

input

5
17 0 10 2 1
11010

output

Note

In the first test case m=20=1,f（0）=0,f（1）=a0=3.

In the second sample m=20+21+23=11, the maximum value of function equals f（5）=a0+a2=17+10=27.

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45352.htm

思路：从左往右读，读到0就积累，读到1的时候，就看是修改这个1为0然后把前面的0改为1更大，还是不变更大。

修改的话，就从当前这个修改成0的1开始积累。

最终修改结果就是我们想要的x。

完整代码：

/*62ms,500KB*/#include<cstdio>#include<algorithm>using namespace std;const int maxm = 100005;int a[maxm];char s[maxm];int main（）{int n, sum, maxn, i;scanf（"%d", &n）;for （i = 0; i < n; ++i）scanf（"%d", &a[i]）;getchar（）;gets（s）;sum = maxn = 0;for （i = 0; i < n; ++i）{if （s[i] & 15）{///看是前面的一串0大，还是当前位置的1大if （maxn > a[i]）{sum += maxn;maxn = a[i]; ///重新积累}else sum += a[i];}else maxn += a[i];///积累maxn}printf（"%d
", sum）;return 0;}