O plajă poate fi văzută ca o matrice cu n linii și m coloane. Elementele matricii sunt codificate cu 0, însemnând o poziție liberă, și 1, însemnând o poziție ocupată. Să se afle aria celui mai mare dreptunghi liber din matricea dată.

Date de intrare

Fișierul de intrare plaja.in conține pe prima linie numerele n și m, iar pe următoarele n linii câte m caractere reprezentând plaja.

Date de ieșire

Fișierul de ieșire plaja.out va conține pe prima linie numărul S, reprezentând aria maximă a unui dreptunghi liber.

Restricții și precizări

1 ≤ n, m ≤ 1000

Exemplu

plaja.in

plaja.out

Explicație

1 1 1 1 1
1 1 0 0 0
1 1 1 0 0
1 1 1 0 0
1 1 1 1 0

Suprafata dreptunghiulara de aria maxima este cea ingrosata.

#include <fstream>

using namespace std;

ifstream cin("plaja.in");
ofstream cout("plaja.out");

int n, m, v[1010][1010], s[1010][1010], i, j, i2, j2, sum, S;
char c;

int main()
{
    cin >> n >> m;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            cin >> c;
            if (c == '0')
                v[i][j] = 0;
            else if (c == '1')
                v[i][j] = 1;
            s[i][j] = s[i-1][j] + v[i][j];
        }
    }
    for (i = 1; i <= n; i++) {
        for (i2 = i; i2 <= n; i2++) {
            j = 1;
            for (j2 = 1; j2 <= m; j2++) {
                sum = s[i2][j2] - s[i-1][j2];
                if (sum)
                    j = j2 + 1;
                else
                    S = max(S, (i2 - i + 1) * (j2 - j + 1));
            }
        }
    }
    cout << S;

    return 0;
}