Pagini recente » Cod sursa (job #640353) | Cod sursa (job #978583) | Cod sursa (job #3343733) | Cod sursa (job #3348959) | Cod sursa (job #3350477)
#include <fstream>
#include <stack>
using namespace std;
ifstream in("bmatrix.in");
ofstream out("bmatrix.out");
const int NMAX=2e2+1;
int n[4], m[4], h[NMAX], l[NMAX], dp[4][NMAX];
bool a[4][NMAX][NMAX];
stack<int> st;
//0 - linia i in sus
//1 - linia n-i+1 in jos
//2 - coloana j la stanga
//3 - coloana m-j+1 la dreapta
void reset_st(int x)
{
while(!st.empty())
st.pop();
st.push(x);
}
void calc_dp(int b)
{
h[0]=h[m[b]+1]=-1;
for(int j=1;j<=m[b];j++)
h[j]=0;
for(int i=1;i<=n[b];i++)
{
dp[b][i]=dp[b][i-1];
reset_st(0);
for(int j=1;j<=m[b];j++)
{
h[j]=(a[b][i][j]==1)?0:h[j]+1;
while(h[j]<=h[st.top()])
st.pop();
l[j]=st.top();
st.push(j);
}
reset_st(m[b]+1);
for(int j=m[b];j>=1;j--)
{
while(h[j]<=h[st.top()])
st.pop();
dp[b][i]=max(dp[b][i], h[j]*(st.top()-l[j]-1));
st.push(j);
}
}
}
int main()
{
char ch;
in>>n[0]>>m[0];
n[1]=n[0], n[2]=n[3]=m[0];
m[1]=m[0], m[2]=m[3]=n[0];
for(int i=1;i<=n[0];i++)
for(int j=1;j<=m[0];j++)
{
in>>ch;
a[0][i][j]=(ch=='1');
a[1][n[0]-i+1][j]=(ch=='1');
a[2][j][i]=(ch=='1');
a[3][m[0]-j+1][i]=(ch=='1');
}
for(int b=0;b<4;b++)
calc_dp(b);
int ans=0;
for(int i=1;i<n[0];i++)
ans=max(ans, dp[0][i]+dp[1][n[0]-i]);
for(int j=1;j<m[0];j++)
ans=max(ans, dp[2][j]+dp[2][m[0]-j]);
out<<ans;
return 0;
}