Cod sursa(job #2184679)

Utilizator catalina200029Olteanu Catalina catalina200029 Data 24 martie 2018 10:39:08
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
#define nmax 205
#define inf 40005

using namespace std;

ifstream f("bmatrix.in");
ofstream g("bmatrix.out");

char a[nmax][nmax];
int n,m,st[nmax],dr[nmax],sus[nmax],jos[nmax],v[nmax],sol;

int main() {
    int i,j,x,y,k;
    f>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            f>>a[i][j];
    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++) {
            if (a[i][j]=='0') v[j]++; ///nr de aparitii consecutive ale lui 0 pe coloana j pana in linia i
            else v[j]=0;
            x=inf;
            y=0;
            for (k=j;k>=1;k--) {
                x=min(x,v[k]); ///inaltimea dr
                y=max(y,x*(j-k+1));
            }
            st[i]=max(st[i],max(st[i-1],y)); ///dr de arie maxima pana la linia i
            sus[j]=max(sus[j],max(sus[j-1],y)); ///dr de arie maxima pana in coloana j
        }
    }
    memset(v,0,sizeof(v));
    for (i=n;i>=1;i--)
        for (j=m;j>=1;j--) {
            if (a[i][j]=='0') v[j]++; ///nr de aparitii consecutive ale lui 0 pe coloana j de la linia i la linia n
            else v[j]=0;
            x=inf;
            y=0;
            for (k=j;k<=m;k++) {
                x=min(x,v[k]); ///inaltimea dr
                y=max(y,x*(k-j+1));
            }
            dr[i]=max(dr[i],max(dr[i+1],y)); ///dr de arie maxima pana la linia i
            jos[j]=max(jos[j],max(jos[j+1],y)); ///dr de arie maxima pana in coloana j
        }
    for (i=1;i<n;i++)
        sol=max(sol,st[i]+dr[i+1]);
    for (i=1;i<m;i++)
        sol=max(sol,sus[i]+jos[i+1]);
    g<<sol;
    return 0;
}