Cod sursa(job #1645725)

Utilizator arhivamanArhiva Man arhivaman Data 10 martie 2016 13:28:41
Problema BMatrix Scor 92
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <fstream>
#include <string.h>
#define nMax 205
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int A[nMax][nMax], H[nMax][nMax], MaxDr[5][nMax], n, m, AUX[nMax][nMax], Sol;
char line[nMax];
struct stiva
{
    int h;
    int ind;
}stck[nMax];
void read()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>line+1;
        for(int j=1;j<=m;j++)
            A[i][j]=line[j]-'0';
    }
}
void sum_part_coloane()
{
    memset(H, 0, sizeof(H));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            H[i][j]=(A[i][j]==0 ? H[i-1][j]+1 : 0);
}
void compute_matrix(int step)
{
    int poz, sol, vf;
    for(int i=1;i<=n;i++)
    {
        vf=0;
        sol=0;
        for(int j=1;j<=m+1;j++)
        {
            poz=j;
            while(H[i][j]<stck[vf].h)
            {
                sol=max(sol, stck[vf].h*(j-stck[vf].ind));
                poz=stck[vf].ind;
                vf--;
            }
            vf++;
            stck[vf].h=H[i][j];
            stck[vf].ind=poz;
        }
        switch(step)
        {
            case 1:MaxDr[1][i]=sol;break;
            case 2:MaxDr[2][i]=sol;break;
            case 3:MaxDr[3][n-i+1]=sol;break;
            case 4:MaxDr[4][n-i+1]=sol;break;
        }
    }
}
void rotate_matrix()
{
    memcpy(AUX, A, sizeof(A));
    swap(n, m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            A[i][j]=AUX[m-j+1][i];
}
void solve()
{
    int vf, poz, sol;
    for(int i=1;i<=n;i++)
    {
        vf=0;
        sol=0;
        for(int j=1;j<=m+1;j++)
        {
            poz=j;
            while(H[i][j]<stck[vf].h)
            {
                sol=stck[vf].h*(j-stck[vf].ind);
                Sol=max(Sol, sol+max(max(MaxDr[1][i-stck[vf].h], MaxDr[2][stck[vf].ind-1]), max(MaxDr[3][i+1], MaxDr[4][j+1])));
                vf--;
            }
            vf++;
            stck[vf].h=H[i][j];
            stck[vf].ind=poz;
        }
    }
}
void prec()
{
    sum_part_coloane();
    compute_matrix(1);
    rotate_matrix();

    sum_part_coloane();
    compute_matrix(2);
    rotate_matrix();

    sum_part_coloane();
    compute_matrix(3);
    rotate_matrix();

    sum_part_coloane();
    compute_matrix(4);
    rotate_matrix();

    sum_part_coloane();
    for(int i=1;i<=n;i++)
        MaxDr[1][i]=max(MaxDr[1][i], MaxDr[1][i-1]);
    for(int i=1;i<=m;i++)
        MaxDr[2][i]=max(MaxDr[2][i], MaxDr[2][i-1]);
    for(int i=n;i>=1;i--)
        MaxDr[3][i]=max(MaxDr[3][i], MaxDr[3][i+1]);
    for(int i=m;i>=1;i--)
        MaxDr[4][i]=max(MaxDr[4][i], MaxDr[4][i+1]);
}
void write()
{
    fout<<Sol;
}
int main()
{
    read();
    prec();
    solve();
    write();
    return 0;
}