Pagini recente » Cod sursa (job #361471) | Cod sursa (job #1984543) | Cod sursa (job #448546) | Cod sursa (job #1954953) | Cod sursa (job #2009268)
#include<fstream>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int INF =1000;
int times,k,n,m,i,j;
int maxim_orizontal_sus,maxim_orizontal_jos,maxim_vertical_stanga, maxim_vertical_dreapta;
int maxim_vertical, maxim_orizontal;
int tablou[2][201][201], sumcol[201][201],stiva[201],biggest[5][201],stanga[201],dreapta[201];
char q;
int main(){
in >> n >> m;
for( i = 1; i <= n; i ++ ){
for( j = 1; j <= m; j ++ ){
in >> q;
if( q == '1' ){
tablou[0][i][j] = -INF;
}
else{
tablou[0][i][j] = 0;
}
}
}
for( times = 0; times < 4; times ++ ){
for( j = 1; j <= m; j ++ ){
for( i = 1; i <= n; i ++ ){
if( tablou[times%2][i][j] != -INF ){
if( sumcol[i-1][j] > 0 ){
sumcol[i][j] = sumcol[i-1][j] + 1;
}
else{
sumcol[i][j] = 1;
}
}
else{
sumcol[i][j] = 0;
}
}
}
for( i = 1; i <= n; i ++ ){
k = 0;
for( j = 1; j <= m; j ++ ){
while( k > 0 and sumcol[i][stiva[k]] >= sumcol[i][j] ){
k--;
}
stanga[j] = stiva[k];
k++; stiva[k] = j;
}
k = 0;
for( j = m; j >= 1; j -- ){
while( k > 0 and sumcol[i][stiva[k]] >= sumcol[i][j] ){
k--;
}
dreapta[j] = stiva[k];
k++; stiva[k] = j;
}
stanga[1] = 0; dreapta[m] = m+1;
for( j = 1; j <= m; j ++ ){
biggest[times+1][i] = max( biggest[times+1][i], sumcol[i][j]*( (dreapta[j]-1) - (stanga[j]+1 ) + 1 ));
}
}
for( i = 1; i <= m; i ++ ){
for( j = 1; j <= n; j ++ ){
tablou[(times+1)%2][i][j] = tablou[times%2][j][m-i+1];
}
}
swap( n,m );
}
for( i = 1; i <= n/2; i ++ ){
swap( biggest[3][i], biggest[3][n-i+1] );
}
for( j = 1; j <= m/2; j ++ ){
swap( biggest[4][j], biggest[4][m-j+1] );
}
for( k = 2; k <= m-1; k ++ ){
maxim_vertical_stanga = 0; maxim_vertical_dreapta = 0;
for( j = 1; j < k; j ++ ){
maxim_vertical_stanga = max( maxim_vertical_stanga, biggest[2][j] );
}
for( j = k; j <= m; j ++ ){
maxim_vertical_dreapta = max( maxim_vertical_dreapta, biggest[4][j] );
}
maxim_vertical = max( maxim_vertical, maxim_vertical_stanga + maxim_vertical_dreapta);
}
for( k = 2; k <= n-1; k ++ ){
maxim_orizontal_sus = 0; maxim_orizontal_jos = 0;
for( i = 1; i < k; i ++ ){
maxim_orizontal_sus = max( maxim_orizontal_sus, biggest[1][i] );
}
for( i = k; i <= n; i ++ ){
maxim_orizontal_jos = max( maxim_orizontal_jos, biggest[3][i] );
}
maxim_orizontal = max( maxim_orizontal_sus+ maxim_orizontal_jos,maxim_orizontal );
}
out<< max( maxim_orizontal,maxim_vertical );
return 0;
}