#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(K,vector>>(N,vector>(N,vector(2,-INF)))); rep(i,N-1){ dp[K-1][i][i+1][0]=A[i]*K+A[i+1]*(K-1); dp[K-1][i][i+1][1]=A[i]*(K-1)+A[i+1]*K; } vector>>> p(2,vector>>(N+2)); for(int c=K-1;c>=0;c--){ rep(j,N) rep(i,j) rep(k,2){ if(c=j-i+1) chmax(dp[c-j+i-1][i-1][j][1],dp[c][i][j][k]+A[i-1]*(c-j+i-1)); }else{ if(j+1!=N&&c>=j-i+1) chmax(dp[c-j+i-1][i][j+1][0],dp[c][i][j][k]+A[j+1]*(c-j+i-1)); if(i!=0) chmax(dp[c-1][i-1][j][1],dp[c][i][j][k]+A[i-1]*(c-1)); } } } vector> q(2); rep(i,N){ for(auto x:p[i%2][i]){ if(x.second==1) q[i%2].insert(x.first); else q[i%2].delate(x.first); } cout<