P3973 [TJOI2015] Linear Algebra

To improve her IQ, ZJY starts to study linear algebra. Her friend Boluo gives her the following problem: Given an $n \times n$ matrix $B$ and a $1 \times n$ matrix $C$. Find a $1 \times n$ 0-1 matrix $A$ such that $D = (A \times B - C) \times A^{\sf T}$ is maximized, where $A^{\sf T}$ is the transpose of $A$, and output $D$.

The first line contains an integer $n$. The next $n$ lines give matrix $B$: in the $i$-th line, the $j$-th number is $B_{i,j}$. The next line contains $n$ integers, representing matrix $C$. Every number in matrices $B$ and $C$ is a non-negative integer not exceeding $1000$.

Output a single integer, the maximum value of $D$.

- For $30\%$ of the testdata, $n \leq 15$. - For $100\%$ of the testdata, $1 \leq n \leq 500$. - There are also two extra unscored hack testdata in subtask 2, with the same ranges as above. Translated by ChatGPT 5