Cod sursa(job #1253708)

Utilizator tudormaximTudor Maxim tudormaxim Data 1 noiembrie 2014 18:06:21
Problema BMatrix Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#define nmax 211
using namespace std;
char lin[nmax];
int n, m, mat[nmax][nmax], st[nmax][nmax], dr[nmax][nmax], stiva[nmax];
int Drept1(int x, int n)
{
    int sol = 0, a;
    for (int i = x; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            a = dr[i][j] - st[i][j] - 1;
            a *= min (mat[i][j], i - x + 1);
            if (sol < a) sol = a;
        }
    return sol;
}
int Drept2(int y, int m)
{
    int sol = 0, a;
    for (int i = 1; i <= m; i++)
        for (int j = y; j <= m; j++)
        {
            a = (min (dr[i][j], m + 1) - max (y - 1, st[i][j]) - 1) * mat[i][j];
            if (sol < a) sol = a;
        }
    return sol;
}
int main()
{
    ifstream fin ("bmatrix.in");
    ofstream fout ("bmatrix.out");
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        fin >> lin;
        for (int j = 0; j < m; j++)
        {
            mat[i][j + 1] = !(lin[j] - '0');
            if (mat[i][j + 1]) mat[i][j + 1] += mat[i - 1][j + 1];
        }
    }
    for (int i = 1, cnt; i <= n; i++)
    {
        stiva[0] = 0;
        cnt = 0;
        for (int j = 1; j <= m; j++)
        {
            while (cnt && mat[i][stiva[cnt]] >= mat[i][j]) cnt--;
            st[i][j] = stiva[cnt];
            stiva[++cnt] = j;
        }
        cnt = 0;
        stiva[0] = m + 1;
        for (int j = m; j >= 1; j--)
        {
            while (cnt && mat[i][stiva[cnt]] >= mat[i][j]) cnt--;
            dr[i][j] = stiva[cnt];
            stiva[++cnt] = j;
        }
    }
    int sol = 0;
    for (int i = 2; i <= n; i++)
    {
        int a = Drept1(1, i - 1) + Drept1(i, n);
        if (a > sol) sol = a;
    }
    for (int j = 2; j <= m; j++)
    {
        int a = Drept2(1, j - 1) + Drept2(j, m);
        if (a > sol) sol = a;
    }
    fout << sol;
    fin.close ();
    fout.close ();
    return 0;
}