Pagini recente » Cod sursa (job #477790) | Cod sursa (job #1014952) | Cod sursa (job #2379638) | Cod sursa (job #208635) | Cod sursa (job #1100899)
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int N, M;
int maxarea;
int A[1001][2002], P[1001][2002];
stack<int> ST;
void pscpld()
{
for (int i = 1; i <= N; ++i)
{
int best = 0;
for (int j = 1; j <= M; ++j)
{
if (best + P[i][best] >= j)
P[i][j] = min(best + P[i][best] - j, P[i][2 * best - j]);
while (j - P[i][j] - 1 > 0 && j + P[i][j] + 1 <= M && A[i][j - P[i][j] - 1] == A[i][j + P[i][j] + 1])
++P[i][j];
if (j + P[i][j] >= best + P[i][best])
best = j;
}
}
}
int main()
{
fin >> N >> M;
M = 2 * M + 1;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
{
if (j % 2 == 1) A[i][j] = -1;
else fin >> A[i][j];
}
pscpld();
for (int j = 8; j <= M; j += 2)
{
int left, right;
for (int i = 1; i <= N + 1; ++i)
{
while (!ST.empty() && P[i][j] <= P[ST.top()][j])
{
int vf = ST.top();
ST.pop();
if (ST.empty()) left = 1;
else left = ST.top() + 1;
right = i - 1;
maxarea = max(maxarea, P[vf][j] * (right - left + 1));
}
ST.push(i);
}
}
fout << maxarea << '\n';
fin.close();
fout.close();
return 0;
}