Cod sursa(job #2006261)

Utilizator refugiatBoni Daniel Stefan refugiat Data 29 iulie 2017 10:36:17
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#define NMAX 205
#define INF (1<<30)
using namespace std;
ifstream si("bmatrix.in");
ofstream so("bmatrix.out");
int n,m;
bool v[NMAX][NMAX];
int h[NMAX];
pair<int,int> st[NMAX];
int sol[4][NMAX];
bool aux[NMAX][NMAX];
string s;

void r90()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            aux[j][n+1-i]=v[i][j];
        }
    }

    swap(n,m);
    memcpy(v,aux,sizeof(v));
}

void solve(int ind)
{
    memset(h,0,sizeof(h));

    for(int i=1;i<=n;++i)
    {
        int top=0;
        sol[ind][i]=sol[ind][i-1];
        for(int j=1;j<=m+1;++j)
        {
            if(v[i][j]==0&&j<=m)
                ++h[j];
            else
                h[j]=0;
            int s=0;
            while(top>0&&st[top].first>=h[j])
            {
                s+=st[top].second;
                sol[ind][i]=max(sol[ind][i],s*st[top].first);
                --top;
            }

            st[++top]=make_pair(h[j],s+1);
        }
    }
}

int main()
{
    si>>n>>m;
    for(int i=1;i<=n;++i)
    {
        si>>s;

        for(int j=1;j<=m;++j)
        {
            v[i][j]=s[j-1]-'0';
        }
    }

    for(int i=0;i<4;++i)
    {
        solve(i);
        r90();
    }

    int ans=0;
    for(int i=1;i<n;++i)
    {
        ans=max(ans,sol[0][i]+sol[2][n-i]);
    }

    for(int i=1;i<m;++i)
    {
        ans=max(ans,sol[1][i]+sol[3][m-i]);
    }

    so<<ans<<'\n';

    return 0;
}