pub use __cargo_equip::prelude::*; use cplib_lang_macros::chmax; use proconio::{fastout, input}; #[fastout] fn main() { input! { n: usize, k: usize, a: [i64; n], } if n < k * 2 - 1 { println!("Impossible"); return; } let mut dp = vec![vec![i64::MIN / 2; k + 1]; n + 1]; dp[0][0] = 0; for i in 0..n { for j in 0..=k { chmax!(dp[i + 1][j], dp[i][j]); if j > 0 { chmax!(dp[i + 1][j], dp[i.saturating_sub(1)][j - 1] + a[i]); } } } let ans = dp[n][k]; println!("{}", ans); } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `git+https://github.com/cacampu/cplib-rs#macros@0.1.0` licensed under `MIT` as `crate::__cargo_equip::crates::cplib_lang_macros` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod cplib_lang_macros {pub use crate::__cargo_equip::macros::cplib_lang_macros::*;#[macro_export]macro_rules!__cargo_equip_macro_def_cplib_lang_macros_chmin{($a:expr,$b:expr)=>{if$a>$b{$a=$b;true}else{false}};}macro_rules!chmin{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_cplib_lang_macros_chmin!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_cplib_lang_macros_chmax{($a:expr,$b:expr)=>{if$a<$b{$a=$b;true}else{false}};}macro_rules!chmax{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_cplib_lang_macros_chmax!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_cplib_lang_macros_mat{($e:expr;$d:expr)=>{vec![$e;$d]};($e:expr;$d:expr,$($ds:expr),+)=>{vec![mat![$e;$($ds),+];$d]};}macro_rules!mat{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_cplib_lang_macros_mat!{$($tt)*})}} } pub(crate) mod macros { pub mod cplib_lang_macros {pub use crate::{__cargo_equip_macro_def_cplib_lang_macros_chmax as chmax,__cargo_equip_macro_def_cplib_lang_macros_chmin as chmin,__cargo_equip_macro_def_cplib_lang_macros_mat as mat};} } pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;} mod preludes { pub mod cplib_lang_macros {} } }