Pagini recente » Cod sursa (job #2634105) | Cod sursa (job #1315284) | Cod sursa (job #2314172) | Cod sursa (job #2630177) | Cod sursa (job #1339666)
#include <fstream>
#include <cstring>
#define DIM 210
using namespace std;
ifstream fin ("bmatrix.in" );
ofstream fout("bmatrix.out");
int n, m, i, j, k, ok, minim, maxim, x, y;
int a[DIM][DIM], b[DIM][DIM], c[DIM][DIM];
int d[DIM][DIM], e[DIM][DIM], nord[DIM];
int f[3][DIM], sud[DIM], est[DIM], vest[DIM];
void Read(){
fin >> n >> m;
for(i = 1; i <= n; i ++)
for(j = 1; j <= m; j ++)
fin >> a[i][j];
return;
}
void SumeNS(){
for(i = 1; i <= n; i ++)
for(j = 1; j <= m; j ++)
if(a[i][j] == 1) b[i][j] = 0;
else b[i][j] = b[i-1][j] + 1;
for(i = n; i >= 1; i --)
for(j = 1; j <= m; j ++)
if(a[i][j] == 1) c[i][j] = 0;
else c[i][j] = c[i+1][j] + 1;
return;
}
void SumeVE(){
for(j = 1; j <= m; j ++)
for(i = 1; i <= n; i ++)
if(a[i][j] == 1) d[i][j] = 0;
else d[i][j] = d[i][j-1] + 1;
for(j = m; j >= 1; j --)
for(i = 1; i <= n; i ++)
if(a[i][j] == 1) e[i][j] = 0;
else e[i][j] = e[i][j+1] + 1;
return;
}
void TundeNS(){
for(i = 1; i <= n; i ++){
k = 0;
for(j = 1; j <= m + 1; j ++){
if(b[i][j] >= f[1][k] && b[i][j] != 0){
k ++;
f[1][k] = b[i][j];
f[2][k] = j;
}
else{
maxim = 0;
while(f[1][k] > b[i][j] && k != 0){
if(f[1][k] == f[1][k-1]){
f[1][k] = 0;
f[2][k] = 0;
k --;
}
else{
if(maxim < b[i][f[2][k]] * (j-f[2][k]))
maxim = b[i][f[2][k]] * (j-f[2][k]);
f[1][k] = 0;
f[2][k] = 0;
k --;
}
}
if(nord[i] < maxim) nord[i] = maxim;
if(b[i][j] != 0){
k ++;
f[1][k] = b[i][j];
f[2][k] = j;
}
}
}
}
maxim = 0;
for(i = 1; i <= n; i ++)
if(nord[i] > maxim)
maxim = nord[i];
fout << maxim << "\n";
return;
}
void TundeSN(){
for(i = n; i >= 1; i --){
k = 0;
for(j = 1; j <= m + 1; j ++){
if(c[i][j] >= f[1][k] && c[i][j] != 0){
k ++;
f[1][k] = c[i][j];
f[2][k] = j;
}
else{
maxim = 0;
while(f[1][k] > c[i][j] && k != 0){
if(f[1][k] == f[1][k-1]){
f[1][k] = 0;
f[2][k] = 0;
k --;
}
else{
if(maxim < c[i][f[2][k]] * (j-f[2][k]))
maxim = c[i][f[2][k]] * (j-f[2][k]);
f[1][k] = 0;
f[2][k] = 0;
k --;
}
}
if(sud[i] < maxim) sud[i] = maxim;
if(c[i][j] != 0){
k ++;
f[1][k] = b[i][j];
f[2][k] = j;
}
}
}
}
maxim = 0;
for(i = 1; i <= n; i ++)
if(sud[i] > maxim)
maxim = sud[i];
fout << maxim << "\n";
return;
}
void TundeVE(){
for(j = 1; j <= m; j ++){
k = 0;
for(i = 1; i <= n + 1; i ++){
if(d[i][j] >= f[1][k] && d[i][j] != 0){
k ++;
f[1][k] = d[i][j];
f[2][k] = i;
}
else{
maxim = 0;
while(f[1][k] > d[i][j] && k != 0){
if(f[1][k] == f[1][k-1]){
f[1][k] = 0;
f[2][k] = 0;
k --;
}
else{
if(maxim < d[f[2][k]][j] * (i-f[2][k]))
maxim = d[f[2][k]][j] * (i-f[2][k]);
f[1][k] = 0;
f[2][k] = 0;
k --;
}
}
if(vest[j] < maxim) vest[j] = maxim;
if(d[i][j] != 0){
k ++;
f[1][k] = d[i][j];
f[2][k] = i;
}
}
}
}
maxim = 0;
for(i = 1; i <= m; i ++)
if(vest[i] > maxim)
maxim = vest[i];
fout << maxim << "\n";
return;
}
/*
void TundeEV(){
}
void Remake_Vectors(){
maxim = 0;
for(i = 1; i <= n; i ++){
if(maxim < nord[i])
maxim = nord[i];
nord[i] = maxim;
}
fout << maxim << "\n";
maxim = 0;
for(i = n; i >= 1; i --){
if(maxim < sud[i])
maxim = sud[i];
sud[i] = maxim;
}
maxim = 0;
fout << maxim << "\n";
/*for(i = 1; i <= m; j ++){
if(maxim < vest[i])
maxim = vest[i];
vest[i] = maxim;
}
maxim = 0;
for(i = m; i >= 1; i --){
if(maxim < est[i])
maxim = est[i];
est[i] = maxim;
}
return;
}
void Max_Array(){
maxim = 0;
for(i = 1; i < n; i ++)
if(nord[i] + sud[i+1] > maxim)
maxim = nord[i] + sud[i+1];
for(i = 1; i < m; i ++)
if(vest[i] + est[i+1] > maxim)
maxim = vest[i] + est[i+1];
fout << maxim;
return;
}*/
int main(){
Read();
SumeNS(); SumeVE();
TundeNS(); TundeSN();
TundeVE(); //TundeEV();
//Remake_Vectors();
//Max_Array();
return 0;
}