记录编号	594781	评测结果	AAAAA
题目名称	不重叠正方形	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.671 s
提交时间	2024-10-05 10:59:06	内存使用	34.13 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
long long pre[1010][1010],sum[1010][1010],a[1010][1010]; 
long long tl[1010][1010],tr[1010][1010],bl[1010][1010],br[1010][1010],ans; 
//对于任何一个选取三个网格的方案，我们总是可以用两条平行于坐标轴的线将三个网格划分到三个区域内（反证） 
int main()
{ 
    freopen("zfx.in","r",stdin);
    freopen("zfx.out","w",stdout);
    scanf("%d%d",&n,&m); 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%lld",&a[i][j]);
        } 
    }  
    for(int i=1;i<=n;i++)//前缀和，pre[i][j]代表前i行前j列的数字之和
    {
        for(int j=1;j<=n;j++)
        {
            pre[i][j]=pre[i-1][j]+pre[i][j-1]+a[i][j]-pre[i-1][j-1];
        }  
    } 
    for(int i=m;i<=n;i++)//差分求出 sum[i][j]，代表以(i,j)为右下角坐标的m*m网格内数字之和
    {
        for(int j=m;j<=n;j++)
        {
            sum[i][j]=pre[i][j]-pre[i-m][j]-pre[i][j-m]+pre[i-m][j-m];
        } 
    } 
    for(int i=m;i<=n;i++)//左上角的最大值，tl[i][j]代表在<=i行，<=j列的区域内，最大的m*m网格数字之和 
    {
        for(int j=m;j<=n;j++)
        {
            tl[i][j]=max(max(tl[i][j-1],tl[i-1][j]),sum[i][j]);
        }
    } 
    
    for(int i=m;i<=n;i++)//右上角 <=i >=j
    {
        for(int j=n-m+1;j>=1;j--)
        {
            tr[i][j]=max(max(tr[i][j+1],tr[i-1][j]),sum[i][j+m-1]);
        }
    } 
    for(int i=n-m+1;i>=1;i--)//左下角 >=i <=j
    {
        for(int j=m;j<=n;j++)
        {
            bl[i][j]=max(max(bl[i+1][j],bl[i][j-1]),sum[i+m-1][j]);
        }
    } 
    for(int i=n-m+1;i>=1;i--)//右下角 >=i >=j
    {
        for(int j=n-m+1;j>=1;j--)
        {
            br[i][j]=max(max(br[i+1][j],br[i][j+1]),sum[i+m-1][j+m-1]);
        }
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
	{ 
        //横向切分，此时i,j代表中间m*m矩阵的右下角坐标 
        if(i-m>=m && i+m<=n && j>=m)  ans=max(ans,sum[i][j]+tr[i-m][1]+br[i+1][1]); 
        //纵向切分，此时i,j代表中间m*m矩阵的右下角坐标
        if(i>=m && j-m>=m && j+m-1<=n)  ans=max(ans,sum[i][j]+bl[1][j-m]+br[1][j+1]); 
        //i,j 代表中间分割点右下角的坐标 
        if(i-1>=m&&i+m-1<=n&&j-1>=m&&j+m-1<=n)
		{ 
            //以i-1为横线，以j-1下半部分为竖线 
            ans=max(ans,br[i][j]+bl[i][j-1]+tr[i-1][1]); 
            //以i-1为横线，以j-1上半部分为竖线 
            ans=max(ans,br[i][1]+tl[i-1][j-1]+tr[i-1][j]); 
            //以j-1为竖线，以i-1左半部分为横线 
            ans=max(ans,br[1][j]+tl[i-1][j-1]+bl[i][j-1]); 
            //以j-1为竖线,以i-1右半部分为横线 
            ans=max(ans,br[i][j]+bl[1][j-1]+tr[i-1][j]);  
        } 
    } 
    printf("%lld",ans);
    return 0;
}