Cod sursa(job #607333)

Utilizator mika17Mihai Alex Ionescu mika17 Data 11 august 2011 18:06:12
Problema BMatrix Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
/*
bmatrix
O((M+N)*N*M)
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
http://drdobbs.com/database/184410529
http://homeofcox-cs.blogspot.com/2010/04/max-rectangle-in-histogram-problem.html
*/

#include <fstream>
#include <stack>
#define max(a,b) ((a) > (b) ? (a) : (b))

char Mat[200][200];
unsigned char below[200][200];

int getMax(int l1,int c1,int l2,int c2)
{
   for(int j=c1;j<=c2;++j)
      below[l2][j] = Mat[l2][j] == '0' ? 1 : 0;
   for(int i=l2 - 1;i>=l1;--i)
      for(int j=c1;j<=c2;++j)
	 below[i][j] = Mat[i][j] == '0' ? below[i + 1][j] + 1 : 0;

   int smax(-1);
   for(int i=l1;i<=l2;++i)
   {
      std::stack <int> st;
      st.push(c1);
      for(int j=c1+1;j<=c2;++j)
      {
	 if(below[i][st.top()] < below[i][j])
	    st.push(j);
	 else if(below[i][st.top()] == below[i][j])
	    smax = max(smax,below[i][st.top()] * (j - st.top() + 1));
	 else //only case left
	 {
	    int t = st.top();
	    do
	    {
	       smax = max(smax,below[i][st.top()] * (t - st.top() + 1));
	       st.pop();
	    }
	    while(!st.empty() && below[i][st.top()] >= below[i][j]);
	    
	    st.push(j);
	 }
      }
      /*
	 - there still may be elements inside st
	 - key observation is that elements inside st are in strictly increasing order by their heights
      */
      if(!st.empty())
      {
	 int t = st.top();
	 do
	 {
	    smax = max(smax,below[i][st.top()] * (t - st.top() + 1));
	    st.pop();
	 }
	 while(!st.empty());
      }
   }

   return smax;
}

int main()
{
	std::ifstream f("bmatrix.in");
	std::ofstream g("bmatrix.out");

	int M,N; f >> M >> N;

	for(int i=0;i<M;++i)
	   for(int j=0;j<N;++j)
	      f >> Mat[i][j];

	//getMax(0,0,M - 1,N - 1);
	int smax(-1);
	for(int i=1;i<N;++i) //horizontal sweep line
	{
	   smax = max(smax,getMax(0,0,M - 1,i - 1) + getMax(0,i,M - 1,N - 1)); 
	}
	for(int i=1;i<M;++i) //vertical sweep line
	{
	   smax = max(smax,getMax(0,0,i - 1,N - 1) + getMax(i,0,M - 1,N - 1));
	}
	g << smax;
	return 0;
}