Pagini recente » Monitorul de evaluare | Cod sursa (job #2738751) | Fotbal3 | Cod sursa (job #721809) | Cod sursa (job #1507644)
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;
const int maxN = 200;
int N, M, ans;
bool mat[1 + maxN + 1][1 + maxN + 1];
int maxDr[1 + maxN + 1][1 + maxN + 1];
template<typename T>
void swap(T &a, T &b) {
if (a != b) {
a = a xor b;
b = a xor b;
a = a xor b;
}
}
void reverseMatrix() {
memset(maxDr, 0, sizeof maxDr);
for(register int i = 1; i <= maxN; ++ i)
for(register int j = i + 1; j <= maxN; ++ j)
swap(mat[i][j], mat[j][i]);
swap(N, M);
}
void computeMaxDr() {
for(register int l1 = 1; l1 <= N; ++ l1) {
bool a[1 + maxN + 1];
memset(a, true, sizeof a);
for(register int l2 = l1; l2 <= N; ++ l2){
for(register int c = 1; c <= M; ++ c)
a[c] &= mat[l2][c];
int l = 0, lmax = 0;
for(register int c = 1; c <= M; ++ c) {
if(a[c]) ++ l;
else l = 0;
lmax = max(l, lmax);
}
maxDr[l1][l2] = lmax * (l2 - l1 + 1);
}
}
}
void solve() {
for(register int L = 1; L < N; ++ L) {
int dr1 = 0, dr2 = 0;
for(register int l1 = 1; l1 <= L; ++ l1)
for(register int l2 = l1; l2 <= L; ++ l2)
dr1 = max(dr1, maxDr[l1][l2]);
for(register int l1 = L + 1; l1 <= N; ++ l1)
for(register int l2 = l1; l2 <= N; ++ l2)
dr2 = max(dr2, maxDr[l1][l2]);
if (dr1 != 0 && dr2 != 0)
ans = max(ans, dr1 + dr2);
}
}
int main(void) {
freopen("bmatrix.in", "r", stdin);
freopen("bmatrix.out", "w", stdout);
scanf("%d%d", &N, &M);
for(register int l = 1; l <= N; ++l) {
scanf("\n");
for(register int c = 1; c <= M; ++c) {
char character;
scanf("%c", &character);
mat[l][c] = 1 - (character - '0');
}
}
ans = 0;
computeMaxDr();
solve();
/*
for(register int l = 1; l <= N; ++l) {
for(register int c = 1; c <= M; ++c) {
printf("%d ", mat[l][c]);
}
printf("\n");
}
printf("\n");
for(register int l = 1; l <= N; ++l) {
for(register int c = 1; c <= N; ++c) {
printf("%d ", maxDr[l][c]);
}
printf("\n");
}
printf("\n");//*/
reverseMatrix();
computeMaxDr();
solve();
/*
for(register int l = 1; l <= N; ++l) {
for(register int c = 1; c <= M; ++c) {
printf("%d ", mat[l][c]);
}
printf("\n");
}
printf("\n");
for(register int l = 1; l <= N; ++l) {
for(register int c = 1; c <= N; ++c) {
printf("%d ", maxDr[l][c]);
}
printf("\n");
}
printf("\n");//*/
printf("%d\n", ans);
return 0;
}