友矩阵
出题人太菜,暂无测试数据。
题目描述
给定一个 \(n\times m\) 的矩阵 \(A\),以及两个正整数 \(a,b\)。
定义 \(f(X)\) 表示矩阵 \(X\) 中所有元素之和。
定义一个矩阵 \(A\) 的子矩阵 \(S\) 为一个区间的二元组 \(([l_x,r_x],[l_y,r_y])\),恰好满足 \(\forall i\in[l_x,r_x],j\in[l_y,r_y]\),\(A_{i,j}\in S\)。
定义矩阵 \(X\) 上的两个子矩阵 \(A=([l_{A,x},r_{A,x}],[l_{A,y},r_{A,y}])\) 和 \(B=([l_{B,x},r_{B,x}],[l_{B,y},r_{B,y}])\) 互为友矩阵当且仅当满足:
- \(f(A)=f(B)\)
- \((l_{A,x},l_{A,y})=(l_{B,x},l_{B,y})\)
- \((r_{A,x},r_{A,y})\not=(r_{B,x},r_{B,y})\)
- \((r_{A,x}-l_{A,x})+(r_{A,y}-l_{A,y})=(r_{B,x}-l_{B,x})+(r_{B,y}-l_{B,y})\)
- \((r_{A,x}-l_{A,x})-(r_{A,y}-l_{A,y})+(r_{B,x}-l_{B,x})-(r_{B,y}-l_{B,y})=0\)
对 \(A\) 中所有行长为 \(a\),列宽为 \(b\) 且存在友矩阵的子矩阵 \(W\),求 \(f(W)\) 的最大值,若不存在友矩阵输出 Chinese_zjc_ L
。
输入输出格式
输入格式
第一行四个正整数 \(n,m,a,b\)。
接下来 \(n\) 行,第 \(i\) 行 \(m\) 个整数 \(A_{i,1},A_{i,2},\cdots,A_{i,m}\),其中 \(A_{i,j}\) 表示矩阵 \(A\) 第 \(i\) 行第 \(j\) 列的元素。
输出格式
若存在满足条件的子矩阵 \(W\),输出 \(f(W)\) 的最大值,否则输出 Chinese_zjc_ L
。
样例
样例1
输入
5 5 2 1
-1 -5 -2 -4 -1
-5 -2 -4 4 4
5 2 4 4 5
2 -3 3 5 2
-3 3 5 2 5
输出
9
样例2
输入
5 5 2 4
9 -1 9 5 2
0 2 -5 -9 9
-7 -7 -3 -3 -5
4 0 -9 -1 -3
-8 8 2 -2 -7
输出
Chinese_zjc_ L
数据范围
对于第一组样例,有 \(W=([3,4],[4,4])\) 满足条件,其对应的友矩阵为 \(W'=([3,3],[4,5])\)。
对于第二组样例,不存在满足条件的 \(W\),因此输出 Chinese_zjc_ L
。
对于所有的数据,满足 \(1\leq a,b\leq n,m\leq 1000,|A_{i,j}|\leq 1919810,a\not=b\)。
本题捆绑测试,即选手只有通过了一个数据包内的所有数据才能得到相应范围的部分分。
数据包编号 | 分值 | \(n,m\leq\) | \(\lvert A_{i,j}\rvert \leq\) |
---|---|---|---|
\(1\) | \(20\) | \(100\) | \(114514\) |
\(2\) | \(20\) | \(200\) | \(1919810\) |
\(3\) | \(20\) | \(500\) | \(100\) |
\(4\) | \(20\) | \(1000\) | \(2500\) |
\(5\) | \(20\) | \(1000\) | \(1919810\) |