結果
問題 | No.3144 Parentheses Modification and Rotation (01 Ver.) |
ユーザー |
![]() |
提出日時 | 2025-05-16 22:24:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 2,141 bytes |
コンパイル時間 | 985 ms |
コンパイル使用メモリ | 103,364 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-27 06:00:06 |
合計ジャッジ時間 | 2,595 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; template <typename T> class segTree { private: const T e; int num; std::vector<T> dat; T (*const eval)(T &, T &) {}; public: segTree(std::vector<T> &v, T E, T (*func)(T &, T &)) : e(E), eval(func) { int siz = static_cast<int>(v.size()); for (num = 1; num < siz; num <<= 1); dat = std::vector<T> (2 * num - 1, e); for (int i = 0; i < siz; ++i) dat[i + num - 1] = v[i]; for (int i = num - 2; i >= 0; --i) dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]); } segTree(int n, T E, T (*func)(T &, T &)) : e(E), eval(func) { for (num = 1; num < n; num <<= 1); dat = std::vector<T> (2 * num - 1, e); } void update_a(int i, T val) { for (i += num - 1, dat[i] = val; i != 0;) { i = (i - 1) / 2; dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]); } } void update_r(int i, T val) { for (i += num - 1, dat[i] = eval(dat[i], val); i != 0;) { i = (i - 1) / 2; dat[i] = eval(dat[i * 2 + 1], dat[i * 2 + 2]); } } T getval(int left, int right) { left = std::max(0, left), right = std::min(num, right); T ansl = e, ansr = e; for (left += num - 1, right += num - 1; left < right; left >>= 1, right >>= 1) { if (!(left & 1)) ansl = eval(ansl, dat[left]); if (--right & 1) ansr = eval(dat[right], ansr); } return eval(ansl, ansr); } T getval(int id) {return dat[num - 1 + id];} }; int main() { int n; cin >> n; string s; cin >> s; int r, m; cin >> r >> m; if (n % 2) { cout << "-1" << endl; return 0; } vector<int> sum(2 * n + 1); for (int i = 0; i < 2 * n; ++i) sum[i + 1] = sum[i] + (s[i % n] == '(' ? 1 : -1); segTree<int> sg(sum, 1e9, [](int &a, int &b) -> int {return min(a, b);}); long long ans = 1e18; for (int i = 0; i < n; ++i) { int mi = sg.getval(i, i + n + 1); int tmp = sum[i] - mi; long long cnt = (tmp + 1) / 2; cnt += abs(sum[i] - sum[i + n] - (tmp + 1) / 2 * 2) / 2; long long c = cnt * m + (long long)i * r; ans = min(ans, c); } cout << ans << endl; }