Pagini recente » Cod sursa (job #3313672) | Cod sursa (job #3337808) | Cod sursa (job #3278656) | Cod sursa (job #3351668) | Cod sursa (job #3315722)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Nmax = 205;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
int A[Nmax][Nmax];
char B[Nmax][Nmax];
int v_sus[Nmax][Nmax], s_sus[Nmax], d_sus[Nmax], st_sus[Nmax], dr_sus[Nmax], maxx_sus[Nmax];
int v_jos[Nmax][Nmax], s_jos[Nmax], d_jos[Nmax], st_jos[Nmax], dr_jos[Nmax], maxx_jos[Nmax];
int32_t main()
{
int n, m, rez;
fin >> n >> m;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
fin >> B[i][j];
A[i][j] = B[i][j] - '0';
}
}
for(int i = 1; i <= n; i ++) { /// sus
for(int j = 1; j <= m; j ++) {
if(A[i][j] == 0) v_sus[i][j] += v_sus[i-1][j] + 1;
else v_sus[i][j] = 0;
}
}
for(int i = n; i >= 1; i --) { /// jos
for(int j = 1; j <= m; j ++) {
if(A[i][j] == 0) v_jos[i][j] += v_jos[i+1][j] + 1;
else v_jos[i][j] = 0;
}
}
for(int i = 1; i <= n + 1; i ++) { /// mergem pe lini
int k_sus = 0, k_jos = 0;
/// sus
for(int j = 1; j <= m; j ++) { /// stanga
while(v_sus[i - 1][j] <= v_sus[i - 1][s_sus[k_sus]] && k_sus > 0) {
k_sus --;
}
st_sus[j] = s_sus[k_sus];
s_sus[++ k_sus] = j;
}
k_sus=0;
for(int j = m; j >= 1; j --) { /// dreapta
while(v_sus[i - 1][j] <= v_sus[i - 1][d_sus[k_sus]] && k_sus > 0) {
k_sus --;
}
dr_sus[j] = d_sus[k_sus];
d_sus[++ k_sus] = j;
}
for(int j = 1; j <= m; j ++) {
if(dr_sus[j] == 0) dr_sus[j] = m + 1;
}
for(int j = 1; j <= m; j ++) {
maxx_sus[i] = max(maxx_sus[i], v_sus[i - 1][j] * (dr_sus[j] - st_sus[j] - 1));
}
/// jos
for(int j = 1; j <= m; j ++) { /// stanga
while(v_jos[i][j] <= v_jos[i][s_jos[k_jos]] && k_jos > 0) {
k_jos --;
}
st_jos[j] = s_jos[k_jos];
s_jos[++ k_jos] = j;
}
k_jos=0;
for(int j = m; j >= 1; j --) { /// dreapta
while(v_jos[i][j] <= v_jos[i][d_jos[k_jos]] && k_jos > 0) {
k_jos --;
}
dr_jos[j] = d_jos[k_jos];
d_jos[++ k_jos] = j;
}
for(int j = 1; j <= m; j ++) {
if(dr_jos[j] == 0) dr_jos[j] = m + 1;
}
for(int j = 1; j <= m; j ++) {
maxx_jos[i] = max(maxx_jos[i], v_jos[i][j] * (dr_jos[j] - st_jos[j] - 1));
}
}
for(int i = 1; i <= n + 1; i ++) {
maxx_sus[i]=max(maxx_sus[i - 1], maxx_sus[i]);
rez = max(rez, maxx_sus[i] + maxx_jos[i]);
}
fout << rez;
return 0;
}