Cod sursa(job #2283321)

Utilizator papinub2Papa Valentin papinub2 Data 15 noiembrie 2018 13:20:50
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int Hmax = 40005;

int main()
{
    int n, m, sol = 0;
    in >> n >> m;

    vector<int> v(m + 5);
    vector<int> st(m + 5);
    vector<int> dr(m + 5);
    vector<int> sus(n + 5);
    vector<int> jos(n + 5);
    vector<string> s(n + 5);

    for (int i = 1; i <= n; i++)
    {
        in >> s[i];
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == '1')
                v[j] = 0;
            else
                v[j]++;

            int cnt = 0;
            int height = Hmax;
            for (int k = j; k >= 0; k--)
            {
                height = min(height, v[k]);
                cnt = max(cnt, height * (j - k + 1));
            }

            sus[i] = max(cnt, max(sus[i - 1], sus[i]));

            if (j)
                st[j] = max(cnt, max(st[j - 1], st[j]));
            else
                st[j] = max(cnt, st[j]);
        }
    }

    for (int i = 1; i <= m; i++)
        v[i] = 0;

    for (int i = n; i >= 1; i--)
        for (int j = m - 1; j >= 0; j--)
        {
            if (s[i][j] == '1')
                v[j] = 0;
            else
                v[j]++;

            int cnt = 0;
            int height = Hmax;
            for (int k = j; k < m; k++)
            {
                height = min(height, v[k]);
                cnt = max(cnt, height * (k - j + 1));
            }

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

    for (int i = 1; i < n; i++)
        sol = max(sol, sus[i] + jos[i + 1]);

    for (int i = 0; i < m - 1; i++)
        sol = max(sol, st[i] + dr[i + 1]);

    out << sol;
    return 0;
}