Pagini recente » Monitorul de evaluare | Clasament dupa rating | Clasament dupa rating | Cod sursa (job #245840) | Cod sursa (job #1963589)
#include <fstream>
#include <algorithm>
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
ofstream fout("bmatrix.out");
char mat[201][201];
int n, m, maxArea, histo[201];
int best[4][201];
void Turn90()
{
char aux[201][201];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
aux[j][n - i + 1] = mat[i][j];
swap(n, m);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
mat[i][j] = aux[i][j];
cout << mat[i][j];
}
cout << '\n';
}
cout << '\n';
}
int MaxHistoRectArea()
{
stack<pair<int, int>> myS;
int maxArea = 0;
for (int i = 1; i <= m; i++)
{
while (!myS.empty() && histo[i] <= myS.top().first)
{
int h = myS.top().first; myS.pop();
int ant = myS.empty() ? 0 : myS.top().second;
maxArea = max(maxArea, h * (i - 1 - ant));
}
int ant = myS.empty() ? 0 : myS.top().second;
maxArea = max(maxArea, histo[i] * (i - ant));
myS.push(make_pair(histo[i], i));
}
while (!myS.empty())
{
int h = myS.top().first; myS.pop();
int ant = myS.empty() ? 0 : myS.top().second;
int area = h * (m - ant);
maxArea = max(maxArea, area);
}
return maxArea;
}
void Process(int v[])
{
memset(histo, 0, sizeof(histo));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
if (mat[i][j] == '0')
histo[j] ++;
else
histo[j] = 0;
v[i] = max(v[i - 1], MaxHistoRectArea());
}
}
int main()
{
freopen("bmatrix.in", "r", stdin);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%s", &mat[i][1]);
Process(best[0]);
Turn90(); Process(best[1]);
Turn90(); Process(best[2]);
Turn90(); Process(best[3]);
swap(n, m);
for (int i = 1; i < n; i++)
maxArea = max(maxArea, best[0][i] + best[2][n - i]);
for (int i = 1; i < m; i++)
maxArea = max(maxArea, best[1][i] + best[3][m - i]);
fout << maxArea << '\n';
return 0;
}