Cod sursa(job #2078815)

Utilizator papinub2Papa Valentin papinub2 Data 29 noiembrie 2017 23:51:24
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

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

const int Nmax = 205;

int x_1, x_2, y_1, y_2;
int n, m, rez, last, sol, maxim, neg, R;
int sum[Nmax][Nmax], v[Nmax][Nmax];
char s[Nmax];

int main()
{
    in >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        in.get();
        in.get(s, Nmax);

        for (int j = 0; j < strlen(s); j++)
        {
            sum[i][j + 1] = sum[i][j] + s[j] - '0';
        }
    }

    for (int i = 1; i <= m; i++)
    {
        for (int j = i; j <= m; j++)
        {
            rez = 0;
            last = 0;

            for (int l = 1; l <= n; l++)
            {
                rez = sum[l][j] - sum[l][i - 1];

                if (rez > 0)
                {
                    rez = 0;
                    sol = 0;
                    last = l;
                }

                else

                {
                    sol = (l - last) * (j - i + 1);
                    if (sol > maxim)
                    {
                        maxim = sol;
                        x_1 = last + 1;
                        y_1 = i;

                        x_2 = l;
                        y_2 = j;
                    }
                }
            }
        }
    }

    for (int i = x_1; i <= x_2; i++)
        for (int j = y_1; j <= y_2; j++)
            v[i][j] = -1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            v[i][j] = v[i][j - 1] + v[i][j];

    R = R + maxim;
    maxim = 0;

    for (int i = 1; i <= m; i++)
    {
        for (int j = i; j <= m; j++)
        {
            rez = 0;
            last = 0;

            for (int l = 1; l <= n; l++)
            {
                rez = sum[l][j] - sum[l][i - 1];

                if (rez > 0)
                {
                    rez = 0;
                    sol = 0;
                    neg = 0;
                    last = l;
                }

                else

                {
                    neg = neg + v[l][j] - v[l][i - 1];
                    sol = (l - last) * (j - i + 1) + neg;
                    maxim = max(maxim, sol);
                }
            }
        }
    }

    R = R + maxim;

    out << R;
    return 0;
}