Pagini recente » Cod sursa (job #2147531) | Cod sursa (job #593612) | Cod sursa (job #3256075) | Cod sursa (job #2930716) | Cod sursa (job #1811150)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream in("matrix2.in");
ofstream out("matrix2.out");
const int maxn = 1005;
int sus[maxn][maxn];
int M[maxn][maxn];
stack <int> stst;
stack <int> stdr;
int st[maxn][maxn];
int dr[maxn][maxn];
int n, m;
void prec()
{
for(int i = 1; i <= n; i++)
{
while(!stst.empty())
stst.pop();
while(!stdr.empty())
stdr.pop();
for(int j = 1; j <= m; j++)
{
while(!stst.empty() && sus[i][stst.top()] >= sus[i][j])
stst.pop();
if(!stst.empty())
st[i][j] = stst.top();
stst.push(j);
}
stdr.push(m + 1);
for(int j = m; j >= 1; j--)
{
while(!stdr.empty() && sus[i][stdr.top()] >= sus[i][j])
stdr.pop();
if(!stdr.empty())
dr[i][j] = stdr.top();
stdr.push(j);
}
}
}
int main()
{
in >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
in >> M[i][j];
if(M[i][j] == 1)
sus[i][j] = 0;
else
sus[i][j] = sus[i - 1][j] + 1;
}
}
prec();
int mx = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
mx = max(mx, sus[i][j] * (dr[i][j] - st[i][j] - 1));
out << mx << "\n";
/*
for(int i = 1; i <= n; i++, cerr << "\n")
for(int j = 1; j <= m; j++)
cerr << st[i][j] << " ";
*/
return 0;
}