QBRECT spoj – Hình chữ nhật 0 1

Nguồn đề bài: http://vn.spoj.com/problems/QBRECT/

Đề bài QBRECT spoj

Cho một bảng kích thước MxN, được chia thành lưới ô vuông đơn vị M dòng N cột ( 1 <= M, N <= 1000 )

Trên các ô của bảng ghi số 0 hoặc 1. Các dòng của bảng được đánh số 1, 2… M theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số 1, 2…, N theo thứ tự từ trái qua phải

Yêu cầu:

Hãy tìm một hình chữ nhật gồm các ô của bảng thoả mãn các điều kiện sau:

1 – Hình chữ nhật đó chỉ gồm các số 1

2 – Cạnh hình chữ nhật song song với cạnh bảng

3 – Diện tích hình chữ nhật là lớn nhất có thể

Input

Dòng 1: Ghi hai số M, N

M dòng tiếp theo, dòng thứ i ghi N số mà số thứ j là số ghi trên ô (i, j) của bảng

Output

Gồm 1 dòng duy nhất ghi diện tích của hình chữ nhật tìm được

Example

Input:
11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1

Output:
49

THUẬT TOÁN

code pascal

const   fi='';
        nmax=1000;
type    data=longint;
var
        f:text;
        A:array[0..nmax+1,0..nmax+1] of byte;
        n,test,m:data;
        sta:data;
        H:array[0..nmax*nmax+1] of data;
        D,L,R:array[0..nmax+1] of data;


procedure docfile;
var     i,j:data;
begin
        assign(f,fi);reset(f);
        readln(f,m,n);
        for i:=1 to m do
                for j:=1 to n do
                        read(f,a[i,j]);
        close(f);
end;

function xem:data;
begin
        exit(h[sta]);
end;

procedure them(x:data);
begin
        inc(sta);
        h[sta]:=x;
end;

function lay:data;
begin
        lay:=h[sta];
        dec(sta);
end;

procedure xuli;
var     i,j,res,dt:data;
begin
        fillchar(d,sizeof(d),0);
        res:=0;
        sta:=0;
        for i:=1 to m do
                begin
                        for j:=1 to n do
                                if a[i,j]<>1 then
                                        d[j]:=i;
                        sta:=0;
                        for j:=1 to n do
                                begin
                                        while (sta>0) and (D[xem]<=D[j]) do
                                                lay;
                                        if sta=0 then
                                                L[j]:=0
                                        else
                                                L[j]:=xem;
                                        them(j);
                                end;
                        sta:=0;
                        for j:=n downto 1 do
                                begin
                                        while (sta>0) and (d[xem]<=d[j]) do
                                                lay;
                                        if sta=0 then
                                                R[j]:=n+1
                                        else
                                                R[j]:=xem;
                                        them(j);
                                end;
                        for j:=1 to n do
                                begin
                                        dt:=(i-d[j])*(R[j]-L[j]-1);
                                        if dt>res then
                                                res:=dt;
                                end;
                end;
        writeln(res);
end;

begin
        docfile;
        xuli;
        readln;
end.

code c++

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

#define maxn        1010

int     n , m , a[maxn][maxn];
int     h[maxn] , l[maxn] , r[maxn] , res;

int main()
{
    scanf("%d%d",&m,&n);
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++) scanf("%d",&a[i][j]);
    h[0] = -1; h[n+1] = -1;
    for (int i=1;i<=m;i++) {
        for (int j=1;j<=n;j++)
            h[j] = a[i][j] * (h[j] + 1);
        for (int j=1;j<=n;j++) {
            l[j] = j;
            while (h[l[j]-1] >= h[j]) l[j] = l[l[j]-1];
        }
        for (int j=n;j>0;j--) {
            r[j] = j;
            while (h[r[j]+1] >= h[j]) r[j] = r[r[j]+1];
        }
        for (int j=1;j<=n;j++)
            res = max(res,h[j]*(r[j]-l[j]+1));
    }
    printf("%d",res);
}