AcWing 1413. 矩形牛棚
原题链接
中等
作者:
cc_25
,
2024-03-30 15:11:38
,
所有人可见
,
阅读 9
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3010;
int n,m,p;
int g[N][N];
int h[N][N];
int q[N];
int r[N],l[N];
int work(int h[])
{
h[0]=-1,h[m+1]=-1;
int tt=0;
q[tt]=0;
for(int i=1;i<=m;i++)
{
while(h[q[tt]]>=h[i])
{
tt--;
}
l[i]=q[tt]+1;
q[++tt]=i;
}
tt=0;
q[tt]=m+1;
for(int i=m;i>0;i--)
{
while(h[q[tt]]>=h[i])
{
tt--;
}
r[i]=q[tt]-1;
q[++tt]=i;
}
int ans=-1;
for(int i=1;i<=m;i++)
{
ans=max(ans,h[i]*(r[i]-l[i]+1));
}
return ans;
}
signed main()
{
cin>>n>>m>>p;
for(int i=1;i<=p;i++)
{
int a,b;
cin>>a>>b;
g[a][b]=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=-1;
for(int i=1;i<=n;i++)
{
int t=work(h[i]);
res=max(res,work(h[i]));
}
cout<<res<<'\n';
return 0;
}