Codeforces Round #205 (Div. 2) C. Find Maximum
C. Find Maximum
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 x contains 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 integers a0,?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. Number m equals .
Output
Print a single integer — the maximum value of function f(x) for all .
Sample test(s)
input
2
3 8
10
output
3
input
5
17 0 10 2 1
11010
output
27
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.
这题，其实，我们知道，尽可能的多的数是最好的，如果当前位是１的话，我们把这一位换成０下面的全是１，这样，循环，就一定能找到最大值了！
#include <iostream>#include <stdio.h>#include <string.h>using namespace std;#define M 100500int pri[M],sum[M];char str[M];int main(){ int n,i; while(scanf("%d",&n)!=EOF){ for(i=0;i<n;i++){ scanf("%d",&pri[i]); sum[i]=i?sum[i-1]+pri[i]:pri[i]; } scanf("%s",str); int strnum=strlen(str); int j=strnum-1; while(j>0&&str[j]=='0'){j--;} strnum=j; int ans=0,len=0; for(i=j;i>=0;i--){ if(str[i]!='0'){ ans=max(ans,len+sum[i-1]); len+=pri[i]; } } ans=max(ans,len); cout<<ans<<endl; } return 0;}