Given a m-by-n (0,1)-matrix, of all its submatrices of all 1’s which is the largest? By largest we mean that the submatrix has the most elements.

The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 2000) on line. Then come the elements of a (0,1)-matrix in row-major order on m lines each with n numbers. The input ends once EOF is met.

For each test case, output one line containing the number of elements of the largest submatrix of all 1’s. If the given matrix is of all 0’s, output 0.

 //单调队列实现  C++提交 若用G++则会T！！！！！

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 #include <map>

 #include<string.h>

 #include<stack>

 #include<set>

 #include <queue>

 using namespace std;

 struct Node

 {

     int val;

     int position;

 }q[];              // 数组模拟单调递增队列

 int n,m;

 int l[];           // 以当前点高度为最小高度的矩形的左区间最大值

 int r[];           //以当前点高度为最小高度的矩形的右区间最大值

 int a[][];

 //求每一行的最大矩形

 int AREA(int nn)

 {

     int h = ; //队头

     int tail = ;//队尾

     //确定以每一个点的高度为最小值的矩形的右区间的最大值

     q[].position = n+;

     q[].val = -;

     for(int i = m;i>=;i--)

     {

         while(q[tail].val >= a[nn][i]) tail--;

         r[i] = q[tail].position-i;

         q[++tail].val = a[nn][i];

         q[tail].position = i;

     }

     //确定以每一个点的高度为最小值的矩形的左区间的最大值

     h = ;

     tail = ;

     q[].position = ;

     q[].val = -;

     for(int i = ;i<=m;i++)

     {

          while(q[tail].val>=a[nn][i]) tail--;

          l[i] = i-q[tail].position;

          q[++tail].val = a[nn][i];

          q[tail].position = i;

     }

     //该行中所有矩形的最大值

     int max1 = -;

     for(int i = ;i<=m;i++)

         max1 = max(max1,(l[i]+r[i]-)*a[nn][i]);

     return max1;

 }

 int main()

 {

     while(~scanf("%d %d",&n,&m))

     {

         for(int i = ;i<=n;i++)

             for(int j = ;j<=m;j++)

                 scanf("%d",&a[i][j]);

         //讲矩阵看做不同高度的矩形进行更新操作

         for(int i = ;i<=n;i++)

             for(int j = ;j<=m;j++)

                 if(a[i][j]) a[i][j] = a[i-][j]+a[i][j];

         int max1 = -;

         //对每行进行遍历确定每行的最大矩形

         for(int i = ;i<=n;i++)

             max1 = max(AREA(i),max1);

         printf("%d\n",max1);

     }

     return ;

 }

 //单调栈实现

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 #include <map>

 #include<string.h>

 #include<stack>

 #include<set>

 #include <queue>

 using namespace std;

 struct re

 {

     int h;

     int p;

 };

 int m,n;

 int a[][];

 int h[][];

 int l[];

 int r[];

 int AREA(int R)

 {

     int i,j;

     int max1 = -;

     stack<re> s;

     //求左区间

     re p0,pi;

     p0.h = -;

     p0.p = -;

     s.push(p0);

     for(i = ;i<n;i++)

     {

         pi.p = i;

         pi.h = h[R][i];

         while(s.top().h>=pi.h) s.pop();

         l[i] = i-s.top().p;

         s.push(pi);

     }

     while(!s.empty()) s.pop();

     //求右区间

      p0.h = -;

      p0.p = n;

      s.push(p0);

     for(i =n- ;i>=;i--)

     {

         pi.p = i;

         pi.h = h[R][i];

         while(s.top().h>=pi.h) s.pop();

         r[i] = s.top().p-i;

         s.push(pi);

     }

     for(i = ;i<n-;i++)

         if((r[i]+l[i]-)*h[R][i]>max1)

             max1= (r[i]+l[i]-)*h[R][i];

     return max1;

 }

 int main()

 {

     int i,j;

     while(~scanf("%d%d",&m,&n))

     {

         for(i = ; i<m; i++)

             for(j = ; j<n; j++)

             {

                 scanf("%d",&a[i][j]);

                 h[i][j] = a[i][j];

             }

         for(i = ; i<n; i++)

             for(j = ; j<m; j++)

                 if(h[j][i]) h[j][i] += h[j-][i];

         int max1 = -;

         for(i = ; i<m; i++) max1 = max(max1,AREA(i));

         printf("%d\n",max1);

     }

 }