Cod sursa(job #961030)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 16:25:44
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
 
using namespace std;
 
int N, M;
char a[211];
int mat[211][211];
int stanga[211][211];
int dreapta[211][211];
int stiva[211];
 
void Citire ()
{
    ifstream fin ("bmatrix.in");
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        fin >> a;
        for (int j = 0; j < M; j++)
        {
            mat[i][j + 1] = !(a[j] - '0');
            if (mat[i][j + 1]) mat[i][j + 1] += mat[i - 1][j + 1];
        }
    }
    fin.close ();
}
 
void Precalc ()
{
    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--;
            stanga[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--;
            dreapta[i][j] = stiva[cnt];
            stiva[++cnt] = j;
        }
    }
}
 
int Find_Rect1 (int X, int N)
{
    int Ans = 0, a;
    for (int i = X; i <= N; i++)
        for (int j = 1; j <= M; j++)
        {
            a = dreapta[i][j] - stanga[i][j] - 1;
            a *= min (mat[i][j], i - X + 1);
            if (Ans < a) Ans = a;
        }
    return Ans;
}
 
int Find_Rect2 (int Y, int M)
{
    int Ans = 0, a;
    for (int i = 1; i <= N; i++)
        for (int j = Y; j <= M; j++)
        {
            a = (min (dreapta[i][j], M + 1) - max (Y - 1, stanga[i][j]) - 1) * mat[i][j];
            if (Ans < a) Ans = a;
        }
    return Ans;
}
 
void Scriere ()
{
    ofstream fout ("bmatrix.out");
    int Ans = 0;
    for (int i = 2; i <= N; i++)
    {
        int a = Find_Rect1 (1, i - 1) + Find_Rect1 (i, N);
        if (a > Ans) Ans = a;
    }
    for (int j = 2; j <= M; j++)
    {
        int a = Find_Rect2 (1, j - 1) + Find_Rect2 (j, M);
        if (a > Ans) Ans = a;
    }
    fout << Ans;
    fout.close ();
}
 
int main ()
{
    Citire ();
    Precalc ();
    Scriere ();
    return 0;
}