Pagini recente » Cod sursa (job #3159725) | Cod sursa (job #2444268) | Cod sursa (job #3163068) | Cod sursa (job #2867334) | Cod sursa (job #1721535)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int mafia = 205;
int n,m,a[mafia][mafia],sol,b[mafia][mafia],s1[mafia][mafia];
int v[mafia],dp1[mafia],dp2[mafia],s2[mafia][mafia];
int stg[mafia],drp[mafia];
stack < pair < int, int > > st;
inline int Check()
{
int i,j,sum = 0;
while(!st.empty()) st.pop();
stg[1] = 0;
st.push(make_pair(v[1],1));
for(i = 2; i <= m; i++)
{
while(!st.empty() && st.top().first >= v[i]) st.pop();
if(v[i]==v[i-1]) stg[i] = stg[i-1]+1;
else if(v[i] > v[i-1]) stg[i] = 0;
else
{
if(st.empty()) stg[i] = i-1;
else stg[i] = (i-st.top().second-1);
}
st.push(make_pair(v[i],i));
}
while(!st.empty()) st.pop();
drp[m] = 0;
st.push(make_pair(v[m],m));
for(i = m-1; i > 0; i--)
{
while(!st.empty() && st.top().first >= v[i]) st.pop();
if(v[i]==v[i+1]) drp[i] = drp[i+1]+1;
else if(v[i] > v[i+1]) drp[i] = 0;
else
{
if(st.empty()) drp[i] = (n-i);
else drp[i] = (st.top().second - i - 1);
}
st.push(make_pair(v[i],i));
}
for(i = 1; i <= m; i++)
sum = max(sum,(stg[i] + drp[i] + 1)*v[i]);
return sum;
}
inline void Solve(int d[205][205])
{
int i,j,x;
for(i = 1; i <= n; i++) dp1[i] = dp2[i] = 0;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
s1[i][j] = (d[i][j] == 0? 1 + s1[i-1][j] : 0);
for(i = n; i >= 1; i--)
for(j = 1; j <= m; j++)
s2[i][j] = (d[i][j] == 0? 1 + s2[i+1][j] : 0);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
v[j] = s1[i][j];
x = Check();
dp1[i] = max(dp1[i-1],x);
}
for(i = n; i >= 1; i--)
{
for(j = 1; j <= m; j++)
v[j] = s2[i][j];
x = Check();
dp2[i] = max(dp2[i+1],x);
}
for(i = 1; i < n; i++)
sol = max(sol,dp1[i] + dp2[i+1]);
}
int main()
{
int i,j;
char x;
fin >> n >> m;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
{
fin >> x;
a[i][j] = x - '0';
b[j][i] = x - '0';
}
Solve(a);
swap(n,m);
Solve(b);
fout << sol;
fout.close();
return 0;
}