結果
問題 | No.3147 Parentheses Modification and Rotation (RM Ver.) |
ユーザー |
|
提出日時 | 2025-05-16 23:57:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 787 bytes |
コンパイル時間 | 4,043 ms |
コンパイル使用メモリ | 253,480 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-05-16 23:57:15 |
合計ジャッジ時間 | 5,839 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; int op(int lhs, int rhs){return min(lhs, rhs);} constexpr int e(){return 1 << 30;} int main(){ int n, r, m; string s; cin >> n >> s >> r >> m; if(n % 2 == 1){ cout << "-1\n"; return 0; } s += s; vector<int> sv(2 * n + 1); for(int i = 0; i < 2 * n; i++){ sv[i + 1] = sv[i] + (s[i] == '(' ? 1 : -1); } atcoder::segtree<int, op, e> seg(sv); ll ans = 1ll << 62; for(int i = 0; i < n; i++){ int mn = min(0, seg.prod(i, i + n) - sv[i]); int tot = (-mn + 1) / 2; int d = (sv[i + n] + 2 * tot) - sv[i]; ans = min(ans, (n - i) % n * (ll)(r) + (ll)(d / 2 + tot) * m); } cout << ans << '\n'; }