結果
問題 | No.2591 安上がりな括弧列 |
ユーザー |
|
提出日時 | 2023-12-19 22:01:20 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,664 bytes |
コンパイル時間 | 4,549 ms |
コンパイル使用メモリ | 151,624 KB |
最終ジャッジ日時 | 2025-02-18 12:20:12 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <algorithm> #include <cstdint> #include <cstddef> #include <functional> #include <iostream> #include <numeric> #include <ranges> #include <vector> #include <atcoder/lazysegtree> using range_add_range_min = atcoder::lazy_segtree< int, [](int x, int y) { return std::min(x, y); }, []{ return 1 << 30; }, int, [](int f, int x) { return f + x; }, [](int f, int g) { return f + g; }, []{ return 0; } >; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::string s; std::cin >> n >> s; std::vector<long long> a(2 * n); for (auto &e : a) std::cin >> e; std::vector<long long> cost(2 * n); long long ans = 0; for (int i = 0; i < 2 * n; ++i) { if (s[i] == '(') { ans += a[i]; cost[i] = -a[i]; } else { cost[i] = a[i]; } } std::vector<int> p(2 * n); std::iota(p.begin(), p.end(), 0); std::ranges::sort(p, {}, [&cost](int i) { return cost[i]; }); std::vector<int8_t> used(2 * n, false); std::vector<int> init(2 * n + 1); for (int i = 0; i < n; ++i) init[i + 1] = init[i] + 1; for (int i = n; i < 2 * n; ++i) init[i + 1] = init[i] - 1; range_add_range_min seg(init); int r = n - 1; for (int i : p) { used[i] = true; if (i <= r) { ans += cost[i]; continue; } while (r >= 0 and used[r]) --r; if (r < 0) break; if (seg.prod(r + 1, i + 1) >= 2) { ans += cost[i]; seg.apply(r + 1, i + 1, -2); --r; } } std::cout << ans << std::endl; }