uva 10667 - Largest Block

/*
Problem link
Type: DP, data structure
Algorithm: I use the stack in the problem, with this I can solve it in O(n^2)
 Let h[i][j] be the height of the consecutive comlumn of 0 at (i,j)
 Let l[i][j] is the index left most element of (i,j) that from h[i][l[i][j]] to h[i][j]
  is all >= h[i][j]
 Let r[i][j] is the index right most element of (i,j) that from h[i][j] to h[i][r[i][j]]
  is all >= h[i][j]
 Find max of (j-l[i][j]+r[i][j]-j+1)*h[i][j] for all i,j
 l and r are calculated in O(n^2) by using the stack
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 110;
//------------------------------
class Stack {
  public:
 int val[maxn];
 int top;
 
 Stack () { top = 0; }
 
 void push(int value) { val[++top] = value; }
 
 int pop() { return(val[top--]); }
};
//------------------------------
int a[maxn][maxn],h[maxn][maxn],r[maxn][maxn],l[maxn][maxn];
int n,b;
//------------------------------
void readfile() {
 cin >> n;
 cin >> b;
 memset(a,0,sizeof(a));
 for (int i=1; i<=b; i++)
 {
  int r1,c1,r2,c2;
  cin >> r1 >> c1 >> r2 >> c2;
  for (int u = r1; u<=r2; u++)
   for (int v = c1; v<=c2; v++) a[u][v] = 1;
 }
 for (int i=1; i<=n; i++)
  for (int j=1; j<=n; j++)
   if (a[i][j]==0)
   {
    if (a[i-1][j]==0) h[i][j] = h[i-1][j]+1;
    else h[i][j] = 1;
   }
   else h[i][j] = 0;
}
//------------------------------
void FindRight() {
 for (int i=1; i<=n; i++)
 {
  Stack st;
  r[i][n] = n;
  st.push(n);
  for (int j=n-1; j>=1; j--)
  {
   r[i][j] = j;
   int tmp = j;
   while (st.top>0 && h[i][j]<=h[i][st.val[st.top]]) tmp = st.pop();
   r[i][j] = r[i][tmp];
   st.push(j);
  }
 }
}
//------------------------------
void FindLeft() {
 for (int i=1; i<=n; i++)
 {
  Stack st;
  l[i][1] = 1;
  st.push(1);
  for (int j=2; j<=n; j++)
  {
   l[i][j] = j;
   int tmp = j;
   while (st.top>0 && h[i][j]<=h[i][st.val[st.top]]) tmp = st.pop();
   l[i][j] = l[i][tmp];
   st.push(j);
  }
 }
}
//------------------------------
int solve() {
 FindRight();
 FindLeft();
 int result = 0;
 for (int i=1; i<=n; i++)
  for (int j=1; j<=n; j++)
   if (((r[i][j]-j+1)+(j-l[i][j]))*h[i][j] > result)
    result = ((r[i][j]-j+1)+(j-l[i][j]))*h[i][j];
 return(result); 
}
//------------------------------
int main() {
 int ntest;
 cin >> ntest;
 for (int test=1; test<=ntest; test++)
 {
  readfile();
  cout << solve() << endl;
 }
 return 0;
}
//------------------------------