結果
問題 | No.3147 Parentheses Modification and Rotation (RM Ver.) |
ユーザー |
👑 ![]() |
提出日時 | 2025-05-16 22:12:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 964 bytes |
コンパイル時間 | 2,115 ms |
コンパイル使用メモリ | 198,468 KB |
実行使用メモリ | 8,968 KB |
最終ジャッジ日時 | 2025-05-16 22:12:35 |
合計ジャッジ時間 | 3,281 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define all(p) p.begin(), p.end() #define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++) using ll = long long; #include <atcoder/segtree> struct F{ int sum = 0; int mim = 0; }; F op(F l, F r){ l.mim = min(l.mim, l.sum + r.mim); l.sum += r.sum; return l; } F e(){ return F{}; } int main(){ int N; cin >> N; string S; cin >> S; ll R, M; cin >> R >> M; if (N & 1){ cout << "-1\n"; return 0; } vector<F> base(N); rep(i, 0, N){ if (S[i] == '(') base[i] = {1, 0}; else base[i] = {-1, -1}; } rep(i, 0, N) base.push_back(base[i]); atcoder::segtree<F, op, e> seg(base); ll ans = (1ll << 60); rep(i, 0, N){ auto tmp = seg.prod(N - i, 2 * N - i); int z = (1 - tmp.mim) / 2; z += abs(tmp.sum + z * 2) / 2; ans = min(ans, R * i + z * M); } cout << ans << "\n"; }