fn main() { input!{ n: usize, t: i64, x: i64, y: i64, mut d: [i64; n], } // dは昇順にする d.sort(); // 階差を取る let mut diff_d = Vec::new(); for i in 0..n-1 { diff_d.push(d[i+1] - d[i]); } // 順番に見て階差がt以上の個数を数える let mut upper_cnt = 0; for i in 0..n-1 { if diff_d[i] > t { upper_cnt += 1;} } // 順番を入れ替えることで、1->2に交換していき、minを得る let mut ret = upper_cnt * x; let mut pq = (upper_cnt, 0); for i in (0..upper_cnt).rev() { if ret > i * x + (upper_cnt - i) * y { ret = i * x + (upper_cnt - i) * y; pq = (i, upper_cnt - i); } } let mut ans = Vec::new(); for _i in 0..n-1 { ans.push(pq.0 * x + pq.1 * y); // 1個ずつ取り出す if x > y { if pq.0 > 0 { pq.0 -= 1;} else if pq.1 > 0 { pq.1 -= 1;} } else { if pq.1 > 0 { pq.1 -= 1;} else if pq.0 > 0 { pq.0 -= 1;} } } ans.push(0); ans.reverse(); for i in 0..n-1 { print!("{} ", ans[i]); } println!("{}", ans[n-1]); } // const MOD17: usize = 1000000007; // const MOD93: usize = 998244353; // const INF: usize = 1 << 60; // let dx = vec![!0, 0, 1, 0]; // 上左下右 // let dy = vec![0, !0, 0, 1]; // 上左下右 // let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; // 上左下右 #[allow(unused)] use proconio::{input, marker::Chars, marker::Usize1}; #[allow(unused)] use std::{ mem::swap, cmp::min, cmp::max, cmp::Reverse, collections::HashSet, collections::BTreeSet, collections::HashMap, collections::BTreeMap, collections::BinaryHeap, collections::VecDeque, iter::FromIterator, };