Pagini recente » Cod sursa (job #2851670) | Cod sursa (job #2693059) | Cod sursa (job #976458) | Cod sursa (job #1453626) | Cod sursa (job #1988121)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
const int nMax = 205;
const int mMax = 205;
int n, m;
char a[nMax][mMax];
int rasp = 0;
void citire()
{
ifstream in("bmatrix.in");
in >> n >> m;
for(int i = 1; i <= n; ++i)
in >> (a[i] + 1);
in.close();
}
int GetMax(int startX, int startY, int stopX, int stopY)
{
int ret = 0;
static int height[mMax];
static int firstSmallerSt[mMax];
static int firstSmallerDr[mMax];
stack<int> st;
for(int i = startY; i <= stopY; ++i)
height[i] = 0;
height[startY - 1] = height[stopY + 1] = -1;
int length;
for(int i = startX; i <= stopX; ++i) //fixam linia de jos
{
for(int j = startY; j <= stopY; ++j)
{
if(a[i][j] == '0')
height[j]++;
else
height[j] = 0;
}
st.push(startY - 1);
for(int j = startY; j <= stopY; ++j)
{
while(st.empty() == false && height[j] <= height[st.top()])
st.pop();
firstSmallerSt[j] = st.top();
st.push(j);
}
while(st.empty() == false)
st.pop();
st.push(stopY + 1);
for(int j = stopY; j >= startY; --j)
{
while(st.empty() == false && height[j] <= height[st.top()])
st.pop();
firstSmallerDr[j] = st.top();
st.push(j);
}
while(st.empty() == false)
st.pop();
for(int j = startY; j <= stopY; ++j)
{
if(height[j] == 0)
continue;
length = firstSmallerDr[j] - firstSmallerSt[j] - 1;
ret = max(ret, length * height[j]);
}
}
return ret;
}
void rezolvare()
{
for(int i = 1; i < n; ++i)
rasp = max(rasp, GetMax(1, 1, i, m) + GetMax(i+1, 1, n, m));
for(int i = 1; i < m; ++i)
rasp = max(rasp, GetMax(1, 1, n, i) + GetMax(1, i+1, n, m));
}
void afisare()
{
ofstream out("bmatrix.out");
out << rasp;
out.close();
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}