Pagini recente » Cod sursa (job #2842207) | Cod sursa (job #2575928) | Cod sursa (job #1201449) | Cod sursa (job #855185) | Cod sursa (job #824617)
Cod sursa(job #824617)
#include <iostream>
#include <fstream>
using namespace std;
int N, M;
char A[103][103];
int H[103][103], M1[103][103], M2[103][103];
#define MAX(a, b) ((a > b) ? (a) : (b))
int main(int argc, char *argv[])
{
FILE *fi = fopen("bmatrix.in", "r");
fscanf(fi, "%d %d", &N, &M);
for (int i(1); i <= N; ++i)
fscanf(fi, "%s\n", A[i]+1);
fclose(fi);
for (int i(1); i <= N; ++i)
for (int j(1); j <= M; ++j)
if (A[i][j] == '0')
H[i][j] = H[i-1][j] + 1;
else
H[i][j] = 0;
for (int i(1); i <= N; ++i)
for (int j(1); j <= M; ++j) {
int max = 0;
int hmin = 202;
for (int k = j; k > 0; --k) {
if (hmin > H[i][k])
hmin = H[i][k];
if (max < (j-k+1) * hmin)
max = (j-k+1) * hmin;
}
M1[i][j] = max;
M1[i][M+1] = MAX(M1[i][M+1], MAX(max, M1[i-1][M+1]));
M1[N+1][j] = MAX(M1[N+1][j], MAX(max, M1[N+1][j-1]));
}
for (int i = N; i >= 1; --i)
for (int j = 1; j <= M; ++j)
if (A[i][j] == '0')
H[i][j] = H[i+1][j] + 1;
else
H[i][j] = 0;
for (int i = N; i >= 1; --i)
for (int j = M; j >= 1; --j) {
int max(0);
int hmin = 202;
for (int k = j; k <= M; ++k) {
if (hmin > H[i][k])
hmin = H[i][k];
if (max < (k-j+1) * hmin)
max = (k-j+1) * hmin;
}
M2[i][j] = max;
M2[i][0] = MAX(M2[i][0], MAX(max, M2[i+1][0]));
M2[0][j] = MAX(M2[0][j], MAX(max, M2[0][j+1]));
}
int R(0);
for (int j(1); j < M; ++j)
if (R < M1[N+1][j] + M2[0][j+1])
R = M1[N+1][j] + M2[0][j+1];
for (int i(1); i < N; ++i)
if (R < M1[i][M+1] + M2[i+1][0])
R = M1[i][M+1] + M2[i+1][0];
ofstream fout("bmatrix.out");
fout << R << endl;
fout.close();
return 0;
}