Submission #71362420

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main () {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n;
  string s;
  cin >> n >> s;
  vector<int> a(n);
  for (auto& x: a) cin >> x;
  while (s.back() == '#') {
    s.pop_back();
    a.pop_back();
  }
  int c = 0;
  while (s[c] == '#') c++;
  s = s.substr(c);
  a = vector<int>(a.begin() + c, a.end());
  n = s.size();

  int mx = *max_element(a.begin(), a.end());
  vector<pair<int, int>> seg_mx_cnt;
  vector<int> has_mx;
  for (int l = 0; l < n;) {
    int r = l;
    while (r < n && s[r] == s[l]) r++;
    if (s[l] == '.') {
      int seg_mx = *max_element(a.begin() + l, a.begin() + r);
      seg_mx_cnt.emplace_back(count(a.begin() + l, a.begin() + r, seg_mx), seg_mx == mx);
    }
    else {
      has_mx.push_back(count(a.begin() + l, a.begin() + r, mx) > 0);
    }
    l = r;
  }
  int64_t ans = 0;
  for (int i = 0; i < (int)has_mx.size(); i++) {
    if (has_mx[i] || seg_mx_cnt[i].second || seg_mx_cnt[i+1].second) {
      ans += 1LL*seg_mx_cnt[i].first*seg_mx_cnt[i+1].first;
    }
  }
  cout << ans << '\n';
}

Submission Info

Judge Result