80分求助,#4爆蛋了qwq
查看原帖
80分求助,#4爆蛋了qwq
223362
Peter3245127684楼主2020/9/8 21:55
#include<bits/stdc++.h>
#define N 2010
using namespace std;
int n,m,Sqr,Mat;
int a[N][N],l[N][N],r[N][N],up[N][N];
template <typename T>
inline T read(T &x)
{
	T flg=1;x=0;
	char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') flg=-flg;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*=flg;
}
template <typename T>
inline void write(T x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T>
inline void writeln(T x) {write(x);puts("");}
template <typename T>
inline void writesp(T x) {write(x);putchar(' ');}
inline int sqr(int x) {return x*x;}
inline int min(const int &x,const int &y) {return x<y?x:y;}
inline int max(const int &x,const int &y) {return x>y?x:y;}
inline void solve(int op)
{
	memset(l,0,sizeof(l));
	memset(r,0,sizeof(r));
	memset(up,0,sizeof(up));
	for(register int i=1;i<=n;++i)
	  for(register int j=1;j<=m;++j)
	    {
	      if(op==1)
	        {
	          if(i&1) a[i][j]^=(j&1);
	          else a[i][j]^=(!(j&1));
			}
	      else a[i][j]^=1;
	      if(!a[i][j]) continue;
	      l[i][j]=r[i][j]=j;
	      up[i][j]=1;
		}
	for(register int i=1;i<=n;++i)
	  for(register int j=2;j<=m;++j)
	    {
	      if(!a[i][j]) continue;
	      if(a[i][j-1]) l[i][j]=l[i][j-1];
		}
	for(register int i=1;i<=n;++i)
	  for(register int j=m-1;j>=1;--j)
	    {
	      if(!a[i][j]) continue;
	      if(a[i][j+1]) r[i][j]=r[i][j+1];
		}
	for(register int i=1;i<=n;++i)
	  for(register int j=1;j<=m;++j)
	    {
	      if(!a[i][j]) continue;
	      if(i>1&&a[i-1][j])
	        {
	          l[i][j]=max(l[i][j],l[i-1][j]);
	          r[i][j]=min(r[i][j],r[i-1][j]);
	          up[i][j]=up[i-1][j]+1;
			}
		  int len=r[i][j]-l[i][j]+1;
		  Sqr=max(Sqr,sqr(min(len,up[i][j])));
		  Mat=max(Mat,len*up[i][j]);
		}
}
signed main()
{
	read(n);read(m);
	for(register int i=1;i<=n;++i)
	  for(register int j=1;j<=m;++j)
	    read(a[i][j]);
	solve(0);solve(1);
	writeln(Sqr);write(Mat);
	return 0;
}
2020/9/8 21:55
加载中...