Cod sursa(job #918169)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 17:56:02
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include<fstream>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,sol;
char A[2][210][210];
int sus[210][210],jos[210][210],solsus[210],soljos[210];
int St[210],vf=-1,st[210],dr[210];
 
inline int Solve(int p,int n,int m)
{
    int i,j,rez=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(A[p][i][j]=='0')
                sus[i][j]=sus[i-1][j]+1;
            else
                sus[i][j]=0;
        }
    }
    for(i=n;i>0;i--)
    {
        for(j=m;j>0;j--)
        {
            if(A[p][i][j]=='0')
                jos[i][j]=jos[i+1][j]+1;
            else
                jos[i][j]=0;
        }
    }
    for(i=1;i<=n;i++)
    {
        solsus[i]=soljos[i]=0;
        for(j=1;j<=m;j++)
        {
            while(vf>=0 && sus[i][St[vf]]>=sus[i][j])
            {
                dr[St[vf]]=j-1;
                vf--;
            }
            if(vf>=0)
                st[j]=St[vf]+1;
            else
                st[j]=1;
            St[++vf]=j;
        }
        while(vf>=0)
        {
            dr[St[vf]]=m;
            vf--;
        }
        for(j=1;j<=m;j++)
            solsus[i]=max(max(solsus[i-1],solsus[i]),sus[i][j]*(dr[j]-st[j]+1));
        //
        for(j=1;j<=m;j++)
        {
            while(vf>=0 && jos[i][St[vf]]>=jos[i][j])
            {
                dr[St[vf]]=j-1;
                vf--;
            }
            if(vf>=0)
                st[j]=St[vf]+1;
            else
                st[j]=1;
            St[++vf]=j;
        }
        while(vf>=0)
        {
            dr[St[vf]]=m;
            vf--;
        }
        for(j=1;j<=m;j++)
            soljos[i]=max(soljos[i],jos[i][j]*(dr[j]-st[j]+1));
    }
    for(i=1;i<n;i++)
        rez=max(rez,solsus[i]+soljos[i+1]);
    return rez;
}
 
int main()
{
    int i,j;
    ifstream fin("bmatrix.in");
    fin>>n>>m;
    for(i=1;i<=n;i++)
        fin>>(A[0][i]+1);
    fin.close();
     
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            A[1][j][i]=A[0][i][j];
    sol=max(Solve(0,n,m),Solve(1,m,n));
     
    ofstream fout("bmatrix.out");
    fout<<sol<<"\n";
    fout.close();
    return 0;
}