結果
| 問題 |
No.3148 Min-Cost Destruction of Parentheses
|
| コンテスト | |
| ユーザー |
miscalc
|
| 提出日時 | 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();
}
}
miscalc