Cod sursa(job #1637718)

Utilizator ancabdBadiu Anca ancabd Data 7 martie 2016 18:54:32
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

int x[2005][2005], sus[2005], jos[2005], m, n, sol, q;
bool p;
char a[2005][2005];

int main()
{
    fin >> n >> m;
    /*for (int i = 1; i <= n; i++)
        for (int j = 1; j <=m; j++)
            fin >> a[i][j];*/

    for (int i = 1; i <= n; ++i)
        fin >> (a[i] + 1);

    //1
    p=true;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            x[i][j] = (1 - a[p ? i : m - j + 1][p ? j : i] + '0') * (x[i - 1][j] + 1);
        sus[i] = 0;
        jos[i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            q = 0;
            for (int k = 1; k <= m; k++)
                if (x[j][k] >= j - i + 1)
                {
                    q++;
                    sus[j] = max(sus[j], q * (j - i + 1));
                    jos[i] = max(jos[i], q * (j - i + 1));
                }
                else q = 0;
        }
        sus[i] = max(sus[i], sus[i - 1]);
        jos[n - i + 1] = max(jos[n - i + 1], jos[n - i + 2]);
    }
    for (int i = 1; i <= n; i++)
        sol = max(sol, sus[i] + jos[i + 1]);

    swap(n, m);

    p = false;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            x[i][j] = (1 - a[p ? i : m - j + 1][p ? j : i] + '0') * (x[i - 1][j] + 1);
        sus[i] = 0;
        jos[i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            q = 0;
            for (int k = 1; k <= m; k++)
                if (x[j][k] >= j - i + 1)
                {
                    q++;
                    sus[j] = max(sus[j], q * (j - i + 1));
                    jos[i] = max(jos[i], q * (j - i + 1));
                }
                else q = 0;
        }
        sus[i] = max(sus[i], sus[i - 1]);
        jos[n - i + 1] = max(jos[n - i + 1], jos[n - i + 2]);
    }
    for (int i = 1; i <= n; i++)
        sol = max(sol, sus[i] + jos[i + 1]);

    fout << sol;
    return 0;
}