use std::convert::TryFrom; trait OrdTools: Ord + Clone + Sized { fn chmin(&mut self, x: Self) { *self = std::cmp::min(self.clone(), x); } fn chmax(&mut self, x: Self) { *self = std::cmp::max(self.clone(), x); } } impl OrdTools for T {} fn main() { let stdin = std::io::stdin(); let (n, l) = { let mut s = String::new(); stdin.read_line(&mut s).unwrap(); let s = s.trim_end().to_owned(); let mut s = s.split_whitespace(); let n: usize = s.next().unwrap().parse().unwrap(); let l: usize = s.next().unwrap().parse().unwrap(); assert!(s.next().is_none()); (n, l) }; let a = { let mut s = String::new(); stdin.read_line(&mut s).unwrap(); let s = s.trim_end().to_owned(); let mut s = s.split_whitespace(); let mut a = vec![0; n]; a.iter_mut() .for_each(|x| *x = s.next().unwrap().parse().unwrap()); assert!(s.next().is_none()); a }; let mut ans = vec![std::i32::MIN; n]; let mut dp = vec![vec![vec![std::i32::MIN; n]; n]; l + 1]; (0..n).for_each(|j| dp[l][j][j] = l as i32 * a[j]); for i in (0..=l).rev() { if i + 3 <= l { let [crr, _, prv, _] = <&mut [_; 4]>::try_from(&mut dp[i..=i + 3]).unwrap(); for j in 0..n { for k in 0..n { crr[j][k].chmax(prv[j][k]); } } } let (first, last) = dp.split_at_mut(i); let crr = &last[0]; for j in 0..n { let mut update = |ni: usize, nj: usize, nk: usize, k| { first[ni][nj][nk].chmax(crr[j][k] + ni as i32 * a[nj]); }; for k in (0..=j).filter(|&k| crr[j][k] != std::i32::MIN) { let d = j - k; if d + 1 <= i && 0 < k { update(i - d - 1, k - 1, j, k); } if 0 < i && j + 1 < n { update(i - 1, j + 1, k, k); } } for k in (j..n).filter(|&k| crr[j][k] != std::i32::MIN) { let d = k - j; if 0 < i && 0 < j { update(i - 1, j - 1, k, k); } if d + 1 <= i && k + 1 < n { update(i - d - 1, k + 1, j, k); } } } (0..n.checked_sub(i).unwrap_or(0)) .for_each(|j| (j + i..n).for_each(|k| ans[j + i].chmax(crr[j][k]))); (i..n).for_each(|j| (0..=j - i).for_each(|k| ans[j - i].chmax(crr[j][k]))); } ans.iter().for_each(|x| println!("{}", x)); }