AcWing 1413. 矩形牛棚
原题链接
中等
作者:
开始独自升级
,
2023-12-01 11:25:57
,
所有人可见
,
阅读 84
#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int n,m;
int p;
int s[N][N];
int sn[N][N];
int solve(int a[])
{
int stk[N],tt=0,w[N];
a[0]=a[m+1]=-1;
stk[tt]=0;
for(int i=1;i<=m;i++)
{
while(tt!=0&&a[stk[tt]]>=a[i])
tt--;
w[i]=i-stk[tt];
stk[++tt]=i;
}
tt=0;
stk[tt]=m+1;
for(int i=m;i>=1;i--)
{
while(tt!=0&&a[stk[tt]]>=a[i])
tt--;
w[i]+=stk[tt]-i;
stk[++tt]=i;
}
int sum=0;
for(int i=1;i<=m;i++)
sum=max(sum,(w[i]-1)*a[i]);
return sum;
}
int main()
{
cin>>n>>m>>p;
while(p--)
{
int x,y;
cin>>x>>y;
s[x][y]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(s[i][j]!=1)
sn[i][j]=sn[i-1][j]+1;
else
sn[i][j]=0;
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,solve(sn[i]));
cout<<res<<endl;
return 0;
}