#![allow(dead_code, unused_imports, unused_macros, non_snake_case)] fn main() { input! { N: usize, S: Chars, R: usize, M: usize, } if N % 2 != 0 { say(-1); return; } let seg = SegTree::::from((0 .. N).map(|i| if S[i] == '(' { (0, 1) } else { (1, 0) } ).to_vec()); let mut ans = INF; for rot in 0 .. N { let l = seg.prod(rot .. N); let r = seg.prod(0 .. rot); let (d, u) = H::op(&l, &r); let d2u = (d + 1) / 2; let u2d = (u + d % 2) / 2; ans.chmin(rot * R + (d2u + u2d) * M); } say(ans); } enum H {} impl SegTreeHelper for H { type F = (); type S = (usize, usize); fn e() -> Self::S { (0, 0) } fn op(&(a, b): &Self::S, &(c, d): &Self::S) -> Self::S { (a + c.saturating_sub(b), d + b.saturating_sub(c)) } } type Int = usize; const MOD: Int = 998244353; // const MOD: Int = 1_000_000_007; const INF: Int = 1_000_000_000_000_000_000; const YESNO: [&'static str; 2] = ["Yes", "No"]; use proconio::{input, input_interactive, marker::{Chars, Bytes, Usize1}}; use std::*; use std::ops::*; use collections::*; // (BTree|Hash)(Set|Map), BinaryHeap, VecDeque, LinkedList use cmp::{self, Reverse}; // cmp::{min, max} fn yes() { println!("{}", YESNO[0]); } fn no() { println!("{}", YESNO[1]); } fn yesno(c: bool) { println!("{}", if c { YESNO[0] } else { YESNO[1] }); } fn say(x: T) -> T { println!("{}", x); x } fn neighbor4(i: usize, j: usize, h: usize, w: usize, mut f: F) { if i > 0 { (f)(i - 1, j); } if i < h - 1 { (f)(i + 1, j); } if j > 0 { (f)(i, j - 1); } if j < w - 1 { (f)(i, j + 1); } } trait MyItertools : Iterator + Sized { fn to_vec(self) -> Vec { self.collect::>() } fn to_vec_rev(self) -> Vec { let mut v = self.collect::>(); v.reverse(); v } fn tally(self) -> HashMap where Self::Item: Copy + Eq + hash::Hash { let mut counts = HashMap::new(); self.for_each(|item| *counts.entry(item).or_default() += 1 ); counts } fn count_if bool>(self, predicate: P) -> usize { self.map(predicate).filter(|&x| x ).count() } fn implode(self, sep: &str) -> String where Self::Item: std::string::ToString { self.map(|x| x.to_string()).to_vec().join(sep) } fn mex(self, gen: impl IntoIterator) -> Self::Item where Self::Item: Ord { let mut v = self.collect::>(); v.sort(); v.dedup(); let mut it = v.into_iter(); gen.into_iter().find(|a| if let Some(x) = it.next() { a != &x } else { true }).unwrap() } } impl MyItertools for T where T: Iterator + Sized {} trait MyOrd : PartialOrd + Sized { fn chmax(&mut self, mut rhs: Self) -> bool { if self < &mut rhs { *self = rhs; true } else { false } } fn chmin(&mut self, mut rhs: Self) -> bool { if self > &mut rhs { *self = rhs; true } else { false } } } impl MyOrd for T {} #[derive(Debug, Clone, Default)] pub struct BTreeMultiset { len: usize, set: BTreeMap } impl<'a, T: Ord> BTreeMultiset { pub fn new() -> Self { Self { len: 0, set: BTreeMap::new() } } pub fn len(&self) -> usize { self.len } pub fn count(&self, x: &T) -> usize { self.set.get(x).copied().unwrap_or(0) } pub fn insert_multiple(&mut self, x: T, count: usize) -> usize { self.len += count; let n = self.set.entry(x).or_insert(0); *n += count; *n } pub fn insert(&mut self, x: T) -> usize { self.insert_multiple(x, 1) } pub fn remove_multiple(&mut self, x: &T, count: usize) -> usize { if let Some(n) = self.set.get_mut(x) { let n0 = *n; *n = n0.saturating_sub(count); let n = *n; self.len -= n0 - n; if n == 0 { self.set.remove(x); } n } else { 0 } } pub fn remove(&mut self, x: &T) -> usize { self.remove_multiple(x, 1) } pub fn iter(&'a self) -> btree_map::Iter<'a, T, usize> { self.set.iter() } pub fn into_iter(self) -> btree_map::IntoIter { self.set.into_iter() } pub fn keys(&'a self) -> btree_map::Keys<'a, T, usize> { self.set.keys() } pub fn range(&'a self, range: impl RangeBounds) -> btree_map::Range<'a, T, usize> { self.set.range(range) } } use segtree::*; pub mod segtree { // Update: 2022-10-29 12:45 #[allow(unused_variables)] pub trait SegTreeHelper { /// 要素の型 type S: Clone; /// 要素の二項演算 fn op(x: &Self::S, y: &Self::S) -> Self::S; /// 要素の単位元 fn e() -> Self::S; /// 作用の型(使わない場合は `()` とする) type F: Clone + Default; /// 要素に作用させる fn map(f: &Self::F, x: &Self::S) -> Self::S { x.clone() } /// 作用の単位元 fn id() -> Self::F { Self::F::default() } /// 作用の合成 fn compose(f: &Self::F, g: &Self::F) -> Self::F { g.clone() } /// 再計算が必要か fn is_failed(x: &Self::S) -> bool { false } } pub struct SegTree { len: usize, size: usize, log: u32, data: UnsafeCell>, lazy: UnsafeCell>, } impl SegTree { /// 長さが `len` 、要素が全て `H::e()` となるセグメント木を作成する。 pub fn new(len: usize) -> Self { assert!(len > 0); let size = len.next_power_of_two(); let log = size.trailing_zeros(); Self { len, size, log, data: UnsafeCell::new(vec![H::e(); size * 2]), lazy: UnsafeCell::new(vec![H::id(); size]), } } /// `p` 番目の要素を取得する。 pub fn get(&self, p: usize) -> H::S { self[p].clone() } /// `p` 番目の要素に `x` を代入する。 pub fn set(&mut self, mut p: usize, x: H::S) { assert!(p < self.len); p += self.size; for i in (1 ..= self.log).rev() { self.push(p >> i); } self.data_mut()[p] = x; for i in 1 ..= self.log { self.update(p >> i); } } /// `range` に含まれる要素の積を取得する。 pub fn prod(&self, range: impl RangeBounds) -> H::S { let (mut l, mut r) = self.range(range); assert!(l <= r); assert!(r <= self.len); l += self.size; r += self.size; if l == r { return H::e(); } for i in (1 ..= self.log).rev() { if (l >> i) << i != l { self.push(l >> i); } if (r >> i) << i != r { self.push(r - 1 >> i); } } let mut x = H::e(); let mut y = H::e(); while l < r { if l & 1 != 0 { x = H::op(&x, &self.data()[l]); l += 1; } l >>= 1; if r & 1 != 0 { y = H::op(&self.data()[r - 1], &y); } r >>= 1; } H::op(&x, &y) } /// 全体の積を取得する。 pub fn all_prod(&self) -> H::S { self.data()[1].clone() } /// `p` 番目の要素に `f` を適用する。 pub fn apply(&mut self, p: usize, f: &H::F) { assert!(p < self.len); let x = H::map(f, &self[p]); self.set(p, x); } /// `range` に含まれる要素に `f` を適用する。 pub fn apply_range(&mut self, range: impl RangeBounds, f: &H::F) { let (mut l, mut r) = self.range(range); assert!(l <= r); assert!(r <= self.len); l += self.size; r += self.size; for i in (1 ..= self.log).rev() { if (l >> i) << i != l { self.push(l >> i); } if (r >> i) << i != r { self.push(r - 1 >> i); } } let (l, r) = { let (l2, r2) = (l, r); while l < r { if l & 1 != 0 { self.all_apply(l, f); l += 1; } l >>= 1; if r & 1 != 0 { self.all_apply(r - 1, f); } r >>= 1; } (l2, r2) }; for i in 1 ..= self.log { if (l >> i) << i != l { self.update(l >> i); } if (r >> i) << i != r { self.update(r - 1 >> i); } } } pub fn max_right(&self, mut l: usize, mut predicate: impl FnMut(&H::S) -> bool) -> usize { assert!(l <= self.len); assert!(predicate(&H::e())); if l == self.len { return self.len; } l += self.size; for i in (1 ..= self.log).rev() { self.push(l >> i); } let mut x = H::e(); loop { l >>= l.trailing_zeros(); if !predicate(&H::op(&x, &self.data()[l])) { while l < self.size { self.push(l); l *= 2; let y = H::op(&x, &self.data()[l]); if predicate(&y) { x = y; l += 1; } } return l - self.size; } x = H::op(&x, &self.data()[l]); l += 1; if l.is_power_of_two() { break; } } self.len } pub fn min_left(&self, mut r: usize, mut predicate: impl FnMut(&H::S) -> bool) -> usize { assert!(r <= self.len); assert!(predicate(&H::e())); if r == 0 { return 0; } r += self.size; for i in (1 ..= self.log).rev() { self.push(r - 1 >> i); } let mut x = H::e(); loop { r -= 1; r >>= r.trailing_zeros(); if !predicate(&H::op(&self.data()[r], &x)) { while r < self.size { self.push(r); r = 2 * r + 1; let y = H::op(&self.data()[r], &x); if predicate(&y) { x = y; r -= 1; } } return r + 1 - self.size; } x = H::op(&self.data()[r], &x); if r.is_power_of_two() { break; } } 0 } fn update(&self, k: usize) { let z = H::op(&self.data()[k * 2], &self.data()[k * 2 + 1]); self.data_mut()[k] = z; } fn all_apply(&self, k: usize, f: &H::F) { let y = H::map(f, &self.data()[k]); self.data_mut()[k] = y; if k < self.size { let h = H::compose(&self.lazy()[k], f); self.lazy_mut()[k] = h; if H::is_failed(&self.data()[k]) { self.push(k); self.update(k); } } } fn push(&self, k: usize) { self.all_apply(2 * k, &self.lazy()[k]); self.all_apply(2 * k + 1, &self.lazy()[k]); self.lazy_mut()[k] = H::id(); } fn range(&self, range: impl RangeBounds) -> (usize, usize) { use Bound::*; (match range.start_bound() { Included(&p) => p, Excluded(&p) => p + 1, Unbounded => 0 }, match range.end_bound() { Included(&p) => p + 1, Excluded(&p) => p, Unbounded => self.len }) } fn data(&self) -> &Vec { unsafe { &*self.data.get() } } fn lazy(&self) -> &Vec { unsafe { &*self.lazy.get() } } fn data_mut(&self) -> &mut Vec { unsafe { &mut *self.data.get() } } fn lazy_mut(&self) -> &mut Vec { unsafe { &mut *self.lazy.get() } } } impl From> for SegTree { fn from(xs: Vec) -> Self { let this = Self::new(xs.len()); for (p, x) in xs.into_iter().enumerate() { this.data_mut()[this.size + p] = x; } for k in (1 .. this.size).rev() { this.update(k); } this } } impl FromIterator for SegTree { fn from_iter>(iter: T) -> Self { Self::from(iter.into_iter().collect::>()) } } impl Index for SegTree { type Output = H::S; fn index(&self, mut p: usize) -> &H::S { assert!(p < self.len); p += self.size; for i in (1 ..= self.log).rev() { self.push(p >> i); } &self.data()[p] } } impl Debug for SegTree where H::S: Debug, H::F: Debug { fn fmt(&self, f: &mut Formatter<'_>) -> Result { f.write_fmt(format_args!("len={}, size={}, log={}, e={:?}, id={:?}\n", self.len, self.size, self.log, H::e(), H::id()))?; let data_str = self.data().iter().map(|x| format!("{:?}", x)).collect::>(); let lazy_str = self.lazy().iter().map(|x| format!("({:?})", x)).collect::>(); let unit_width = lazy_str.iter().chain(data_str.iter()).map(String::len).max().unwrap(); fn print_row(f: &mut Formatter<'_>, raw_row: &[String], pad: usize) -> Result { let mut row = vec![]; for raw in raw_row { row.push(format!("{:^width$}", raw, width=pad)); } f.write_str("|")?; f.write_str(&row.join("|"))?; f.write_str("|\n") } for i in 0 .. self.log { print_row(f, &data_str[1 << i .. 2 << i], (unit_width + 1) * (1 << self.log - i) - 1)?; print_row(f, &lazy_str[1 << i .. 2 << i], (unit_width + 1) * (1 << self.log - i) - 1)?; } print_row(f, &data_str[self.size ..], unit_width)?; Ok(()) } } use std::{cell::*, fmt::*, iter::*, ops::*}; }