Cod sursa(job #1340590)
Utilizator | Data | 11 februarie 2015 22:00:50 | |
---|---|---|---|
Problema | BMatrix | Scor | 4 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 8.83 kb |
#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];
char s[DIM];
void Read(){
fin >> n >> m;
for(i = 1; i <= n; i ++){
fin >> s + 1;
for(j = 1; j <= m; j ++)
a[i][j] = s[j] - '0';
}
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]);
if(k > 1){
f[1][k] = 0;
f[2][k] = 0;
k --;
}
else{
f[1][k] = b[i][j];
b[k][j] = b[i][j];
}
}
}
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]);
if(k > 1){
f[1][k] = 0;
f[2][k] = 0;
k --;
}
else{
f[1][k] = c[i][j];
c[k][j] = c[i][j];
}
}
}
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]);
if(k > 1){
f[1][k] = 0;
f[2][k] = 0;
k --;
}
else{
f[1][k] = d[i][j];
d[k][j] = d[i][j];
}
}
}
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(){
for(j = m; j >= 1; j --){
k = 0;
for(i = 1; i <= n + 1; i ++){
if(e[i][j] >= f[1][k] && e[i][j] != 0){
k ++;
f[1][k] = e[i][j];
f[2][k] = i;
}
else{
maxim = 0;
while(f[1][k] > e[i][j] && k != 0){
if(f[1][k] == f[1][k-1]){
f[1][k] = 0;
f[2][k] = 0;
k --;
}
else{
if(maxim < e[f[2][k]][j] * (i-f[2][k]))
maxim = e[f[2][k]][j] * (i-f[2][k]);
if(k > 1){
f[1][k] = 0;
f[2][k] = 0;
k --;
}
else{
f[1][k] = e[i][j];
e[k][j] = e[i][j];
}
}
}
if(est[j] < maxim) est[j] = maxim;
if(e[i][j] != 0){
k ++;
f[1][k] = e[i][j];
f[2][k] = i;
}
}
}
}
/*
maxim = 0;
for(i = 1; i <= m; i ++)
if(est[i] > maxim)
maxim = est[i];
fout << maxim << "\n";
*/
return;
}
void Remake_Vectors(){
maxim = 0;
for(i = 1; i <= n; i ++){
if(maxim < nord[i])
maxim = nord[i];
nord[i] = maxim;
}
maxim = 0;
for(i = n; i >= 1; i --){
if(maxim < sud[i])
maxim = sud[i];
sud[i] = maxim;
}
maxim = 0;
for(i = 1; i <= m; i ++){
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;
}