// 問題文と制約は読みましたか? // #[fastout] fn main() { input! { n :usize, k :usize, xs: [i64; n] } let mut dp = vec![vec![[NEG_INF; 2]; k + 1]; n + 1]; dp[0][0][false as usize] = fin(0); for i in 0..n { for ki in 0..=k { dp[i + 1][ki][false as usize] = max(dp[i][ki][true as usize], dp[i][ki][false as usize]); if ki != 0 { dp[i + 1][ki][true as usize] = dp[i][ki - 1][false as usize] + xs[i]; } } } let ans = max(dp[n][k][false as usize], dp[n][k][true as usize]); if ans.is_fin() { println!("{}", ans.get_fin()); } else { println!("Impossible"); } } // ====== import ====== #[allow(unused_imports)] use { itertools::{Itertools, chain, iproduct, izip}, proconio::{ derive_readable, fastout, input, marker::{Bytes, Chars, Usize1}, }, std::{ cmp::Reverse, collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet}, }, }; // ====== output func ====== #[allow(unused_imports)] use print_util::*; pub mod print_util { use itertools::Itertools; use proconio::fastout; #[fastout] pub fn print_vec(arr: &[T]) { for a in arr { println!("{}", a); } } #[fastout] pub fn print_vec_1line(arr: &[T]) { println!("{}", arr.iter().join(" ")); } #[fastout] pub fn print_vec2>(arr: &[R]) { for row in arr { println!("{}", row.as_ref().iter().join(" ")); } } pub fn print_bytes(bytes: &[u8]) { println!("{}", std::str::from_utf8(bytes).unwrap()); } pub fn print_chars(chars: &[char]) { println!("{}", chars.iter().collect::()); } #[fastout] pub fn print_vec_bytes>(vec_bytes: &[R]) { for row in vec_bytes { println!("{}", std::str::from_utf8(row.as_ref()).unwrap()); } } #[fastout] pub fn print_vec_chars>(vec_chars: &[R]) { for row in vec_chars { println!("{}", row.as_ref().iter().collect::()); } } pub fn print_yesno(ans: bool) { println!("{}", if ans { "Yes" } else { "No" }); } } // ====== snippet ====== use {mod_neg_ext_int::*, std::cmp::max}; pub mod mod_neg_ext_int { use std::{ cmp::Ordering, convert::Infallible, fmt, ops::{Add, AddAssign, Mul, Sub, SubAssign}, }; pub const NEG_INF: NegExtInt = NegExtInt::NEG_INF; pub fn fin(x: i64) -> NegExtInt { NegExtInt::fin(x) } #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)] pub struct NegExtInt(i64); impl NegExtInt { pub const NEG_INF: Self = Self(i64::MIN); pub fn fin(x: i64) -> Self { Self(x) } pub fn get_fin(self) -> i64 { if self.is_fin() { self.0 } else { panic!("called `NegExtInt::get_fin()` on a negative infinity") } } pub fn get_fin_or(self, default: i64) -> i64 { if self.is_fin() { self.0 } else { default } } #[inline] pub fn is_fin(self) -> bool { self.0 != i64::MIN } pub fn is_neg_inf(self) -> bool { self.0 == i64::MIN } pub fn to_option(self) -> Option { if self.is_fin() { Some(self.0) } else { None } } pub fn from_option(opt: Option) -> NegExtInt { match opt { Some(a) => Self(a), None => Self::NEG_INF, } } pub fn times(self, t: i64) -> Self { self * t } } impl Add for NegExtInt { type Output = NegExtInt; fn add(self, rhs: Self) -> Self::Output { if self.is_neg_inf() || rhs.is_neg_inf() { Self::NEG_INF } else { Self::fin(self.0 + rhs.0) } } } impl AddAssign for NegExtInt { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl Add for NegExtInt { type Output = NegExtInt; fn add(self, rhs: i64) -> Self::Output { if self.is_neg_inf() { Self::NEG_INF } else { Self::fin(self.0 + rhs) } } } impl AddAssign for NegExtInt { fn add_assign(&mut self, rhs: i64) { *self = *self + rhs; } } impl Sub for NegExtInt { type Output = NegExtInt; fn sub(self, rhs: i64) -> Self::Output { if self.is_neg_inf() { Self::NEG_INF } else { Self::fin(self.0 - rhs) } } } impl SubAssign for NegExtInt { fn sub_assign(&mut self, rhs: i64) { *self = *self - rhs; } } impl Mul for NegExtInt { type Output = NegExtInt; fn mul(self, rhs: i64) -> Self::Output { match rhs.cmp(&0) { Ordering::Less => panic!("multiplier must be non-negative."), Ordering::Equal => Self::fin(0), Ordering::Greater => { if self.is_fin() { Self::fin(self.0 * rhs) } else { Self::NEG_INF } } } } } impl std::iter::Sum for NegExtInt { fn sum>(iter: I) -> Self { let mut s = 0; for x in iter { if x.is_neg_inf() { return Self::NEG_INF; } s += x.0; } Self::fin(s) } } impl fmt::Display for NegExtInt { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { if self.is_neg_inf() { write!(f, "-∞") } else { write!(f, "{}", self.0) } } } impl fmt::Debug for NegExtInt { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { if self.is_neg_inf() { write!(f, "-∞") } else { write!(f, "{}", self.0) } } } }