1 solutions
-
0
C++ :
#include<iostream> #include<cstring> #include<cstdio> #include<stack> using namespace std; const int maxn=1002; int n,m,tot=0,a[maxn][maxn]={0},Left[maxn]={0},Right[maxn]={0}; void init(); void monotone(); int main() { init(); monotone(); return 0; } void init() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int x; cin>>x; if(x==0)a[i][j]=a[i][j-1]+1; else a[i][j]=0; } } } void monotone() { for(int k=1;k<=m;k++)//列高 { stack<int> q; for(int i=1;i<=n+1;i++)//n+1行本不存在,多一行是为了把队列清空 { while(!q.empty()&&a[i][k]<a[q.top()][k]) { Right[q.top()]=i-1; q.pop(); } q.push(i); } stack<int> p; for(int i=n;i>=0;i--) { while(!p.empty()&&a[i][k]<a[p.top()][k]) { Left[p.top()]=i+1; p.pop(); } p.push(i); } for(int i=1;i<=n;i++) { int x=(Right[i]-Left[i]+1)*a[i][k]; if(tot<x)tot=x; } memset(Right,0,sizeof(Right)); memset(Left,0,sizeof(Left)); } cout<<tot<<endl; }
- 1
Information
- ID
- 548
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By