Pagini recente » Cod sursa (job #299648) | Cod sursa (job #2205590) | Cod sursa (job #1595976) | Cod sursa (job #1465673) | Cod sursa (job #1401115)
#include <iostream>
#include <fstream>
#include <stack>
#define nmax 205
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n,m,dp[nmax][nmax],dp2[nmax][nmax];
struct Coord{
int h,poz;
};
stack<Coord>up,bot;
char a[nmax][nmax],t[nmax][nmax];
inline int FINDMAX(int lin){
int i,j,best,p,best2,thebest;
Coord b;
best=best2=thebest=0;
for(i=1;i<=m;i++)
if(dp[lin][i]){
j=i;
while(dp[lin][j]){ //top
if(up.empty() || dp[lin][j] >= up.top().h){
b.h = dp[lin][j];
b.poz = j;
up.push(b);
}
else{
p=up.top().poz;
while(!up.empty() && up.top().h > dp[lin][j]){
b = up.top();
up.pop();
best=max(best,b.h*(p-b.poz+1));
}
b.h = dp[lin][j]; b.poz = j;
up.push(b);
}
// bot
if(bot.empty() || dp2[lin+1][j] >= bot.top().h){
b.h = dp2[lin+1][j];
b.poz = j;
bot.push(b);
}
else{
p=bot.top().poz;
while(!bot.empty() && bot.top().h > dp[lin+1][j]){
b = bot.top();
bot.pop();
best2=max(best2,b.h*(p-b.poz+1));
}
b.h = dp2[lin+1][j]; b.poz = j;
bot.push(b);
}
j++;
}
// top
p=up.top().poz;
while(!up.empty()){
b = up.top();
up.pop();
best=max(best,b.h*(p-b.poz+1));
}
// bot
p=bot.top().poz;
while(!bot.empty()){
b = bot.top();
bot.pop();
best2=max(best2,b.h*(p-b.poz+1));
}
//g << best2<<' ';
thebest=max(thebest,best+best2);
best=best2=0;
i=j;
}
return thebest;
}
inline void ROTATE(){
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
dp[i][j]=dp2[i][j]=dp[j][i]=dp2[j][i]=0;
t[j][i]=a[i][j];
}
swap(n,m);
//g << n << ' '<< m<<'\n';
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(t[i][j]=='0')dp[i][j]=dp[i-1][j]+1;
for(i=n;i>0;i--)
for(j=1;j<=m;j++)
if(t[i][j]=='0') dp2[i][j]=dp2[i+1][j]+1;
}
inline void BMATRIX(){
int i,j,best=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]=='0')dp[i][j]=dp[i-1][j]+1;
for(i=n;i>0;i--)
for(j=1;j<=m;j++)
if(a[i][j]=='0') dp2[i][j]=dp2[i+1][j]+1;
for(i=1;i<=n;i++)
best=max(best,FINDMAX(i));
ROTATE();
for(i=1;i<=n;i++)
best=max(best,FINDMAX(i));
// for(i=1;i<=n;i++){
// for(j=1;j<=m;j++)
// g<<t[i][j]<<' ';
// g <<'\n';
// }
g << best<<'\n';
}
int main(){
int i;
f >> n >> m;
i=1;
while(f >> (a[i]+1))i++;
f.close();
BMATRIX();
g.close();
return 0;
}