Cod sursa(job #1256448)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 6 noiembrie 2014 12:15:54
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>

using namespace std;

bool a[1005][1005];
int s[1005][1005];
int d[1005][1005];
int dir[4][1005];
int n, m;

void process(int k, int n, int m)
{
    memset(d, 0, sizeof(d));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(a[i][j])d[i][j]=0;
            else d[i][j]=d[i-1][j]+1;
    stack <int> st;
    int lf[1005], rg[1005];
    memset(lf, 0, sizeof(lf));
    memset(rg, 0, sizeof(rg));
    for(int i=0;i<n;i++)
    {
        while(!st.empty())st.pop();
        for(int j=0;j<m;j++)
        {
            while(!st.empty() && d[i][st.top()]>=d[i][j])
                st.pop();
            if(!st.empty())lf[j]=st.top()+1;
            else lf[j]=0;
            st.push(j);
        }
        while(!st.empty())st.pop();
        for(int j=m-1;j>=0;j--)
        {
            while(!st.empty() && d[i][st.top()]>=d[i][j])
                st.pop();
            if(!st.empty())rg[j]=st.top()-1;
            else rg[j]=m-1;
            st.push(j);
        }
        int A=-1;
        for(int j=0;j<m;j++)
            A=max(A, d[i][j] * (rg[j]-lf[j]+1));
        dir[k][i]=max(dir[k][i-1], A);
    }
}

bool b[1005][1005];

void rotation()
{
    memset(b, 0, sizeof(b));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            b[m-1-j][i]=a[i][j];
    int aux=n;
    n=m;
    m=aux;
    memcpy(a, b, sizeof(b));
}

int main()
{
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++)
	{
		scanf("\n");
        for(int j=0;j<m;j++)
        {
        	char c;
        	scanf("%c", &c);
			a[i][j]=c=='1';
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
        }
	}
    for(int k=0;k<4;k++)
    {
        process(k, n, m);
        rotation();
    }
    reverse(dir[1], dir[1]+m);
    reverse(dir[2], dir[2]+n);
    int ans=-1;
    for(int i=0;i<=n;i++)
		ans=max(ans, dir[0][i]+dir[2][i+1]);
	for(int i=0;i<=m;i++)
		ans=max(ans, dir[3][i]+dir[1][i+1]);
    printf("%d\n", ans);
    return 0;
}