76pts wa2,6,8 答案少1 求调qwq

P1736 创意吃鱼法

Shadow_Lord @ 2023-03-29 19:18:35

#include<bits/stdc++.h>
using namespace std;
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<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
int n,m,f[2501][2501][2],cnt,ans,num[2501][2501];
bool df[2501][2501];
int main()
{
    n=read();m=read();
    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=m;j++)
        {
            cin>>df[i][j];
            if(df[i][j])num[i][j]++;
            num[i][j]=num[i][j]+num[i-1][j]+num[i][j-1]-num[i-1][j-1];
            if(df[i][j])cnt++;
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(df[i][j])
            {
                cnt--;
                if(df[i-1][j-1])
                {
                    f[i][j][0]=f[i-1][j-1][0]+1;
                }
                if(df[i-1][j+1])
                {
                    f[i][j][1]=f[i-1][j+1][1]+1;
                }
                int x=f[i][j][0],y=f[i][j][1];
                if(num[i][j]-num[i-x][j]-num[i][j-x]+num[i-x][j-x]==x)
                {
                    ans=max(ans,f[i][j][0]);
                }
                else f[i][j][0]=1;
                if(num[i][j+y-1]-num[i][j-1]-num[i-y][j+y-1]+num[i-y][j-1]==y)
                ans=max(ans,f[i][j][1]);
                else f[i][j][1]=1;
            }
            if(cnt==0)break;
        }
    }
    cout<<ans;
    return 0;
}

by Shadow_Lord @ 2023-03-30 18:17:02

已切,此贴完结


|