use proconio::input; use std::collections::VecDeque; fn main() { input! { _n: usize, s: String, r: i64, m: i64, } let a = s .chars() .map(|c| match c { '(' => 1, ')' => -1, _ => unreachable!(), }) .collect::>(); let mut deque = VecDeque::::new(); let mut start_value = 0; let mut end_value = 0; for (i, &x) in a.iter().enumerate() { end_value += x; while let Some(&Event { time: _, value }) = deque.front() { if end_value <= value { deque.pop_back(); } else { break; } } deque.push_back(Event { time: i, value: end_value, }); } let ans = if (end_value - start_value) % 2 == 0 { std::iter::once((start_value, deque.front().unwrap().value, end_value)) .chain(a.iter().enumerate().map(|(i, &x)| { start_value += x; end_value += x; while let Some(&Event { time, value: _ }) = deque.front() { if time < i { deque.pop_front(); } else { break; } } while let Some(&Event { time: _, value }) = deque.front() { if end_value <= value { deque.pop_back(); } else { break; } } deque.push_back(Event { time: s.len() + i, value: end_value, }); (start_value, deque.front().unwrap().value, end_value) })) .enumerate() .map(|(i, (x, y, z))| ((x - y + 1) / 2 + (z - y + 1) / 2) * m + i as i64 * r) .min() .unwrap() } else { -1 }; println!("{ans}"); } #[derive(Debug, Clone, Copy)] struct Event { time: usize, value: i64, }