Pagini recente » Cod sursa (job #800019) | Cod sursa (job #1003704) | Cod sursa (job #2648319) | Cod sursa (job #1452954) | Cod sursa (job #1387384)
#include <fstream>
#include <stack>
#include <set>
#include <cstring>
using namespace std;
#define NMAX 207
stack < pair < int , int > > q;
multiset < int > w;
int r[NMAX],l[NMAX],u[NMAX],d[NMAX],prec[NMAX],sol[NMAX];
int t[NMAX][NMAX];
string str;
int i,j,N,M,ans,sus,stanga;
int solve(int x[],int N)
{
int i,ans=0;
memset(sol,0,sizeof(sol));
while (q.size()) q.pop();
for (i=1;i<=N;++i)
{
while (q.size() && q.top().first>=x[i])
q.pop();
if (q.empty()) sol[i] = i;
else sol[i] = i-q.top().second;
q.push(make_pair(x[i],i));
}
while (q.size()) q.pop();
for (i=N;i;--i)
{
while (q.size() && q.top().first>=x[i])
q.pop();
if (q.empty()) sol[i] += N-i;
else sol[i] += q.top().second - i - 1;
ans = max(ans , sol[i]*x[i]);
q.push(make_pair(x[i],i));
}
return ans;
}
int main()
{
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
f>>N>>M;
for (i=1;i<=N;++i)
{
f>>str;
for (j=0;j<M;++j)
t[i][j+1]=(str[j]=='0');
}
for (i=N;i;--i)
{
for (j=1;j<=M;++j)
d[j] = (t[i][j]) ? d[j]+1 : 0;
prec[i] = solve(d,M);
w.insert(-prec[i]);
}
for (i=1;i<=N;++i)
{
w.erase(w.find(-prec[i]));
for (j=1;j<=M;++j)
u[j] = (t[i][j]) ? u[j]+1 : 0;
prec[i] = solve(u,M) ;
sus = max(sus , prec[i]);
ans = max(ans , sus - *w.begin());
}
memset(prec,0,sizeof(prec));
w.clear();
for (j=M;j;--j)
{
for (i=1;i<=N;++i)
l[i] = (t[i][j]) ? l[i]+1 : 0;
prec[j] = solve(l,N);
w.insert(-prec[j]);
}
for (j=1;j<=M;++j)
{
w.erase(w.find(-prec[j]));
for (i=1;i<=N;++i)
r[i] = (t[i][j]) ? r[i]+1 : 0;
prec[j] = solve(r,M);
stanga = max(stanga , prec[j]);
ans = max(ans , stanga - *w.begin());
}
g<<ans<<'\n';
return 0;
}