Pagini recente » Cod sursa (job #2009063) | Cod sursa (job #3321047) | Cod sursa (job #334649) | Cod sursa (job #2197248) | Cod sursa (job #3350475)
#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]={-1}, 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()
{
while(!st.empty())
st.pop();
st.push(0);
}
void calc_dp(int b)
{
for(int j=1;j<=m[b];j++)
h[j]=0;
for(int i=1;i<=n[b];i++)
{
reset_st();
dp[b][i]=dp[b][i-1];
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();
dp[b][i]=max(dp[b][i], h[j]*(j-st.top()));
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]=a[0][i][j];
a[2][j][i]=a[0][i][j];
a[3][m[0]-j+1][i]=a[0][i][j];
}
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;
}