Cod sursa(job #1557403)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 27 decembrie 2015 14:43:14
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <string.h>

#define Ndim 205
#define ush unsigned short int
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
ush N,M,sol,P[Ndim][Ndim],V[Ndim];
struct strct{ush val,poz;}ST[Ndim];
bool A[Ndim][Ndim],AUX[Ndim][Ndim];
char S[Ndim];
void read()
{
    fin>>N>>M;
    for(int i=1;i<=N;i++)
    {
        fin>>S+1;
        for(int j=1;j<=M;j++)
            A[i][j]=S[j]-'0';
    }
}
void rotate_matrix_90()
{
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            AUX[j][N-i+1]=A[i][j];
    memcpy(A,AUX,sizeof(A));
    swap(M,N);
}
ush verif(int l)
{
    ush i,j,vf=0,val1=0,val2=0,lpoz;
    memset(V,0,sizeof(V));
    for(i=1;i<=l;i++)
    {
        for(j=1;j<=M;j++)
        {
            V[j]=(V[j]+1)*(1-A[i][j]);
            lpoz=j;
            while(V[j]<ST[vf].val)
            {
                val1=max(val1,(ush)((j-ST[vf].poz)*ST[vf].val));
                lpoz=ST[vf].poz;
                vf--;
            }
            if(V[j]==ST[vf].val)
                continue;
            ST[++vf].val=V[j];
            ST[vf].poz=lpoz;
        }
        V[j]=0;
        while(V[j]<ST[vf].val)
        {
            val1=max(val1,(ush)((j-ST[vf].poz)*ST[vf].val));
            vf--;
        }
    }
    vf=0;
    memset(V,0,sizeof(V));
    for(i=l+1;i<=N;i++)
    {
        for(j=1;j<=M;j++)
        {
            V[j]=(V[j]+1)*(1-A[i][j]);
            lpoz=j;
            while(V[j]<ST[vf].val)
            {
                val2=max(val2,(ush)((j-ST[vf].poz)*ST[vf].val));
                lpoz=ST[vf].poz;
                vf--;
            }
            if(V[j]==ST[vf].val)
                continue;
            ST[++vf].val=V[j];
            ST[vf].poz=lpoz;
        }
        V[j]=0;
        while(V[j]<ST[vf].val)
        {
            val2=max(val2,(ush)((j-ST[vf].poz)*ST[vf].val));
            vf--;
        }
    }
    return val1+val2;
}
void solve()
{
    int i,j;
    for(i=1;i<N;i++)
        sol=max(sol,verif(i));
    rotate_matrix_90();
    for(i=1;i<N;i++)
        sol=max(sol,verif(i));
}
void print()
{
    fout<<sol;
}
int main()
{
    read();
    solve();
    print();
    return 0;
}