/* https://yukicoder.me/problems/no/1246 最終的に使う範囲は区間になる 終点を決めたとする l,rでdp? l,r,0→l,rの区間でどこにいるか 300*300*2*300 最後をどうするかが問題 偶奇別にセグ木を持って更新? O(N*N*K*logN) ? ====解説を見た==== 区間の間の移動は関係ない →偶数回とどまった後に端に移動するという移動に一元化可能 →始点の問題も解決できる dp[今いる端][今いない端][高さ] = スコアの最大値 で解ける */ #include #include #include #include #include #include using namespace std; #define rep(i,n,m) for(int (i)=(n);(i)<(m);(i)++) #define rrep(i,n,m) for(int (i)=(n);(i)>(m);(i)--) using ll = long long; const ll mod = 998244353; const int inf = 1000000000; int main(){ int N,K; scanf("%d %d",&N,&K); vector A(N); rep(i,0,N) scanf("%d" , &A[i]); vector>> dp(N,vector>(N,vector (K+1,-1*inf))); vector ans(N,-1*inf); rep(i,0,N){ dp[i][i][K] = K * A[i]; } rrep(k,K,-1){ rep(a,0,N){ rep(b,0,N){ if (k == 0){ ans[a] = max(dp[a][b][k] , ans[a]); continue; } if (k-2 >= 0 && a != b){ dp[a][b][k-2] = max(dp[a][b][k-2] , dp[a][b][k]); } if (a <= b){ if (a-1 >= 0){ dp[a-1][b][k-1] = max(dp[a-1][b][k-1] , dp[a][b][k] + (k-1)*A[a-1] ); } if (a+k <= b){ ans[a+k] = max(ans[a+k] , dp[a][b][k]); } if (b-a <= k && a != b){ dp[b][a][k-(b-a)] = max(dp[b][a][k-(b-a)] , dp[a][b][k]); } } if (a >= b){ if (a+1 < N){ dp[a+1][b][k-1] = max(dp[a+1][b][k-1] , dp[a][b][k] + (k-1)*A[a+1]); } if (a-k >= b){ ans[a-k] = max(ans[a-k] , dp[a][b][k]); } if (a-b <= k && a != b){ dp[b][a][k-(a-b)] = max(dp[b][a][k-(a-b)] , dp[a][b][k]); } } } } } rep(i,0,N){ printf("%d\n",ans[i]); } }