有氧100pts,无氧80pts求助!

P1719 最大加权矩形

poor_OIer @ 2024-07-28 22:07:00

#include<bits/stdc++.h>
using namespace std;
int n,a[125][125],tot[125][125][125],ans=-1828810;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=read(),tot[i][1][j]=a[i][j]+tot[i][1][j-1];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<n;k++)
                tot[i][k][j]=tot[i][1][j]-tot[i][1][k];
        }
    }
    for(int fromi=1;fromi<=n;fromi++)
        for(int fromj=1;fromj<=n;fromj++)
            for(int toi=fromi;toi<=n;toi++)
                for(int toj=fromj;toj<=n;toj++)
                {
                    int sum=0;
                    for(int i=fromi;i<=toi;i++)
                        sum+=tot[i][fromj][toj];
                    if(sum>ans)
                        ans=sum;
                }
    cout<<ans;
    return 0;
}

by tallnut @ 2024-07-28 22:24:16

@poor_OIer

不是。。你这五次方复杂度吸氧居然能过。。


by piyuhan666 @ 2024-08-09 10:02:49

what


by qiutian02 @ 2024-08-24 18:08:24

6


by ymmy @ 2024-11-01 16:52:02

666


|