P99568

线性代数

难度 7 级 网络流
讨论 统计 0通过 0提交 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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

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

输入

第一行输入一个整数 n。接下来 n 行输入 B 矩阵,第 i 行第 j 个数代表 B 接下来一行输入 n 个整数,代表矩阵 C。矩阵 B 和矩阵 C 中每个数字都是不过 1000 的非负整数。

输出

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

样例

样例 1
输入
3
1 2 1
3 1 0
1 2 3
2 3 7
输出
2

提示

  • 对于 30\% 的数据,n \leq 15;
  • 对于 100\% 的数据,1 \leq n \leq 500;

来源

天津省选

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交