Cod sursa(job #1494161)

Utilizator felixiPuscasu Felix felixi Data 30 septembrie 2015 19:31:09
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
#define N 201
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("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 Drept1(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 Drept2(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()
{
    fin>>n>>m;
    for(i=1; i<=n; ++i)
    {
        fin>>(s+1);
        for(j=1; j<=m; ++j)
        {
            if(s[j]=='0')
                a[i][j]=a[i-1][j]+1;      ///i coloana, j linia
        }
    }
    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,Drept1(1,i-1)+Drept1(i,n));

    for(j=2; j<=m; ++j)
        sol=max(sol,Drept2(1,j-1)+Drept2(j,m));
    fout<<sol<<'\n';
    fin.close();
    fout.close();
    return 0;
}