結果

問題 No.3148 Min-Cost Destruction of Parentheses
ユーザー tassei903
提出日時 2025-05-16 23:04:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 143 ms / 4,000 ms
コード長 2,293 bytes
コンパイル時間 3,791 ms
コンパイル使用メモリ 294,748 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2025-05-16 23:04:20
合計ジャッジ時間 6,626 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;
const ll INF = 1e18;

#define sz(x) (int)(x).size()
#define rep(i, n) for (int i = 0; i < n; i++)
#define FOR(i, l, r) for(int i = l; i < r; i++)
#define all(v) (v).begin(), (v).end()

template<typename T>
ostream &operator<< (ostream& os, const vector<T> &v){
	rep(i, sz(v)) {
		os << v[i];
		if (i < sz(v)-1)os << " ";
	}
	return os;
}

void out(){
	cout << endl;
}

template<typename Head, typename ...Tail>
void out(Head h, Tail ...t) {
	cout << h << " ";
	out(t...);
}

const int inf = 1e9;
const ll mod = 998244353;
using pii = pair<int, int>;

#include <atcoder/dsu>
#include <atcoder/modint>

using mint = atcoder::modint998244353;

void solve() {
    int n;cin >> n;

    string S;cin >> S;
    vector<int> a(n+1);
    rep(i, n) cin >> a[i+1];
    vector<int> p(n + 1, -1);
    stack<int> sk;sk.push(0);
    int t = 1;
    rep(i, n * 2) {
        if (S[i] == '(') {
            p[t] = sk.top();
            sk.push(t++);
        }
        else {
            sk.pop();
        }
    }
    // FOR(i, 1, n+1) cerr << p[i] << " ";
    // cerr << endl;

    vector<int> cnt(n+1, 1);cnt[0] = 0;
    vector<ll> sum(n+1, 0);
    FOR(i, 1, n + 1) sum[i] = a[i];
    vector<ll> ans(n + 1, 0); FOR(i, 1, n + 1) ans[i] = a[i];

	auto cmp = [&](int a, int b) {
		if(cnt[a] * sum[b] == cnt[b] * sum[a]) return a < b;
		else return (cnt[a] * sum[b] < cnt[b] * sum[a]);
	};

	set<int, decltype(cmp)> pq(cmp);

	FOR(i, 1, n + 1) {
		pq.insert(i);
	}
	// out(pq.size());
	atcoder::dsu dsu(n+1);
	vector<int> mindex(n+1);iota(all(mindex), 0);
	int c = pq.size();
	rep(_, n) {
		// assert(!pq.empty());out(pq.size(), c);
		auto x = pq.begin();
		int i = *x, j = dsu.leader(p[mindex[i]]);
		// assert(!dsu.same(i, j));
		int nxt = dsu.merge(i, j);
		pq.erase(i),c--;if (mindex[j] > 0)pq.erase(j),c--;
		// out(i, j, nxt);
		mindex[nxt] = min(mindex[i], mindex[j]);
		ans[nxt] = ans[i] + ans[j] + cnt[j] * sum[i];
		sum[nxt] = sum[i] + sum[j];
		cnt[nxt] = cnt[i] + cnt[j];
		if (mindex[nxt] > 0) pq.insert(nxt),c++;
	}

	// out(ans);
	ll s = sum[dsu.leader(0)];
	cout << ans[dsu.leader(0)]<< endl;

}


int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    
    // int T;cin >> T;
    int T = 1;
    while(T--) solve();
    
    
}
0