問題一覧 > 通常問題

No.1247 ブロック登り

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 35
作問者 : 👑 tute7627 / テスター : ngtkana
お気に入りにしたユーザー ProblemId : 4458 / 自分の提出
問題文最終更新日: 2020-08-24 20:23:49
Block Climbing
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 268 (順位表) の他の問題:

Problem Statement

$N$ cells are arranged in a horizontal row, numbered $1$ to $N$ from left to right.
Initially, no blocks are stacked on any cell, and every cell has height $0$.
You have decided to climb up to height $K$ by the following procedure.

  1. Choose one cell as the starting point and move there.
  2. Repeat the following action $K$ times.
    • Choose one cell adjacent to the cell you are currently on. In the $i$-th action, stack blocks so that the height of the chosen cell becomes $i$, then move to the chosen cell.
Two cells are adjacent if and only if the absolute difference of their numbers is equal to $1$.

Let $H_i$ be the height of cell $i$ after climbing up to height $K$. The score of a climb is defined as $A_1 H_1 + A_2 H_2 + \dots + A_N H_N$.
For each of the cases where the starting point is cell $1,2,\dots,N$, find the maximum score of a climb.

Input

$N\ K$
$A_1\ A_2 \dots A_N$
  • All inputs are integers.
  • $2 \le N \le 300$
  • $1 \le K \le 300$
  • $-10000 \le A_i \le 10000$

Output

Output $N$ lines.
On the $i$-th line, output the maximum score of a climb when the starting point is cell $i$.
Print a newline at the end.

Sample

Sample 1
Input
5 4
1 3 3 2 4
Output
31
25
31
29
28

Consider the case where the starting point is cell $5$.
In the $1$st action, the only option is to move to cell $4$. The heights of the cells from the left become $(0,0,0,1,0)$.
In the $2$nd action, move to cell $3$. The heights of the cells from the left become $(0,0,2,1,0)$.
In the $3$rd action, move to cell $4$. The heights of the cells from the left become $(0,0,2,3,0)$.
In the $4$th action, move to cell $5$. Height $K$ is reached here, and $H=(0,0,2,3,4)$.
The score of this climb is $1 \times 0 + 3 \times 0 + 3 \times 2 + 2 \times 3 + 4 \times 4 = 28$.

Sample 2
Input
3 6
-10000 -10000 -10000
Output
-110000
-110000
-110000

Sample 3
Input
8 8
9 1 9 -2 -1 7 4 6
Output
133
143
140
134
148
132
154
123

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