Pagini recente » Cod sursa (job #2878473) | Cod sursa (job #1013134) | Cod sursa (job #1717167) | Cod sursa (job #1216358) | Cod sursa (job #3185199)
#include <bits/stdc++.h>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int NMAX = 201;
int a[NMAX][NMAX], dir[NMAX][NMAX];
int directii[4][NMAX];
int n, m;
void debug( int N, int M){
for( int l = 1; l <= N; l++ ){
for( int c = 1; c <= M; c++ )
out << dir[l][c];
out << "\n";
}
out << "\n";
}
int skyline( deque <pair<int, int>> dq, int x ){
int aria = 0, after_me = x;
for( int i = 0; i < dq.size(); i++ )
aria = max( aria, dq.front().first * after_me ), after_me -= dq.front().second ,dq.pop_front();
return aria;
}
void bmatrix( int N, int M, int mat[NMAX][NMAX], int tip){
int up[NMAX];
for( int i = 1; i <= M; i++ )
up[i] = 0;
for( int l = 1; l <= N; l++ ){
int aria = 0, lungime = 0;
deque <pair<int, int>> dq;
for( int c = 1; c <= M; c++ ){
if( mat[l][c] == 0 ){
lungime++;
up[c]++;
int lenght = 1;
while( !dq.empty() && up[c] < dq.back().first ){
lenght += dq.back().second;
dq.pop_back();
}
aria = max( aria, lenght * up[c]);
dq.push_back({up[c], lenght});
aria = max( aria, skyline(dq, lungime) );
}
else{
up[c] = lungime = 0;
dq.clear();
}
}
directii[tip][l] = max(aria, directii[tip][l-1]);
}
}
int main()
{
in >> n >> m;
for( int l = 1; l <= n; l++ ){
char ch;
for( int c = 1; c <= m; c++ ){
in >> ch;
a[l][c] = ch - '0';
}
}
for( int l = 1; l <= n; l++ )
for( int c = 1; c <= m; c++ )
dir[l][c] = a[l][c];
// debug(n, m);
bmatrix(n, m, dir, 0);
for( int l = 1; l <= n/2; l++ )
for( int c = 1; c <= m; c++ ){
dir[l][c] = a[n-l+1][c];
dir[n-l+1][c] = a[l][c];
}
// debug(n, m);
bmatrix(n, m, dir, 1);
for( int l = 1; l <= m; l++ )
for( int c = 1; c <= n; c++ )
dir[l][c] = a[n-c+1][l];
// debug(m, n);
bmatrix(m, n, dir, 2);
for( int l = 1; l <= m; l++ )
for( int c = 1; c <= n; c++ )
dir[l][c] = a[c][m-l+1];
bmatrix(m, n, dir, 3);
int rez = 0;
for( int i = 2; i < n; i++ ){
rez = max( rez, directii[0][i] + directii[1][n-i] );
// out << directii[0][i] << " " << directii[1][n-i] << "\n";
}
// out << "\n";
for( int i = 2; i < m; i++ ){
rez = max( rez, directii[2][i] + directii[3][m-i]);
// out << directii[2][i] << " " << directii[3][m-i] << "\n";
}
out << rez;
return 0;
}