Pagini recente » Cod sursa (job #458531) | Cod sursa (job #692355) | Cod sursa (job #2237027) | Cod sursa (job #1982680) | Cod sursa (job #1783902)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
bool matrix[300][300];
int n, m;
int h[300];
long long lmax[300], lmaxoglind[300];
void roteste(); /// roteste spre dreapta
void oglindeste(); /// inversiune fata de mij axei ox
long long skyline(int c); /// cel mai mare dreptunghi care are baza pe linia c, c din { 1, 2, ... n - 1 }
long long f(); /// maximul pt matrix (dupa se roteste matrixul si se apeleaza din nou)
int main()
{
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
in >> n >> m;
char c;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
in >> c;
if (c == '0')
matrix[i][j] = true;
}
}
long long mxm = f();
oglindeste();
roteste();
mxm = max(mxm, f());
out << mxm;
return 0;
}
long long f()
{
for (int i = 1; i <= n; i++)
lmax[n - i + 1] = skyline(i);
oglindeste();
for (int i = 1; i <= n; i++)
lmaxoglind[i] = skyline(i);
long long mxm = 0;
for (int i = 1; i < n; i++) {
lmaxoglind[i] = max(lmaxoglind[i], lmaxoglind[i - 1]);
mxm = max(mxm, lmax[i + 1] + lmaxoglind[i]);
}
return mxm;
}
long long skyline(int c)
{
if (c == 1) {
int r = 0, mxm = 0;
for (int i = 1; i <= m; i++) {
if (matrix[1][i])
r++, h[i] = 1;
else
mxm = max(mxm, r), h[i] = 0, r = 0;
}
mxm = max(mxm, r);
return mxm;
}
for (int i = 1; i <= m; i++) {
if (matrix[c][i] == 0)
h[i] = 0;
else
h[i]++;
}
stack <pair <int, int>> s;
long long mxm = 0;
for (int i = 1; i <= m; i++) {
int l = 0;
while (!s.empty() && s.top().first >= h[i]) {
l += s.top().second;
mxm = max(mxm, 1ll * l * s.top().first);
s.pop();
}
s.push({ h[i], l + 1 });
}
int l = 0;
while (!s.empty()) {
l += s.top().second;
mxm = max(mxm, 1ll * l * s.top().first);
s.pop();
}
return mxm;
}
void roteste()
{
bool matrix2[250][250];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
matrix2[i][j] = matrix[j][i];
swap(n, m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
matrix[i][j] = matrix2[i][j];
}
void oglindeste()
{
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n / 2; j++)
swap(matrix[j][i], matrix[n - j + 1][i]);
}
}