結果
問題 |
No.3148 Min-Cost Destruction of Parentheses
|
ユーザー |
![]() |
提出日時 | 2025-09-25 14:17:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 131 ms / 4,000 ms |
コード長 | 2,895 bytes |
コンパイル時間 | 3,792 ms |
コンパイル使用メモリ | 295,916 KB |
実行使用メモリ | 78,228 KB |
最終ジャッジ日時 | 2025-09-25 14:17:12 |
合計ジャッジ時間 | 7,686 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; #define vc vector using vl = vc<ll>; #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<int> 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> &s, const auto &g) { auto comp = [](S *a, S *b) { return *a > *b; }; using PQ = priority_queue<S *, vc<S *>, 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> s(N + 1); s.at(0) = {1, 1}; rep(i, 1, N + 1) { cin >> s.at(i).c0; s.at(i).c1 = 1; } vc<vl> 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(); } }