Cod sursa(job #1790300)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 27 octombrie 2016 23:15:49
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.26 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MaxN 300
#define INF 2140000000
 
FILE *IN,*OUT;
int N,M,L[MaxN][MaxN],C[MaxN][MaxN],RL[MaxN][MaxN],RC[MaxN][MaxN];
struct coord{int x,y,Size;}Fwd[MaxN][MaxN],Rect[MaxN][MaxN],Bkd[MaxN][MaxN];
bool v[MaxN][MaxN];
char Ch;
 
inline int min(int a,int b)
{
    if(a<b)
        return a;
    else return b;
}
inline int max(int a,int b)
{
    if(a>b)
        return a;
    else return b;
}
 
int main()
{
    IN=fopen("bmatrix.in","r");
    OUT=fopen("bmatrix.out","w");
  
    fscanf(IN,"%d%d ",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            fscanf(IN,"%c ",&Ch);
			if(Ch=='0')
				v[i][j]=false;
			else v[i][j]=true;
        }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            if(v[i][j])
                L[i][j]=C[i][j]=0;
            else
            {
                L[i][j]=L[i][j-1]+1;
                C[i][j]=C[i-1][j]+1;
            }
        }
    for(int i=N;i>0;i--)
        for(int j=M;j>0;j--)
        {
            if(v[i][j])
                RL[i][j]=RC[i][j]=0;
            else
            {
                RL[i][j]=RL[i][j+1]+1;
                RC[i][j]=RC[i+1][j]+1;
            }
        }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            if(v[i][j])
            {
                Fwd[i][j].x=i,Fwd[i][j].y=j,Fwd[i][j].Size=0;
                Rect[i][j]=Fwd[i][j];
            }
            else
            {
                int Max=INF;
                for(int k=i;k>=i-C[i][j]+1;k--)
                {
                    Max=min(Max,L[k][j]);
                    if(Fwd[i][j].Size<Max*(i-k+1))
                    {
                        Fwd[i][j].x=k;
                        Fwd[i][j].y=j-Max+1;
                        Fwd[i][j].Size=(i-k+1)*Max;
                        Rect[i][j]=Fwd[i][j];
                    }
                }
            }
                if(Fwd[i][j-1].Size>Fwd[i][j].Size)
                    Fwd[i][j]=Fwd[i][j-1];
                if(Fwd[i-1][j].Size>Fwd[i][j].Size)
                    Fwd[i][j]=Fwd[i-1][j];
        }
    for(int i=N;i>0;i--)
        for(int j=M;j>0;j--)
        {
            if(v[i][j])
                Bkd[i][j].x=i,Bkd[i][j].y=j,Bkd[i][j].Size=0;
            else
            {
                int Max=INF;
                for(int k=i;k<=i+RC[i][j]-1;k++)
                {
                    Max=min(Max,RL[k][j]);
                    if(Bkd[i][j].Size<(k-i+1)*Max)
                    {
                        Bkd[i][j].x=k;
                        Bkd[i][j].y=j+Max-1;
                        Bkd[i][j].Size=(k-i+1)*Max;
                    }
                }
            }
                if(Bkd[i][j+1].Size>Bkd[i][j].Size)
                    Bkd[i][j]=Bkd[i][j+1];
                if(Bkd[i+1][j].Size>Bkd[i][j].Size)
                    Bkd[i][j]=Bkd[i+1][j];
        }
    int Total=0;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            Total=max(Total,Rect[i][j].Size+(max(max(Fwd[N][Rect[i][j].y-1].Size,Fwd[Rect[i][j].x-1][M].Size),max(Bkd[i+1][1].Size,Bkd[1][j+1].Size))));
        }
    fprintf(OUT,"%d",Total);
    return 0;
}