結果
問題 | No.2591 安上がりな括弧列 |
ユーザー |
|
提出日時 | 2023-12-19 22:01:29 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,664 bytes |
コンパイル時間 | 1,733 ms |
コンパイル使用メモリ | 143,072 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-27 09:00:26 |
合計ジャッジ時間 | 2,564 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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;}