NC19900. [AHOI2014]拼图
描述
输入描述
每个输入文件中包含多组测试数据。
输入文件第一行包含一个整数T，代表测试数据的组数，接下来按顺序描述了每组测试数据。
每组测试数据的第一行包含两个整数S和N。
接下来S组输入，第i组对应编号为i的拼图。
在第i组输入中，第一行包含一个整数；
接下来N行描述一个N行列的0/1矩形；
其中第x行y列为0则表示该拼图对应位置的颜色是白色，反之则为黑色。
输出描述
对于每组数据输出一行包含一个整数ans，表示最大可能的全白色子矩形的面积。
示例1
输入:
1 3 4 4 1001 0000 0010 1001 3 000 010 000 011 2 00 10 01 00
输出:
6
C++11(clang++ 3.9) 解法, 执行用时: 62ms, 内存消耗: 888K, 提交时间: 2019-03-16 14:05:10
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<vector>
using namespace std;
#define LL long long
int read()
{
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
return s*f;
}
int read2()
{
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';break;ch=getchar();}
return s*f;
}
//smile please
int T,S,N,w[100005],ans;
bitset<100005> sa[405],pa;
int rr[405];
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
for(T=read();T--;)
{S=read();N=read();ans=0;
if(N<=300)
{
for(int i=1;i<=S;i++)
{w[i]=read()+w[i-1];
for(int j=1;j<=N;j++)
for(int k=w[i-1]+1;k<=w[i];k++)
sa[j][k]=read2();
}
for(int i=1;i<=N;i++)
{pa=sa[i];
for(int j=i;j<=N;j++)
{pa|=sa[j];
int sum=0,sum2=0;
int l1=0,lw1=0,l2=0;
int r1=0,rw1=0,r2=0;
for(int k=1;k<=w[S];k++)
sum=(pa[k]?0:sum+1),
ans=max(ans,(j-i+1)*sum);
for(int k=1;k<=S;k++)
{sum=0;
for(int l=w[k-1]+1;l<=w[k]&&!pa[l];l++)
sum++;
if(sum==w[k]-w[k-1])
{sum2+=w[k]-w[k-1];continue;}
if(sum>l1)
l2=l1,l1=sum,lw1=k;
else
if(sum>l2)
l2=sum;
sum=0;
for(int l=w[k];l>=w[k-1]+1&&!pa[l];l--)
sum++;
if(sum>r1)
r2=r1,r1=sum,rw1=k;
else
if(sum>r2)
r2=sum;
}
ans=max(ans,((lw1==rw1?max(l1+r2,l2+r1):l1+r1)+sum2)*(j-i+1));
}
}
}
else
{
for(int i=1;i<=S;i++)
{w[i]=read()+w[i-1];
for(int j=1;j<=N;j++)
for(int k=w[i-1]+1;k<=w[i];k++)
sa[k][j]=read2();
}
for(int j=1;j<=w[S];j++)
rr[j]=0;
for(int i=N;i>=1;i--)
{for(int j=1;j<=w[S];j++)
rr[j]=(sa[j][i]?0:rr[j]+1);
for(int j=1;j<=w[S];j++)
{int sum=0,sum2=0;
int l1=0,lw1=0,l2=0;
int r1=0,rw1=0,r2=0;
for(int k=1;k<=w[S];k++)
sum=(rr[k]<rr[j]?0:sum+1),
ans=max(ans,rr[j]*sum);
for(int k=1;k<=S;k++)
{sum=0;
for(int l=w[k-1]+1;l<=w[k]&&rr[l]>=rr[j];l++)
sum++;
if(sum==w[k]-w[k-1])
{sum2+=w[k]-w[k-1];continue;}
if(sum>l1)
l2=l1,l1=sum,lw1=k;
else
if(sum>l2)
l2=sum;
sum=0;
for(int l=w[k];l>=w[k-1]+1&&rr[l]>=rr[j];l--)
sum++;
if(sum>r1)
r2=r1,r1=sum,rw1=k;
else
if(sum>r2)
r2=sum;
}
ans=max(ans,((lw1==rw1?max(l1+r2,l2+r1):l1+r1)+sum2)*rr[j]);
}
}
}
printf("%d\n",ans);
}
//fclose(stdin);
//fclose(stdout);
return 0;
}