結果

問題 No.3148 Min-Cost Destruction of Parentheses
ユーザー 👑 potato167
提出日時 2025-05-16 22:05:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 125 ms / 4,000 ms
コード長 3,083 bytes
コンパイル時間 2,479 ms
コンパイル使用メモリ 218,740 KB
実行使用メモリ 16,904 KB
最終ジャッジ日時 2025-05-16 22:05:09
合計ジャッジ時間 5,871 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define all(p) p.begin(), p.end()
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)


namespace po167{
//minmize \sum_{i=0,1,...,n-1}(u[q[i]]*\sum_{j=0,1,...,i}(d[q[j]]))
//st q is permutation
//order[p[i]]<order[i]
//p[root]=-1
//https://atcoder.jp/contests/agc023/submissions/40321108
std::pair<long long, std::vector<int>> scheduling_cost(std::vector<int> p, std::vector<int> u, std::vector<int> d) {
    int n=p.size();
    struct _job{
        long long cost;
        long long time;
        int ind;
        int hash = 0;
    };
    std::vector<int> par(n);
    std::vector<_job> val(n);
    long long ans=0;
    for (int i = 0; i< n; i++){
        par[i] = i;
        val[i].cost = (long long)u[i];
        val[i].time = (long long)d[i];
        val[i].ind = i;
        ans += val[i].cost * val[i].time;
    }
    auto concat_job = [&](_job &l, _job r) -> void {
        ans += l.time * r.cost;
        l.time += r.time;
        l.cost += r.cost;
    };
    auto comp_job = [&](_job l, _job r) -> bool {
        if (r.time == 0 && r.cost == 0) return false;
        if (l.time == 0 && l.cost == 0) return true;
        return l.cost * r.time < l.time * r.cost;
    };
    auto root = [&](auto self, int a)-> int {
        if (a == par[a]) return a;
        par[a] = self(self, par[a]);
        return par[a];
    };
    std::priority_queue<_job,std::vector<_job>, std::function<bool(_job, _job)>> pq(comp_job);
    int t = -1;
    for (int i = 0; i < n; i++){
        if (p[i] == -1) t = i;
    }
    std::vector<int> seen(n), hash(n);
    for (int i = 0; i < n; i++){
        if (i != t){
            pq.push(val[i]);
        }
    }
    int count = 0;
    while (!pq.empty()){
        _job tmp = pq.top();
        pq.pop();
        if (tmp.hash != hash[tmp.ind]) continue;
        seen[tmp.ind] = n - count;
        count++;
        par[tmp.ind] = p[tmp.ind];
        int r = root(root, tmp.ind);
        concat_job(val[r], tmp);
        if (r != t){
            val[r].hash = count;
            hash[r] = count;
            pq.push(val[r]);
        }
    }
    std::vector<int> order;
    order.reserve(n);
    std::vector<std::vector<int>> G(n);
    std::priority_queue<std::pair<int, int>> valid;
    for (int i = 0; i < n; i++){
        if (0 <= p[i]) G[p[i]].push_back(i);
        else valid.push({seen[i], i});
    }
    while (!valid.empty()){
        int a = valid.top().second;
        order.push_back(a);
        valid.pop();
        for (auto x : G[a]) valid.push({seen[x], x});
    }
    return {ans, order};
}
}


int main(){
    int N;
    cin >> N;
    vector<int> p(N + 1, -1);
    stack<int> st;
    int ind = 0;
    string S;
    cin >> S;
    st.push(0);
    for (auto c : S){
        if (c == '(') st.push(++ind);
        else{
            auto tmp = st.top();
            st.pop();
            p[tmp] = st.top();
        }
    }
    vector<int> U(N + 1, 1);
    U[0] = 0;
    vector<int> A(N + 1);
    rep(i, 0, N) cin >> A[i + 1];
    cout << po167::scheduling_cost(p, A, U).first << "\n";
}
0