60分，求调

Handsome_Brother_Boy @ 2024-07-12 15:02:32

#include<bits/stdc++.h>
using namespace std;
long long n,a[101][101],s[101][101],maxn;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int x=i;x<=n;x++)
            {
                for(int y=j;y<=n;y++)
                {
                    maxn=max(maxn,s[x][y]-s[i][y]-s[x][j]+s[i][j]);
                }
            }
        }
    }
    cout<<maxn;
    return 0;
 } 

by qiuribomu @ 2024-07-12 15:06:25

4个for不超时？

by kczw @ 2024-07-12 15:07:44

@Handsome_Brother_Boy

#include<bits/stdc++.h>
using namespace std;
long long n,a[121][121],s[121][121],maxn;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int x=i;x<=n;x++)
            {
                for(int y=j;y<=n;y++)
                {
                    maxn=max(maxn,s[x][y]-s[i-1][y]-s[x][j-1]+s[i-1][j-1]);
                }
            }
        }
    }
    cout<<maxn;
    return 0;
 } 

by kczw @ 2024-07-12 15:08:53

@Handsome_Brother_Boy 首先题目最下面有 n\le 120

by kczw @ 2024-07-12 15:11:36

其次类前缀和，求区间 [l,r] 的和是 presum_r-presum_{l-1}，求从第 i 行第 j 列到第 x 行第 y 列的公式也理应是 presum_{x,y}-presum_{i-1,y}-presum_{x,j-1}+presum_{i-1,j-1}。

by kczw @ 2024-07-12 15:13:33

@qiuribomu

by qiuribomu @ 2024-07-12 15:17:00

@qzhongly 我傻了，忘看范围了，4个for给我看呆了

by kczw @ 2024-07-12 15:21:18

@qiuribomu 人之常情，但感觉应该有更优的方法。

by Handsome_Brother_Boy @ 2024-07-12 15:27:42

@qzhongly 谢谢大佬

by ChelseaLi @ 2024-07-25 17:08:45

@qiuribomu 根本不会超时的，这是类似于判断边界的

by shanshan8487 @ 2024-07-29 16:33:29

wa！