use proconio::input; use std::cmp; const INF: i64 = 1_000_000_000_000_000_000; fn main() { input! { n: usize, k: usize, a: [i64; n], } // 自明な不可能判定 // N個の数列から隣接せずに選べる最大個数は (N + 1) / 2 個 if k > (n + 1) / 2 { println!("Impossible"); return; } // dp[j][flag] // j: 選んだ個数 (0 <= j <= k) // flag: 直前の要素を選んだか (0: 選んでいない, 1: 選んだ) let mut dp = vec![vec![-INF; 2]; k + 1]; dp[0][0] = 0; for i in 0..n { let mut next_dp = vec![vec![-INF; 2]; k + 1]; for j in 0..=k { // 【遷移1】i番目の要素を削除(選ばない)場合 // 前回選んでいても、いなくてもよいので、大きい方を引き継ぐ next_dp[j][0] = cmp::max(dp[j][0], dp[j][1]); // 【遷移2】i番目の要素を選ぶ場合 // 「前回選んでいない状態(dp[j-1][0])」からしか遷移できない if j > 0 && dp[j - 1][0] != -INF { next_dp[j][1] = dp[j - 1][0] + a[i]; } } // テーブルを更新 dp = next_dp; } // 答えは N 番目まで見て K 個選んだ状態の最大値 let ans = cmp::max(dp[k][0], dp[k][1]); println!("{}", ans); }