贪心

因为 $a_i\geq 0$，所以明显多选不亏。

可以从高到低位考虑，改动原来的数必须往小了改，所以改动的最高位必须是 $1$ 改成 $0$。如果选择将某一个 $1$ 变为 $0$，那么后面的数无论怎么改都是小于原数的，所以全部填上 $1$ 就可以了。

所以具体来说做一个从低位到高位的前缀和，枚举每一个为 $1$ 的位，高位记录从后面到这一位的答案，低位查询前缀和得到改变这一位的答案，取最大值输出即可。

时间复杂度 $O(n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
#include<cstring>
#define rep(a,b,c) for(int c(a);c<=(b);++c)
inline int read()
{
	int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res;
}
template<typename T> inline T max(const T&x,const T&y){return x<y?y:x;}
const int N=1e5+10;char s[N];int a[N],n;
int main()
{
	n=read();rep(1,n,i)a[i]=a[i-1]+read();scanf("%s",s);
	int res=0,ans=0;for(int i=n-1;~i;--i)if(s[i]=='1'){ans=max(ans,res+a[i]);res+=a[i+1]-a[i];}
	printf("%d\n",max(res,ans));return 0;
}