Cod sursa(job #1416235)

Utilizator EpictetStamatin Cristian Epictet Data 7 aprilie 2015 17:44:19
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#define Max_Size 205
#define INF Max_Size * Max_Size
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
typedef struct { int val, p1, p2; } art;
int N, M, sol, V1[Max_Size][Max_Size], V2[Max_Size][Max_Size];
art 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);

                if (maxim1 > Max1[k].val)
                {
                    Max1[k].val = maxim1;
                    Max1[k].p1 = j1;
                    Max1[k].p2 = j2;
                }
                if (maxim2 > Max2[k].val)
                {
                    Max2[k].val = maxim2;
                    Max2[k].p1 = j1;
                    Max2[k].p2 = j2;
                }
            }
        }
    }

    for (int k1 = 1; k1 <= N; k1++)
    {
        for (int k2 = 1; k2 <= N; k2++)
        {
            if (Max1[k1].p2 < Max2[k2].p1 || Max1[k1].p1 > Max2[k2].p2)
            {
                sol = max (sol, Max1[k1].val + Max2[k2].val);
            }
        }
    }

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

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

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