Pagini recente » Borderou de evaluare (job #3304212) | Borderou de evaluare (job #3334687) | Borderou de evaluare (job #3356135) | Borderou de evaluare (job #3331094) | Cod sursa (job #3354530)
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n,m;
int A[205][205];
int up[205][205], l[205][205], r[205][205];
void read()
{
fin >> n >> m;
for(int i = 0; i < n; ++i){
string s;
fin >> s;
for(int j = 0; j < m; ++j){
A[i][j] = s[j] - '0';
}
}
}
void buildUp(int r1, int r2, int c1, int c2)
{
for(int j = c1; j <= c2; ++j){
for(int i = r1; i <= r2; ++i){
if(A[i][j] == 0){
if(i == r1){
up[i][j] = 1;
}
else{
up[i][j] = up[i - 1][j] + 1;
}
}
else{
up[i][j] = 0;
}
}
}
}
void buildLeftRight(int r1, int r2, int c1, int c2)
{
for(int i = r1; i <= r2; ++i){
stack<int> st;
st.push(c1);
l[i][c1] = c1 - 1;
for(int j = c1 + 1; j <= c2; ++ j){
while(!st.empty() && up[i][j] <= up[i][st.top()]){
st.pop();
}
if(st.empty()){
l[i][j] = c1 - 1;
}
else{
l[i][j] = st.top();
}
st.push(j);
}
}
for(int i = r1; i <= r2; ++i){
stack<int> st;
st.push(c2);
r[i][c2] = c2 + 1;
for(int j = c2 - 1; j >= c1; --j){
while(!st.empty() && up[i][j] <= up[i][st.top()]){
st.pop();
}
if(st.empty()){
r[i][j] = c2 + 1;
}
else{
r[i][j] = st.top();
}
st.push(j);
}
}
}
int maxArea(int r1, int r2, int c1, int c2)
{
buildUp(r1, r2, c1, c2);
buildLeftRight(r1, r2, c1, c2);
int maxA = 0;
for(int i = r1; i <= r2; ++i){
for(int j = c1; j <= c2; ++j){
int a = (r[i][j] - l[i][j] - 1) * up[i][j];
if(a > maxA){
maxA = a;
}
}
}
return maxA;
}
void solve()
{
int maxA = 0;
for(int i = 0; i < n - 1; ++i){
int a = maxArea(0, i, 0, m - 1) + maxArea(i + 1, n - 1, 0, m - 1);
if(a > maxA){
maxA = a;
}
}
for(int j = 0; j < m - 1; ++j){
int a = maxArea(0, n - 1, 0, j) + maxArea(0, n - 1, j + 1, m - 1);
if(a > maxA){
maxA = a;
}
}
fout << maxA;
}
int main()
{
read();
solve();
return 0;
}