AcWing 1413. 矩形牛棚
原题链接
中等
作者:
我已经不想再做刺客了
,
2022-02-25 20:42:32
,
所有人可见
,
阅读 232
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=3010;
int a[N][N],h[N][N],n,m,k,l[N],r[N],tt,q[N],ans;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>k;
while(k--){
int x,y;
cin>>x>>y;
a[x][y]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!a[i][j])h[i][j]=h[i-1][j]+1;
}
}
for(int i=1;i<=n;i++){
h[i][0]=-1;
tt=0;
q[tt]=0;
for(int j=1;j<=m;j++){
while(h[i][j]<=h[i][q[tt]])tt--;
l[j]=q[tt];
q[++tt]=j;
}
h[i][m+1]=-1;
tt=0;
q[tt]=m+1;
for(int j=m;j>=1;j--){
while(h[i][j]<=h[i][q[tt]])tt--;
r[j]=q[tt];
q[++tt]=j;
}
for(int j=1;j<=m;j++){
if(!a[i][j])
ans=max(ans,h[i][j]*(r[j]-l[j]-1));
}
}
cout<<ans;
}