#include #pragma GCC optimize("Ofast") #define _GLIBCXX_DEBUG using namespace std; using std::cout; using std::cin; using std::endl; using ll=long long; using ld=long double; ll ILL=1167167167167167167; const int INF=1100000000; const ll mod=1e9+7; #define rep(i,a) for (int i=0;i using _pq = priority_queue, greater>; template ll LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template ll UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;} template bool chmax(T &a,const T &b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} void yneos(bool a){if(a) cout<<"Yes\n"; else cout<<"No\n";} namespace po167{ template struct my_set_max{ priority_queue exist; priority_queue absent; void op(){ while(!absent.empty()&&exist.top()==absent.top()){ exist.pop(); absent.pop(); } } size_t size(){ op(); return exist.size()-absent.size(); } T get(){ op(); return exist.top(); } void insert(T a){ exist.push(a); } void delate(T a){ absent.push(a); } }; template struct my_set_min{ priority_queue, greater> exist; priority_queue, greater> absent; void op(){ while(!absent.empty()&&exist.top()==absent.top()){ exist.pop(); absent.pop(); } } T get(){ op(); return exist.top(); } size_t size(){ op(); return exist.size()-absent.size(); } void insert(T a){ exist.push(a); } void delate(T a){ absent.push(a); } }; template struct my_set_med{ my_set_max pq_left; my_set_min pq_right; void op(){ while(pq_left.size()>pq_right.size()){ T tmp=pq_left.get(); pq_left.delate(tmp); pq_right.insert(tmp); } while(pq_left.size()a) pq_left.insert(a); else pq_right.insert(a); } void delate(T a){ if(pq_left.size()!=0&&pq_left.get()>=a) pq_left.delate(a); else pq_right.delate(a); } std::pair get(){ op(); assert(pq_left.size()!=0); if(pq_left.size()==pq_right.size()){ return {pq_left.get(),pq_right.get()}; } else return {pq_left.get(),pq_left.get()}; } size_t size(){ return pq_left.size()+pq_right.size(); } }; } using po167::my_set_max; using po167::my_set_min; using po167::my_set_med; void solve(); // oddloop int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t=1; //cin>>t; rep(i,t) solve(); } void solve(){ int N,K; cin>>N>>K; vector A(N); rep(i,N) cin>>A[i]; vector>>> dp(2,vector>>(K,vector>(N,vector(N,-INF)))); rep(i,N-1){ dp[0][K-1][i][i+1]=A[i]*K+A[i+1]*(K-1); dp[1][K-1][i][i+1]=A[i]*(K-1)+A[i+1]*K; } vector>> p(N+2); for(int c=K-1;c>=0;c--){ rep(k,2) rep(j,N) rep(i,j){ if(c=K-2||tmp!=dp[k][c+2][i][j]){ int l=i,r=min(j,i+c),d=i; if(k==0) l=max(i,j-c),r=j,d=j; d+=c; d%=2; if(r%2!=d) r--; if(l%2!=d) l++; r+=2; p[l].push_back({tmp,1}); p[r].push_back({tmp,-1}); } if(c==0) continue; if(k==0){ if(j+1!=N) chmax(dp[0][c-1][i][j+1],tmp+A[j+1]*(c-1)); if(i!=0&&c>=j-i+1) chmax(dp[1][c-j+i-1][i-1][j],tmp+A[i-1]*(c-j+i-1)); }else{ if(j+1!=N&&c>=j-i+1) chmax(dp[0][c-j+i-1][i][j+1],tmp+A[j+1]*(c-j+i-1)); if(i!=0) chmax(dp[1][c-1][i-1][j],tmp+A[i-1]*(c-1)); } } } vector> q(2); rep(i,N){ for(auto x:p[i]){ if(x.second==1) q[i%2].insert(x.first); else q[i%2].delate(x.first); } cout<