AcWing 1413. 矩形牛棚
原题链接
中等
作者:
geats兔
,
2024-04-04 01:03:12
,
所有人可见
,
阅读 6
#include<iostream>
const int N=3010;
using namespace std;
int g[N][N],h[N][N];
int stack[N],top;
int l[N],r[N];
int n,m,p;
int work(int h[N]){
h[0]=h[m+1]=-1;
top=0;
stack[++top]=0;
for(int i=1;i<=m;i++)
{
while(top&&h[stack[top]]>=h[i]) top--;
l[i]=stack[top];
stack[++top]=i;
}
top=0;
stack[++top]=m+1;
for(int i=m;i>0;i--){
while(top&&h[stack[top]]>=h[i]) top--;
r[i]=stack[top];
stack[++top]=i;
}
int res=0;
for(int i=1;i<=m;i++)
res=max(res,h[i]*(r[i]-l[i]-1));
return res;
}
int main()
{
cin>>n>>m>>p;
while(p--){
int x,y;
cin>>x>>y;
g[x][y]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(!g[i][j])
h[i][j]=h[i-1][j]+1;
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,work(h[i]));
cout<<res<<endl;
return 0;
}