Cod sursa(job #991042)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 29 august 2013 16:08:34
Problema BMatrix Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<fstream>
#define N 209
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int vf,n,m,i,j,sol,st[N],a[N][N],r[N][N],l[N][N];
char s[N];
inline int rez1(int p1,int p2)
{
    int i,j,sol=0;
    for(i=p1;i<=p2;++i)
    for(j=1;j<=m;++j)
    {
        sol=max(sol,(r[i][j]-l[i][j]-1)*min(a[i][j],i-p1+1));
    }
    return sol;
}
inline int rez2(int p1,int p2)
{
    int i,j,sol=0;
    for(i=1;i<=n;++i)
    for(j=p1;j<=p2;++j)
    {
        sol=max(sol,(min(r[i][j],p2+1)-max(l[i][j],p1-1)-1)*a[i][j]);
    }
    return sol;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
    {
        f>>(s+1);
        for(j=1;j<=m;++j)
        {
            if(s[j]=='0')
            a[i][j]=a[i-1][j]+1;
        }
    }
    for(i=1;i<=n;++i)
    {
        st[0]=0;
        vf=0;
        for(j=1;j<=m;++j)
        {
            while(vf&&a[i][st[vf]]>=a[i][j])
            --vf;
            l[i][j]=st[vf];
            st[++vf]=j;
        }
        st[0]=m+1;
        vf=0;
        for(j=m;j;--j)
        {
            while(vf&&a[i][st[vf]]>=a[i][j])
            --vf;
            r[i][j]=st[vf];
            st[++vf]=j;
        }
    }
    for(i=2;i<=n;++i)
    {
        sol=max(sol,rez1(1,i-1)+rez1(i,n));
    }
    for(j=2;j<=m;++j)
    {
        sol=max(sol,rez2(1,j-1)+rez2(j,m));
    }
    g<<sol<<'\n';
    return 0;
}