結果

問題 No.3148 Min-Cost Destruction of Parentheses
ユーザー Nauclhlt🪷
提出日時 2025-03-27 19:44:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,650 bytes
コンパイル時間 2,579 ms
コンパイル使用メモリ 206,772 KB
実行使用メモリ 7,348 KB
最終ジャッジ日時 2025-05-15 23:06:54
合計ジャッジ時間 5,251 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 7 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;

bool is_balanced(string s)
{
    int open = 0;
    for (int i = 0; i < (int)s.size(); i++)
    {
        if (s[i] == '(') open++;
        else if (s[i] == ')') open--;

        if (open < 0) return false;
    }

    return open == 0;
}

int main()
{
    int N;
    cin >> N;
    
    assert(1 <= N && N <= 100000);

    string S;
    cin >> S;
    assert(S.size() == 2 * N);

    assert(is_balanced(S));

    vector<ll> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    stack<int> s;
    vector<ll> v;
    vector<int> parent(N + 1);
    vector<int> d(N + 1);
    int next = 1;
    v.push_back(0);
    s.push(0);
    parent[0] = -1;

    for (int i = 0; i < (int)S.size(); i++)
    {
        if (S[i] == '(')
        {
            v.push_back(A[next - 1]);
            s.push(next);
            next++;
        }
        else
        {
            int me = s.top();
            s.pop();
            int p = s.top();

            parent[me] = p;
            d[p]++;
        }
    }

    ll x = 0;
    ll ans = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for (int i = 1; i <= N; i++)
    {
        if (d[i] == 0)
        {
            pq.emplace(v[i], i);
        }
    }

    while (!pq.empty())
    {
        ll val = pq.top().first;
        int n = pq.top().second;
        pq.pop();

        if (n == 0) break;

        x += val;
        ans += x;
        d[parent[n]]--;
        if (d[parent[n]] == 0)
        {
            pq.emplace(v[parent[n]], parent[n]);
        }
    }

    cout << ans << endl;
}
0