76pts wa2,6,8 答案少1 求调qwq
查看原帖
76pts wa2,6,8 答案少1 求调qwq
648756
Shadow_Lord楼主2023/3/29 19:18
#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;
}
2023/3/29 19:18
加载中...