Cod sursa(job #1387316)

Utilizator ZenusTudor Costin Razvan Zenus Data 13 martie 2015 23:26:26
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <stack>
#include <cstring>

using namespace std;

#define NMAX 207

stack < pair < int , int > > q;
int h[NMAX],sol[NMAX];
int t[NMAX][NMAX];
string str;
int i,j,N,M,ans;

int solve(int x1,int y1,int x2,int y2)
{
    memset(h,0,sizeof(h));
    int i,j,ans=0;

    for (i=x1;i<=x2;++i)
    {
        for (j=y1;j<=y2;++j)

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

        for (j=y1;j<=y2;++j)
        {
            h[j] = (t[i][j]) ? h[j]+1 : 0;

            while (q.size() && q.top().first>=h[j])
            q.pop();

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

            q.push(make_pair(h[j],j));
        }

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

        for (j=y2;j>=y1;--j)
        {
            while (q.size() && q.top().first>=h[j])
            q.pop();

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

            ans = max (ans , sol[j]*h[j]);

            q.push(make_pair(h[j],j));
        }
    }

    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=1;i<=N;++i)
ans=max(ans,solve(1,1,i,M)+solve(i+1,1,N,M));

for (i=1;i<=M;++i)
ans=max(ans,solve(1,1,N,i)+solve(1,i+1,N,M));

g<<ans<<'\n';

return 0;
}