Pagini recente » Cod sursa (job #544530) | Cod sursa (job #1233938) | Cod sursa (job #577020) | Cod sursa (job #1712958) | Cod sursa (job #1500867)
# 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; } if (sus[i][j]) 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; } if (jos[I][j]) 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]); if (S[i] && J[i+1]) maxx=max(maxx, S[i]+J[i+1]); } } 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; }