sample input
5 6
7 2 3 1 1
5 0 6 0 0
8 6 6 5 3
4 3 7 8 2
4 0 0 6 9
sample output
20
样例解释:
分别以(2,1)为左上角(5,2)为右下角和以(1,3)为左上角以(4,5)
为右下角的两个矩阵。
数据范围:
对于20的数据n≤5
对于50的数据n≤50
另有5的数据满足所有电脑的便利值均为1
另另有25的数据满足所有的电脑便利值相同
对于100的数据满足n≤300，p≤50，0≤a[i][j]≤65536
首先，我们会想到n^4的暴力dp，但一看n的范围，完全装不下。
所以我们要考虑优化掉一维。
我们考虑枚举l和r这两条线，代表矩形的左右边界，同时我们对每一行求一个前缀和，方便我们更新。
l和r为矩形的左右两边，i和tong[i]为上下两边。
tong[i]的作用下次再说。
这样，我们就会得到每个矩形的和，并考虑对答案的贡献。
我们开两个数组f[i],g[i]
g[i]表示i这条直线的右边的最大矩形（不一定紧贴）
f[i]是紧贴着i这条线的左边的最大矩形
tong[i]存每一次矩形数字之和%p后的结果，第一次出现在哪一行。-1为没有出现过。（可能有点绕口雾）
tot为当前矩形的数字之和 tot += sum[i][r] - sum[i][l-1];
设k为tot % p之后的结果，当k不为1时会有以下两种情况。
1.k为0，是p的倍数，表明可以更新答案。
2.k这个结果以前出现过，那么tong[k]到k这一行矩形的数字和也恰好是p的倍数。
我们就可以更新一下两个数组。。
f[r] = max(f[r],(r-l+1) * (i-tong[tot]));
g[l] = max(g[l],(r-l+1) * (i-tong[tot]));
当我们矩形都找完后，还要在更新一下g数组，因为我们只考虑了紧贴的情况，而没有考虑不紧贴。
务必要倒叙枚举，因为后面的答案可以影响前面的结果，所以要倒序。
那么答案是什么呢？？？
for(int i = 1; i < n-1; i++) ans = max(ans,f[i] + g[i+1]);
i一定要到n-2不能到n-1，因为到n的话g数组的定义就会矛盾。
g[i+1]是为了防止与f[i]的边重叠。
PS：
对于为什么在“第二种：以前出现过模p得到k的情况”的时候也要更新答案？“
我们重新考虑题意：一块矩形的和是p的倍数，也就是模p为零
可以用式子表示为：
s当前−s上一次≡0(modp)
进一步转化为：
s当前≡s上一次(modp)
所以可理解为，只要上一次和这一次在模p意义的数字一样，就可以更新答案了，因为他们相减之后一定是p的倍数，可手跑几组例子
至此，关于“第二种：以前出现过模p得到k的情况”的时候也要更新答案？”这句话，也就不难理解了——from Thestars。
但我们发现少考虑了一种一个矩形在上，一个矩形在下的情况，这是我们只要旋转一下，在跑一遍就ok了
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,p,f[310],g[310],sum[310][310],tong[55],a[310][310],ans;
inline int read()
{
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10+ch -'0'; ch = getchar();}
return s * w;
}
void slove()
{
for(int i = 1; i <= n; i++) f[i] = g[i] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
sum[i][j] = sum[i][j-1] + a[i][j];//每一行求一个区间和
}
}
for(int l = 1; l <= n; l++)//枚举左边的线
{
for(int r = l; r <= n; r++)//右边的线
{
for(int i = 1; i <= p ;i++) tong[i] = -1;//桶里存模p结果第一次出现的行数 ，tong[0] 不要忘记初始化为0
int tot = 0;
for(int i = 1; i <= n; i++)
{
tot += sum[i][r] - sum[i][l-1];
tot %= p;//模p的结果开个桶
if(tong[tot] != -1)//不是第一次出现
{
f[r] = max(f[r],(r-l+1) * (i-tong[tot]));//更新
g[l] = max(g[l],(r-l+1) * (i-tong[tot]));
}
else tong[tot] = i;
}
}
}
for(int i = n-1; i; i--) g[i] = max(g[i],g[i+1]);//这一步考虑的是没有紧贴的情况
for(int i = 1; i < n-1; i++) ans = max(ans,f[i] + g[i+1]);
}
void zhuan()
{
for(int i = 1; i <= n; i++)
{
for(int j = i+1; j <= n; j++)
{
int xx = a[i][j]; int yy = a[j][i];
xx ^= yy; yy ^= xx; xx ^= yy;
a[i][j] = xx; a[j][i] = yy;
}
}
}
int main()
{
n = read(); p = read();
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
a[i][j] = read();
}
}
slove();
zhuan();
slove();
printf("%d\n",ans);
fclose(stdin); fclose(stdout);
return 0;
}