問題一覧 > 通常問題

No.1247 ブロック登り

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 23
作問者 : tute7627tute7627 / テスター : ngtkanangtkana
5 ProblemId : 4458 / 出題時の順位表
問題文最終更新日: 2020-08-24 20:23:49

問題文

$N$ 個のセルが横一列に並んでおり、セルには左から順に $1$ から $N$ の番号がついています。
最初、全てのセルにはブロックが積まれておらず、高さは $0$ です。
あなたは以下の手順で高さ $K$ まで登ることにしました。

  1. 開始地点とするセルを一つ選び、そこに移動する。
  2. 以下の行動を $K$ 回繰り返す。
    • 現在、自分がいるセルと隣接しているセルを一つ選ぶ。$i$ 回目の行動では、選んだセルの高さが $i$ となるようにブロックを積み、選んだセルに移動する。
なお、二つのセルの番号の差の絶対値が $1$ に等しい時に限り、二つのセルは隣接しているとします。

高さ $K$ まで登った後の番号 $i$ のセルの高さを $H_i$ として登り方のスコアを $A_1 H_1 + A_2 H_2 + \dots + A_N H_N$ と定義します。
開始地点を番号 $1,2,\dots,N$ のセルとしたときのそれぞれについて、登り方のスコアの最大値を求めてください。

入力

$N\ K$
$A_1\ A_2 \dots A_N$
  • 入力は全て整数である。
  • $2 \le N \le 300$
  • $1 \le K \le 300$
  • $-10000 \le A_i \le 10000$

出力

$N$ 行出力してください。
$i$ 行目には開始地点を番号 $i$ のセルとしたときの登り方のスコアの最大値を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
5 4
1 3 3 2 4
出力
31
25
31
29
28

開始地点を番号 $5$ のセルとした場合を考えます。
$1$ 回目の行動では番号 $4$ のセルに移動するしかありません。セルの高さは左から $(0,0,0,1,0)$ となります。
$2$ 回目の行動では番号 $3$ のセルに移動します。セルの高さは左から $(0,0,2,1,0)$ となります。
$3$ 回目の行動では番号 $4$ のセルに移動します。セルの高さは左から $(0,0,2,3,0)$ となります。
$4$ 回目の行動では番号 $5$ のセルに移動します。ここで高さ $K$ に到達し、$H=(0,0,2,3,4)$ となります。
この登り方のスコアは、$1 \times 0 + 3 \times 0 + 3 \times 2 + 2 \times 3 + 4 \times 4 = 28$ となります。

サンプル2
入力
3 6
-10000 -10000 -10000
出力
-110000
-110000
-110000

サンプル3
入力
8 8
9 1 9 -2 -1 7 4 6
出力
133
143
140
134
148
132
154
123

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。