#3912. [TJOI2015]线性代数

[TJOI2015]线性代数

[TJOI2015]线性代数

题目描述

为了提高智商,ZJY 开始学习线性代数。

她的小伙伴菠萝给她出了这样一个问题:给定一个 n×nn \times n 的矩阵 BB 和一个 1×n1 \times n 的矩阵 CC。求出一个 1×n1×n 的 01 矩阵 AA,使得 D=(A×BC)×ATD=(A×B-C)×A^{\sf T} 最大,其中ATA^{\sf T}AA的转置,输出DD

输入格式

第一行输入一个整数 nn。接下来 nn 行输入 BB 矩阵,第 ii 行第 jj 个数代表 BB 接下来一行输入 nn 个整数,代表矩阵 CC。矩阵 BB 和矩阵 CC 中每个数字都是不过 10001000 的非负整数。

输出格式

输出一个整数,表示最大的 DD

样例 #1

样例输入 #1

3
1 2 1
3 1 0
1 2 3
2 3 7

样例输出 #1

2

提示

  • 对于 30%30\% 的数据,n15n \leq 15
  • 对于 100%100\% 的数据,1n5001 \leq n \leq 500
  • 另外还有两组不计分的 hack 数据,放在 subtask 2 中,数据范围与上面一致。