問題一覧 > 通常問題

No.2095 High Rise

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 107
作問者 : koboshikoboshi / テスター : p-adicp-adic
5 ProblemId : 7205 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-30 18:22:22

問題文

$N$ 階建てのマンションがあり、各階には $M$ 部屋あります。

このマンションにはエレベーターがなかったので、新たにエレベーターを設置することにしました。そのため、いくつかの部屋をエレベーター設置のために取り壊すことにしました。

$i$ 階にある $j$ 番目の部屋を取り壊すには費用 $A_{i,j}$ がかかります。

部屋を取り壊した後、エレベーターを次のように設置します。

  • $i_1,i_2,j \ (1\le i_1\lt i_2\le N, 1\le j\le M)$ に対して、$i_1,i_1+1,\ldots,i_2$ 階の $j$ 番目の部屋がすべて取り壊されているとき、この場所にエレベーターを設置することができる。これにより $i_1,i_1+1,\ldots,i_2$ 階が互いに行き来可能になる。
  • エレベーターは複数台設置してもよい。

エレベーターを使って $1$ 階からすべての階に行けるようにしたいです。エレベーターは複数台使ってもよいです。

$1$ 階からすべての階に行けるようにするために必要な、部屋を取り壊す費用の合計の最小値を求めてください。

制約

  • $1\le N,M\le 1000$
  • $1\le A_i\le 10^9$
  • 入力はすべて整数

入力

$N$ $M$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,M}$
$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,M}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,M}$

出力

$1$ 階からすべての階に行けるようにするために必要な部屋を取り壊す費用の最小値を出力してください。

サンプル

サンプル1
入力
3 4
9 9 9 1
1 9 9 1
1 9 9 9
出力
4

取り壊す費用が $1$ の部屋をすべて取り壊せばよいです。

サンプル2
入力
4 3
2 3 6
2 3 6
6 3 2
6 3 2
出力
12

サンプル3
入力
1 1
998244353
出力
0

取り壊す必要はありません。

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