Pagini recente » Cod sursa (job #367630) | Cod sursa (job #1382632) | Cod sursa (job #1138648) | Cod sursa (job #359892) | Cod sursa (job #1401263)
#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;
};
int big,dx,dy,px,py;
int bigg,dxx,dyy,pxx,pyy;
stack<Coord>up,bot;
char a[nmax][nmax],t[nmax][nmax];
inline int FINDMAX(int lin,int dp[nmax][nmax]){
int i,j,best,p,thebest;
Coord b;
best=thebest=0;
for(i=1;i<=m;i++)
if(dp[lin][i]){
j=i;
while(dp[lin][j]){
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);
}
j++;
}
p=up.top().poz;
while(!up.empty()){
b = up.top();
up.pop();
best=max(best,b.h*(p-b.poz+1));
}
thebest=max(thebest,best);
best=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);
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,best2,thebest;
best=best2=thebest=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=best2=0;
for(j=1;j<=i;j++)
best=max(best,FINDMAX(j,dp));
for(j=i+1;j<=n;j++)
best2=max(best2,FINDMAX(j,dp));
thebest=max(thebest,best+best2);
}
ROTATE();
for(i=1;i<=n;i++){
best=best2=0;
for(j=1;j<=i;j++)
best=max(best,FINDMAX(j,dp2));
for(j=i+1;j<=n;j++)
best2=max(best2,FINDMAX(j,dp2));
thebest=max(thebest,best+best2);
}
g << thebest<<'\n';
}
int main(){
int i;
f >> n >> m;
i=1;
while(f >> (a[i]+1))i++;
f.close();
BMATRIX();
g.close();
return 0;
}