Pagini recente » urmasii_lui_taraban | Cod sursa (job #1596940)
#include <fstream>
#include <stack>
using namespace std;
int n,m;
int a[1001][1001];
int p[1001][1001];
stack<int> S;
void Manacher(int A[],int P[])
{
int l = 0,r = -1;
for (int i = 1; i <= m; i++) {
if (i > r) P[i] = 1;
else P[i] = min(P[l+r-i],r-i+1);
int L = i - P[i] + 1;
int R = P[i] + i - 1;
while (L-1 >= 1 && R+1 <= m && A[L-1] == A[R+1]) L--,R++,P[i]++;
if (R > r)
r = R, l = L;
}
for (int i = 1; i <= m; i++)
P[i] = P[i] * 2 - 1;
}
int Solve(int j)
{
int Ret = n;
for (int i = 1; i <= n; i++) {
if (S.empty() || p[S.top()][j] <= p[i][j]) S.push(i);
else {
int u = S.top();
while (!S.empty() && p[S.top()][j] > p[i][j]) {
Ret = max(Ret,(u-S.top()+1)*p[S.top()][j]);
S.pop();
}
S.push(i);
}
}
int u = n;
while (!S.empty()) {
Ret = max(Ret,(u-S.top()+1)*p[S.top()][j]);
S.pop();
}
return Ret;
}
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++)
Manacher(a[i],p[i]);
int Ans = n;
for (int j = 1; j <= m; j++)
Ans = max (Ans, Solve(j));
fout << Ans;
}