#include #include #include using namespace std; const long long INF = 1e18; int main() { // 入出力の高速化 ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; if (!(cin >> n >> k)) return 0; vector a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } // 自明な不可能判定 // N個の数列から隣接せずに選べる最大個数は (N + 1) / 2 個 if (k > (n + 1) / 2) { cout << "Impossible\n"; return 0; } // dp[j][flag] // j: 選んだ個数 (0 <= j <= k) // flag: 直前の要素を選んだか (0: 選んでいない, 1: 選んだ) vector> dp(k + 1, vector(2, -INF)); dp[0][0] = 0; for (int i = 0; i < n; ++i) { vector> next_dp(k + 1, vector(2, -INF)); for (int j = 0; j <= k; ++j) { // 【遷移1】i番目の提出を削除しない場合 // 前回削除していても、していなくてもよいので、大きい方を引き継ぐ next_dp[j][0] = 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]; } } // テーブルを更新 swap(dp, next_dp); } // 答えは N 番目まで見て K 個選んだ状態の最大値 long long ans = max(dp[k][0], dp[k][1]); cout << ans << "\n"; return 0; }