Pagini recente » Cod sursa (job #1273992) | Cod sursa (job #1388552) | Cod sursa (job #2444869) | Cod sursa (job #2911115) | Cod sursa (job #3181666)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 202;
int n,m,v[NMAX][NMAX],stv[NMAX],st[NMAX],dr[NMAX],h[NMAX],vf;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int solve(int l, int r){
int ans = 0;
memset(h, 0, sizeof(h));
int len = r-l+1;
for(int i = l; i <= r; i++){
vf = 0;
stv[vf] = 0;
for(int j = 1; j <= m; j++){
h[j] = (v[i][j] == 0 ? (h[j]+1) : 0);
while(vf > 0 && h[j] <= h[stv[vf]]){
vf--;
}
st[j] = stv[vf]+1;
stv[++vf] = j;
}
vf = 0;
stv[vf] = m+1;
for(int j = m; j >= 1; j--){
while(vf > 0 && h[j] <= h[stv[vf]]){
vf--;
}
dr[j] = stv[vf]-1;
if(h[j]){
ans = max(ans, (dr[j]-st[j]+1)*h[j]);
}
stv[++vf] = j;
}
}
memset(h, 0, sizeof(h));
for(int i = 1; i <= m; i++){
vf = 0;
stv[vf] = r-1;
for(int j = l; j <= r; j++){
h[j] = (v[j][i] == 0 ? (h[j]+1) : 0);
while(vf > 0 && h[j] <= h[stv[vf]]){
vf--;
}
st[j] = stv[vf]+1;
stv[++vf] = j;
}
vf = 0;
stv[vf] = r+1;
for(int j = r; j >= l; j--){
while(vf > 0 && h[j] <= h[stv[vf]]){
vf--;
}
dr[j] = stv[vf]-1;
if(h[j]){
ans = max(ans, (dr[j]-st[j]+1)*h[j]);
}
stv[++vf] = j;
}
}
return ans;
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
char ch;
fin >> ch;
v[i][j] = (ch-'0');
}
}
int ans = 0;
for(int i = 1; i <= n; i++){
ans = max(ans, solve(1, i) + solve(i+1, n));
}
fout << ans;
return 0;
}