#P3996. [TJOI2015]线性代数

    ID: 2915 传统题 1000ms 128MiB 尝试: 2191 已通过: 843 难度: 7 上传者: 标签>CF2300提高+/省选-最小割建模Dinic当前弧优化最大流最小割定理闭合子图问题

[TJOI2015]线性代数

[TJOI2015] 线性代数

题目描述

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

她的小伙伴菠萝给她出了这样一个问题:给定一个 n×nn \times n 的矩阵 BB 和一个 1×n1 \times n 的矩阵 CC。求出一个 1×n1×n 的 01 矩阵 AA,使得 D=(A×B−C)×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\% 的数据,n≤15n \leq 15;
  • 对于 100%100\% 的数据,1≤n≤5001 \leq n \leq 500;