Pagini recente » Cod sursa (job #1930972) | Cod sursa (job #1290737) | Cod sursa (job #1744001) | Cod sursa (job #2298717) | Cod sursa (job #1099343)
#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];
int lf[1001], rg[1001];
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 = 2; j <= M; j += 2)
{
while (!ST.empty())
ST.pop();
for (int i = 1; i <= N; ++i)
{
while (!ST.empty() && P[i][j] <= P[ST.top()][j])
ST.pop();
if (ST.empty()) lf[i] = i;
else lf[i] = i - ST.top();
ST.push(i);
}
while (!ST.empty())
ST.pop();
for (int i = N; i >= 1; --i)
{
while (!ST.empty() && P[i][j] <= P[ST.top()][j])
ST.pop();
if (ST.empty()) rg[i] = N - i + 1;
else rg[i] = ST.top() - i;
ST.push(i);
}
for (int i = 1; i <= N; ++i)
maxarea = max(maxarea, P[i][j] * (lf[i] + rg[i] - 1));
}
fout << maxarea << '\n';
fin.close();
fout.close();
return 0;
}