#![allow(non_snake_case, unused_imports)] use std::collections::{BinaryHeap, Bound, HashMap, HashSet, VecDeque}; use std::hash::Hash; use std::ops::RangeBounds; use ac_library::{Additive, Min, Segtree}; use proconio::{input, marker::Usize1, marker::Chars}; use itertools::Itertools; #[allow(unused_macros)] macro_rules! d { ( $( $x:expr ),* $(,)? ) => { eprintln!( concat!( $( stringify!($x), "={:?} " ),* ), $( $x ),* ); }; } #[allow(dead_code)] fn yn(b: bool) -> &'static str { if b { "Yes" } else { "No" } } fn accum_dp( xs: &[X], f: impl Fn(K, V, X) -> Vec<(K, V)>, op: impl Fn(V, V) -> V, e: V, init: impl IntoIterator, ) -> HashMap where K: Eq + Hash + Copy, V: Copy, X: Copy, { let mut dp: HashMap = init.into_iter().collect(); for &x in xs { let pp = std::mem::take(&mut dp); for (fm_key, fm_val) in pp { for (to_key, to_val) in f(fm_key, fm_val, x) { let old = dp.get(&to_key).copied().unwrap_or(e); dp.insert(to_key, op(old, to_val)); } } } dp } fn main() { input! { N: usize, K: usize, A: [i64; N], } let op = |a: i64, b: i64| a.max(b); let f = |k: (usize, bool), v, x| { // k : (選んだ個数, 直前を選んだか) let (cnt, b) = k; let mut res = Vec::new(); // 選ばない res.push(((cnt, false), v)); if !b && cnt < K { res.push(((cnt+1, true), v+x)); } res }; let init = [((0, false), 0)]; let dp = accum_dp(&A, f, op, i64::MIN, init); let mut ans = i64::MIN; for ((cnt, _), v) in dp { if cnt == K { ans = ans.max(v) } } if ans == i64::MIN { println!("Impossible"); } else { println!("{}", ans); } }