Pagini recente » Cod sursa (job #407724) | Cod sursa (job #723488) | Cod sursa (job #1457590) | Cod sursa (job #1344216) | Cod sursa (job #1467084)
#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)
// 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 SolSus[Nmax], SolJos[Nmax];
int N, M, BestSol = -1;
char v[Nmax][Nmax], aux[Nmax][Nmax];
stack < pair < int, 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 ){
SolSus[i] = SolSus[i-1];
for ( int j = 1; j <= M; ++j ){
int last = j;
while ( !St.empty() && LimSus[i][j] < LimSus[i][St.top().first] ){
SolSus[i] = max ( SolSus[i], LimSus[i][St.top().first] * (j- St.top().second) );
last = St.top().second;
St.pop();
}
if ( LimSus[i][j] == 0 )
continue;
if ( St.empty() )
St.push ( make_pair ( j, last ) );
else if ( LimSus[i][St.top().first] < LimSus[i][j] )
St.push ( make_pair ( j, last ) );
}
while ( !St.empty() ){
SolSus[i] = max ( SolSus[i], LimSus[i][St.top().first] * ( M - St.top().second + 1 ) );
St.pop();
}
}
}
void GetLower (){
memset ( SolJos, 0, sizeof(SolJos) );
ClearStack();
for ( int i = N; i >= 1; --i ){
SolJos[i] = SolJos[i+1];
for ( int j = 1; j <= M; ++j ){
int last = j;
while ( !St.empty() && LimJos[i][j] < LimJos[i][St.top().first] ){
SolJos[i] = max ( SolJos[i], LimJos[i][St.top().first] * (j - St.top().second) );
last = St.top().second;
St.pop();
}
if ( LimJos[i][j] == 0 )
continue;
if ( St.empty() )
St.push ( make_pair ( j, last ) );
else if ( LimJos[i][St.top().first] < LimJos[i][j] )
St.push ( make_pair ( j, last ) );
}
while ( !St.empty() ){
SolJos[i] = max ( SolJos[i], LimJos[i][St.top().first] * ( M - St.top().second + 1 ) );
St.pop();
}
}
}
void Rezolva(){
GetUpper();
GetLower();
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;
}