Pagini recente » Cod sursa (job #291887) | Cod sursa (job #545664) | Cod sursa (job #737897) | Cod sursa (job #1280757) | Cod sursa (job #1467019)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
#define Nmax 202
FILE *f = fopen ( "bmatrix.in", "r" );
FILE *g = fopen ( "bmatrix.out", "w" );
// v = matricea pe care lucrez
// aux = matrice pentru rotit
// LimSus[i][j] = cat de mult pot urca, numai pe elem de 0 de pe pozitia (i,j)
// LimSus[i][j] = cat de mult pot cobora, numai pe elem de 0 de pe pozitia (i,j)
// CelMaiSt[x] = primul element din stanga lui x, mai mic decat el
// CelMaiDr[x] = primul element din dreapta lui x, mai mic decat el
// SolSus[x] = aria celui mai mare dreptunghi plin de 0 care are latura de jos pe linia i
// SolJos[x] = aria celui mai mare dreptunghi plin de 0 care are latura de sus pe linia i
int LimSus[Nmax][Nmax], LimJos[Nmax][Nmax];
int CelMaiSt[Nmax], CelMaiDr[Nmax], SolSus[Nmax], SolJos[Nmax];
int N, M, BestSol = -1;
char v[Nmax][Nmax], aux[Nmax][Nmax];
stack < int > St;
void Citire(){
fscanf ( f, "%d%d%*c", &N, &M );
for ( int i = 1; i <= N; ++i )
fscanf ( f, "%s%*c", v[i]+1 );
}
void ClearStack (){
while ( !St.empty() )
St.pop();
}
void Precalc (){
memset ( LimSus, 0, sizeof (LimSus) );
memset ( LimJos, 0, sizeof (LimJos) );
for ( int i = 1, k = N; i <= N; ++i, --k ){
for ( int j = 1; j <= M; ++j ){
if ( v[i][j] == '0' )
LimSus[i][j] = LimSus[i-1][j] + 1;
if ( v[k][j] == '0' )
LimJos[k][j] = LimJos[k+1][j] + 1;
}
}
}
void Roteste (){
for ( int i1 = 1, i2 = N; i1 <= N; ++i1, --i2 )
for ( int j = 1; j <= M; ++j )
aux[j][i2] = v[i1][j];
memcpy( v, aux, sizeof (aux) );
swap ( N, M );
}
void GetUpper (){
memset(SolSus, 0, sizeof(SolSus) );
ClearStack();
for ( int i = 1; i <= N; ++i ){
for ( int j = 1; j <= M; ++j ){
int last = j;
if ( LimSus[i][j] == 0 )
continue;
CelMaiSt[j] = j;
while ( !St.empty() && LimSus[i][j] <= LimSus[i][St.top()] ){
last = St.top();
St.pop();
}
CelMaiSt[j] = CelMaiSt[last];
St.push(j);
}
ClearStack();
for ( int j = M; j >= 1; --j ){
int last = j;
if ( LimSus[i][j] == 0 )
continue;
CelMaiDr[j] = j;
while ( !St.empty() && LimSus[i][j] <= LimSus[i][St.top()] ){
last = St.top();
St.pop();
}
CelMaiDr[j] = CelMaiDr[last];
St.push(j);
}
for ( int j = 1; j <= M; ++j )
SolSus[i] = max ( SolSus[i], LimSus[i][j] * (CelMaiDr[j] - CelMaiSt[j] + 1) );
}
}
void GetLower (){
memset(SolJos, 0, sizeof(SolJos) );
ClearStack();
for ( int i = 1; i <= N; ++i ){
for ( int j = 1; j <= M; ++j ){
int last = j;
if ( LimJos[i][j] == 0 )
continue;
CelMaiSt[j] = j;
while ( !St.empty() && LimJos[i][j] <= LimJos[i][St.top()] ){
last = St.top();
St.pop();
}
CelMaiSt[j] = CelMaiSt[last];
St.push(j);
}
ClearStack();
for ( int j = M; j >= 1; --j ){
int last = j;
if ( LimJos[i][j] == 0 )
continue;
CelMaiDr[j] = j;
while ( !St.empty() && LimJos[i][j] <= LimJos[i][St.top()] ){
last = St.top();
St.pop();
}
CelMaiDr[j] = CelMaiDr[last];
St.push(j);
}
for ( int j = 1; j <= M; ++j )
SolJos[i] = max ( SolJos[i], LimJos[i][j] * (CelMaiDr[j] - CelMaiSt[j] + 1) );
}
}
void Rezolva(){
GetUpper();
GetLower();
for ( int i = 1, j = N; i <= N; ++i, --j ){
SolSus[i] = max ( SolSus[i-1], SolSus[i] );
SolJos[j] = max ( SolJos[j+1], SolJos[j] );
}
for ( int i = 1; i <= N; ++i )
BestSol = max ( BestSol, SolSus[i] + SolJos[i+1] );
}
void Scrie(){
fprintf ( g, "%d", BestSol );
}
int main(){
Citire();
Precalc();
Rezolva();
Roteste();
Precalc();
Rezolva();
Scrie();
return 0;
}