問題一覧 > 通常問題

No.1345 Beautiful BINGO

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 65
作問者 : maguromaguro / テスター : KoDKoD blackyukiblackyuki PCTprobabilityPCTprobability
2 ProblemId : 5745 / 出題時の順位表
問題文最終更新日: 2021-03-24 18:53:43

問題文

maguro君は謎解きが大好きです。同じく謎解きが好きな先輩のために、maguro君は謎解きビンゴを作りました。

ビンゴは $N \times N$ マスの用紙を使って行われます。上から $i$ 行目、左から $j$ 列目のマスを $(i,j) \ (1 \leq i,j \leq N)$ とします。

それぞれのマスには謎が書かれており、 $(i,j)$ を開くためには、 $A_{i,j}$ の知力を消費してそのマスの謎を解く必要があります。

通常、一列でも揃えばビンゴですが、maguro君はただのビンゴでは満足しません。 $N$ 本の列、 $N$ 本の行、 $2$ 本の対角線のうち、それの上にあるマス $N$ 個全て開いているものが $M$ 本以上ある必要があります。

このとき、条件を満たすようにするために消費する知力の総和の最小値を求めてください。

(2021/3/24)問題文を一部修正しました。

入力

$N\ M$
$A_{1,1}\ A_{1,2}\ \cdots\ A_{1,N - 1}\ A_{1,N}$
$A_{2,1}\ A_{2,2}\ \cdots\ A_{2,N - 1}\ A_{2,N}$
$\vdots$
$A_{N,1}\ A_{N,2}\ \cdots\ A_{N,N - 1}\ A_{N,N}$
  • 入力は全て整数である。
  • $2 \leq N \leq 16$
  • $1 \leq M \leq 2N + 2$
  • $1 \leq A_{i,j} \leq 100\ (1 \leq i,j \leq N)$

出力

条件を満たすようにするために消費する知力の総和の最小値を出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 2
3 1 4
1 5 9
2 6 5
出力
11

$(1,1),(1,2),(1,3),(2,1),(3,1)$ を開くのが最適です。

サンプル2
入力
4 3
1 9 3 2
4 1 2 5
7 2 1 6
2 9 8 1
出力
21

$(1,1),(1,4),(2,1),(2,2),(2,3),(2,4),(3,2),(3,3),(4,1),(4,4)$ を開くのが最適です。

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