No.1247 ブロック登り
タグ : / 解いたユーザー数 34
作問者 : 👑
ngtkana
問題文
$N$ 個のセルが横一列に並んでおり、セルには左から順に $1$ から $N$ の番号がついています。
最初、全てのセルにはブロックが積まれておらず、高さは $0$ です。
あなたは以下の手順で高さ $K$ まで登ることにしました。
- 開始地点とするセルを一つ選び、そこに移動する。
- 以下の行動を $K$ 回繰り返す。
- 現在、自分がいるセルと隣接しているセルを一つ選ぶ。$i$ 回目の行動では、選んだセルの高さが $i$ となるようにブロックを積み、選んだセルに移動する。
高さ $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もしくは右上の雲マークをクリックしてアカウントを作成してください。