Pagini recente » Cod sursa (job #285950) | Cod sursa (job #902535) | Cod sursa (job #334569) | Cod sursa (job #1292159) | Cod sursa (job #750888)
Cod sursa(job #750888)
#include <fstream>
#include <algorithm>
using namespace std;
int N, M;
int A[1002][1002], B[1002][1002];
int st[1002], lf[1002], rg[1002];
int maxarea;
int main()
{
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
fin >> N >> M;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
fin >> A[i][j];
for (int i = 1; i <= N; ++i)
{
int center = 0, last = 0;
for (int j = 1; j <= M; ++j)
{
B[i][j] = 1;
if (last > j)
B[i][j] = B[i][center - (j - center)];
while (j - B[i][j] / 2 > 1 && j + B[i][j] / 2 < M && A[i][j - B[i][j] / 2 - 1] == A[i][j + B[i][j] / 2 + 1])
B[i][j] += 2;
if (j + B[i][j] / 2 > last)
{
center = j;
last = j + B[i][j] / 2;
}
}
}
for (int i = 1; i <= M; ++i)
{
st[0] = 0;
for (int j = 1; j <= N; ++j)
{
while (st[0] && B[j][i] <= B[st[st[0]]][i])
--st[0];
if (!st[0]) lf[j] = j;
else lf[j] = j - st[st[0]];
st[++st[0]] = j;
}
st[0] = 0;
for (int j = N; j >= 1; --j)
{
while (st[0] && B[j][i] <= B[st[st[0]]][i])
--st[0];
if (!st[0]) rg[j] = N - j + 1;
else rg[j] = st[st[0]] - j;
st[++st[0]] = j;
}
for (int j = 1; j <= N; ++j)
maxarea = max(maxarea, B[j][i] * (lf[j] + rg[j] - 1));
}
fout << maxarea << '\n';
fin.close();
fout.close();
}