#include #include //cin/cout #include //cout string #include //rambda #include #include //next/prev #include #include //iota #include #include #include #include #include #include #include using namespace atcoder; using namespace std; using llong = long long; const llong INF = 1LL << 60;//INF > 10^18(1e18) const int INF32 = 1LL << 30;//INF32 > 10^9(1e9) template bool chmax(T& max, const T& b) { if (max >= b) return false; max = b; return true; } template bool chmin(T& min, const T& b) { if (min <= b) return false; min = b; return true; } ///////////////////ここまでtoolbox///////////////////////////////////// int main() { int N, K; cin >> N >> K; if (K * 2 - 1 > N) { cout << "Impossible\n"; return 0; } vectorA(N); for (int n = 0; n < N; n++) { cin >> A[n]; } //dp[2][n][k] = 過去n問に提出をK個削除した時点での不正度の合計 vector>>dp(2,vector>(N+1, vector(K+1, -INF))); dp[0][0][0] = 0; for (int n = 0; n < N; n++) { for (int k = 0; k <= K; k++) { //削除しない chmax(dp[0][n + 1][k], dp[0][n][k]); chmax(dp[0][n + 1][k], dp[1][n][k]); if (k < K) { //削除する chmax(dp[1][n + 1][k + 1], dp[0][n][k] + A[n]); } } } llong ans = max(dp[0][N][K], dp[1][N][K]); cout << ans << endl; return 0; }