1 solutions

  • 0
    @ 2024-12-10 22:27:30

    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