Cod sursa(job #828393)

Utilizator dariusdariusMarian Darius dariusdarius Data 3 decembrie 2012 18:46:17
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[210][210],aux[210][210];
int n,m,rez,d1[210],d2[210],st[210],left[210],right[210],c[210][210];
void change(int i) 
{
	int aaux,left,right;
	left=1;right=m;
    while(left<=right)
	{
        aaux=a[i][left];a[i][left]=a[i][right];a[i][right]=aaux;
        aaux=c[i][left];c[i][left]=c[i][right];c[i][right]=aaux;
		left++;right--;
    }
}
void rotire_dreapta() 
{
    memset(aux,0,sizeof(aux));
	int i,j,aaux;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            aux[j][n-i+1]=a[i][j];
    aaux=n;n=m;m=aaux;
    memcpy(a,aux,sizeof(a));
}
void solve(int i,int nameless[210]) 
{
    memset(nameless,0,sizeof(nameless));
    memset(st,0,sizeof(st));
    for(int j=1;j<=m;j++) 
	{
        st[++st[0]]=j;
        nameless[j]=j;
        while(st[0]>1 && c[i][st[st[0]-1]]>=c[i][st[st[0]]]) 
		{
            nameless[j]=min(nameless[j],nameless[st[st[0]-1]]);
            st[st[0]-1]=st[st[0]];
            st[0]--;
        }
    }
}
void magic(int nameless[210])
{
    memset(nameless,0,sizeof(nameless));
    memset(c,0,sizeof(c));
	int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(a[i][j]=='0')
                c[i][j]=1+c[i-1][j];
    for(i=1;i<=n;i++) 
	{
        solve(i,left);
        change(i);
        solve(i,right);
        for(j=1;j<=m;j++)
            right[j]=m-right[j]+1;
        int sst,ddr,auxx;
		sst=1;ddr=m;
		while(sst<=ddr)
		{
			auxx=right[sst];right[sst]=right[ddr];right[ddr]=auxx;
			sst++;ddr--;
		}
        change(i);
        nameless[i]=nameless[i-1];
        for(j=1;j<=m;j++)
            if(a[i][j]=='0')
                nameless[i]=max(nameless[i],c[i][j]*(right[j]-left[j]+1));
    }
}
int main() 
{ 
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",a[i]+1);
    magic(d1);
    rotire_dreapta();rotire_dreapta();
    magic(d2);
    for(int i=1;i<=n/2;i++)
        swap(d2[i],d2[n+1-i]);
    for(int i=1;i<n;i++)
        rez=max(rez,d1[i]+d2[i+1]);
    rotire_dreapta();
    magic(d1);
    rotire_dreapta();
	rotire_dreapta();
    magic(d2);
    for(int i=1;i<=n/2; i++)
        swap(d2[i],d2[n+1-i]);
    for(int i=1;i<n;i++)
        rez=max(rez,d1[i]+d2[i+1]);
    printf("%d\n", rez);
    return 0;
}