#include using namespace std; using ll = long long; using pll = pair; #define vc vector using vl = vc; #define ov(a, b, c, name, ...) name #define rep2(i, l, r) for(ll i = (l); i < ll(r); i++) #define rep1(i, n) rep2(i, 0, n) #define rep(...) ov(__VA_ARGS__, rep2, rep1)(__VA_ARGS__) #define fec(...) for(const auto& __VA_ARGS__) #define per(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--) #define ALL(x) begin(x), end(x) #define SZ(x) (ll) size(x) #define LB(v, x) (lower_bound(ALL(v), x) - begin(v)) #define eb emplace_back bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; } bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; } const ll INF = ll(4e18) + 100; void printvec(const auto& v) { for(auto it = begin(v); it != end(v); it++) cout << *it << " "; cout << endl; } #ifdef LOCAL #define local(...) __VA_ARGS__ #else #define local(...) #endif struct S { ll c0, c1, inv = 0; deque p{}; bool operator>(S &r) const { if (c0 == 0 && c1 == 0) return false; if (r.c0 == 0 && r.c1 == 0) return true; return c1 * r.c0 > c0 * r.c1; } void merge(S &r) { inv += r.inv + c1 * r.c0, c0 += r.c0, c1 += r.c1; if (p.size() > r.p.size()) { while (!r.p.empty()) p.push_back(r.p.front()), r.p.pop_front(); } else { swap(p, r.p); while (!r.p.empty()) p.push_front(r.p.back()), r.p.pop_back(); } } }; auto zotree(vc &s, const auto &g) { auto comp = [](S *a, S *b) { return *a > *b; }; using PQ = priority_queue, decltype(comp)>; auto dfs = [&](auto dfs, int p, int pp) -> PQ { PQ pq{comp}; fec(e : g[p]) { if (pp == e) continue; auto ch = dfs(dfs, e, p); if (pq.size() < ch.size()) pq.swap(ch); while (!ch.empty()) pq.push(ch.top()), ch.pop(); } while (!pq.empty() && !(*pq.top() > s[p])) s[p].merge(*pq.top()), pq.pop(); pq.push(&s[p]); return pq; }; auto pq = dfs(dfs, 0, -1); // 0 が root S res(0, 0); while (!pq.empty()) res.merge(*pq.top()), pq.pop(); return res; } void main2() { ll N; cin >> N; string T; cin >> T; vc s(N + 1); s.at(0) = {1, 1}; rep(i, 1, N + 1) { cin >> s.at(i).c0; s.at(i).c1 = 1; } vc G(1); vl sta{0}; fec(c : T) { local( cout << "sta= "; printvec(sta); rep(i, G.size()) { cout << i << " "; printvec(G.at(i)); } ); if (c == '(') { ll v = sta.back(); ll nv = G.size(); G.eb(); G.at(v).eb(nv); sta.eb(nv); } else { sta.pop_back(); } } ll ans = zotree(s, G).inv; cout << ans << "\n"; } int main() { #ifndef LOCAL cin.tie(0)->sync_with_stdio(0), cout.tie(0); #endif local(while (true)) { ll t = 1; // cin >> t; while(t--) main2(); } }