Pagini recente » Cod sursa (job #3314545) | Cod sursa (job #3317899) | Cod sursa (job #2859393) | Cod sursa (job #487175) | Cod sursa (job #3316201)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 205;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
int A[Nmax][Nmax], n, m;
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];
int rez_orizontal;
int v_dreapta[Nmax][Nmax], s_dreapta[Nmax], d_dreapta[Nmax], st_dreapta[Nmax], dr_dreapta[Nmax], maxx_dreapta[Nmax];
int v_stanga[Nmax][Nmax], s_stanga[Nmax], d_stanga[Nmax], st_stanga[Nmax], dr_stanga[Nmax], maxx_stanga[Nmax];
int rez_vertical;
void bordare() {
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 <= m; i ++) { /// stanga
for(int j = 1; j <= n; j ++) {
if(A[j][i] == 0) v_stanga[j][i] += v_stanga[j-1][i] + 1;
else v_stanga[j][i] = 0;
}
}
for(int i = m; i >= 1; i --) { /// dreapta
for(int j = 1; j <= n; j ++) {
if(A[j][i] == 0) v_dreapta[j][i] +=v_dreapta[j+1][i] + 1;
else v_dreapta[j][i] = 0;
}
}
}
void orizontal() {
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 ++) { /// st
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 --) { /// dr
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 ++) { /// st
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 --) { /// dr
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_orizontal = max(rez_orizontal, maxx_sus[i] + maxx_jos[i]);
}
}
void vertical() {
for(int i = 1; i <= m + 1; i ++) { /// mergem pe coloane
int k_stanga = 0, k_dreapta = 0;
/// stanga
for(int j = 1; j <= n; j ++) { /// st
while(v_stanga[j - 1][i] <= v_stanga[j - 1][s_stanga[k_stanga]] && k_stanga > 0) {
k_stanga --;
}
st_stanga[i] = s_stanga[k_stanga];
s_stanga[++ k_stanga] = i;
}
k_stanga=0;
for(int j = n; j >= 1; j --) { /// dr
while(v_stanga[j - 1][i] <= v_stanga[j - 1][d_stanga[k_stanga]] && k_stanga > 0) {
k_stanga --;
}
dr_stanga[i] = d_stanga[k_stanga];
d_stanga[++ k_stanga] = i;
}
for(int j = 1; j <= n; j ++) {
if(dr_stanga[j] == 0) dr_stanga[j] = n + 1;
}
for(int j = 1; j <= n; j ++) {
maxx_stanga[i] = max(maxx_stanga[i], v_stanga[i - 1][j] * (dr_stanga[j] - st_stanga[j] - 1));
}
/// dreapta
for(int j = 1; j <= n; j ++) { /// st
while(v_dreapta[i][j] <= v_dreapta[i][s_dreapta[k_dreapta]] && k_dreapta > 0) {
k_dreapta --;
}
st_dreapta[j] = s_dreapta[k_dreapta];
s_dreapta[++ k_dreapta] = j;
}
k_dreapta=0;
for(int j = n; j >= 1; j --) { /// dr
while(v_dreapta[i][j] <= v_dreapta[i][d_dreapta[k_dreapta]] && k_dreapta > 0) {
k_dreapta --;
}
dr_dreapta[j] = d_dreapta[k_dreapta];
d_dreapta[++ k_dreapta] = j;
}
for(int j = 1; j <= n; j ++) {
if(dr_dreapta[j] == 0) dr_dreapta[j] = n + 1;
}
for(int j = 1; j <= n; j ++) {
maxx_dreapta[i] = max(maxx_dreapta[i], v_dreapta[i][j] * (dr_dreapta[j] - st_dreapta[j] - 1));
}
}
for(int i = 1; i <= m + 1; i ++) {
maxx_stanga[i]=max(maxx_stanga[i - 1], maxx_stanga[i]);
rez_vertical = max(rez_vertical, maxx_stanga[i] + maxx_dreapta[i]);
}
}
int32_t main()
{
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';
}
}
bordare();
orizontal();
vertical();
fout << max(rez_orizontal, rez_vertical);
return 0;
}