Pagini recente » Cod sursa (job #710511) | Cod sursa (job #1572862) | Cod sursa (job #2383683) | Cod sursa (job #3226534) | Cod sursa (job #819458)
Cod sursa(job #819458)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
#define MAXN 300
int N, M;
char A[MAXN][MAXN];
void doSums(int a[MAXN][MAXN]) {
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
if (A[i][j] == '0')
a[i][j] = a[i - 1][j] + 1;
}
void doMatrix(int best[MAXN]) {
int a[MAXN][MAXN];
int left[MAXN], right[MAXN];
memset(a, 0, sizeof(a));
doSums(a);
for (int i = 1; i <= N; ++i) {
int coada[MAXN];
coada[0] = 0;
for (int j = 1; j <= M; ++j) {
while (coada[0] && a[i][coada[coada[0]]] >= a[i][j])
--coada[0];
coada[++coada[0]] = j;
if (coada[0] == 1)
left[j] = j;
else
left[j] = j - coada[coada[0] - 1];
}
coada[0] = 0;
for (int j = M; j >= 1; --j) {
while (coada[0] && a[i][coada[coada[0]]] >= a[i][j])
--coada[0];
coada[++coada[0]] = j;
if (coada[0] == 1)
right[j] = M - j + 1;
else
right[j] = coada[coada[0] - 1] - j;
}
int aux = 0;
for (int j = 1; j <= M; ++j)
aux = max(aux, left[j] * a[i][j] + right[j] * a[i][j] - a[i][j]);
best[i] = max(best[i - 1], aux);
}
}
void reverse() {
for (int i = 1; i <= N / 2; ++i)
for (int j = 1; j <= M; ++j)
swap (A[i][j], A[N - i + 1][j]);
}
void solve (int &rez) {
int max1[MAXN], max2[MAXN];
memset (max1, 0, sizeof(max1));
memset (max2, 0, sizeof(max2));
doMatrix (max1);
reverse();
doMatrix (max2);
reverse();
for (int i = 1; i < N; ++i)
rez = max(rez, max1[i] + max2[N - i]);
}
void flip () {
char a[MAXN][MAXN];
memcpy (a, A, sizeof(A));
for (int i = 1; i <= M; ++i)
for (int j = 1; j <= N; ++j)
a[i][j] = A[j][i];
memcpy (A, a, sizeof(a));
swap (N, M);
}
void read () {
fin >> N >> M;
for (int i = 1; i <= N; ++i)
fin >> (A[i] + 1);
}
int main () {
int rez = 0;
read();
solve(rez);
flip();
solve(rez);
fout << rez << "\n";
return 0;
}