Cod sursa(job #1387384)

Utilizator ZenusTudor Costin Razvan Zenus Data 14 martie 2015 08:14:09
Problema BMatrix Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <stack>
#include <set>
#include <cstring>

using namespace std;

#define NMAX 207

stack < pair < int , int > > q;
multiset < int > w;
int r[NMAX],l[NMAX],u[NMAX],d[NMAX],prec[NMAX],sol[NMAX];
int t[NMAX][NMAX];
string str;
int i,j,N,M,ans,sus,stanga;

int solve(int x[],int N)
{
    int i,ans=0;

    memset(sol,0,sizeof(sol));
    while (q.size()) q.pop();

    for (i=1;i<=N;++i)
    {
        while (q.size() && q.top().first>=x[i])
        q.pop();

        if (q.empty()) sol[i] = i;
        else sol[i] = i-q.top().second;

        q.push(make_pair(x[i],i));
    }

    while (q.size()) q.pop();

    for (i=N;i;--i)
    {
        while (q.size() && q.top().first>=x[i])
        q.pop();

        if (q.empty()) sol[i] += N-i;
        else sol[i] += q.top().second - i - 1;

        ans = max(ans , sol[i]*x[i]);

        q.push(make_pair(x[i],i));
    }

    return ans;
}

int main()
{
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

f>>N>>M;

for (i=1;i<=N;++i)
{
    f>>str;

    for (j=0;j<M;++j)
    t[i][j+1]=(str[j]=='0');
}

for (i=N;i;--i)
{
    for (j=1;j<=M;++j)
    d[j] = (t[i][j]) ? d[j]+1 : 0;

    prec[i] = solve(d,M);
    w.insert(-prec[i]);
}

for (i=1;i<=N;++i)
{
    w.erase(w.find(-prec[i]));

    for (j=1;j<=M;++j)
    u[j] = (t[i][j]) ? u[j]+1 : 0;

    prec[i] = solve(u,M) ;

    sus = max(sus , prec[i]);
    ans = max(ans , sus - *w.begin());
}

memset(prec,0,sizeof(prec));
w.clear();

for (j=M;j;--j)
{
    for (i=1;i<=N;++i)
    l[i] = (t[i][j]) ? l[i]+1 : 0;

    prec[j] = solve(l,N);
    w.insert(-prec[j]);
}

for (j=1;j<=M;++j)
{
    w.erase(w.find(-prec[j]));

    for (i=1;i<=N;++i)
    r[i] = (t[i][j]) ? r[i]+1 : 0;

    prec[j] = solve(r,M);

    stanga = max(stanga , prec[j]);
    ans = max(ans , stanga - *w.begin());
}

g<<ans<<'\n';

return 0;
}