# POJ 3494. Largest Submatrix of All 1』s

http://poj.org/problem?id=3494
http://zhuanlan.zhihu.com/qinchao/19873823

http://poj.org/problem?id=2559

```//}/* .................................................................................................................................. */

const int N = int(2e3) + 9;

int A[N][N], h[N], l[N], r[N];
int n, m;

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

while (~scanf("%d %d", &n, &m)){
REP_2_1(i, j, n, m) RD(A[i][j]);

int z = 0; h[0] = 0, h[m+1] = 0; REP_1(i, n){
REP_1(j, m) h[j] = (A[i][j] == 1 ? h[j] + 1 : 0);

stack<int> s; s.push(0); REP_1(i, m){
if (h[i]){
while (h[i] <= h[s.top()]) s.pop();
l[i] = s.top()+1;
}
else{
CLR(s);
}
s.push(i);
}

CLR(s); s.push(m+1); DWN_1(i, m, 1){
if (h[i]){
while (h[i] <= h[s.top()]) s.pop();
r[i] = s.top();
}
else{
CLR(s);
}
s.push(i);
}

REP_1(i, m) checkMax(z, h[i]*(r[i]-l[i]));
}
OT(z);
}
}

```

```

//}/* .................................................................................................................................. */

const int N = int(2e3) + 9;

int A[N][N], h[N][N], l[N][N], r[N][N];
int n, m;

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

fill(A[0], A[0]+N, 1);
fill(r[0], r[0]+N, INF);

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

REP_2_1(i, j, n, m) RD(A[i][j]);

int z = 0; RST(h, l, r); REP_1(i, n){

FOR_1(j, 1, m) l[i][j] = A[i][j] ? l[i][j-1] + 1 : 0;
DWN_1(j, m, 1) r[i][j] = A[i][j] ? r[i][j+1] + 1 : 0;

REP_1(j, m) if (A[i][j] && A[i-1][j]){
h[i][j] = h[i-1][j] + 1;
checkMin(l[i][j], l[i-1][j]);
checkMin(r[i][j], r[i-1][j]);
}
REP_1(j, m) checkMax(z, (h[i][j]+1)*(r[i][j]+l[i][j]-1));
}

OT(z);
}
}

```