Cod sursa(job #1416206)

Utilizator EpictetStamatin Cristian Epictet Data 7 aprilie 2015 17:01:34
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#define Max_Size 205
#define INF Max_Size * Max_Size
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
int N, M, sol, V1[Max_Size][Max_Size], V2[Max_Size][Max_Size];
int Max1[Max_Size], Max2[Max_Size];
bool B[Max_Size][Max_Size];
char c;

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        fin.get(c);
        for (int j = 1; j <= M; j++)
        {
            fin.get(c);
            B[i][j] = c - '0';
        }
    }

    for (int j = 1; j <= M; j++)
    {
        for (int i = 1; i <= N; i++)
        {
            if (!B[i][j])
            {
                V1[i][j] = V1[i - 1][j] + 1;
            }
            else
            {
                V1[i][j] = 0;
            }
        }

        for (int i = N; i >= 1; i--)
        {
            if (!B[i][j])
            {
                V2[i][j] = V2[i + 1][j] + 1;
            }
            else
            {
                V2[i][j] = 0;
            }
        }
    }

    for (int k = 1; k <= N + 1; k++)
    {
        for (int j1 = 1; j1 <= M; j1++)
        {
            int maxim1 = 0, minim1 = INF, maxim2 = 0, minim2 = INF;
            for (int j2 = j1; j2 <= M; j2++)
            {
                if (V1[k - 1][j2] < minim1) minim1 = V1[k - 1][j2];
                if (minim1 * (j2 - j1 + 1) > maxim1) maxim1 = minim1 * (j2 - j1 + 1);

                if (V2[k][j2] < minim2) minim2 = V2[k][j2];
                if (minim2 * (j2 - j1 + 1) > maxim2) maxim2 = minim2 * (j2 - j1 + 1);
            }

            Max1[k] = max (Max1[k], maxim1);
            Max2[k] = max (Max2[k], maxim2);
        }
    }

    for (int k = 1; k <= N; k++) {
        Max1[k] = max (Max1[k], Max1[k - 1]);
        Max2[N - k + 1] = max (Max2[N - k + 1], Max2[N - k + 2]);
    }

    for (int k = 1; k <= N; k++) {
        sol = max (sol, Max1[k] + Max2[k]);
    }

    fout << sol << '\n';
    fout.close();
    return 0;
}