Cod sursa(job #2954863)

Utilizator YosifIosif Andrei Stefan Yosif Data 15 decembrie 2022 17:47:07
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <bits/stdc++.h> 
using namespace std;

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

int s[202][202], n, m, line1[202], line2[202], col1[202], col2[202];
int a[202], b[202];

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char c;
            fin >> c;
            s[i][j] = (c == '1') + s[i - 1][j];
        }

    int aux;

    for (int i = 1; i <= n; i++)
        for (int k = i; k <= n; k++) 
        {
            int last = 1;

            for (int j = 1; j <= m; j++)
                if (s[k][j] - s[i - 1][j] == 0)
                    a[j] = last;
                else
                    a[j] = -1, last = j + 1;

            last = m;

            for (int j = m; j >= 1; j--)
                if (s[k][j] - s[i - 1][j] == 0)
                    b[j] = last;
                else
                    last = j - 1;

            for (int j = 1; j <= m; j++)
            {
                if (a[j] == -1)
                    continue;

                aux = (b[j] - a[j] + 1) * (k - i + 1);

                line1[k] = max(line1[k], aux);
                line2[i] = max(line2[i], aux);

                col1[j] = max(col1[j], (j - a[j] + 1) * (k - i + 1));
                col2[j] = max(col2[j], (b[j] - j + 1) * (k - i + 1));
            }
        }

    for (int i = 1; i <= n; i++)
        line1[i] = max(line1[i], line1[i - 1]);

    for (int i = n; i >= 1; i--)
        line2[i] = max(line2[i], line2[i + 1]);

    for (int j = 1; j <= m; j++)
        col1[j] = max(col1[j], col1[j - 1]);

    for (int j = m; j >= 1; j--)
        col2[j] = max(col2[j], col2[j + 1]);

    int maxi = 0;

    for (int i = 1; i <= n; i++)
        for (int k = i; k <= n; k++)
        {
            int j = 1;

            while (j <= m && s[k][j] - s[i - 1][j] != 0)
                j++;

            while (j <= m)
            {
                int last = j++;

                while (j <= m && s[k][j] - s[i - 1][j] == 0)
                    j++;

                aux = (k - i + 1) * (j - last);
                aux += max(max(line1[i - 1], line2[k + 1]), max(col1[last - 1], col2[j]));
                maxi = max(maxi, aux);

                while (j <= m && s[k][j] - s[i - 1][j] != 0)
                    j++;
            }
        }

    fout << maxi;
   
    return 0;
}