Pagini recente » Cod sursa (job #1176354) | Cod sursa (job #2027045) | Cod sursa (job #2280224) | Cod sursa (job #326073) | Cod sursa (job #1730919)
#include <fstream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <stack>
using namespace std;
#define ll long long
#define llu long long unsigned
#define pb push_back
#define mp make_pair
//string problemName = "home";
//string inFile = problemName+".in";
//string outFile = problemName+".out";
//ifstream fin(inFile.c_str());
//ofstream fout(outFile.c_str());
const int N = 205;
char v[N][N];
int dph[N][N], dpst[N][N], dpdr[N][N];
int s[N];
int solve(int x1, int y1, int x2, int y2){
int i,j;
for(i = x1;i <= x2;i++){
for(j = y1;j <= y2;j++){
if(v[i][j] == '0'){
dph[i][j] = dph[i-1][j]+1;
}else{
dph[i][j] = 0;
}
}
}
int e;
for(i = x1;i <= x2;i++){
e = 0;
for(j = y1;j <= y2;j++){
while(e > 0 && dph[i][j] <= dph[i][s[e]]){
e--;
}
if(e == 0){
dpst[i][j] = y1-1;
}else{
dpst[i][j] = s[e];
}
s[++e] = j;
}
}
for(i = x1;i <= x2;i++){
e = 0;
for(j = y2;j >= y1;j--){
while(e > 0 && dph[i][j] <= dph[i][s[e]]){
e--;
}
if(e == 0){
dpdr[i][j] = y2+1;
}else{
dpdr[i][j] = s[e];
}
s[++e] = j;
}
}
int a,bst = 0;
for(i = x1;i <= x2;i++){
for(j = y1;j <= y2;j++){
if(v[i][j] == '0'){
a = dph[i][j]*(dpdr[i][j]-dpst[i][j]-1);
if(a > bst){
bst = a;
}
dph[i][j] = dpdr[i][j] = dpst[i][j] = 0;
}
}
}
return bst;
}
int main(){
int n,m,i,ans;
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
ans = 0;
scanf("%d %d",&n,&m);
for(i = 1;i <= n;i++){
scanf("%s",v[i]+1);
}
for(i = 2;i <= m;i++){
ans = max(ans, solve(1, 1, n, i-1) + solve(1, i, n, m));
}
for(i = 2;i <= n;i++){
ans = max(ans, solve(1, 1, i-1, m) + solve(i, 1, n, m));
}
printf("%d",ans);
return 0;
}