Cod sursa(job #2921071)

Utilizator Iordache_CezarIordache Cezar Iordache_Cezar Data 27 august 2022 12:10:53
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.45 kb
#include <bits/stdc++.h>
#define NMAX 208

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

char a[NMAX][NMAX];
long long r[NMAX][NMAX], c[NMAX][NMAX], sus[NMAX], jos[NMAX], dr[NMAX], st[NMAX];
long long ans, n, m;

void arie();

int main()
{
    fin >> n >> m;
    for (long long i = 1; i <= n; i++)
        for (long long j = 1; j <= m; j++)
            fin >> a[i][j];
    arie();
    ///calcul raspuns
    for (long long i = 1; i < n; i++)
        ans = max(ans, sus[i] + jos[i+1]);
    for (long long i = 1; i < m; i++)
        ans = max(ans, st[i] + dr[i+1]);
    fout << ans;
    return 0;
}

void arie()
{
    long long total_area = 0, area, minc, left, right;
    for (long long i = 1; i <= n; i++)
    {
        if (a[i][1] == '0')
            r[i][1] = 1;
        else
            r[i][1] = 0;
        for (long long j = 2; j <= m; j++)
        {
            if (a[i][j] == '1')
                r[i][j] = 0;
            else
                r[i][j] = r[i][j-1] + 1;
        }

        for (long long j = 1; j <= m; j++)
        {
            if (i == 1)
                c[1][j] = (a[1][j] == '1' ? 0:1);
            else
            {
                if (a[i][j] == '0')
                    c[i][j] = c[i-1][j] + 1;
                else
                    c[i][j] = 0;
            }
        }
    }

    for (long long i = 1; i <= n; i++)
        for (long long j = 1; j <= m; j++)
            if (a[i][j] == '0')
            {
                minc = c[i][j];
                area = minc;
                left = j;
                for (long long k = j-1; k >= 1; k--)
                {
                    if (c[i][k] == 0)
                        break;
                    minc = min(minc, c[i][k]);
                    if (minc * (j - k + 1) > area)
                    {
                        area = minc * (j - k + 1);
                        left = k;
                    }
                }

                sus[i] = max(max(sus[i], sus[i - 1]),area);
                st[j] = max(max(st[j], st[j - 1]),area);
            }


    for (long long i = n; i >= 1; i--)
    {
        if (a[i][m] == '0')
            r[i][m] = 1;
        else
            r[i][m] = 0;
        for (long long j = m-1; j >= 1; j--)
        {
            if (a[i][j] == '1')
                r[i][j] = 0;
            else
                r[i][j] = r[i][j+1] + 1;
        }

        for (long long j = m; j >= 1; j--)
        {
            if (i == n)
                c[n][j] = (a[n][j] == '1' ? 0:1);
            else
            {
                if (a[i][j] == '0')
                    c[i][j] = c[i+1][j] + 1;
                else
                    c[i][j] = 0;
            }
        }
    }

    for (long long i = n; i >= 1; i--)
        for (long long j = m; j >= 1; j--)
            if (a[i][j] == '0')
            {
                minc = c[i][j];
                area = minc;
                for (long long k = j+1; k <= m; k++)
                {
                    if (c[i][k] == 0)
                        break;
                    minc = min(minc, c[i][k]);
                    if (minc * (k - j + 1) > area)
                    {
                        area = minc * (k - j + 1);
                    }
                }

                jos[i] = max(max(jos[i], jos[i + 1]),area);
                dr[j] = max(max(dr[j], dr[j + 1]),area);
            }

}