Pagini recente » Cod sursa (job #393706) | Cod sursa (job #278313) | Clasament dupa rating | Istoria paginii utilizator/salazar11 | Cod sursa (job #2006261)
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#define NMAX 205
#define INF (1<<30)
using namespace std;
ifstream si("bmatrix.in");
ofstream so("bmatrix.out");
int n,m;
bool v[NMAX][NMAX];
int h[NMAX];
pair<int,int> st[NMAX];
int sol[4][NMAX];
bool aux[NMAX][NMAX];
string s;
void r90()
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
aux[j][n+1-i]=v[i][j];
}
}
swap(n,m);
memcpy(v,aux,sizeof(v));
}
void solve(int ind)
{
memset(h,0,sizeof(h));
for(int i=1;i<=n;++i)
{
int top=0;
sol[ind][i]=sol[ind][i-1];
for(int j=1;j<=m+1;++j)
{
if(v[i][j]==0&&j<=m)
++h[j];
else
h[j]=0;
int s=0;
while(top>0&&st[top].first>=h[j])
{
s+=st[top].second;
sol[ind][i]=max(sol[ind][i],s*st[top].first);
--top;
}
st[++top]=make_pair(h[j],s+1);
}
}
}
int main()
{
si>>n>>m;
for(int i=1;i<=n;++i)
{
si>>s;
for(int j=1;j<=m;++j)
{
v[i][j]=s[j-1]-'0';
}
}
for(int i=0;i<4;++i)
{
solve(i);
r90();
}
int ans=0;
for(int i=1;i<n;++i)
{
ans=max(ans,sol[0][i]+sol[2][n-i]);
}
for(int i=1;i<m;++i)
{
ans=max(ans,sol[1][i]+sol[3][m-i]);
}
so<<ans<<'\n';
return 0;
}