Advertisement
ekzolot

Untitled

Mar 20th, 2023
735
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int solve(vector<int>& a, vector<int>& prefix, vector<int>& m, int k){
  5.     if (k==m.size()-1){
  6.         //int x=max(a[m[k]], prefix[m[k]]);
  7.         //cout<<k<<" "<<x<<"\n";
  8.         return max(a[m[k]], prefix[m[k]]);
  9.     }
  10.     //int x=max(prefix[m[k]], a[m[k]]+solve(a, prefix, m, k+1));
  11.     //cout<<k<<" "<<x<<"\n";
  12.     return max(prefix[m[k]], a[m[k]]+solve(a, prefix, m, k+1));
  13. }
  14. signed main(){
  15.     int n;
  16.     cin>>n;
  17.     vector<int> a(n);
  18.     for (int i=0; i<n; i++){
  19.         cin>>a[i];
  20.     }
  21.     string s;
  22.     cin>>s;
  23.     int t=(int) s.size();
  24.     reverse(s.begin(), s.end());
  25.     vector<int> m;
  26.     for (int i=0; i<t; i++){
  27.         if (s[i]=='1'){
  28.             m.push_back(t-1-i);
  29.         }
  30.     }
  31.     if (m.size()==0){
  32.         cout<<0<<"\n";
  33.         return 0;
  34.     }
  35.     vector<int> prefix(n+1);
  36.     for (int i=1; i<=n; i++){
  37.         prefix[i]=prefix[i-1]+a[i-1];
  38.     }
  39.     int ans=solve(a, prefix, m, 0);
  40.     cout<<ans<<"\n";
  41. }
  42.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement