Codeforces #205 Div2. C. Find Maximum

CF205はDiv2Onlyなので練習のみ。
http://codeforces.com/contest/353/problem/C

問題

N個の数列A[i]と、2進数でN桁の数Mが与えられる。
0<=x<=Mとなるxにおいて、xのi桁目が1であるようなiについてA[i]の総和をとったものをf(x)とする。
f(x)の最大値を求めよ。

解法

Mのi桁目が1の時、xとしてi桁目が0となる数字を取れば、(i-1)桁目以下は全て1にできる。
よって、Mのうち1となる桁をそれぞれ0として、それ以下の桁を全部1にしたxに対してにf(x)を求め、その最大値を求めればよい。
事前に前処理すればf(x)はO(1)で計算できるので、全体でO(N)で処理できる。

int N,A[100001];
string S;
int t1[100001],t2[100001];

void solve() {
	int f,i,j,k,l, x,y,N;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	cin>>S;
	
	FOR(i,N) t1[i]=A[i]+((i>0)?t1[i-1]:0);
	FOR(i,N) t2[i]=((S[i]=='1')?A[i]:0)+((i>0)?t2[i-1]:0);
	x=t2[N-1];
	FOR(i,N) if(i>0 && S[i]=='1') x=max(x,t2[N-1]-t2[i]+t1[i-1]);
	_P("%d\n",x);
}

まとめ

ここら辺はまだ簡単。