poj 3494 单调栈

#include<cstdio> #include<cstring> #define MAX(x,y) ((x)>(y)?(x):(y)) using namespace std; int n,m,d[2020]; int stack[2020],l[2020],r[2020]; long long res; void cal() { int tot=0; for(int i=0;i<n;i++) { while(tot>0&&d[stack[tot-1]]>=d[i]) tot--; l[i]=tot==0?0:(stack[tot-1]+1); stack[tot++]=i; } tot=0; for(int i=n-1;i>=0;i--) { while(tot>0&&d[stack[tot-1]]>=d[i]) tot--; r[i]=tot==0?n:stack[tot-1]; stack[tot++]=i; } for(int i=0;i<n;i++) res=MAX(res,d[i]*(r[i]-l[i])); } int main() { while(~scanf("%d%d",&m,&n)) { int x; res=0; memset(d,0,sizeof(d)); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { scanf("%d",&x); if(x) d[j]+=1; else d[j]=0; } cal(); } printf("%lld\n",res); } }