Cod sursa(job #1500883)

Utilizator margikiMargeloiu Andrei margiki Data 12 octombrie 2015 20:09:36
Problema BMatrix Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
# include <fstream>
# include <algorithm>
# include <cstring>
# define NR 205
using namespace std; ifstream f("bmatrix.in"); ofstream g("bmatrix.out"); struct elem {     int X, poz; }st1[NR], st2[NR]; int i,j,n,m,x,y,poztop,VV1,VV2,I,maxx; int sus[NR][NR], jos[NR][NR], S[NR], J[NR], a[NR][NR], b[NR][NR]; char ch; void init () {     memset (S, 0, sizeof(S));     memset (J, 0, sizeof(J));     for (int i=0; i<=n+1; ++i)         for (int j=0; j<=m+1; ++j)             sus[i][j]=0, jos[i][j]=0; } void rezolva () {     int i,j; init ();     for (i=1; i<=n; ++i)         for (j=1; j<=m; ++j) {             if (!a[i][j]) sus[i][j]=sus[i-1][j] + 1;             if (!a[n-i+1][j]) jos[n-i+1][j]=jos[n-i+2][j] + 1;         }      for (i=1; i<=n; ++i) {         VV1=0; VV2=0; I=n-i+1;         memset (st1, 0, sizeof(st1));         memset (st2, 0, sizeof(st2));          for (j=1; j<=m; ++j) {              if (sus[i][j] > st1[VV1].X) {                 st1[++VV1].X=sus[i][j];                 st1[VV1].poz=j;             }             else {                 poztop=st1[VV1].poz;                 while (VV1 && st1[VV1].X >= sus[i][j]) {                     S[i]=max(S[i], st1[VV1].X*(j-1-st1[VV1].poz+1));                     --VV1;                 }                 st1[++VV1].poz=poztop; st1[VV1].X=sus[i][j];             }               if (jos[I][j] > st2[VV2].X) {                 st2[++VV2].X=jos[I][j];                 st2[VV2].poz=j;             }             else {                 poztop=st2[VV2].poz;                 while (VV2 && st2[VV2].X >= jos[I][j]) {                     J[I]=max(J[I], st2[VV2].X*(j-1-st2[VV2].poz+1));                     --VV2;                 }                 st2[++VV2].poz=poztop; st2[VV2].X=jos[I][j];             }         }         while (VV1) {             S[i]=max(S[i], st1[VV1].X*(m-st1[VV1].poz+1));             --VV1;         }         while (VV2) {             J[I]=max(J[I], st2[VV2].X*(m-st2[VV2].poz+1));             --VV2;         }     }      for (i=1; i<=n; ++i) {         S[i]=max(S[i], S[i-1]);         J[i]=max(J[i], J[i+1]);          maxx=max(maxx, S[i-1]+J[i]);     } } void roteste () {     for (int i=1; i<=n; ++i)         for (int j=1; j<=m; ++j) {             b[m-j+1][i]=a[i][j];             a[i][j]=0;         }     swap(n, m);     for (int i=1; i<=n; ++i)         for (int j=1; j<=m; ++j)             a[i][j]=b[i][j]; } int main () {     f>>n>>m; f.get();     for (i=1; i<=n; ++i) {         for (j=1; j<=m; ++j) {             f>>ch;             a[i][j]=ch-'0';         }         f.get();     }      rezolva ();     roteste ();     rezolva ();      g<<maxx<<"\n";      return 0; }