Pagini recente » Cod sursa (job #1756852) | Cod sursa (job #596328) | Cod sursa (job #1187504) | Cod sursa (job #1795912) | Cod sursa (job #1811098)
#include <iostream>
#include <fstream>
#include <bitset>
#include <stack>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int maxn = 205;
bitset <maxn> M[maxn];
int sus[maxn][maxn];
int st[maxn][maxn];
int dr[maxn][maxn];
stack <int> stst;
stack <int> stdr;
void erase_st()
{
while(!stst.empty())
stst.pop();
while(!stdr.empty())
stdr.pop();
}
void erase_mat()
{
for(int i = 0; i < maxn; i++)
{
for(int j = 0; j < maxn; j++)
{
st[i][j] = 0;
dr[i][j] = 0;
sus[i][j] = 0;
}
}
}
int solve(int x1, int y1, int x2, int y2)
{
erase_mat();
for(int i = x1; i <= x2; i++)
{
for(int j = y1; j <= y2; j++)
{
if(M[i][j] == 1)
sus[i][j] = 0;
else
sus[i][j] = sus[i - 1][j] + 1;
}
}
for(int i = x1; i <= x2; i++)
{
erase_st();
for(int j = y1; j <= y2; j++)
{
while(!stst.empty() && sus[i][stst.top()] >= sus[i][j])
stst.pop();
if(!stst.empty())
st[i][j] = stst.top();
else
st[i][j] = y1 - 1;
stst.push(j);
}
//stdr.push(y2 + 1);
for(int j = y2; j >= y1; j--)
{
while(!stdr.empty() && sus[i][stdr.top()] >= sus[i][j])
stdr.pop();
if(!stdr.empty())
dr[i][j] = stdr.top();
else
dr[i][j] = y2 + 1;
stdr.push(j);
}
}
int mx = 0;
for(int i = x1; i <= x2; i++)
for(int j = y1; j <= y2; j++)
mx = max(mx, sus[i][j] * (dr[i][j] - st[i][j] - 1));
return mx;
}
int main()
{
int n, m;
in >> n >> m;
for(int i = 1; i <= n; i++)
{
string s = "";
in >> s;
for(int j = 0; j < m; j++)
M[i][j + 1] = s[j] - '0';
}
int mx = 0;
for(int lin = 1; lin < n; lin++)
mx = max(mx, solve(1, 1, lin, m) + solve(lin + 1, 1, n, m));
for(int col = 1; col < m; col++)
mx = max(mx, solve(1, 1, n, col) + solve(1, col + 1, n, m));
out << mx << "\n";
return 0;
}