Pagini recente » Cod sursa (job #2799151) | Cod sursa (job #1180668) | Cod sursa (job #1227170) | Cod sursa (job #2269836) | Cod sursa (job #1311224)
#include <fstream>
#include <iostream>
#define DIM 203
using namespace std;
struct nod {
int h;
int p;
};
nod S[DIM];
char s[DIM][DIM], b[DIM][DIM];
int a[DIM][DIM];
int sus[DIM], jos[DIM];
int n, m, i, j, sol, nr;
void calcul() {
int i, j, k, aria, poz, aux;
for (i=1;i<=n;i++) {
for (j=1;j<=m;j++)
if (s[i][j] == '0')
a[i][j] = 1 + a[i-1][j];
else
a[i][j] = 0;
sus[i] = jos[i] = 0;
}
for (i=1;i<=n;i++) {
k = 0;
for (j=1;j<=m+1;j++){
if (a[i][j] > S[k].h) {
k++;
S[k].h = a[i][j];
S[k].p = j;
continue;
}
while (k > 0 && a[i][j] <= S[k].h) {
int aria = (j-S[k].p)*S[k].h;
sus[i] = max(sus[i], aria);
poz = S[k].p;
k--;
}
if (a[i][j] > 0) {
k++;
S[k].p = poz;
S[k].h = a[i][j];
}
}
}
for (i=2;i<=n;i++)
sus[i] = max(sus[i], sus[i-1]);
for (i=1;i<=n/2;i++)
for (j=1;j<=m;j++) {
aux = s[i][j];
s[i][j] = s[n-i+1][j];
s[n-i+1][j] = aux;
}
for (i=1;i<=n;i++) {
for (j=1;j<=m;j++)
if (s[i][j] == '0')
a[i][j] = 1 + a[i-1][j];
else
a[i][j] = 0;
}
for (i=1;i<=n;i++) {
k = 0;
for (j=1;j<=m+1;j++){
if (a[i][j] > S[k].h) {
k++;
S[k].h = a[i][j];
S[k].p = j;
continue;
}
while (k > 0 && a[i][j] <= S[k].h) {
int aria = (j-S[k].p)*S[k].h;
jos[i] = max(jos[i], aria);
poz = S[k].p;
k--;
}
if (a[i][j] > 0) {
k++;
S[k].p = poz;
S[k].h = a[i][j];
}
}
}
for (i=2;i<=n;i++)
jos[i] = max(jos[i], jos[i-1]);
for (i=1;i<=n/2;i++) {
aux = jos[i];
jos[i] = jos[n-i+1];
jos[n-i+1] = aux;
}
for (i=1;i<=n/2;i++)
for (j=1;j<=m;j++) {
aux = s[i][j];
s[i][j] = s[n-i+1][j];
s[n-i+1][j] = aux;
}
/*
for (i=1;i<=n;i++)
for (j=i;j<=n;j++) {
nr = 0;
for (k=1;k<=m;k++) {
if (a[j][k] >= j-i+1)
nr++;
else
nr=0;
aria = nr * (j-i+1);
sus[j] = max(sus[j], aria);
jos[i] = max(jos[i], aria);
}
}
*/
}
void afisare(char a[DIM][DIM], int n, int m) {
int i, j;
for (i=1;i<=n;i++) {
for (j=1;j<=m;j++)
cout<<a[i][j];
cout<<"\n";
}
cout<<"\n";
}
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int main() {
fin>>n>>m;
for (i=1;i<=n;i++) {
fin>>s[i] + 1;
}
//afisare(s, n, m);
calcul();
for (i=1;i<n;i++)
sol = max(sol, jos[i+1] + sus[i]);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
b[m-j+1][i] = s[i][j];
swap(n, m);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
s[i][j] = b[i][j];
// afisare(s, n, m);
calcul();
for (i=1;i<n;i++)
sol = max(sol, jos[i+1] + sus[i]);
fout<<sol;
return 0;
}