結果
問題 | No.3148 Min-Cost Destruction of Parentheses |
ユーザー |
![]() |
提出日時 | 2025-05-16 22:47:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 611 ms / 4,000 ms |
コード長 | 1,933 bytes |
コンパイル時間 | 4,841 ms |
コンパイル使用メモリ | 282,268 KB |
実行使用メモリ | 135,996 KB |
最終ジャッジ日時 | 2025-05-16 22:47:21 |
合計ジャッジ時間 | 14,539 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000005 #define Inf64 4000000000000000001LL vector<vector<int>> E; int vnum = 0; int ps[200005]; void dfs(string &s,int &ci,int cv){ ci++; while(true){ if(ci==s.size())break; if(s[ci]==')'){ ci++; break; } vnum++; E[cv].push_back(vnum); ps[vnum] = cv; dfs(s,ci,vnum); } } int main(){ int n; cin>>n; string s; cin>>s; vector<long long> a(n); rep(i,n)cin>>a[i]; s.insert(s.begin(),'('); s.push_back(')'); a.insert(a.begin(),0); int ci = 0; E.resize(a.size()); dfs(s,ci,0); ps[0] = -1; priority_queue<vector<long long>,vector<vector<long long>>, function<bool(vector<long long>,vector<long long>)>> pq([](vector<long long> a, vector<long long> b){return a[0]*b[1]>a[1]*b[0];}); rep(i,n+1){ pq.push({1,a[i],i,1}); } dsu D(n+1); vector<deque<int>> ans(n+1); vector<int> cp(n+1); vector<int> sum(n+1),sz(n+1); rep(i,n+1){ cp[i] = i; ans[i] = {i}; sz[i] = 1; sum[i] = a[i]; } while(pq.size()>0){ auto t = pq.top(); pq.pop(); if(D.size(t[2])!=t[3])continue; int u = t[2]; int p = cp[u]; if(ps[p]==-1)continue; int v = D.leader(ps[p]); if(ans[u].size()<ans[v].size()){ rep(j,ans[u].size())ans[v].push_back(ans[u][j]); ans[u].resize(0); } else{ for(int j=ans[v].size()-1;j>=0;j--)ans[u].push_front(ans[v][j]); ans[v].resize(0); } D.merge(u,v); int l = D.leader(u); if(ans[u].size()>0)swap(ans[u],ans[l]); else swap(ans[v],ans[l]); cp[l] = cp[v]; sum[l] = sum[u] + sum[v]; sz[l] = sz[u] + sz[v]; pq.push({sz[l],sum[l],l,D.size(l)}); } long long Ans = 0; deque<int> anss = ans[D.leader(0)]; rep(i,anss.size()){ // cout<<a[anss[i]]<<endl; long long v = i; v *= a[anss[i]]; Ans +=v; } cout<<Ans<<endl; return 0; }