/*贪心 负数一定不取枚举最高位是1 且答案取为0的 位置， 更新答案。*/#include
     
      #include
      
       #include
       
        #define ll long long#define N 100010using namespace std;int n;ll a[N],ans,sum[N];char s[N];ll read(){    ll x=0,f=1;char c=getchar();    while(c>'9'||c<'0'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int main(){    freopen("maximum.in","r",stdin);    freopen("maximum.out","w",stdout);    scanf("%d",&n);    for(int i=1; i<=n; i++)    {        a[i]=read();        sum[i]=sum[i-1];        if(a[i]>0)sum[i]=sum[i-1]+a[i];    }    scanf("%s",s+1);    ll c=0;    for(int i=n; i>=1; i--)      if(s[i]=='1')      {          ans=max(ans,c+sum[i-1]);          c+=max(a[i],0LL);      }    ans=max(ans,c);    printf("%I64d\n",ans);    return 0;}
       
      
     

 

 

/*15暴力*/#include
     
      #include
      
       #include
       
        #include
        
         #define N 1010using namespace std;int n,k;int l,r,mid;int num[N],tmp[N];int ans;int minn(int a,int b,int i){    if(a
         
          mid)        {            if(tmp[i+1]>tmp[i]) tmp[i]=max(tmp[i],tmp[i-1]+mid);            else tmp[i]=minn(abs(tmp[i-1]-tmp[i+1]),tmp[i-1]+mid-tmp[i+1],i);            sum++;            }    if(sum>k)    return false;    else return true;}int main(){    scanf("%d%d",&n,&k);    for(int i=1; i<=n; i++)    scanf("%d",&num[i]);    l=0;    r=1000000000;    while(l<=r)    {        mid=(l+r)/2;        if(check())    ans=mid,r=mid-1;        else l=mid+1;    }    printf("%d",ans);}
         
        
       
      
     

 

 

 

不会分块

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int maxn = 200000;const int len = 400;int n, A, B,m;int a[maxn],b[maxn],l[maxn],r[maxn],lb[maxn],tot;int answer[300][300];int rt[300][maxn], lt[300][maxn],d[maxn];//int root[maxn*len], ll[maxn*len], rr[maxn*len],data[maxn*len];int find(int x){ for (int l = 0, r = m; l < r;) { int mid = (l + r) / 2; if (b[mid] == x) return mid; if (b[mid]>x) r = mid; else l = mid + 1; } return -1;}/*int build(int l, int r){ if (l == r) { tot++; ll[tot] = rr[tot] = 0; data[tot] = d[l]; return tot; } tot++; int tmp = tot; ll[tmp] = build(l, (l + r) / 2); rr[tmp] = build((l + r) / 2 + 1, r); data[tmp] = min(data[ll[tmp]], data[rr[tmp]]); return tmp;}int change(int i, int l, int r,int x){ if (l == x && r == x) { tot++; ll[tot] = rr[tot] = 0; data[tot] = n + 1; return tot; } tot++; int tmp = tot; ll[tot] = ll[i]; rr[tot] = rr[i]; if (l <= x && x <= (l + r) / 2) ll[tmp] = change(ll[i], l, (l + r) / 2, x); else rr[tmp] = change(rr[i], (l + r) / 2 + 1, r, x); data[tmp] = min(data[ll[tmp]], data[rr[tmp]]); return tmp;}int check(int i, int l, int r, int x, int &ans){ if (l > x) return 0; if (1 <= l && r <= x) { ans = min(ans, data[i]); return 0; } check(ll[i], l, (l + r) / 2, x, ans); check(rr[i], (l + r) / 2 + 1, r, x, ans); return 0;}*/int main(){ double ti = clock(); freopen("sequence.in", "r", stdin); freopen("sequence.out", "w", stdout); scanf("%d%d%d", &n, &A, &B); a[0] = 0; for (int i = 1; i <= n; i++) { char c; for (scanf(" %c", &c); c != 'A' && c != 'B'; scanf(" %c", &c)); if (c == 'A') a[i] = a[i - 1] + B; else a[i] = a[i - 1] - A; } for (int i = 0; i <= n; i++) b[i] = a[i]; sort(b, b + n + 1); m = unique(b, b + n + 1) - b; for (int i = 0; i <= n; i++) { a[i] = find(a[i]); if (a[i] == -1) { printf("???\n"); return 0; } } n++; int k = n / len; for (int i = 0; i <= k; i++) { int ans = 0; tot++; for (int j = i*len; j < n; j++) { if (j%len == 0) { answer[i][j / len] = ans; } if (lb[a[j]] != tot) { lb[a[j]] = tot; l[a[j]] = j; } ans = max(ans, j - l[a[j]]); } } for (int i = 0; i < n; i++) r[i] = -1; for (int i = 0; i < n; i++) { r[a[i]] = i; if (i%len == len - 1) { int tmp = i / len; for (int j = 0; j < n; j++) rt[tmp][j] = r[j]; } } for (int i = 0; i < n; i++) l[i] = -1; for (int i = n - 1; i >= 0; i--) { l[a[i]] = i; if (i%len == 0) { int tmp = i / len; for (int j = 0; j < n; j++) lt[tmp][j] = l[j]; } } int q; scanf("%d", &q); int ans = 0; for (; q; q--) { int L, R; scanf("%d%d", &L, &R); L--; int kl = L / len, kr = R / len; ans = 0; if (kl == kr) { tot++; for (int i = L; i <= R; i++) { if (lb[a[i]] != tot) { lb[a[i]] = tot; l[a[i]] = i; } ans = max(ans, i - l[a[i]]); } } else { ans = answer[kl + 1][kr]; tot++; int tmp = min(n, (kl + 1)*len); for (int i = L; i < tmp; i++) { if (lb[a[i]] != tot) { lb[a[i]] = tot; l[a[i]] = i; ans = max(ans, rt[kr - 1][a[i]] - i); } } tmp = min(R + 1, n); for (int i = kr*len; i < tmp; i++) { if (lb[a[i]] != tot) { if (lt[kl + 1][a[i]] != -1) ans = max(ans, i - lt[kl + 1][a[i]]); } else ans = max(ans, i - l[a[i]]); } } printf("%d\n", ans); } /*int q; for (scanf("%d", &q); q; q--) { // if (q % 5000 == 0) cerr << q << endl; int L, R; tot++; scanf("%d%d", &L, &R); int ans = 0; for (int i = L - 1; i <= R; i++) { if (lb[a[i]] != tot) { lb[a[i]] = tot; l[a[i]] = i; } ans = max(ans, i - l[a[i]]); } printf("%d\n", ans); }*/ /*for (int i = 0; i <= n; i++) { if (lb[a[i]] == 0) { lb[a[i]] = 1; l[a[i]] = i; d[i] = n + 1; } else { r[l[a[i]]] = i; d[i] = i - l[a[i]]; l[a[i]] = i; } } root[0] = build(1, n); for (int i = 1; i <= n; i++) { if (r[i-1] != 0) root[i] = change(root[i - 1], 1, n, r[i-1]); else root[i] = root[i - 1]; } int q; for (scanf("%d", &q); q; q--) { int L, R; scanf("%d%d", &L, &R); L--; int ans = n + 1; check(root[L], 1, n, R, ans); if (ans == n + 1) printf("-1\n"); else printf("%d\n", ans); }*/ /* int q; int tans = 0; for (scanf("%d", &q); q; q--) { int L, R; scanf("%d%d", &L, &R); L--; tot++; int ans = n + 1; for (int i = L; i <= R; i++) { if (lb[a[i]] != tot) { lb[a[i]] = tot; l[a[i]] = i; } else { ans = min(ans, i - l[a[i]]); l[a[i]] = i; } } if (ans == n + 1) printf("-1\n"); else { printf("%d\n", ans); tans = max(tans, ans); } } cerr << clock()-ti << " "<
            
             <<" "<
             <<" "<<