Pagini recente » Cod sursa (job #2754015) | Cod sursa (job #314627) | Cod sursa (job #883297) | Cod sursa (job #2165786) | Cod sursa (job #1416235)
#include <fstream>
#define Max_Size 205
#define INF Max_Size * Max_Size
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
typedef struct { int val, p1, p2; } art;
int N, M, sol, V1[Max_Size][Max_Size], V2[Max_Size][Max_Size];
art Max1[Max_Size], Max2[Max_Size];
bool B[Max_Size][Max_Size];
char c;
int main()
{
fin >> N >> M;
for (int i = 1; i <= N; i++)
{
fin.get(c);
for (int j = 1; j <= M; j++)
{
fin.get(c);
B[i][j] = c - '0';
}
}
for (int j = 1; j <= M; j++)
{
for (int i = 1; i <= N; i++)
{
if (!B[i][j]) V1[i][j] = V1[i - 1][j] + 1;
else V1[i][j] = 0;
}
for (int i = N; i >= 1; i--)
{
if (!B[i][j]) V2[i][j] = V2[i + 1][j] + 1;
else V2[i][j] = 0;
}
}
for (int k = 1; k <= N + 1; k++)
{
for (int j1 = 1; j1 <= M; j1++)
{
int maxim1 = 0, minim1 = INF, maxim2 = 0, minim2 = INF;
for (int j2 = j1; j2 <= M; j2++)
{
if (V1[k - 1][j2] < minim1) minim1 = V1[k - 1][j2];
if (minim1 * (j2 - j1 + 1) > maxim1) maxim1 = minim1 * (j2 - j1 + 1);
if (V2[k][j2] < minim2) minim2 = V2[k][j2];
if (minim2 * (j2 - j1 + 1) > maxim2) maxim2 = minim2 * (j2 - j1 + 1);
if (maxim1 > Max1[k].val)
{
Max1[k].val = maxim1;
Max1[k].p1 = j1;
Max1[k].p2 = j2;
}
if (maxim2 > Max2[k].val)
{
Max2[k].val = maxim2;
Max2[k].p1 = j1;
Max2[k].p2 = j2;
}
}
}
}
for (int k1 = 1; k1 <= N; k1++)
{
for (int k2 = 1; k2 <= N; k2++)
{
if (Max1[k1].p2 < Max2[k2].p1 || Max1[k1].p1 > Max2[k2].p2)
{
sol = max (sol, Max1[k1].val + Max2[k2].val);
}
}
}
for (int k = 1; k <= N; k++) {
Max1[k].val = max (Max1[k].val, Max1[k - 1].val);
Max2[N - k + 1].val = max (Max2[N - k + 1].val, Max2[N - k + 2].val);
}
for (int k = 1; k <= N; k++) {
sol = max (sol, Max1[k].val + Max2[k].val);
}
fout << sol << '\n';
fout.close();
return 0;
}