#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define mind(a,b) (a>b?b:a) #define maxd(a,b) (a>b?a:b) #define absd(x) (x<0?-(x):x) #define pow2(x) ((x)*(x)) #define rep(i,n) for(int i=0; i=0; --i) #define repl(i,s,n) for(int i=s; i<=n; ++i) #define replr(i,s,n) for(int i=n; i>=s; --i) #define repf(i,s,n,j) for(int i=s; i<=n; i+=j) #define repe(e,obj) for(auto e : obj) #define SP << " " << #define COL << " : " << #define COM << ", " << #define ARR << " -> " << #define PNT(STR) cout << STR << endl #define POS(X,Y) "(" << X << ", " << Y << ")" #define DEB(A) " (" << #A << ") " << A #define DEBREP(i,n,val) for(int i=0; i P; //typedef pair P; typedef pair PI; typedef pair IP; typedef pair PP; typedef priority_queue, greater

> pvqueue; #define N 3003 int n, m; int w[N]; int dp[N], rs[N]; bool used[N][N]; int base; int main() { cin >> n >> m; rep(i, n) cin >> w[i]; int ans = -INF; // 1 rep(i, m+1) dp[i] = rs[i] = -INF; dp[1] = 0; repl(i, 1, n-1) { int dp2[N]; int base = (i==n-1 ? w[n-1] : 0); dp2[0] = -INF; rep(j, m) { dp2[j+1] = maxd(-INF, dp[j]+w[i-1]+base); dp2[j+1] = maxd(dp2[j+1], rs[j]+base); } rep(j, m+1) rs[j] = maxd(dp[j], rs[j]); rep(j, m+1) dp[j] = dp2[j]; ans = maxd(ans, dp[m]); } // 0 rep(i, m+1) dp[i] = rs[i] = -INF; rs[0] = 0; repl(i, 1, n-1) { int dp2[N]; dp2[0] = -INF; rep(j, m) { dp2[j+1] = maxd(-INF, dp[j]+w[i-1]); dp2[j+1] = maxd(dp2[j+1], rs[j]); } rep(j, m+1) rs[j] = maxd(dp[j], rs[j]); rep(j, m+1) dp[j] = dp2[j]; ans = maxd(ans, dp[m]); } cout << ans << endl; return 0; }