Ever the capitalist, Farmer John wants to extend his milking business by purchasing more cows. He needs space to build a new barn for the cows.

FJ purchased a rectangular field with R (1 ≤ R ≤ 3,000) rows numbered 1..R and C (1 ≤ C ≤ 3,000) columns numbered 1..C. Unfortunately, he realized too late that some 1x1 areas in the field are damaged, so he cannot
build the barn on the entire RxC field.

FJ has counted P (0 ≤ P ≤ 30,000) damaged 1x1 pieces and has asked for your help to find the biggest rectangular barn (i.e., the largest area) that he can build on his land without building on the damaged pieces.

PROGRAM NAME: rectbarn

INPUT FORMAT

• Line 1: Three space-separated integers: R, C, and P.
• Lines 2..P+1: Each line contains two space-separated integers, r and c, that give the row and column numbers of a damaged area of the field

SAMPLE INPUT (file rectbarn.in)

3 4 2
1 3
2 1

OUTPUT FORMAT

• Line 1: The largest possible area of the new barn

SAMPLE OUTPUT (file rectbarn.out)

6

OUTPUT DETAILS

  1 2 3 4
 +-+-+-+-+
1| | |X| |
 +-+-+-+-+
2|X|#|#|#|
 +-+-+-+-+
3| |#|#|#|
 +-+-+-+-+

Pieces marked with 'X' are damaged and pieces marked with '#' are part of the new barn. 

题意：给你一个n*m的矩阵，有些方格不能要，求最大的子矩阵面积

分析：最大子矩阵问题，有两种解法 ，一种是按点，然后离散化再扫描，复杂度O(P^2)，一种是逐格扫描，DP。。。复杂度为O（RC），按数据量分析，这题适合用第二中方法。。。具体看王知昆的论文

PS：这题的数据拿不下来啊，貌似太大了？

代码：

/*
ID: 15114582
PROG: rectbarn
LANG: C++
*/
#include<cstdio>
#include<iostream>
using namespace std;
const int mm=3003;
int L[mm],H[mm],R[mm];
bool g[mm][mm];
int i,j,k,lm,rm,n,m,ans;
int main()
{
    freopen("rectbarn.in","r",stdin);
    freopen("rectbarn.out","w",stdout);
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=0;i<=n;++i)
            for(j=0;j<=m;++j)
                g[i][j]=1;
        while(k--)
        {
            scanf("%d%d",&i,&j);
            g[i][j]=0;
        }
        for(ans=j=0;j<=m;++j)H[j]=0,L[j]=1,R[j]=m;
        for(i=1;i<=n;++i)
        {
            for(lm=j=1;j<=m;++j)
                if(g[i][j])++H[j],L[j]=max(L[j],lm);
                else H[j]=0,L[j]=1,R[j]=m,lm=j+1;
            for(rm=j=m;j>=1;--j)
                if(g[i][j])
                {
                    R[j]=min(R[j],rm);
                    ans=max(ans,(R[j]-L[j]+1)*H[j]);
                }
                else rm=j-1;
        }
        printf("%d\n",ans);
    }
	return 0;
}