No.1345 Beautiful BINGO
タグ : / 解いたユーザー数 79
作問者 :
maguro
/ テスター :
KoD
PCTprobability
Problem Statement
maguro loves puzzles. For his senior, who also loves puzzles, maguro has made a puzzle bingo.
The bingo is played on a sheet of $N \times N$ squares. Let $(i,j) \ (1 \leq i,j \leq N)$ denote the square in the $i$-th row from the top and the $j$-th column from the left.
Each square has a puzzle written on it, and to open $(i,j)$, you must solve the puzzle on that square by spending $A_{i,j}$ intellect.
Normally, completing even a single line makes a bingo, but maguro is not satisfied with an ordinary bingo. Among the $N$ columns, the $N$ rows, and the $2$ diagonals, at least $M$ of them must have all $N$ squares on them open.
Find the minimum total intellect that must be spent to satisfy this condition.
(2021/3/24) Part of the problem statement has been corrected.
Input
$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}$
- All inputs are integers.
- $2 \leq N \leq 16$
- $1 \leq M \leq 2N + 2$
- $1 \leq A_{i,j} \leq 100\ (1 \leq i,j \leq N)$
Output
Output the minimum total intellect that must be spent to satisfy the condition. Print a newline at the end.
Sample
Sample 1
Input
3 2 3 1 4 1 5 9 2 6 5
Output
11
It is optimal to open $(1,1),(1,2),(1,3),(2,1),(3,1)$.
Sample 2
Input
4 3 1 9 3 2 4 1 2 5 7 2 1 6 2 9 8 1
Output
21
It is optimal to open $(1,1),(1,4),(2,1),(2,2),(2,3),(2,4),(3,2),(3,3),(4,1),(4,4)$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。